NetworkXメモ（有向グラフ）

概要

最近研究でNetworkXを使い出したので自分用のメモとしてよく使いそうなモジュールを書いていきます．

Pythonを使い出して間もないので，スマートに書けてないと思います．あと言葉使いが間違ってる部分があるかもしれない(メソッドとかパッケージとか)．

NetworkXパッケージの導入はpipでできます．pip install networkxでOKです．

Reference : http://networkx.readthedocs.io/en/stable/

NetworkXパッケージのインポート

まずNetworkXパッケージをインポートします．NetworkXのドキュメントではnxとして短縮名をつけています．

python3.5

import networkx as nx

グラフの作成

空のグラフの作成

まず，グラフを扱うために空のグラフを作成します．有向グラフ(Directed Graph)の場合はDiGraph()で生成することができます．無向グラフの場合はGraph()です．

python3.5

Graph = nx.DiGraph()

ノードの追加

先ほど作成した空のグラフにノードを追加していきます．ノードはDiGraph.add_node()メソッドで追加することができます．

python3.5

>>> Graph.add_node('hoge')
>>> Graph.add_node('fuga')

ノード一覧の取得

ノードの一覧を取得するのはDiGraph.nodes()です．または，Graph.nodes(data=True/False)でも出力することができます．引数を与えなかった場合，dataのデフォルト値はFalseです．data=Trueとした場合，ノード名とノードの持つ属性(attribute)の辞書からなるタプルのリストとして取得されます．

対話型インタプリタならGraph.nodes()を叩くだけで一覧が出力されますが，本質的にはノード一覧を取得してるだけなのでファイル実行中にノード一覧を出力したい場合はprint(Graph.nodes())としないとダメです．

python3.5

>>> Graph.nodes()
['fuga', 'hoge']
>>> Graph.nodes(data=False)
['fuga', 'hoge']
>>> Graph.nodes(data=True)
[('fuga', {}), ('hoge', {})]

まとめてノードを追加する

さらに，リストや辞書からまとめてノードを追加することもできます．これはDiGraph.add_nodes_from()メソッドを使います．

python3.5

>>> Graph.add_nodes_from(['foo','bar'])
>>> Graph.nodes(data=False)
['fuga', 'bar', 'hoge', 'foo']

属性付きのノードを作成する

先ほどのノード一覧の出力で，DiGraph.nodes(data=True)とした場合，ノード名とノードの持つ属性の辞書からなるタプルのリストが出力されると紹介しました．属性付きのノードを生成するのもDiGraph.add_node()です．

python3.5

>>> Graph.add_node('hoge', color = 'green')
>>> Graph.add_node('fuga', color = 'red')
>>> Graph.nodes(data=True)
[('fuga', {'color': 'red'}), ('hoge', {'color': 'green'})]

属性は好きなだけ追加することができます．

python3.5

>>> Graph.add_node('foo', color = 'white', lang = 'en')
>>> Graph.nodes(data=True)
[('fuga', {'color': 'red'}), ('foo', {'color': 'white', 'lang': 'en'}), ('hoge', {'color': 'green'})]

ノードの削除

グラフに追加したノードを削除するにはDiGraph.remove_node()メソッドを使います．

python3.5

>>> Graph.nodes()
['fuga', 'hoge', 'bar', 'foo']
>>> Graph.remove_node('bar')
>>> Graph.nodes()
['fuga', 'hoge', 'foo']

まとめてノードを削除する

ノードの追加と同様に，リストや辞書からまとめてノードを削除することもできます．これはDiGraph.remove_nodes_from()メソッドを使います．

python3.5

>>> e = Graph.nodes()
>>> e
['fuga', 'hoge', 'foo']
>>> Graph.remove_nodes_from(e)
>>> Graph.nodes()
[]

エッジの追加

ノードとノードを繋ぐエッジを追加していきます．エッジはDiGraph.add_edge()メソッドで追加することができます．有向グラフなので1つ目の引数がstart、2つ目の引数がtargetになります．

Python3.5

>>> Graph.nodes(data=False)
['hoge', 'foo', 'fuga', 'bar']
>>> Graph.add_edge('hoge','fuga')
>>> Graph.add_edge('foo','bar')

エッジ一覧の取得

エッジの一覧を取得するのはDiGraph.edges()です．エッジ一覧の取得もノードと同様，data=True/Falseで属性の表示/非表示を選ぶことができます．

こちらも対話型インタプリタだとGraph.edges()を叩くだけで一覧が出力されますが，コードのファイル実行で一覧を出力させたい場合はprint(Graph.edges())としないとダメです．

Python3.5

>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.edges(data=False)
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.edges(data=True)
[('hoge', 'fuga', {}), ('foo', 'bar', {})]

まとめてエッジを追加する

エッジもノード同様リストや辞書からまとめて追加することができます．エッジの場合はDiGraph.add_edges_from()メソッドを使います．

