NetworkXメモ（有向グラフ）

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

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

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

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

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

```py3:python3.5
import networkx as nx
```

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

```py3:python3.5
Graph = nx.DiGraph()
```
## ノードの追加

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

```py3: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())`としないとダメです．

```py3:python3.5
>>> Graph.nodes()
['fuga', 'hoge']
>>> Graph.nodes(data=False)
['fuga', 'hoge']
>>> Graph.nodes(data=True)
[('fuga', {}), ('hoge', {})]
```

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

```py3:python3.5
>>> Graph.add_nodes_from(['foo','bar'])
>>> Graph.nodes(data=False)
['fuga', 'bar', 'hoge', 'foo']
```

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

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

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

```py3: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()`メソッドを使います．

```py3:python3.5
>>> Graph.nodes()
['fuga', 'hoge', 'bar', 'foo']
>>> Graph.remove_node('bar')
>>> Graph.nodes()
['fuga', 'hoge', 'foo']
```

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

```py3:python3.5
>>> e = Graph.nodes()
>>> e
['fuga', 'hoge', 'foo']
>>> Graph.remove_nodes_from(e)
>>> Graph.nodes()
[]
```

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

```py3: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())`としないとダメです．

```py3: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()`メソッドを使います．

```py3: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()`です．

```py3: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のリストから重み付きエッジをまとめて追加します．

```py3: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`以外のキーで重みを指定したい場合は変更することも可能です．その場合はキーを以下のように設定します．

```py3: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()`メソッドを使います．

```py3:python3.5
>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.remove_edge('hoge','fuga')
>>> Graph.edges()
[('foo', 'bar')]
```

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

```py3:python3.5
>>> e = Graph.edges()
>>> e
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.remove_edges_from(e)
>>> Graph.edges()
[]
```

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

```py3: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`のノードに至る全経路を探索してみます．

![flowchart.png](https://qiita-image-store.s3.amazonaws.com/0/66988/749a2dfd-7479-25d9-3a2e-3c7ed7ca5a8d.png)

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

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

```py3: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)
```

以下実行結果．

```text:実行結果
all paths
['a', 'b', 'c']
['a', 'b', 'd', 'c']
['a', 'c']
['a', 'd', 'c']
```

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

## 最短経路探索

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

ちなみに最短経路探索モジュールのリファレンスは[ここ](http://networkx.readthedocs.io/en/stable/reference/algorithms.shortest_paths.html)です．