wolfram-mathematica - 元のレイアウトの機能を維持しながら、小さな変更を加えた後の再レイアウト グラフ

Question

Mathematica 8で次のことを行う簡単な方法はありますか?

1. グラフを作成し、グラフ レイアウトを使用して表示します。
2. グラフを少し変更します (たとえば、エッジまたは頂点を追加または削除します)。
3. オブジェクトの「形状」が多かれ少なかれ保持されるように、元のレイアウトから開始してレイアウトを再計算します。たとえば、以前のレイアウトの座標から開始するスプリングエレクトリック レイアウト アルゴリズムを再実行します。

2 つのディスプレイ間でグラフが変更されていない場合、レイアウトも (または最小限に) 変更されるべきではありません。新品のディスプレイを使用しても、GraphどちらでもGraphPlotかまいません。

編集:本質的に、同様のグラフには同様のレイアウトが必要です。すでにレイアウトされている可能性のある既存のグラフを変更することで、常に同様のグラフを取得しますが、一般的なソリューションはすべて受け入れられます。

EDIT 2:この種のものが役立つ例を次に示します。http://ccl.northwestern.edu/netlogo/models/GiantComponentに移動し、[ブラウザーで実行] をクリックします (Java が必要)。[セットアップ] をクリックし、[実行] をクリックします。グラフが進化しているのがわかります。Mathematica でこれを行うと、連続するグラフのそれぞれが完全に異なって見え、進化しているのが同じグラフであることがわかりにくくなります。いくつかのアプリケーションでは、グラフの小さな変化を視覚化できると非常に便利です。しかし、多くの連続した変更が行われた場合、レイアウトの再計算は必須であり、単純にエッジをフェードまたはハイライトするだけでは十分ではありません。繰り返しますが、これは単なる例です。Mathematica を使用してグラフをアニメーション化したり、巨大なコンポーネントの出現を視覚化したりするつもりはありません。

Answer 1

MMA 8.0 でグラフを変更するための 2 つの基本的な方法を次に示します。HighlightGraph1 つ目は、特に に依存していGraphHighlightStyle -> "DehighlightHide"ます。2 番目のアプローチは、グラフの将来のバリアントでグラフの 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エッジ (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]

グラフの全体的な外観を変更せずにグラフ エッジを「追加」します。

グラフ エッジを追加するのは少し難しくなります。思いつく方法は2つあります。ここで使用される方法は、逆方向に機能します。最初に新しいエッジを非表示に含めてから、後で明らかにします。非表示の「追加される」エッジを持つ最初のグラフは、「新しい」エッジを持つグラフと同様のレイアウトになります。その理由は次のとおりです。これらは実際には同じグラフですが、異なる数のエッジを示しています。

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形式、M8Graph形式があります。

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

これはせいぜい部分的な答えです。また、Mma 7 を使用しています。

「孤立した」頂点 (エッジを接続していない) が含まれるようにグラフを変更しても、新しいグラフに頂点を表示したい場合は、adjacency matrix(Carl Woll によって最初に指摘されたように)に変換することで実行できます。

例えば：

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

新しいグラフ gr2 を次のように定義します。

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

頂点 1 を示す新しいプロットは、たとえば次のように生成できます。

Needs["GraphUtilities`"];

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

与える

Answer 4

GraphLayoutオプションが問題のグラフに役立つかどうかを確認することをお勧めします。

ComponentLayoutとの可能な値のすべての組み合わせをPackingLayoutサンプル グラフ (graph0および次のコードでgraph1はgraph01 つのエッジが削除されています) で確認しました。いくつかの組み合わせは、あなたの目的にとって間違いなくより便利に見えます（エッジが削除されたときのグラフレイアウトの変更は少なくなります。私は見つけました

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