【Python】NetworkX 2.0の基礎的な使い方まとめ

[NetworkX](https://networkx.github.io/documentation/stable/index.html)は、グラフ/ネットワーク理論系の計算を行うためのPythonのパッケージです。
最近(2017-09-21)、メジャーアップデートして[バージョン2.0が公開](https://networkx.github.io/documentation/networkx-2.0/release/release_2.0.html)されました。

NetworkX 2.0は1.x系からAPIが大きく整理されています。
これを機に使い方をまとめようと思います。

# インストール

pipでインストールしてください。

```
pip install networkx
```

古いバージョンをインストール済みなら`-U`オプションで更新できます。

```
pip install -U networkx
```

# グラフの構築
`networkx.Graph`クラスおよびその派生クラスに頂点と辺を追加していきます。
下の例ではintを頂点としていますが、[hashable](https://qiita.com/yoichi22/items/ebf6ab3c6de26ddcc09a)ならなんでも頂点として使えます。

```py
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)                
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)                                    
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

# 辺の削除
G.remove_edge(3, 4)                    
G.remove_edges_from([(1, 3), (2, 5)])

# 頂点の削除 (削除された頂点に接続されている辺も削除されます)
G.remove_node(5)
G.remove_nodes_from([3, 4])

# 指定したパス上の頂点と辺を追加
nx.add_path(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5

# 指定した閉路上の頂点と辺を追加
nx.add_cycle(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5 → 1

# 放射状に頂点と辺を追加
nx.add_star(G, [1, 2, 3, 4, 5])  # 1 → 2, 1 → 3, 1 → 4, 1 → 5
```

# グラフの可視化
グラフの可視化には、Matplotlibを使う方法とPyGraphvizを使う方法があります。
設定可能な項目が多いのでこの記事では軽い説明に留めます。

## Matplotlibを使う
Matplotlibを使う方法の利点は、インストールが簡単なことです。
欠点は曲線的な辺を描画してくれないことで、複雑なグラフになると頂点や辺やラベルが盛大に重なります。長いラベルをつけるのには向いていません。

```py
import matplotlib.pyplot as plt
import networkx as nx

G = nx.DiGraph()
nx.add_path(G, [3, 5, 4, 1, 0, 2, 7, 8, 9, 6])
nx.add_path(G, [3, 0, 6, 4, 2, 7, 1, 9, 8, 5])

nx.draw_networkx(G)
plt.show()
```
![matplotlib.png](https://qiita-image-store.s3.amazonaws.com/0/154890/1da44eb2-19d5-41a4-5394-88a6ad42d2ed.png)


## PyGraphvizを使う
PyGraphvizを使うと、Matplotlibを使うよりも気の利いた見た目になります。
欠点は、WindowsにPyGraphvizをインストールするのが多少面倒なことです。
Ubuntuなら `apt install graphviz libgraphviz-dev` して `pip install pygraphviz` でOK。

### インストール手順（Windows）
1. Graphvizをインストールする。（ http://wingraphviz.sourceforge.net/wingraphviz/ ）
2. Githubで公開されているビルド済みwheelを使ってPyGraphvizをインストールする。

```bash
# Python 3.6
pip install "https://github.com/CristiFati/Prebuilt-Binaries/blob/master/PyGraphviz/v1.5/Graphviz-2.42.2/pygraphviz-1.5-cp36-cp36m-win_amd64.whl?raw=true"

# Python 3.7
pip install "https://github.com/CristiFati/Prebuilt-Binaries/blob/master/PyGraphviz/v1.5/Graphviz-2.42.2/pygraphviz-1.5-cp37-cp37m-win_amd64.whl?raw=true"

# Python 3.8
pip install "https://github.com/CristiFati/Prebuilt-Binaries/blob/master/PyGraphviz/v1.5/Graphviz-2.42.2/pygraphviz-1.5-cp38-cp38-win_amd64.whl?raw=true"
```
（参考：[Installing pygraphviz on Windows 10 64-bit, Python 3.6](https://stackoverflow.com/questions/45093811/installing-pygraphviz-on-windows-10-64-bit-python-3-6)）

### 使い方

```py
import networkx as nx

G = nx.DiGraph()
nx.add_path(G, [3, 5, 4, 1, 0, 2, 7, 8, 9, 6])
nx.add_path(G, [3, 0, 6, 4, 2, 7, 1, 9, 8, 5])

nx.nx_agraph.view_pygraphviz(G, prog='fdp')  # pygraphvizが必要
```

<img width=300 src="https://qiita-image-store.s3.amazonaws.com/0/154890/9cef309b-b797-e42e-41f1-5c48ddb96671.png"/>

Jupyter Notebookを使っている場合は、SVGで表示することができます。

```py
import networkx as nx
from IPython.display import SVG, display

G = nx.DiGraph()
nx.add_path(G, [3, 5, 4, 1, 0, 2, 7, 8, 9, 6])
nx.add_path(G, [3, 0, 6, 4, 2, 7, 1, 9, 8, 5])

svg = SVG(nx.nx_agraph.to_agraph(G).draw(prog='fdp', format='svg'))
display(svg)
```
![jupyter.png](https://qiita-image-store.s3.amazonaws.com/0/154890/ba1a7e4d-91e7-01e7-53e2-5b511df8c026.png)

# 基本的な情報の取得
この辺は1.xから変更が多いようです。

```py
import matplotlib.pyplot as plt
import networkx as nx

G = nx.DiGraph()
nx.add_cyle(G, [1, 2, 3, 4, 5])
nx.add_star(G, [1, 2, 3, 4, 5])

# 頂点の一覧
print(list(G.nodes))
# [1, 2, 3, 4, 5]

# 辺の一覧
print(list(G.edges))
# [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (4, 5), (5, 1)]

# 指定した始点に対する、終点の一覧と辺の一覧
print(list(G.succ[1]), G.out_edges(1))
# [2, 3, 4, 5] [(1, 2), (1, 3), (1, 4), (1, 5)]

# 指定した終点に対する、始点の一覧と辺の一覧
print(list(G.pred[5]), G.in_edges(5))
# [4, 1] [(4, 5), (1, 5)]

# 指定した頂点に対する、隣接している頂点の数とその一覧
print(G.degree(4), list(nx.all_neighbors(G, 4)))
# 3, [3, 1, 5]
```

# 頂点や辺にデータをもたせる
`G.nodes`と`G.edges`は、頂点および辺をキー、その属性値の辞書を値とした、Mapping (辞書っぽいオブジェクト) になっています。
さらに`G.succ`はネストしたMappingになっており、辺の始点→終点→属性辞書の順に辿ることができます。同様に`G.pred`は辺の終点→始点→属性辞書の順に辿ることができます。

```py
import matplotlib.pyplot as plt
import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 3)])

# G.nodes[頂点][属性キー] = 属性値
G.nodes[1]['a'] = 'Alice'

# G.edges[辺][属性キー] = 属性値
G.edges[1, 2]['b'] = 'Bob'

# G.succ[始点][終点][属性キー] = 属性値
G.succ[2][3]['c'] = 'Carol'

# G.pred[終点][始点][属性キー] = 属性値
G.pred[3][1]['d'] = 'Dave'

print(dict(G.nodes))
# {1: {'a': 'Alice'}, 2: {}, 3: {}}

print(dict(G.edges))
# {(1, 2): {'b': 'Bob'}, (1, 3): {'d': 'Dave'}, (2, 3): {'c': 'Carol'}}

print(G.succ)
# {1: {2: {'b': 'Bob'}, 3: {'d': 'Dave'}}, 2: {3: {'c': 'Carol'}}, 3: {}}

print(G.pred)
# {1: {2: {'b': 'Bob'}, 3: {'d': 'Dave'}}, 2: {3: {'c': 'Carol'}}, 3: {}}
```

`nx.set_node_attributes()`や`nx.get_edge_attributes()`を使うと属性値をまとめて取得したり設定したりできます。

```py
import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 3)])

# すべての頂点に同じ属性値を設定する.
nx.set_node_attributes(G, name='a', values='Alice')

# 頂点ごとに属性値を個別に設定する. キーは共通.
nx.set_node_attributes(G, name='b', values={2: 'Bob', 3: 'Bravo'})

# まるごと渡す.
nx.set_node_attributes(G, values={1: {'c': 'Carol'}, 2: {'d': 'Dave'}})

print(nx.get_node_attributes(G, 'b'))
# {2: 'Bob', 3: 'Bravo'}

print(nx.get_node_attributes(G, 'c'))
# {2: 'Carol'}

print(dict(G.nodes))
# {1: {'a': 'Alice', 'c': 'Carol'}, 2: {'a': 'Alice', 'b': 'Bob', 'd': 'Dave'}, 3: {'a': 'Alice', 'b': 'Bravo'}}
```

# 探索系の関数
```py
import matplotlib.pyplot as plt
import networkx as nx

G = nx.DiGraph()
nx.add_cyle(G, [1, 2, 3, 4, 5])
nx.add_star(G, [1, 2, 3, 4, 5])

# 2点間の最短経路
print(nx.shortest_path(G, source=2, target=1))
# [2, 3, 4, 5, 1]

# 指定した点から各点への最短経路
print(nx.shortest_path(G, source=2))
# {1: [2, 3, 4, 5, 1], 2: [2], 3: [2, 3], 4: [2, 3, 4], 5: [2, 3, 4, 5]}

# 各点から指定した点への最短経路
print(nx.shortest_path(G, target=1))
# {1: [1], 2: [2, 3, 4, 5, 1], 3: [3, 4, 5, 1], 4: [4, 5, 1], 5: [5, 1]}

# 各点から各点への最短経路
print(nx.shortest_path(G))
# ...

# ゴール地点までの最短経路長が、ある長さ未満に収まるスタート地点とその経路
print(nx.single_target_shortest_path(G, target=1, cutoff=2))
# {1: [1], 4: [4, 5, 1], 5: [5, 1]}

# スタート地点からの最短経路長が、ある長さ未満に収まるゴール地点とその経路
print(nx.single_source_shortest_path(G, source=3, cutoff=2))
# {3: [3], 4: [3, 4], 5: [3, 4, 5]}

# スタート地点からゴール地点までのすべての単純路 (同じ頂点を通らないパス)
print(list(nx.all_simple_paths(G, source=1, target=5)))
# [[1, 2, 3, 4, 5], [1, 3, 4, 5], [1, 4, 5], [1, 5]]
```

# さいごに
他にも1.xからの変更点がいろいろとあるようです。
暇を見つけてちょこちょこ更新していこうと思います。