Jupyter Notebook上でMETISを用いた領域分割

# はじめに
- Notebook上でグラフの生成、分割、描写までの流れを確認した
- グラフに関する知識が少なくても手軽に分割できるため備忘録として残しておく

## ポイント
- C言語のグラフ分割ライブラリMETISをNotebook上で使用する
    - https://metis.readthedocs.io/en/latest/
- グラフ構造自体はNetworkXを利用する
    - https://networkx.github.io/documentation/networkx-1.10/tutorial/tutorial.html
- 描写にはGraphvizを利用する
    - https://graphviz.readthedocs.io/en/stable/index.html


# 動かしてみた
- 今回の動作環境
  - クライアント（Windows 10 Pro）
     - ブラウザ : Google Chrome 68.0.3440.106
  - サーバ（Ubuntu 18 on VMware Workstation 12 Player）
     - Jupyter : 4.4
     - JupyterLab : 0.33.11
     - python : 3.6
     - networkx : 2.1
     - metis : 0.2a4
     - graphviz : 0.9

## インストール
以下の手順でMETIS及びラッパーをインストールする

```bash:console
wget http://glaros.dtc.umn.edu/gkhome/fetch/sw/metis/metis-5.1.0.tar.gz
tar zxfv metis-5.1.0.tar.gz
cd metis-5.1.0/build
cmake ../
make config shared=1
make && make install
export PATH=/usr/local/lib:$PATH
export LD_LIBRARY_PATH=/usr/local/lib/
python3 -m pip install metis
```


## 簡単なグラフの分割
グラフを3分割して色分けするまでの流れを例示する

### 必要ライブラリ
```python
import numpy
import networkx # グラフの作成のため
import metis    # グラフの分割のため
import graphviz # グラフの描画のため
```


### データの用意
```python
nodes = numpy.arange(12)          # ノードを配列で用意
edges = []                        # エッジを配列で用意
for i in range(1,len(nodes)):
    if i % 4 == 3:
        edges.append((i-1,i))
        edges.append((i-2,i))
    else:
        u = i-(i%4+(i+1)%4%3%2)
        v = i
        edges.append( (u, v) )    # ノード u と v をつなぐ

print('nodes\t',nodes)
print('edges\t',edges)
```

出力
nodes	 [ 0  1  2  3  4  5  6  7  8  9 10 11]
edges	 [(0, 1), (0, 2), (2, 3), (1, 3), (3, 4), (4, 5), (4, 6), (6, 7), (5, 7), (7, 8), (8, 9), (8, 10), (10, 11), (9, 11)]

### グラフの生成
```python
G = networkx.Graph()               # 無向グラフの用意
G.add_nodes_from(nodes)
G.add_edges_from(edges)
G.graph['graph']={'rankdir':'LR'}  # グラフ描写を横向きに設定

g = networkx.nx_agraph.to_agraph(G)
g.draw('file1.png',prog='circo')   # ファイル出力
graphviz.Source(g)                 # 画面描写
```

出力
![image.png](https://qiita-image-store.s3.amazonaws.com/0/23691/389126a3-b2d8-84ee-50ba-e397f75bde55.png)


### グラフの分割
```python
npart = 3                          # 分割数=3
(edgecut, parts) = metis.part_graph(G,npart)

print('edgec\t',edgecut)           # エッジカット数
print('parts\t',parts)             # 分割後の各ノードの番号を配列で表示
```

出力
edgec    2
parts    [0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1]

### グラフの描写
```python
# 分割後のノードの番号に応じて色分け
colors = ['#FF0000','#0000FF','#00FF00','#FFFF00','#FF00FF','#00FFFF']
for i, p in enumerate(parts):
    G.node[i]['color'] = colors[p]

g = networkx.nx_agraph.to_agraph(G)
g.draw('file2.png',prog='circo')
graphviz.Source(g)
```


出力
![image.png](https://qiita-image-store.s3.amazonaws.com/0/23691/ed8b44dd-650b-ccd4-bbc0-2e58aad4bb4c.png)

2分割のとき
![image.png](https://qiita-image-store.s3.amazonaws.com/0/23691/0725ecf8-594f-e4b0-a3f7-28b374434304.png)

4分割のとき
![image.png](https://qiita-image-store.s3.amazonaws.com/0/23691/ef5d9fdf-2493-cf53-0bf2-276a2fbe72a9.png)

5分割のとき
![image.png](https://qiita-image-store.s3.amazonaws.com/0/23691/9bc3c61a-a44d-9fc1-a3e6-e7d2a0b29b99.png)

6分割のとき
![image.png](https://qiita-image-store.s3.amazonaws.com/0/23691/18dc93b8-3918-5a09-35aa-d8ccd43cbbb1.png)


# 終わりに
- 手軽に領域分割ができた
    - NetworkXのグラフを用意しておけば、コードにして1行で分割ができる
    - 複雑な数式等を考えなくても動作する
    - Notebook上でGraphvizと併用すれば、実行直後に描写でき初心者にも易しい