November 18, 2008

Python+networkxで連結成分分解

networkx.componentで連結成分分解できる。(有向グラフなら強連結成分分解も)
以下メモ。
#!/usr/bin/local/python
# -*- coding: utf-8 -*-

import networkx as nx

#二項分布(p=0.1)に従ってリンクの張られるランダムネットワーク
G = nx.binomial_graph(10,0.1)

print G.nodes()
print G.edges()

#連結成分分解
components = nx.component.connected_components(G)

print components