在小修改后重新布局图形,同时保留原始布局的特征

Question

在Mathematica 8中有一种简单的方法可以执行以下操作吗？

1. 构建图形,并使用一些图形布局显示它.
2. 稍微修改图形(例如,添加或删除边或顶点).
3. 从原始布局开始重新计算布局,以便或多或少地保留对象的"形状".例如,重新运行弹簧电动布局算法,从先前布局的坐标开始.

如果图形在两个显示之间没有变化,则布局不应该改变(或者只是最小化).使用新的显示Graph或GraphPlot都是可以接受的.

编辑:本质上我需要类似图形的类似布局.我总是通过修改现有的图形来获得类似的图形,这些图形可能已经布局,但任何通用的解决方案都是可以接受的.

编辑2:这是一个这种事情有用的例子.转到http://ccl.northwestern.edu/netlogo/models/GiantComponent并单击"在浏览器中运行"(需要Java).单击设置,然后单击执行.您可以看到图表的演变.如果我们在Mathematica中这样做,那么每个连续的图形看起来都会完全不同,并且很难看出它是同一个正在发展的图形.在几个应用程序中,能够可视化图形的小变化是非常有用的.但是,如果进行了许多连续的更改,那么重新计算布局是必须的,简单地淡化或突出显示边缘是不够的.同样,这只是一个例子:我不是试图使用Mathematica来动画图形,或者想象巨型组件的出现.

Answer 1

以下是在MMA 8.0中更改图形的两种基本方法.第一个依赖于HighlightGraph,特别是依赖于GraphHighlightStyle -> "DehighlightHide".第二种方法在该图的未来变体中使用图的VertexCoordinates.

我们将与添加分开讨论删除,因为它们涉及的方法略有不同.

[PS:我对我的答案进行了多次编辑,以使其更清晰.]

首先是一些数据:

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}

这是初始图表:

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

"删除"图形边缘而不更改图形的整体外观.

让我们开始删除位于图形中心的边(4,11).remainingEdgesAndVertices包含所有顶点和初始边,但edge(4,11)除外.

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

让我们"删除"(即隐藏)边缘(4,11):

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

如果我们实际上已经删除了边缘(4,11),那么图形将从根本上改变它的外观.

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

"添加"图形边缘而不更改图形的整体外观.

添加图形边缘更具挑战性.有两种方式可以想到.这里使用的方法向后工作.您首先以隐藏形式包含新边缘,然后稍后将其揭开.具有隐藏的"待添加"边缘的初始图形将采用类似于具有"新"边缘的图形的布局.原因是:它们实际上是相同的图形:然而它们显示不同数量的边缘.

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

现在显示添加了"新边缘"的图表.

这看起来与图1非常不同.但它似乎是图4的自然延伸.

即时添加新顶点和边

还有另一种方法可以在保持整体外观的同时添加边(和顶点).它的灵感来自Sjoerd在回答中所写的内容.

让我们为未来的顶点99保留点{0,0}.我们只需将该点添加到 VertexCoordinatesfrom g2:

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

现在让我们看看它的样子.g3只是g2,带有附加顶点(999)和边缘(4,99).

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

此过程允许我们在向前移动时添加新的边和顶点.但是需要一些试验和错误来确保新顶点位于合适的位置.

仅添加另一条边(没有新顶点)要容易得多:只需添加新边并使用VertexCoordinates前一图中的边.

您应该能够使用相同的方法从图表中删除边缘(使用相同的方法VertexCoordinates).

Answer 2

如您所知,MMA中存在多种图形格式.我们有Combinatorica包格式,GraphPlot格式和M8 Graph格式.

GraphPlot
您可以GraphPlot按如下方式找到节点的坐标.

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

该图可以手动操作.您仍然可以在其中找到旧坐标和新坐标:

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

您可以使用修改后的坐标再次绘制绘图:

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

或绘制新图表

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

默认情况下看起来像这样:

使用旧坐标:

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,你可以一个GraphPlot,但你可以访问它的顶点坐标.

GraphData["AGraph"]

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

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

拥有这些旧坐标是件好事,因为如果我们使用它的邻接矩阵重新创建这个图形,它的布局会略有不同.这可以使用旧坐标恢复.

Answer 3

您可能想检查该GraphLayout选项是否有助于解决有问题的图表。

我用一个示例图（在下面的代码中删除了一条边）检查了ComponentLayout和的所有可能值的组合。有些组合对于您的目的来说肯定看起来更有用（当删除边时，图形布局的变化更少。我发现PackingLayoutgraph0graph1graph0

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

最好地保留布局。

显示所有组合的代码是

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