Graphviz(dot)ノート　基礎編

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

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

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


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

![graph1.png](https://qiita-image-store.s3.amazonaws.com/0/234070/cae3d2d4-c1db-5a5b-bf18-d69c9ffd15e5.png)

~~~dot:dot
digraph xxx {
	A
}
~~~


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

\------------------------------------------------------------------------------

![q.png](https://qiita-image-store.s3.amazonaws.com/0/234070/fdab0b5c-3284-7e5e-d359-00a718dce0ea.png)

~~~dot:dot
digraph xxx {
    A
    a
    B,C
    D;E;F
}
~~~
 - 複数のノードは改行、セミコロン(;)、カンマ(,)で区切ります。
 - 大文字、小文字は区別されます。


\------------------------------------------------------------------------------

![q.png](https://qiita-image-store.s3.amazonaws.com/0/234070/1cd1da05-2410-f3bd-f454-e931d940567b.png)


~~~dot:dot
digraph xxx {
	""
	" "
	"!"
	"$"
	"\%"
	"\""
	"\\"
	"ABC\nDEF"
	"ABC
DEF"
}
~~~
 - ノードのIDに空文字列、空白、特殊文字を使用する場合は文字列全体を二重引用符(")で囲む必要があります。  
　二重引用符で囲まれた文字列内の\ (バックスラッシュ)、二重引用符(")は\ (バックスラッシュ)でエスケープする必要があります。



\------------------------------------------------------------------------------

![q.png](https://qiita-image-store.s3.amazonaws.com/0/234070/7a64de22-785b-46d8-cd60-41c48c1ed133.png)


~~~dot:dot
digraph xxx {
	"graph"
	"node"
	"edge"
	"->"
}
~~~

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

![graph2.png](https://qiita-image-store.s3.amazonaws.com/0/234070/b45d9300-25d2-fa01-cc81-ea503efedcc4.png)

~~~dot:dot

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

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

\------------------------------------------------------------------------------
![q.png](https://qiita-image-store.s3.amazonaws.com/0/234070/98585c46-4b53-8a61-cfb4-158e01ba384a.png)

~~~dot:dot
digraph xxx {
	A[label="A1"]
	B1[label="B"]
	B2[label="B"]
	C[label="C2"]
}
~~~
 - labelを指定することにより、IDと異なる文字列をノード内に表示することができます。
 - 異なるノードに同じ文字列を表示することもできます。
 - IDが同じノードに異なるlabelを指定した場合、後優先となります。

\=========================================================

###**【エッジ(edge)】**

![graph1.png](https://qiita-image-store.s3.amazonaws.com/0/234070/11d30307-cc11-c4eb-f187-814397fed058.png)

~~~dot:dot
digraph xxx {
	A->B
}
~~~


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

\------------------------------------------------------------------------------

![graph4.png](https://qiita-image-store.s3.amazonaws.com/0/234070/4bf34420-46a0-d77b-a63a-66886e859254.png)

~~~dot: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:bash
ulimit -s unlimited
dot -T svg e32768.gv -o e32768.svg
~~~
~~~dot:e32768.gv
digraph {
    A1->A2
    A2->A3
    ～途中省略～
    A32767->A32768
    A32768->A1
}
~~~



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

\------------------------------------------------------------------------------

~~~bash:bash
ulimit -s unlimited
dot -T svg q128.gv -o q128.svg
dot -T svg e16384.gv -o e16384.svg
~~~
~~~dot:q128.gv
digraph {
    A1, A2, ～途中省略～ A127, A128
    ->
    A1, A2, ～途中省略～ A127, A128
}
~~~
~~~dot: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がかけることがわかりました。
<pre>\`\`\`plantuml
digraph xx{
    A->B
}
\`\`\`</pre>

#**参考**
[The DOT Language](https://graphviz.gitlab.io/_pages/doc/info/lang.html)


#**おわりに**

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