Re-layout graph after small modification while preserving features of original layout

Question

Is there a simple way to do the following in Mathematica 8?

1. Construct a graph, and display it using some graph layout.
2. Modify the graph slightly (e.g. add or remove an edge or a vertex).
3. Re-compute the layout starting from the original layout, in such a way that the the "shape" of the object is more or less preserved. E.g. re-run a spring-electric layout algorithm starting with the coordinates of the previous layout.

If the graph hasn't changed between two displays, the layout shouldn't change either (or only minimally). Using the display of the new Graph or GraphPlot are both acceptable.

EDIT: In essence I need similar layouts for similar graphs. I always obtain similar graphs by modifying an existing one, which may have already been laid out, but any generic solution is acceptable.

EDIT 2: Here's an example of where this kind of thing is useful. Go to http://ccl.northwestern.edu/netlogo/models/GiantComponent and click "Run in browser" (requires Java). Click Setup then click Go. You can see the graph evolve. If we do this in Mathematica, then each of the successive graphs will look completely different, and it will be difficult to see that it is the same graph that is evolving. In several applications it's quite useful to be able to visualize small changes to the graph as such. But if many successive changes are done, then re-computing the layout is a must, simply fading or highlighting edges is not sufficient. Again, this is just an example: I'm not trying to use Mathematica to animate a graph, or to visualize the emergence of the giant component.

Answer 1

Here are two basic approaches for altering graphs in MMA 8.0. The first relies on HighlightGraph and in particular on GraphHighlightStyle -> "DehighlightHide". The second approach uses the VertexCoordinates of a graph in future variants of that graph.

We'll discuss deletion separately from addition because they involve slightly different methods.

[P.S. : I made several edits to my answer in to make it clearer.]

First some data:

edges={1\[UndirectedEdge]8,1\[UndirectedEdge]11,1\[UndirectedEdge]18,1\[UndirectedEdge]19,1\[UndirectedEdge]21,1\[UndirectedEdge]25,1\[UndirectedEdge]26,1\[UndirectedEdge]34,1\[UndirectedEdge]37,1\[UndirectedEdge]38,4\[UndirectedEdge]11,4\[UndirectedEdge]12,4\[UndirectedEdge]26,4\[UndirectedEdge]27,4\[UndirectedEdge]47,4\[UndirectedEdge]56,4\[UndirectedEdge]57,4\[UndirectedEdge]96,4\[UndirectedEdge]117,5\[UndirectedEdge]11,5\[UndirectedEdge]18,7\[UndirectedEdge]21,7\[UndirectedEdge]25,7\[UndirectedEdge]34,7\[UndirectedEdge]55,7\[UndirectedEdge]76,8\[UndirectedEdge]11,26\[UndirectedEdge]29,26\[UndirectedEdge]49,26\[UndirectedEdge]52,26\[UndirectedEdge]111,27\[UndirectedEdge]28,27\[UndirectedEdge]51,42\[UndirectedEdge]47,49\[UndirectedEdge]97,51\[UndirectedEdge]96}

Here is the initial graph:

g = Graph[edges, VertexLabels -> "Name", ImagePadding -> 10, 
ImageSize -> 500]

"Deleting" a graph edge without changing the overall appearance of the graph.

Let's begin to remove the edge (4,11) located at the center of the graph. remainingEdgesAndVertices contains all vertices and the initial edges with the exception of edge (4,11).

remainingEdgesAndVertices = 
 Join[VertexList[g],  Complement[EdgeList[g], {4 \[UndirectedEdge] 11}]]

Let's "delete" (i.e. hide) the edge (4,11):

 HighlightGraph[g, remainingEdgesAndVertices, VertexLabels -> "Name", 
   ImagePadding -> 10, GraphHighlightStyle -> "DehighlightHide", 
   ImageSize -> 500]

If we had actually removed edge (4, 11) the graph would have radically changed its appearance.

 Graph[Complement[edges, {4 \[UndirectedEdge] 11}], 
   VertexLabels -> "Name", ImagePadding -> 10, ImageSize -> 500]