Python3.5

>>> Graph.nodes()
['fuga', 'hoge', 'foo', 'bar']
>>> Graph.add_edges_from([('hoge','fuga'),('foo','bar')])
>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]

属性付きのエッジを追加する

もちろんエッジにも属性をつけることができます．むしろエッジに属性をつける場合のほうが多いかもしれません．重み付きグラフをこれで実現できます．

ちなみに重み付きグラフの場合は重みをweightで設定しておくと，後々経路探索とかのときにキーのデフォルト値がweightである場合が多いので楽です．
属性付きのエッジもDiGraph.add_edge()です．

Python3.5

>>> Graph.add_edge('foo', 'hoge', weight=0.7)
>>> Graph.add_edge('bar', 'fuga', weight=0.7)
>>> Graph.edges(data=True)
[('foo', 'hoge', {'weight': 0.7}), ('bar', 'fuga', {'weight': 0.7})]

まとめて重み付きエッジを追加する

重み付きグラフを作るシチュエーションは多いので，NetworkXには重み付きエッジを追加しやすいようにDiGraph.add_weighted_edges_from()メソッドがあります．

add_edges_from()では，(始点,終点)の2-tupleのリストからエッジをまとめて追加しました．
add_weighted_edges_from()では，(始点,終点,重み)の3-tupleのリストから重み付きエッジをまとめて追加します．

python3.5

>>> Graph.add_weighted_edges_from([('hoge','fuga',0.4),('foo','bar',0.2)])
>>> Graph.edges(data=True)
[('hoge', 'fuga', {'weight': 0.4}), ('foo', 'bar', {'weight': 0.2})]

特に指定しない場合は重みのキーはweightで設定されます．しかし，もしweight以外のキーで重みを指定したい場合は変更することも可能です．その場合はキーを以下のように設定します．

python3.5

>>> Graph.add_weighted_edges_from([('hoge','fuga',0.4),('foo','bar',0.2)],weight='omomi')
>>> Graph.edges(data=True)
[('hoge', 'fuga', {'omomi': 0.4}), ('foo', 'bar', {'omomi': 0.2})]

エッジの削除

グラフに追加したエッジを削除するにはDiGraph.remove_edge()メソッドを使います．

python3.5

>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.remove_edge('hoge','fuga')
>>> Graph.edges()
[('foo', 'bar')]

まとめてエッジを削除する

エッジの追加と同様に，リストや辞書からまとめてエッジを削除することもできます．これはDiGraph.remove_edges_from()メソッドを使います．

python3.5

>>> e = Graph.edges()
>>> e
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.remove_edges_from(e)
>>> Graph.edges()
[]

すべてのノードとエッジを削除する

今まで追加してきたノードやエッジをすべて削除して空のグラフに戻したくなったときはDiGraph.clear()メソッドを使います．

python3.5

>>> Graph.nodes()
['fuga', 'hoge', 'bar', 'foo']
>>> Graph.edges()
[('fuga', 'foo'), ('hoge', 'fuga'), ('bar', 'hoge'), ('foo', 'bar')]
>>> Graph.clear()
>>> Graph.nodes()
[]
>>> Graph.edges()
[]

経路探索

これでグラフが作成できました．NetworkXには経路探索アルゴリズムもいろいろ含まれており，簡単に経路探索ができます．
僕の研究ではある始点から終点までの全ての経路を取得する必要があるので，まずはこれを書いてみます．

全経路の取得

今回はサンプルとして以下の様なグラフを仮定して，aのノードからcのノードに至る全経路を探索してみます．

経路探索の場合は最短経路を見つける場合が多いですが，NetworkXには全経路を取得するモジュールも存在していて，それがnx.all_simple_paths(G, source, target, cutoff=None)です．
cutoffは探索をやめる深さで，これを指定した場合cutoff以下の長さの経路のみが返ってきます．デフォルトでは指定されていません．

全経路を取得するために以下のようなコードを書きました．

allpaths.py

import networkx as nx

Graph = nx.DiGraph()

Graph.add_nodes_from(['a','b','c','d'])

Graph.add_edges_from([('a','b'),('a','c'),('a','d'),('b','c'),('b','d'),('d','c')])

print('all paths')
for path in nx.all_simple_paths(Graph, source='a', target='c'):
    print(path)

以下実行結果．

実行結果

all paths
['a', 'b', 'c']
['a', 'b', 'd', 'c']
['a', 'c']
['a', 'd', 'c']

全経路が取得できていることが確認できました．

最短経路探索

最短経路探索のモジュールはいろいろなアルゴリズムが実装されていて，それはもうダイクストラ法もワーシャル-フロイド法もベルマン-フォード法も実装されてる(グラフ全然分からないのでどういうアルゴリズムかは知らない)んですが，僕の研究の興味の対象が最短経路ではないので今後気力が続いたら加筆します．

ちなみに最短経路探索モジュールのリファレンスはここです．