Dynamic Graph visualization

Question

I'm working on a C++ library that will be used to construct and study certain graphs (as in a set of connected vertices, not a function plot). These graphs will be dynamic in nature (and can potentially be very large) and I'm looking for ways to visualize them.

I looked at a few solutions such as Gephi which can visualize dynamic graphs, but then decided that this should be something that Mathematica would do well.

My C++ library keeps track of a 'lifetime' for each vertex and edge and I can output the graph data any way I need to.

Although I've visualized a lot of graphs in Mathematica with GraphPlot and GraphPlot3D I'm not sure what's the best way to visualize a dynamic graph?

I've used Dynamic and Manipulate extensively and I've been able to use Manipulate to draw a series of successive 'snapshots' of a graph at each time step. The problem with this approach is that you're redrawing the entire graph each time even though only one vertex or edge has changed. Also when you redraw the entire graph there's no guarantee that the vertices will be put in similar places, so adding one edge causes the picture to totally change. This kills the ability to animate the changing graph.

What seems to be needed is the ability to change the graph slightly and then locally recompute the graph drawing forces without redrawing the graph from scratch. Is this possible? Something like a hypothetical GraphPlotDynamic[].

Edit

Here is a contrived example showing the problem. The format for each edge is.

{source, target, begin, end}

This creates the graph connectivity.

dynamicGraph = 
   {{0, 1, 0, 20}, {1, 2, 1, Infinity}, {2, 3, 2, 21}, {3, 4, 3, 22}, 
    {4, 5, 4, Infinity}, {5, 6, 5, Infinity}, {6, 7, 6, 26}, {7, 8, 7, 25},     
    {8, 9, 8, Infinity}, {9, 10, 9, 24}, {0, 6, 10, 27}, {1, 6, 11, Infinity}, 
    {1, 5, 12, Infinity}, {2, 5, 13, Infinity}, {2, 4, 14, Infinity}, 
    {6, 8, 15, Infinity}, {5, 8, 16, Infinity}, {5, 9, 17, Infinity}, 
    {4, 9, 18, Infinity}, {4, 10, 19, 23}};

Now the graph is rendered with GraphPlot. The edges are selected based on whether t is within the edge's lifetime.

Manipulate[
   GraphPlot[#1 -> #2 & @@@ Select[dynamicGraph, #[[3]] <= t <= #[[4]] &], 
     VertexRenderingFunction -> (Text[#2, #1] &)], {t, 0, 31, 1}]

This graph has a relatively natural progression of adding nodes in a line then connecting the line by folding it back on itself twice. Then all the outside edges are deleted and you are left with hexagon with all vertices connected to one vertex at the center. But when clicking through the Manipulate the graph jumps around at each step so it's hard to keep track of what is being added and taken away.

Edit

Here is an example video of what I'm talking about. This is from Ubigraph and does more than what I'm asking for since it does fancy camera angles and rotations as the graph is being constructed. But what's important is that as the vertices and edges are being added the force directed algorithm is continuously running so the graph is constantly updated.

http://ubietylab.net/ubigraph/content/Demos/Animation.html

Answer 1

Not quite sure how this could handle with very large amounts of data, but maybe this is something of use.

The following code I think could easily be adapted to take an input stream efficiently. Essentially I predesignate each vertices position using RandomReal, but I bet there's a way to make things look less erratic despite an arbitrary amount of vertices being allowed.

Options[GraphPlotDynamic] = {VertexRenderingFunction -> (Point[#1] &)};

GraphPlotDynamic[lis:{{_, _, _, _}..}, OptionsPattern[]] := 
 Module[{posHash, chosenEdges, chosenVerts, vRender},

  vRender = OptionValue[VertexRenderingFunction];

  Set[posHash[#], RandomReal[{0, 1}, 2]] & /@ Range[0, Length[lis] - 1];
  posHash[{args__}] := posHash /@ {args};

  Manipulate[
   chosenEdges = Select[dynamicGraph, #[[3]] <= t <= #[[4]] &][[All, 1 ;; 2]];
   chosenVerts = vRender[posHash[#], #] & /@ Union[Flatten[chosenEdges]];

   Graphics[{
     Red, Line[posHash[##]] & /@ chosenEdges,
     Black, chosenVerts
   }, PlotRange -> {{0, 1}, {0, 1}}],

   {t, 0, 31, 1}]

  ]

And here's your example (t=24, t=25):

GraphPlotDynamic[dynamicGraph, VertexRenderingFunction -> (Style[Text[#2, #1], Large] &)]