Python から Graphviz を使う（ pydot を日本語で出力）(4) では、pydot を使って隣接行列からグラフを描いてみた。今日は、接続行列(incidence matrix) からグラフを描いてみる。
たとえば、次のようなグラフがあったとする。
これを隣接行列で表せば、次のようになる。a のノードと b のノードは隣り合っているので 1。a と b も隣り合っているので 1...。ここでは、あくまでもノードとノードの隣接状態だけを見ている。別の言葉で言えば、始点と終点を表したもの。
終点
a b c d
----------
始 a 0 1 1 1
点 b 1 0 1 1
c 1 1 0 1
d 1 1 1 0
次に、本題の接続行列。接続行列では、このエッジにつながっているのはどのノードという見方をする。e1 につながっているのは、a と b なのでそこが 1、それ以外は 0。e2 につながっているのは a と c なのでそこを1、それ以外は 0 という形で行列を作る。つまり、あるエッジにはどのノードがつながっているかが端的に表されたものになる。e1～e6の行は必ず2 になる（エッジの両端を表すところに 1 なので）。これが接続行列ということになる。通常は、ノードとエッジが逆にすると思うが、pydot だと、この状態で渡さないと処理上グラフが描けないので注意。それじゃいやな場合は末尾参照。
ノード
a b c d
---------------
エ e1 1, 1, 0, 0 e1 の行を足すと 2 になる
ッ e2 1, 0, 1, 0 e2 の行を足すと 2 になる
ジ e3 1, 0, 0, 1 e3 の行を足すと 2 になる
e4 0, 1, 1, 0 e4 の行を足すと 2 になる
e5 0, 1, 0, 1 e5 の行を足すと 2 になる
e6 0, 0, 1, 1 e6 の行を足すと 2 になる
ということで、これを実際に pydot のコードで書いてみる。
import pydot
# 接続行列を用意する
matrix = [[1, 1, 0, 0],
[1, 0, 1, 0],
[1, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 0, 1],
[0, 0, 1, 1]]
# 接続行列からグラフを生成する。
g = pydot.graph_from_incidence_matrix(matrix)
# 左から右へ描くオプションをここでは使ってみる。
g.set_rankdir('LR')
# グラフを出力する。
g.write_png('test5.png')
これで、接続行列からグラフを作成することができた。だけども、エッジにラベルを付けたいなということで、もう少しやってみる。
edges = g.get_edge_list()
e = 1
for edge in g.get_edge_list():
label = "e%s" % e # ラベルは e1 ～ e6 とする。
edge.set_label(label)
e += 1
# グラフを出力する。
g.write_png('test6.png')
結果として、下の図が描けた。
生成される dot ファイルは下のようなものになる。
graph G {
[rankdir=LR;]
"1";
"2";
"1" -- "2" [label=e1];
"3";
"1" -- "3" [label=e2];
"4";
"1" -- "4" [label=e3];
"2" -- "3" [label=e4];
"2" -- "4" [label=e5];
"3" -- "4" [label=e6];
}
試しに、ここでも日本語を使ってみる。エッジのラベルに日本語が使えるかの確認。
e = 1
for edge in g.get_edge_list():
label = "エッジ: %s" % e # ラベルは e1 ～ e6 とする。
edge.set_label(label)
edge.set_fontname('arialuni.ttf')
edge.set_fontsize(9)
e += 1
# グラフにタイトルを日本語で付ける
g.set_fontname('arialuni.ttf')
g.set_size(12)
g.set_label('接続行列からのグラフの生成例')
# グラフを出力する。
g.write_png('test7.png')
もし、接続行列を上記のようにするのが嫌だという場合は、次のようにすればいいかな。
import Numeric
# このままだと pydot が扱えないので
# e1 e2 e3 e4 e5 e6
matrix = [[1, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 1, 0],
[0, 1, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 1]])
# これで pydot が扱えるように並び替えられる
# ちなみに、これでリストが array になるのだが、そのままでも
# 扱える。もし、リストに直すなら、
# Numeric.transpose(matrix).tolist()
matrix = Numeric.transpose(matrix)
# あとは同じ
# 接続行列からグラフを生成する。
g = pydot.graph_from_incidence_matrix(matrix)
# 左から右へ描くオプションをここでは使ってみる。
g.set_rankdir('LR')
# グラフを出力する。
g.write_png('test8.png')
