Search on the blog

2016年1月1日金曜日

graph-toolでグラフのビジュアライズ

 Pythonのgraph-toolというライブラリを使うとグラフ(ネットワーク)の美しいビジュアライズが出来る。公式サイトを見るとアニメーションなども作れるようでなかなか面白そう。
 とりあえずサンプルとして、Warshall Floydで有向グラフを強連結成分分解して色分けするということをやってみた。

インストール
homebrewでインストールできる。
brew tap homebrew/science
brew install graph-tool

有向グラフの作成
from graph_tool.all import *

v_num = 8
edges = [
    [0,1,0,0,0,0,0,0],
    [0,0,1,0,0,0,0,0],
    [1,0,0,1,0,0,0,0],
    [0,0,0,0,1,0,0,0],
    [0,0,0,0,0,1,0,0],
    [0,0,0,0,0,0,1,0],
    [0,0,0,0,1,0,0,1],
    [0,0,0,0,1,0,0,0]
]

g = Graph()
v = g.add_vertex(v_num)
for i in xrange(v_num):
    for j in xrange(v_num):
        if edges[i][j] == 1:
            g.add_edge(i, j)

graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=15,
            output_size=(600, 600), output="directed_graph.png")
以下が作成された画像。


強連結成分分解
dp = [edge[:] for edge in edges]
for k in xrange(v_num):
    for i in xrange(v_num):
        for j in xrange(v_num):
            dp[i][j] |= dp[i][k] & dp[k][j]

scc_grp = g.new_vertex_property("int")
for i in xrange(v_num):
    if g.vertex(i) in scc_grp.__dict__: continue
    scc_grp[g.vertex(i)] = i
    for j in xrange(v_num):
        if dp[i][j] & dp[j][i]:
            scc_grp[g.vertex(j)] = i

graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=15, 
           vertex_fill_color = scc_grp, output_size=(600, 600), output="directed_graph_scc.png")
以下が作成された画像。成分ごとに色分けされている。

参考ページ
Quick start using graph-tool(公式ページ)
graph_tool.draw - Graph drawing and layout(公式ページ)

0 件のコメント:

コメントを投稿