3

NetworkX は主にグラフ分析用であり、PyGraphviz は主に描画用であり、それらは連携して動作するように設計されています。ただし、NetworkX のグラフ描画 (MatPlotLib 経由) が PyGraphviz のグラフ描画 (Graphviz 経由) よりも優れている点が少なくとも 1 つあります。つまり、NetworkX には有向グラフ専用のスプリング レイアウト アルゴリズム (spring_layout関数経由でアクセス可能) があり、PyGraphviz にはいくつかのスプリングがあります。neato無向グラフであるかのように有向グラフをレイアウトするレイアウト アルゴリズム (プログラムなどからアクセス可能)。グラフの方向を実際に処理する唯一の Graphviz / PyGraphviz レイアウト プログラムは ですがdot、dot強制的に方向付けされたレイアウトではなく、階層レイアウトを作成します。

有向グラフのスプリング レイアウトに関する NetworkX と PyGraphviz の違いを示す例を次に示します。

import networkx as nx
import pygraphviz as pgv
import matplotlib.pyplot as ppt

edgelist = [(1,2),(1,9),(3,2),(3,9),(4,5),(4,6),(4,9),(5,9),(7,8),(7,9)]

nxd = nx.DiGraph()
nxu = nx.Graph()
gvd = pgv.AGraph(directed=True)
gvu = pgv.AGraph()

nxd.add_edges_from(edgelist)
nxu.add_edges_from(edgelist)
gvd.add_edges_from(edgelist)
gvu.add_edges_from(edgelist)

pos1 = nx.spring_layout(nxd)
nx.draw_networkx(nxd,pos1)
ppt.savefig('1_networkx_directed.png')
ppt.clf()

pos2 = nx.spring_layout(nxu)
nx.draw_networkx(nxu,pos2)
ppt.savefig('2_networkx_undirected.png')
ppt.clf()

gvd.layout(prog='neato')
gvd.draw('3_pygraphviz_directed.png')

gvu.layout(prog='neato')
gvu.draw('4_pygraphviz_undirected.png')

1_networkx_directed.png:( http://farm9.staticflickr.com/8516/8521343506_0c5d62e013.jpg )

2_networkx_undirected.png:( http://farm9.staticflickr.com/8246/8521343490_06ba1ec8e7.jpg )

3_pygraphviz_directed.png:( http://farm9.staticflickr.com/8365/8520231171_ef7784d983.jpg )

4_pygraphviz_undirected.png:( http://farm9.staticflickr.com/8093/8520231231_80c7eab443.jpg )

3 番目と 4 番目に描かれた図は、矢印が異なるだけで基本的に同じです (図全体が回転していますが、それ以外は違いはありません)。ただし、1 番目と 2 番目の図のレイアウトは異なります。これは、NetworkX のレイアウト アルゴリズムがランダム性の要素を導入しているためだけではありません。

上記のコードを繰り返し実行すると、これが偶然の出来事ではないことがわかります。NetworkX のspring_layout関数は明らかに、あるノードから別のノードへのアークがある場合、2 番目のノードは最初のノードよりもグラフの中心に近くなければならないという前提で書かれています (つまり、 で説明されているグラフedgelistが方向付けられている場合、ノード 2 はノード 1 と 3 よりもノード 9 に近く、ノード 6 はノード 4 よりもノード 9 に近く、ノード 8 はノード 7 よりもノード 9 に近くなければなりません。これは、ノードからわかるように、常に完全に機能するとは限りません。上の最初の図では 4 と 5 ですが、2 と 9 の両方を中心に近づけることに比べれば小さな問題であり、私の観点からの「エラー」は非常にわずかです)。言い換えれば、NetworkXspring_layoutは階層的であり、強制的に管理されています。

有向グラフでコア/周辺構造がより明確になるため、これは優れた機能です (作業している仮定によっては、入ってくるアークのないノードは、数が多くても周辺の一部と見なすことができます)。出アークの）。@skyebend は、ほとんどのレイアウト アルゴリズムが有向グラフを無向であるかのように扱う理由を以下で説明していますが、上記のグラフは、(a) NetworkX が有向グラフを異なる方法で処理し、(b) 分析に役立つ原理に基づいた方法で処理していることを示しています。

これは PyGraphviz / Graphviz を使用して複製できますか?

残念ながら、NetworkX の(実際には) 関数のドキュメントとコメント付きのソース コードでは、なぜ NetworkX がその結果を生成するのかについての手がかりが得られません。spring_layoutfruchterman_reingold_layout

これは PyGraphviz を使用して NetworkXspring_layout関数を使用してネットワークを描画した結果です (この質問に対する私自身の回答を以下で参照してください)。5_pygraphviz_plus_networkx.png: ( http://farm9.staticflickr.com/8378/8520231183_e7dfe21ab4.jpg )

4

2 に答える 2

5

さて、私はそれを理解したと思うので、私は自分の質問に答えるつもりです。PyGraphviz自体ではできないと思います。ただし、PyGraphvizにNetworkXからノード位置を取得するように指示できますが、（を使用して!）それらをペグして、neatoプログラムがで計算されたノード位置にラバースタンプを付ける以外のことを実際に実行できないようにしますspring_layout。上記に次のコード行を追加します。

for k,v in pos1.iteritems():
    gvd.get_node(k).attr['pos']='{},{}!'.format(v[0]*10,v[1]*10)

gvd.layout(prog='neato')
gvd.draw('5_pygraphviz_plus_networkx.png')

結果は完全ではありません-ノードが互いに重なり合うのを防ぐために、座標に10を掛ける必要がありました。これは（明らかに）クラッジです-しかし、それは改善です。 0度は外側にあり（NetworkXでレイアウトする利点）、ノード自体に飲み込まれない適切な矢印があります（PyGraphvizで描画する利点）。

ただし、これは厳密には私が求めていたものではないことを認識しています（つまり、PyGraphviz / Graphviz自体を使用したソリューション）。

誰かがより良い解決策を提供できれば、私は幸せになります！

編集：上記のように問題に対するより良い解決策を提供した人は誰もいないので、私はそれが実際に機能していることを示すために私自身の答えを受け入れるつもりです。ただし、skyebendの回答にも投票します。これは、問題を解決するわけではありませんが、根本的な問題を理解するのに非常に役立つためです。

于 2013-02-06T17:15:14.973 に答える
4

Graphviz には、スプリング レイアウトに類似した強制的にノードを配置するためのfdpおよびsfdpレイアウト モードもあります。私は NetworkX に詳しくありませんが、うまくいくようgvu.layout(prog='fdp')ですか? NetworkX が Graphviz に追加の引数を渡すことを許可している場合、微調整できる構成可能なレイアウト パラメーターが多数あり、希望に近いレイアウトが得られる可能性があります。Graphviz ドキュメントを参照してください: http://www.graphviz.org/content/attrs

ただし、fdp レイアウトはネットワークを無向グラフとして扱います。私が知っているほとんどの「春」のレイアウトは、距離が対称であるユークリッド空間 (画面) にネットワークを変換する必要があるため、ネットワークを無向として扱います。1 つの例外は、一種のニート/ドット ハイブリッドとして、アークを整列させようとする「マグネティック」スプリング レイアウトです。

アルゴリズムの実装は、有向ネットワークのネットワーク距離を、レイアウトによって最適化される無向の重み/距離に変換する方法も異なる場合があります。有向アークの解釈方法をより詳細に制御したい場合は、この手順を自分で明示的に実行することをお勧めします。

于 2013-02-22T16:38:10.227 に答える