I have a network of nodes connected by edges. And I have the starting and ending lengths of all the edges. If I wanted to transform this network from its starting state into its ending state, how can I solve this problem numerically? I have never used a numerical library before, so I don't know where to start.

Define the properties of this network (graph) a bit better... What does it mean to transform the network? Are there restrictions on how to do this transformation? Is the solution you're looking for the final arrangement, or is it the series of steps that were taken to get from the initial state to the final state? Do edges have lengths (weights) of their own, or are the lengths derived from something else (eg. the positions of the nodes)? Can you create, destroy or change edges at will, or is this part of the restrictions? Are you working in 2D, 3D or something else? Do you really want a numerical result, which implies an approximation, or is an exact algorithm what you'd really prefer?

Transform as in move the nodes from their starting position to their ending position.
All nodes have equal weights. Can't destroy edges. I would say it is 2D.
No other constraints apply, other than the network shouldn't transform itself into a tangled mess. :)

It may not be an exact perfect solution, as some edge lengths might prevent other
edge lengths from reaching their ending length. It just has to try its best.

If you know that the end configuration is a valid one, i.e., not a tangled mess you could try simply to transform every link length somewhat towards the final length every simulation frame.

Somewhat could be fD * ( fFinalLength - fStartLength ), where fD is a small float.

Solve node positions every frame using Gauss Seidel (which lonesock suggested to Mystery here), Verlet, Euler (model links as springs), or conjugate gradient (model links as springs).

Of these CG will give you the most stable final state if your final state link lengths are less than optimal. Others may fluctuate. CG is a bit of a pain to implement if you're not solid on this kind of stuff so try the other methods first. Start from simple and switch methods to more difficult ones only when you're sure the simple is not the method for your needs.

JD

Can it be done without using springs? I prefer not to use them.

If you want a "numerical" solution, you'll probably need to iterate your solutions according to some relationship between the current edge lengths and the desired edge lengths. An obvious way to do this is with a spring-like difference from the desired length... you could use some other relationship though.

What bothers you about springs? The fact that they're springs in theory, the form of the relationship ("force" proportional to displacement from desired length), or something else? You could easily use a nonlinear spring model (force proportional to displacement squared or somesuch).

When you first start, it might also help to use something other than springs for a while, especially if the final network is significantly different from the starting network... Maybe some sort of node-position swapping... Do you start and final networks always have the same edges (sane number, between the same vertices), but only varies in edge length?

Only node positions change, connection between edges remain the same. Is there anyway I can express this
problem as Ax=b? I have no idea how to express this problem as a solvable equation.

Maybe this is a terminology problem. I assumed you meant "numerically" as the alternative to analytically or closed form solutions, as one could use to solve an initial value problem, or approximate the value of an difficult or impossible integral.

In effect, that's what the springs suggestion would be doing... it's just a rather more complicated problem...

Each vertex has an x and y position, and you want to minimize the difference between the actual and a specified length of the edges between the vertices.

The lengths L(n) = sqrt( (x2(n) - x1(n))^2 + (y2(n) - y1(n))^2 )

where L(n) is the length of edge n, and x2(n) and x1(n) are the x coordinates of the two vertices at the ends of edge n, and y2(n) and y1(n) are the y coordinates of those vertices.

You also have D(n), which is the desired length of edge n.

What you want is a relationship between D(n) and L(n). Something like this...

Sum( ( D(n) - L(n) )^2 ) = 0

if you expand this, it ends up looking like a very big complicated equation with 3*n variables...

This isn't simple to solve, like A*x = B, so you need some iterative way to solve, like treating the difference between the desired and actual edge distances like a spring, and iterating through multiple estimates and adjusting the current arrangements so that the edge lengths get closer to the goal lengths...

Quote:Original post by raydog
Is there anyway I can express this problem as Ax=b?

Yes, you model the connections of your network as you want (springs, beams, whatever) from which you get the stiffness matrix (A in your equation). Then, in your equation, x is the displacement vector, and b is the force vector. Usually the system is solved with iterative methods I mentioned above.

For a 2D beam element I gave the stiffness matrix in this thread. However, a better explanation with images can be found here for truss elements, and here for beam elements. Struss is a central force element, i.e., a spring whereas a beam element implements also bending stiffness. If you want to make the elements such that they're completely solid (no springs, no beams, solid) modify the equation accordingly (look at lonesock's responses here).

Any case, you'll need an iterative method to solve the state you're searching.

Quote:Original post by Tron3k
How about using springs behind the scenes to calculate the final position of each node, and then simply slide the nodes using linear interpolation towards their final destinations? Should work, and there won't be any of the unappealing bounciness that is associated with springs.

Good point (this is where the audience should go "duh" on my earlier post). Find the final state with the method and element model of your choice, then interpolate the transition frames like Tron3k suggests. Note, that if you know the geometry (node positions) of the initial and final network already you can just interpolate the middle frames without heavy calculations. For more complex transition (not linear) you could solve for selected middle frames and do a piecewise linear interpolation between the initial and final frame.

JD

P.S. Sorry for the rushed response. I'm in a bit of a hurry. Have to clean my desk ASAP, switching jobs, you see.

[Edited by - JesusDesoles on August 31, 2004 1:56:19 AM]