pythonのフレームワークNetworkXでグラフ理論

グラフ理論~点と線~

　数学の一分野でありながら、情報系の特にアルゴリズム分野で発展してきたグラフ理論。
基本的な部分はとっても簡単で、とにかく点(node)と線(edge)について考える学問。
　実装に使う言語は、boostにgraphアルゴリズムがあるようなのでc++とも考えたけど、軽量言語でサクサク作りたかったし、ドキュメントも充実してそうなNetworkXというフレームワークを使うことに。

インストール

公式サイトはこちら。
コマンドラインから、

sudo pip install networkx

以上。matplotlibとかpygraphvizはインストールしときましょう。pygraphvizはpip install pygraphvizでインストールできないようなので、こちらからダウンロードする。

チュートリアル

nodeとedgeの作成にnetworkx。作成したグラフの視覚化にmatplotlibを使う。

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()

node(点)をつくる

G.add_node(1)
print G.nodes()

>>>[1]

edge()(線)をつくる

G.add_node(2)
G.add_edge(3, 4)
print G.nodes()
print G.edges()

>>>[2, 3, 4]
>>>[(3, 4)]

matplotlibで描写する

nx.draw(G)
plt.show()
#グラフの描写

pygraphvizを使えば、ムービーとかも作れます。