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（公式ページ）