NetworkXと学ぶグラフ理論その0 - 何かを書き留める何か

はじめに

「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")

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