【NetworkX】ネットワークの中の最大の連結成分を取り出す【Python】
networkxを使って遊んでみます。
下の図のようなネットワーク(グラフ)が与えられたとき、この中の最大の連結成分を取り出します。
見ての通り、{4, 5, 6, 7, 8}が最大の連結成分になります。
まずは、ネットワークを描画してみます。
import networkx as nx edge_list = [ (1, 2), (2, 3), (3, 1), (4, 5), (5, 6), (6, 7), (7, 8), (8, 4), (9, 10) ] # グラフ作成 G = nx.Graph() G.add_edges_from(edge_list) # 描画 pos = nx.spring_layout(G, k=0.7) nx.draw(G, pos, with_labels=True, font_size=18, node_size=800, node_color="orange", font_color="black")
nx.connected_componentsを使って、最大の連結成分を求めます。
largest_cc = max(nx.connected_components(G), key=len) largest_cc >>>{4, 5, 6, 7, 8}
この通り、{4, 5, 6, 7, 8}が出てきました。
また、各連結成分をグラフとして取り出したい場合は以下のように書きます。
試しに0番目の部分グラフを描画してみます。
ちなみに、0番目が最大の連結成分とは限らないです。
# 各連結成分をグラフとして取り出す S = [G.subgraph(c).copy() for c in nx.connected_components(G)] # 試しにS[0]を描画 pos = nx.spring_layout(S[0], k=0.7) nx.draw(S[0], pos, with_labels=True, font_size=18, node_size=800, node_color="orange", font_color="black")
こんな感じになりました。
今回はこのへんで!