3

多くのサブグラフを持つグラフがあります。2 つのノードを両方向、つまり A-->B と B-->A で接続するいくつかのエッジがあります。双方向性は重要です。これは、A が B に移動するか、B が A に移動するかについての知識が不足していることを表し、どちらが正しいかを判断する簡単な方法がないためです。

サブグラフの数を知りたいのですが、各サブグラフのエッジを Pandas DataFrame に出力します。ただし、NetworkX は、提供された connected_components_subgraph(G) 関数で無向グラフのみを取り込みます。グラフを無向グラフに変換すると、connected_components_subgraph() を使用して各エッジのノードを取得できますが、エッジの方向性が失われます。

私が達成しようとしていることを行う簡単な方法はありますか?

4

2 に答える 2

5

弱連結成分を探しているのではないでしょうか?

そのアルゴリズムはエッジを無向であるかのように扱い、そのグラフの連結成分を返します。

In [1]: import networkx as nx

In [2]: G = nx.DiGraph([(1,2),(2,1),(3,4)])

In [3]: for w in nx.weakly_connected_component_subgraphs(G):
   ...:     print(w.edges())
   ...:     
[(1, 2), (2, 1)]
[(3, 4)]
于 2013-09-07T13:57:01.490 に答える
1

強い連結成分であるグラフのSCCを探しています。それらは、 DFS (深さ優先検索)のバリアントで見つけることができます。

ウィキの記事を参照する必要があります。

于 2013-09-05T18:55:33.813 に答える