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.

Academy

If the problem is the other way, i.e. removing some vertices and graphs from a graph and minimally change the graph layout, then what one can do is to display those vertices and edges in transparent color but don't actually remove them. – Jump

@Computist Yes, that is essentially what "DehighlightHide" does. – Debbi

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).

Debbi

In several places, vertex 999 is incorrectly described as vertex 99. I'd change it but I already made lots of edits and want to avoid making this a community wiki. – Debbi

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.

Advisee

+1 for showing how to grab the VertexCoordinates. It turns out that they can be both read and set in MMA 8.0. – Debbi

Answer 3

You might want to check if the GraphLayout option helps with your graph in problem.

I checked all the combinations of possible values of ComponentLayout and PackingLayout with an example graph (graph0 and graph1 which is graph0 with one edge removed, in the following code). Some combinations definitely look more useful for your purpose (changes the graph layout less when an edge is removed. I find

"ComponentLayout" -> "CircularEmbedding"
"ComponentLayout" -> "LayeredDrawing"
"ComponentLayout" -> "SpiralEmbedding"

preserve the layout the best.

The code to show all combinations is

In[5]:= Quit
In[12]:= $COMPONENTLAYOUTS={(*Automatic,None,*)"CircularEmbedding","HighDimensionalEmbedding","LayeredDrawing","LinearEmbedding","RadialEmbedding","RandomEmbedding","SpiralEmbedding","SpringElectricalEmbedding","SpringEmbedding"};
$PACKINGLAYOUTS={"ClosestPacking","ClosestPackingCenter","Layered","LayeredLeft","LayeredTop","NestedGrid"};
layoutopt[c_,p_]:=GraphLayout-> {"ComponentLayout"->$COMPONENTLAYOUTS[[ c]],"PackingLayout"-> $PACKINGLAYOUTS[[p]]};
In[4]:= words=DictionaryLookup["*zz"];
In[5]:= graph0=Flatten[Map[(Thread[#\[DirectedEdge]DeleteCases[Nearest[words,#,3],#]])&,words]];
i=RandomInteger[{1,Length[graph0]}];
graph0[[i]]
graph1=Drop[graph0,{i}];
Out[7]= tizz\[DirectedEdge]fizz
In[18]:= g0[i_,j_]:=Graph[graph0,VertexLabels->"Name",ImagePadding->20,ImageSize->200,layoutopt[i,j]];
g1[i_,j_]:=Graph[graph1,VertexLabels->"Name",ImagePadding->20,ImageSize->200,layoutopt[i,j]]

Column[Grid/@Table[
{
$COMPONENTLAYOUTS[[c]],
$PACKINGLAYOUTS[[p]],
g0[c,p],
g1[c,p]
},
{c,1,Length[$COMPONENTLAYOUTS]},
{p,1,Length[$PACKINGLAYOUTS]}
]]

Jump

Answer 4

This is at best a partial answer. Also, I am working with Mma 7.

If I modify a graph such that it now contains an 'orphan' vertex (no connecting edges) but I still want to show the vertex on a new graph, this may be done by converting to an adjacency matrix (as originally pointed out by Carl Woll)

For example:

gr1 = {1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 1};
gplot1 = GraphPlot[gr1, Method -> "CircularEmbedding", 
  VertexLabeling -> True]

Defining a new graph, gr2, as follows:

gr2 = {2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6}

A new plot showing vertex 1 may be generated as follows, for example:

Needs["GraphUtilities`"];

 gplot2 = 
 GraphPlot[SparseArray@Map[# -> 1 &, EdgeList[gr2]], 
  VertexLabeling -> True, 
  VertexCoordinateRules -> 
   Thread[VertexList[gr1] -> 
     First@Cases[gp1, GraphicsComplex[points_, __] :> points, 
       Infinity]]]

giving

Paphlagonia