グラフ内のすべての接続ノードをカウントする

Question

私は、（順序付けられていない）数のペアの> 10kリストを持っています。私はそれらを直接または間接的に接続されたペアのセットに分類したいと思います。私はこれが無向グラフに相当すると思う。私はPythonを使用していて、この構造を表現するためにthisのようなものを試しました。 iに接続されているすべての数字を知るために

は、 私はi除く、リスト内のすべてのjためjからiからのパスがあるかどうかを調べることができます。しかし、この実装では、処理時間は、私が扱っているリストのサイズには長すぎます。これを行うより効率的な方法はありますか？ （または、すでに確立されているPythonライブラリがありますか？）

Answer 1

グラフの接続コンポーネントを計算したいかのように思えます。 networkxパッケージとそのtools for computing componentsを調べることをお勧めします。例えば

、我々のデータは数値のペアのリスト、グラフ内のエッジを表す各ペアであると仮定する。これらのエッジで表されるグラフにおいて

pairs = [ 
    (1, 2), 
    (2, 4), 
    (3, 5), 
    (2, 5), 
    (7, 9), 
    (9, 10), 
    (8, 7) 
] 

、の任意の対の間の経路が存在しますセット{1, 2, 3, 4, 5}のノードと、任意のノードのペアの間のパスも{6, 7, 8, 9, 10}にあります。しかし、例えば、5から7への経路はありません。つまり、グラフには2つの接続されたコンポーネントがあります。これらのコンポーネントを発見するために

、我々は最初のnetworkxをインポートし、グラフを作成します。コンポーネントを計算

>>> import networkx as nx 
>>> graph = nx.from_edgelist(pairs) 

は発電機であり、従ってここでは、我々は変換

>>> list(nx.connected_components(graph)) 
>>> [{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}] 

nx.connected_components

のと同じくらい簡単です接続されたすべてのコンポーネントを表示するために結果をリストに表示します。我々はまた、すぐに接続されているコンポーネントの数を数えることができる

>>> nx.node_connected_component(graph, 3) 
{1, 2, 3, 4, 5} 

：

我々はまた、指定されたノードを含む連結成分を見つけることができます

>>> nx.number_connected_components(graph) 
2