Re-layout schedule after a small modification while maintaining the features of the original layout

Question

Is there an easy way to do the following in Mathematica 8?

• Build a graph and display it using a graphic layout.
• Change the graph a bit (for example, add or remove an edge or vertex).
• Recalculate the layout, starting from the original layout, so that the "shape" of the object is more or less saved. For instance. restart the spring-electric layout algorithm starting from the coordinates of the previous layout.

If the graph has not changed between the two displays, the layout should not change (or only minimally). Using a new Graph or GraphPlot acceptable.

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

EDIT 2: Here is an example of how this view is useful. Go to http://ccl.northwestern.edu/netlogo/models/GiantComponent and click Run in Browser (Java required). Click Settings, then click Go. You can see how the chart is developing. If we do this in Mathematica, then each of the successive graphs will look completely different, and it will be difficult to understand that this is the same graph that is developing. In several applications, it is very useful to visualize small changes in the chart as such. But if a lot of successive changes are made, then recalculating the layout is necessary, just attenuation or highlighting is not enough. Again, this is just an example: I'm not trying to use Mathematica to animate a graph or to visualize the appearance of a giant component.

Answer 1

Here are two basic approaches to changing graphs in MMA 8.0. The first depends on HighlightGraph and, in particular, on GraphHighlightStyle -> "DehighlightHide" . The second approach uses VertexCoordinates graphics in future versions of this graphics.

We will discuss removal separately from additions because they contain slightly different methods.

[PS: I made a few changes to my answer 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 schedule:

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

"Deletion" of the graph graph without changing the overall appearance of the graph.

Let's start removing the edge (4.11) located in the center of the graph. remainingEdgesAndVertices contains all the vertices and the initial edges, except for the edge (4.11).

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

Let "remove" (i.e. hide) the edge (4, 11):

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

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

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

"Adding" a graph graph without changing the general appearance of the graph.

Adding the edges of the graph is a bit more complicated. Two ways come to mind. The method used here works in the opposite direction. First, you include the new edge in a hidden shape, and then open it later. The initial graph with the hidden, “added” edges will be in the layout, similar to the graph with the “new” edge. The reason is that they are actually 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 added “new edge”.

This is very different from Figure 1. But this is apparently a natural continuation of Figure 4.

Adding new vertices and edges on the fly

There is another way to add edges (and vertices) while maintaining the overall appearance. This was inspired by what Sjord wrote in his answer.

Let the point {0,0} be reserved for future vertex 99. We just add this point to VertexCoordinates from g2:

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

Now let's see how it looks. g3 is just g2 with an extra vertex (999) and an 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 to verify that the new vertices are in a suitable position, some trial and error will be required.

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

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

Answer 2

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

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

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

This graph can be manipulated manually. You can find both old and 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 graph again using the changed coordinates:

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

or draw a new chart

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

which 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] 

---

Schedule

I do not think that you can manipulate Graph as you can 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’s good to have these old coordinates, because if we recreate this graph using its adjacency matrix, its layout is a little different. This can be restored using the old coordinates.

Answer 3

You might want to check if GraphLayout helps to use your chart in the problem.

I checked all combinations of the 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 layout of the chart less when the edge is removed. I find

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

save the layout better.

Code to display all combinations

 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]} ]] 

Answer 4

This is at best a partial answer. In addition, I work with Mma 7.

If I change the graph so that it now contains the top of the 'orphan' (no connecting edges), but I still want to show the vertex on the new graph, this can be done by converting to an adjacency matrix (as Karl Wall originally pointed out)

For instance:

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

The definition of the new graph gr2 is as follows:

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

A new graph showing top 1 can 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]]] 

gives