Graphvizの非レイアウト系ツールメモ

Graphvizにはグラフをレイアウトするツールの他にもグラフを編集、変換したり、指標値を計算するツール群があることを最近知った。簡単に動作確認した範囲をメモ。使ったGraphvizのバージョンは2.20.2-8ubuntu3*1。

まず、入力用にグラフデータのサンプルinput1.dotを用意。

digraph DIRECTED {
	node [shape=circle]
	A
	B -> { G }
	C -> { C D O }
	E -> { F H K }
	F -> { E H }
	G -> { E }
	I -> { J K L }
	H -> { B }
	J -> { N }
	K -> { I M }
	L -> { N }
	N -> { I }
}

circoでレイアウトした結果input1.png。

以下、ツールのコマンド名のアルファベット順。

acyclic：　入力グラフから閉路がなくなるように辺の方向を反転させる

いわゆるDAGに変換する。ただし、辺の反転なので自己ループはそのまま残る。
入力グラフに応じてコマンドの終了ステータスが変わる。

• 0 入力グラフにもともと閉路がなかった
• 1 入力グラフに閉路があった
• 2 入力グラフが無向グラフだった（この場合、コマンドは何も出力しない）
• 255 エラー

例。出力をcircoに渡してレイアウトする。

$ acyclic ./input1.dot | circo -Tpng -o ./acyclic.png

結果の画像acyclic.png。

bcomps：　入力グラフを二連結成分に分割する

デフォルトでは分割された各成分はDOT言語のsubgraphとして元のgraphに包含された形で出力される。各成分を別々のグラフとして出力したい場合は-xオプションを付ける。

例。

$ bcomps ./input1.dot 
digraph DIRECTED {
	node [shape=circle];
	subgraph DIRECTED_bcc_1 {
		I -> J;
		I -> L;
		J -> N;
		L -> N;
		N -> I;
	}
	subgraph DIRECTED_bcc_2 {
		K -> I;
		I -> K;
	}
	subgraph DIRECTED_bcc_3 {
		K -> M;
	}
	subgraph DIRECTED_bcc_4 {
		E -> K;
	}
	subgraph DIRECTED_bcc_5 {
		B -> G;
		G -> E;
		E -> F;
		E -> H;
		F -> E;
		F -> H;
		H -> B;
	}
	subgraph DIRECTED_bcc_6 {
		C -> C;
		C -> D;
	}
	subgraph DIRECTED_bcc_7 {
		C -> C;
		C -> O;
	}
	A;
}

ccomps：　入力グラフを連結成分に分割する

bcompsと同じく、デフォルトでは各成分はsubgraphとして出力され、-xオプションを付ければ別々のグラフとして出力される。特定の頂点を含む成分のみをグラフとして出力させるには、-Xオプションで頂点を指定する。

例。頂点Dを含む連結成分を出力。

$ ccomps -X D ./input1.dot 
digraph DIRECTED_cc {
	C -> C;
	C -> D;
	C -> O;
}

強連結成分の分割は後に出てくるsccmapコマンドで。

diffimg：　二つの画像の差分を出力する

二つの画像の各ピクセルで差分を取った結果を出力する。同じ画像なら結果は黒一色の画像になる。また、公式のドキュメントに記述が見当たらなかったが、試した範囲では同じ画像なら終了ステータスが0、違う画像なら1になるようだ。

例。終了ステータスの確認まで。

$ diffimg ./input1.png ./acyclic.png ./diffimg.png
$ echo $?
1

結果の画像diffimg.png。

Graphvizとしては異色なツール。Graphvizにあるからには、上の例のようにグラフのレイアウト結果を比較して二つのレイアウトのどこが違うか（または全く同じか）を調べるためのツールである。と思うが、二つの画像の各ピクセルの差分を取っているだけなのでどんな画像にも使える。サイズが違う画像同士でも問題なく、対応フォーマットはpng, jpg, gifと、Ghostscriptがあればpsも可らしい。

タイミング良く（？）ちょうど今日、ImageMagickのコマンドで同じことをやるにはどうすればいいかを紹介した記事がある。

• 2枚の画像のdiff（差分）を超簡単に調べる方法 - 昼メシ物語

dijkstra：　入力グラフの指定した頂点から各頂点までの距離を計算する

辺の長さはデフォルトでは全て1となるが、入力グラフに辺のlen属性が指定してあればその値が使われる。計算された距離は、各頂点のdist属性として出力される。また、最大距離（到達不可能な頂点は除く）はグラフのmaxdist属性として出力される。
入力グラフが有向グラフの場合、辺の向きは無視される。

例。頂点Kからの各距離を計算。

$ dijkstra K ./input1.dot 
digraph DIRECTED {
	graph [maxdist="3.000"];
	node [shape=circle];
	A;
	B	 [dist="3.000"];
	G	 [dist="2.000"];
	B -> G;
	E	 [dist="1.000"];
	G -> E;
	C -> C;
	C -> D;
	C -> O;
	F	 [dist="2.000"];
	E -> F;
	H	 [dist="2.000"];
	E -> H;
	K	 [dist="0.000"];
	E -> K;
	F -> E;
	F -> H;
	H -> B;
	I	 [dist="1.000"];
	K -> I;
	M	 [dist="1.000"];
	K -> M;
	I -> K;
	J	 [dist="2.000"];
	I -> J;
	L	 [dist="2.000"];
	I -> L;
	N	 [dist="2.000"];
	J -> N;
	L -> N;
	N -> I;
}

