Graphviz(dot)ノート 基礎編

#はじめに
このノートはGraphviz(dot)を使うえで基礎となる知識をまとめたものです。

#基本
###【有向グラフ(digraph)】

dot

digraph xxx {
	//コメント
	/*コメント*/
	#コメント
}

• digraphはdotで有向グラフを書くときの予約語です。
• xxxはグラフ(graph)のIDです。IDは省略可能です。このIDは生成されるイメージに影響しません。
  ※ svgに出力した場合は「TITLE要素」になります。
• コメントの記述は、/* */、//、#を使用します。

=========================================================
###【ノード(node)】

dot

digraph xxx {
	A
}

• Aはノード(node)のIDです。英数字アンダースコア(_)の文字が使用できます。アンダースコアから始めることもできます。

------------------------------------------------------------------------------

dot

digraph xxx {
    A
    a
    B,C
    D;E;F
}

• 複数のノードは改行、セミコロン(;)、カンマ(,)で区切ります。
• 大文字、小文字は区別されます。

------------------------------------------------------------------------------

dot

digraph xxx {
	""
	" "
	"!"
	"$"
	"\%"
	"\""
	"\\"
	"ABC\nDEF"
	"ABC
DEF"
}

• ノードのIDに空文字列、空白、特殊文字を使用する場合は文字列全体を二重引用符(")で囲む必要があります。
  　二重引用符で囲まれた文字列内の\ (バックスラッシュ)、二重引用符(")は\ (バックスラッシュ)でエスケープする必要があります。

------------------------------------------------------------------------------

dot

digraph xxx {
	"graph"
	"node"
	"edge"
	"->"
}

• dotの予約語はそのままではIDに使用できません、二重引用符(")で囲む必要があります。

------------------------------------------------------------------------------

dot

digraph xxx {
	漢字ひらがなカタカナ半角ｶﾀｶﾅ [fontname = ダミー]
}

• IDに日本語も使えます。
• 日本語を使用する場合、Windows版のGraphviz(dot)ではfontnameの指定が必要でした。
  fontnameには「ダミー」など存在しないフォント名を指定しても日本語は表示されますが、fontnameを指定しないと文字化けします。

------------------------------------------------------------------------------

dot

digraph xxx {
	A[label="A1"]
	B1[label="B"]
	B2[label="B"]
	C[label="C2"]
}

• labelを指定することにより、IDと異なる文字列をノード内に表示することができます。
• 異なるノードに同じ文字列を表示することもできます。
• IDが同じノードに異なるlabelを指定した場合、後優先となります。

=========================================================

###【エッジ(edge)】

dot

digraph xxx {
	A->B
}

• AとBを結ぶ矢印をエッジ(edge)といいます。有向グラフのエッジは->で表現します。

------------------------------------------------------------------------------

dot

digraph xxx {
    A,B -> X,Y,Z
}

• カンマで区切った複数のノードをエッジで結んだ例です。

#制限値と性能

###【エッジ数の上限(maximum number of edges)】

• エッジ数の上限は32,768でした(Centos版のdot)。
  stack sizeはunlimitedにしています。
  3回計測して平均999秒(986秒～1,008秒)かかりました。

bash

ulimit -s unlimited
dot -T svg e32768.gv -o e32768.svg

e32768.gv

digraph {
    A1->A2
    A2->A3
    ～途中省略～
    A32767->A32768
    A32768->A1
}

• 32,769のエッジを処理させようとしたとき、dotを起動して、約４分後に「out of memory」のメッセージを表示し、「Segmentation fault」でコアダンプしました。

------------------------------------------------------------------------------

bash

ulimit -s unlimited
dot -T svg q128.gv -o q128.svg
dot -T svg e16384.gv -o e16384.svg

q128.gv

digraph {
    A1, A2, ～途中省略～ A127, A128
    ->
    A1, A2, ～途中省略～ A127, A128
}

e16384.gv

digraph {
    A1->A2
    A2->A3
    ～途中省略～
    A16383->A16384
    A16384->A1
}

• 処理時間は、ノード数やエッジ数から単純計算で求まるものではないようです。

ファイル	ノード数	エッジ数	処理時間
q128.gv	128	16,384	22時間13分30秒(80,010秒)
e16384.gv	16,384	16,384	4分47秒(287秒)

128個のノードの場合、エッジ数の最大は16,384です。

=========================================================

###【ノード数の上限(maximum number of nodes)】

• 409,600以上
  409,600ノードの処理に15,816秒(4時間23分36秒)かかりました。
  限界値の見極めはできていません。

#環境
Graphviz 2.38.0
ホスト　Windows10 COREi7
VM　　　VirtualBox バージョン 5.2.6 r120293 (Qt5.6.2)
　　　　　CentOS Linux release 7.4.1708 (Core)
VSCode+拡張機能(Markdown Preview EnhancedとPlantUML)でdigraphがかけることがわかりました。

\`\`\`plantuml
digraph xx{
    A->B
}
\`\`\`

#参考
The DOT Language

#おわりに

• プログラムでdotソースを出力する場合、ノードのIDは二重引用符で囲んだ方がよいです。
• エッジ数の上限は32,768。stackサイズによっては上限に満たずdotが異常終了します。