久々にNetworkXを使ったのですが、その時使った関数のメモです。
とあるノードの集合に対して、ある条件を満たすペアに対してエッジを張って行き、その結果出来上がった非連結なグラフから連結成分たちを取り出すという操作をやりました。
使った関数をこのブログでまだ紹介していなかったのでその周辺の操作も含めて紹介します。
とりあえず、サンプルのグラフを準備しておきましょう。連結成分が3組と、孤立ノードが2個ある次のようなグラフを作りました。
import networkx as nx
G = nx.Graph()
G.add_edges_from([
(1, 2), (2, 3), (3, 1), # コンポーネント1
(4, 5), (5, 6), # コンポーネント2
(7, 8), # コンポーネント3
])
G.add_nodes_from([9, 10]) # 孤立ノードを2個追加見ての通り、(孤立してるのも含めて)連結成分が5組ありますね。
ここから連結している成分を取り出すには、nx.connected_components() というメソッドを使います。
参考: connected_components — NetworkX 3.4.2 documentation
結果がイテレーターで帰ってくるのですが今回の例は小さいのでlistにしておきましょう。
connected_components = list(nx.connected_components(G))
print(connected_components)
"""
[{1, 2, 3}, {4, 5, 6}, {8, 7}, {9}, {10}]
"""
はい、5組がそれぞれ出てきました。
孤立成分を除きたい場合は、この中からノードが2個以上あるものに絞り込むと良いでしょう。print([c for c in connected_components if len(c) > 1])
# [{1, 2, 3}, {4, 5, 6}, {8, 7}]逆に、ノードが1個のものに絞ると孤立成分が抽出できます。しかし、孤立成分を探す場合は、nx.isolates() という専用メソッドもあります。
参考: isolates — NetworkX 3.4.2 documentation
print(list(nx.isolates(G)))
# [9, 10]また、連結成分の数や孤立成分の数を返す関数として、number_connected_components, number_of_isolates がそれぞれ用意されています。
print(nx.number_connected_components(G))
# 5
print(nx.number_of_isolates(G))
# 2最後に、このノードが含まれてる連結成分が欲しいんだ、というケースもあると思います。その場合は、node_connected_component()を使います。
参考: node_connected_component — NetworkX 3.4.2 documentation
print(nx.node_connected_component(G, 4))
# {4, 5, 6}帰ってきているのはそのノードを含む連結成分のノードの一覧(set)であって、サブグラフオブジェクトではないのでその点は注意してください。これは先ほどの連結成分の一覧を返してきてたメソッドと同様です。