gc：　入力グラフの頂点数、辺数、連結成分数、クラスター数を出力する

Unix系OSのwcコマンドのグラフバージョン。ここでいうクラスターとは、DOT言語のclusterのこと*2。

例。-aオプションで頂点数、辺数、連結成分数、クラスター数を全て表示。

$ gc -a ./input1.dot 
      15      19       3       0 DIRECTED (./input1.dot)

gvcolor：　入力グラフの指定した頂点の色を下方の頂点に流し込んで色を付ける

入力グラフのいくつかの頂点にcolor属性で色を指定しておけば、その色をrankの意味で下にあって連結している頂点へ流し込んで色を付ける。複数の色が流れ込んだ場合はそれらの"平均"の色になる。

このツールだけは下の入力グラフinput2.dotを使う。三つの頂点だけ色を指定しておく。

digraph DIRECTED2 {
	2 -> 3 -> 4 -> 5
	2 -> 1 -> 12
	6 -> 3 -> 7 -> 8
	9 -> 10 -> 7 -> 11
	10 -> 12
	2 [color="red"]
	6 [color="green"]
	9 [color="blue"]
}

例。最初のdotでレイアウト情報を計算してgvcolorに渡す必要がある。

$ dot ./input2.dot | gvcolor | dot -Tpng -o ./gvcolor.png

結果の画像gvcolor.png。

nop：　入力グラフのDOTフォーマットを標準（canonical）形式で表示する

標準がどんな形式なのか調べていないが、省略記法やインデントが正規化されると思えば良いかも。

例。グルーピングしていた頂点間の連結表記が解体され、行末にはセミコロンが付加されている。

$ nop ./input1.dot 
digraph DIRECTED {
	node [shape=circle];
	A;
	B -> G;
	G -> E;
	C -> C;
	C -> D;
	C -> O;
	E -> F;
	E -> H;
	E -> K;
	F -> E;
	F -> H;
	H -> B;
	K -> I;
	K -> M;
	I -> K;
	I -> J;
	I -> L;
	J -> N;
	L -> N;
	N -> I;
}

prune：　入力グラフの指定した頂点を枝狩りする

ここでいう枝狩りとは、指定した頂点をルートとする部分グラフを削除する（manページにある原文は "removes subgraphs rooted at nodes specified"）ことらしい。訳しただけなので「指定した頂点をルートとする部分グラフ」は自分でも意味がよくわからないが、文字通り枝のように伸び出ている部分を切り捨てていくイメージで。

-nオプションで頂点を指定する。原文で "nodes" と複数形になっている通り、二個以上指定できる。

例。頂点Cと頂点Kを枝狩りした結果をcircoでレイアウトする。

$ prune -n C -n K ./input1.dot | circo -Tpng -o prune.png

結果の画像prune.png。

sccmap：　入力グラフを強連結成分に分割する

各成分はクラスターとして出力される。また、各成分を頂点とみなしたときのグラフも出力される。入力グラフが無向グラフの場合は警告が出力される。

例。最後に入力グラフの頂点数、辺数、強連結成分数が表示されているが、これは標準エラー出力。

$ sccmap ./input1.dot 
digraph cluster_0 {
	K -> I;
	I -> K;
	I -> J;
	I -> L;
	J -> N;
	L -> N;
	N -> I;
}
digraph cluster_1 {
	B -> G;
	G -> E;
	E -> F;
	E -> H;
	F -> E;
	F -> H;
	H -> B;
}
digraph scc_map {
	cluster_1 -> cluster_0;
}
15 nodes, 19 edges, 2 strong components

tred：　入力グラフの推移還元（transitive reduction）を出力する

とってもざっくり書くと頂点間の到達可能性を損なわずに可能な限り辺を間引く。

用途としては、頂点が連結しまくってて密度が高い部分がたくさんある有向グラフから辺を間引いて見やすくレイアウトしたいときに使うといいかもしれない。入力グラフが無向グラフの場合は何も出力されない。

例。出力をcircoに渡してレイアウトする。閉路がある場合は結果が一意にならないので警告が出る。

$ tred ./input1.dot | circo -Tpng -o ./tred.png
warning: DIRECTED has cycle(s), transitive reduction not unique
cycle involves edge F -> E

結果の画像tred.png。左側の部分グラフから辺が二本抜かれている。

その他

上でまとめたツール以外にも、グラフデータのフォーマット変換や編集ツールがある。今回試していないものでは、このあたりが便利そうだ。

• unflatten:　グラフレイアウトの際のアスペクト比を調整する
• gvpack：　複数のグラフレイアウトをマージする
• gvpr：　awkのグラフバージョンのようなもの

こういうツールもある、ということを頭の片隅に置いておけばいつか役立つかも。

*1:2011/3/26時点の最新安定版は2.26.3

*2:名前が"cluster"から始まるgraphまたはsubgraph