読者です 読者をやめる 読者になる 読者になる

何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

NetworkXと学ぶグラフ理論 その0

Python Graph Theory

はじめに

「NetworkXでグラフ理論」という書籍なりテキストは得てしてツールであるNetworkXの使い方に終始して肝心のグラフ理論は単なる道具として扱われる傾向がある(と私は思っている)。なるべくNetworkXは添え物にしてグラフ理論の話題を中心に書いていきたい。

準備

まずはツールであるNetworkXの準備を行う。

Python

http://www.python.jp/download/からPythonをダウンロードする。バージョンは2.7系と3.3系があるが今後のことを考えると3.3系のほうがよいのではないかと思う。

Numpy

非公式バイナリからインストールする。

Matplotlib

非公式バイナリからインストールする。

その他

他にもScipy, SymPyなど便利なツールがあるがとりあえずは上記の3つで足りるはず。最後に

pip install networkx

でNetworkXをインストールすれば完了である。

テスト

差し当たり、以下のソースを実行してみて画像が得られれば導入は成功しているはずである。

import networkx as nx
import matplotlib.pyplot as plt

G = nx.fast_gnp_random_graph(20, 0.5)
print("Edges:", G.number_of_edges())
nx.draw_circular(G)
plt.savefig("random.png")
plt.close()

for v in G.nodes():
    N = G.subgraph(G.neighbors(v))
    G.remove_edges_from(N.edges())

print("Edges:", G.number_of_edges())
nx.draw_circular(G)
plt.savefig("random-after.png")

続けばグラフの定義から始めます。