Python
Graphviz
graph
networkx
Jupyter

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


はじめに


  • Notebook上でグラフの生成、分割、描写までの流れを確認した

  • グラフに関する知識が少なくても手軽に分割できるため備忘録として残しておく


ポイント


動かしてみた


  • 今回の動作環境


    • クライアント(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) # 画面描写

出力

image.png


グラフの分割

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)

出力

image.png

2分割のとき

image.png

4分割のとき

image.png

5分割のとき

image.png

6分割のとき

image.png


終わりに


  • 手軽に領域分割ができた


    • NetworkXのグラフを用意しておけば、コードにして1行で分割ができる

    • 複雑な数式等を考えなくても動作する

    • Notebook上でGraphvizと併用すれば、実行直後に描写でき初心者にも易しい