Implementations of spring/electrostatic drawing for graphs with specified edge lengths

Question

Suppose I have some non-planar graph $G$ with fully specified edge lengths $(r_1,...,r_N) \in R$, but where I do not have specified coordinates for the vertices. I want to draw $G$ on a two dimensional surface by specifying the edges as springs of some length, having electrostatic repulsion between the vertices, and then doing something akin to simulated annealing.

Mathematica seems to have functionality for all of the above, but it doesn't let you specify edge lengths. Is there any software, in the public domain or not, that does all of this? I've tried Tulip and GraphViz. Tulip simply doesn't let you specify edge lengths, and Graphviz has very limited functionality in terms of specifying edge lengths and setting any sort of parameters for the simulated annealing step.

Update - I happen to know ahead of time that my particular set of edge lengths work! The graph was previously drawn on a two-dimensional plain, but I don't have access to the coordinates.

I suppose I'm really looking for a package that can simulate a two-dimensional network of balls and springs. Molecular dynamics software can do this, but the overhead there is enormous...

Answer 1

Like Mark said, it won't be always possible to do what you want. However, I would suggest trying LevelScheme to draw squiggly arrows which look like springs. Here's an example:

<< "LevelScheme`"
pts = {{{0, 0}, {1, 1}}, {{0, 0}, {1, 1}}, {{1, 1}, {2, 0}}, {{2, 
     0}, {1, -1}}, {{1, -1}, {0, 0}}, {{0, 0}, {2, 0}}};
Figure[{
  SetOptions[SchemeArrow, ArrowType -> SquiggleArrow],
  SchemeArrow @@@ pts
  },
 PlotRange -> {{-0.1, 2.1}, {-1.1, 1.1}}
 ]

You can then embellish this by changing the wavelength of the arrows individually, which could represent different tension in the springs and add little disks that represent the vertices, etc. This is a bastardization of the level scheme diagrams in nuclear physics, but I guess is close to what you want.

Answer 2

There's no reason to expect to be able to do this. You can't place 4 points all distance one apart in the plane, for example.

Answer 3

OK, the discussion surrounding my previous answer makes it clear that the OP has edge lengths that work. In this case, the problem can be specified algebraically and then solved. Here's one approach to doing that. Of course, it's always good to have a specific example stated in the question. Lacking that, we can generate the essentials of the example.

Here's a random graph with 10 vertices and 20 edges.

SeedRandom[1];
g = RandomGraph[{10, 20}];

Let's draw it and extract out the vertex location information. Thus, we will know lengths that work.

pic = GraphPlot[g];
pts = pic[[1, 1, 1]];

For any configuration with those lengths, the following expression will be zero.

length[UndirectedEdge[u_, v_]] := 
  Norm[pts[[u]] - pts[[v]]];
expr = Sum[((x[e[[1]]] - x[e[[2]]])^2 +
  (y[e[[1]]] - y[e[[2]]])^2 -
  length[e]^2)^2, {e, EdgeList[g]}];

Unfortunately, the expression is quite hard to minimize. Let's suppose that we have inexact estimates of the original vertex locations. (Perhaps this is possible, perhaps not.) We could simulate this like so. Note that we are simply randomly perturbing the original picture.

vars = Flatten[Table[{
   {x[i], pts[[i, 1]] + RandomReal[{-0.4, 0.4}]},
   {y[i], pts[[i, 2]] + RandomReal[{-0.4, 0.4}]}},
  {i, 1, 10}], 1];

Now, the following should yield vertex locations that work.

FindMinimum[expr, vars]

Answer 4

Maybe tulip does what you want?

Answer 5

You could also try to implement it yourself. It's not that hard and a lot of fun. "Simulated annealing" in this case is simply applying electrostatic physics with friction.

The key point is to use a Kd-Tree or an Octree to limit the complexity of the simulation. Otherwise O(n²) complexity will defeat you :)