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及びラッパーをインストールする

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分割して色分けするまでの流れを例示する

必要ライブラリ

import numpy
import networkx # グラフの作成のため
import metis    # グラフの分割のため
import graphviz # グラフの描画のため

データの用意

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)]

グラフの生成

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)                 # 画面描写

出力

グラフの分割

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]

グラフの描写

# 分割後のノードの番号に応じて色分け
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)

出力

2分割のとき

4分割のとき

5分割のとき

6分割のとき

終わりに

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