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が異常終了します。