"Adding" a graph edge without changing the overall appearance of the graph.

Adding a graph edge is slightly more challenging. There are two ways that come to mind. The method used here works backwards. You include the new edge first in hidden form and then uncover it later. The initial graph with the hidden, "to-be-added" edge will be in a layout similar to that of the graph with the "new" edge. The reason is this: they are in fact the same graph: however they show different numbers of edges.

g2 = Graph[Append[edges, 42 \[UndirectedEdge] 37], 
 VertexLabels -> "Name", ImagePadding -> 10, ImageSize -> 500]

HighlightGraph[g2, 
   Join[Complement[EdgeList[g2], {42 \[UndirectedEdge] 37}], 
   VertexList[g2]], VertexLabels -> "Name", ImagePadding -> 10, 
   GraphHighlightStyle -> "DehighlightHide"]

Now show the graph with the "new edge" added.

This looks very different from Figure 1. But it seems to be a natural extension of Fig. 4.

Adding new vertices and edges on-the-fly

There is another way to add edges (and vertices) while maintaining the overall appearance. It was inspired by something Sjoerd wrote in his response.

Let's reserve the point {0,0} for a future vertex 99. We simply add that point to the VertexCoordinates from g2:

vc = VertexCoordinates -> 
  Append[AbsoluteOptions[g2, VertexCoordinates][[2]], {0, 0}]

Now let's see what it looks like. g3 is just g2 with the additional vertex (999) and edge (4,99).

g3 = Graph[Append[EdgeList [g2], 4 \[UndirectedEdge] 999], vc, 
  VertexLabels -> "Name", ImagePadding -> 10, 
  GraphHighlightStyle -> "DehighlightHide", ImageSize -> 500]

This procedure allows us to add new edges and vertices as we move forward. But some trial and error will be needed to ensure that the new vertices are located in a suitable position.

Adding only another edge (without a new vertex) is much easier: just add the new edge and use the VertexCoordinates from the prior graph.

You should be able to delete edges from a graph using the same approach (using same VertexCoordinates).

Answer 2

As you know there are several graph formats floating around in MMA. We have the Combinatorica package format, the GraphPlot format and the M8 Graph format.

GraphPlot
You can find the coordinates of GraphPlot nodes as follows.

GraphPlot[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4}, DirectedEdges -> True,
           VertexLabeling -> True]

This plot can be manually manipulated. You can still find both the old and the new coordinates in it:

VertexCoordinateRules -> {{0.000196475, 0.}, {0.,0.847539}, 
                          {0.916405, 0.423865}, {2.03143, 0.42382}}

VertexCoordinateRules -> {{0.000196475, 0.}, {0., 0.847539}, 
                          {1.07187,0.708887}, {1.9537, 0.00924285}}

You can draw the plot again using the modified coordinates:

GraphPlot[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4}, DirectedEdges -> True,
          VertexLabeling -> True, newRules]

or draw a new graph

GraphPlot[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 1 -> 5, 5 -> 4}, 
          DirectedEdges -> True, VertexLabeling -> True]

that by default looks like this:

using the old coordinates:

updatedRules = VertexCoordinateRules -> 
                 Append[VertexCoordinateRules /. newRules, {1, 0}];
GraphPlot[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 1 -> 5, 5 -> 4}, 
           DirectedEdges -> True, VertexLabeling -> True, updatedRules]

---

Graph

I don't think you can manipulate a Graph as you can a GraphPlot, but you can access its vertex coordinates.

GraphData["AGraph"]

oldCoords = AbsoluteOptions[GraphData["AGraph"], VertexCoordinates]

(* ==>  VertexCoordinates -> {{1., 2.}, {2., 3.}, {2., 1.}, {1.,1.}, 
                       {1., 3.}, {2., 2.}} *)

It is good to have these old coordinates because if we re-create this graph using its adjacency matrix its layout is slightly different. This can be restored using the old coordinates.