Calendar

January 2010
M T W T F S S
    Feb »
 123
45678910
11121314151617
18192021222324
25262728293031

Graphvizによる有向グラフの自動生成


Graphvizとは

AT&T研究所が開発したグラフ描画ツールです。
ただし、折れ線グラフや棒グラフみたいなExcelで作成するようなグラフではなく、ダイヤグラムや有向グラフなどが対象となります。

Graphvizの公式サイト

Graphvizを使うことにより、高品質な有向グラフを作成することが出来ます。どんなグラフを作成できるかは、Graphviz公式サイト 生成したグラフのサンプルを参照して下さい。

ソフトウェア技術者の方にとっては、Graphivizの使い方はそれほど難しくありませんし、ネットで検索すれば多くの解説記事が見つかります。
そのため本記事ではGraphvizの説明は最低限に留め、Graphvizをどのように活用していくかに焦点を当てていきます。

基本的な使い方

まずは Graphvizを全く知らない人のために、簡単なグラフ作成手順を紹介しておきます。

作成手順

  1. DOT言語のスクリプトを作成し
  2. dotコマンドを使って、スクリプトからグラフを作成します。

使ってみよう

まずは簡単なdotスクリプトを作成してみます。

dottest.dot
digraph sample{
  graph [rankdir = LR];
  one -> two;
  one -> three;
  two -> four;
  two -> five;
  five -> six -> seven;
}

スクリプトの詳細は後回しにして、まずはdotコマンドを使ってグラフ画像を作ってみましょう。

dotコマンドの書式

dotコマンドの基本的な使い方は以下の通りです。

 dot -T[出力形式] [スクリプトファイル名] -o [出力ファイル名]
実行例

以下のように実行します。

$ dot -Tpng dottest.dot -o dottest.png

成功すれば、次のような画像ファイルが作成されます。

(変換結果:dottest.png)
dottest.png

dotスクリプトの説明

上で使ったdotスクリプトについて簡単に説明します。

digraph sample{
  ...
}

スクリプト全体を、"digraph [ID]{""}" で囲みます。
IDには任意の名前をつけることが出来ます。ただし使用できる文字に制限があります。

  graph [rankdir = LR];

グラフを横方向に作成するオプションで、省略可能です。 省略した場合、縦方向にグラフが作成されます。

  one -> two;

ノードとノードをエッジ("->") で連結して記述します。

 five -> six -> seven;

このように3つ以上を一度に記述することもできます。

ノード名

ノード名にはアルファベット[a-zA-Z]、アンダースコア('_')、数字[0-9]が使えます。 ただし、以下の制限があります。

  • 数字から始まってはいけません(C言語等の変数名の制限と同じですね)
  • ハイフン('-'), > は使えません (エッジで使用します)
  • 空白(' ')も使えません(単語の区切りになります)

上記のルールに抵触するノード名を使う場合、次のどちらかの対応が必要になります。

  1. ノード名全体をダブルクォートで囲う
    "4.3BSD",  "Mac OS X" など
  2. label属性で表示文字列を指定

    ノード名 [label="表示名"]

Graphvizの公式サイトには、もっと詳しい説明があります。

少し凝ったスクリプト

次にもう少し凝った、多少意味のあるグラフを作ってみましょう。

題材はBSDの系譜図です。

The UNIX system family tree: Research and BSD を参考にしました。ただし、全て再現すると大変なので、一部(?)省略しています。

digraph BSD{
  graph [rankdir = LR];

  "4.3BSD NET/2" [label="4.3BSD NET/2", shape=box];
  "386BSD" [label="386BSD"];
  "4.3BSD NET/2" -> "386BSD";

  "4.4BSD" [label="4.4BSD"];
  "4.3BSD NET/2" -> "4.4BSD";

  "BSD/386" [label="BSD/386"];
  "4.3BSD NET/2" -> "BSD/386";
  "4.3BSD NET/2" -> NetBSD;

  subgraph cluster0{
    label="(NetBSD)";
    color=lightgray;
    "NetBSD" [label="NetBSD"];
    "NetBSD -current" [label="NetBSD -current", color=yellow, style=filled];
    "NetBSD" -> "NetBSD -current";
  }
  "386BSD" -> "NetBSD";
  "4.4BSD" -> "NetBSD";

  subgraph cluster1{
    label="(FreeBSD)";
    color=lightgray;
    "FreeBSD" [label="FreeBSD"];
    "FreeBSD 9 -current" [label="FreeBSD 9 -current", color=yellow, style=filled];
    "FreeBSD" -> "FreeBSD 9 -current";
  }
  "386BSD" -> FreeBSD;
  "4.4BSD" -> FreeBSD;

  "DragonFly" [label="DragonFly", color=yellow, style=filled];
  "FreeBSD" -> "DragonFly"  [label="FreeBSD 4.8", fontcolor=blue, fontsize=9];

  "BSD/OS" [label="BSD/OS"];
  "BSD/386" -> "BSD/OS";
  "4.4BSD" -> "BSD/OS";

  subgraph cluster2{
    label="(OpenBSD)";
    color=lightgray;
    "OpenBSD" [label="OpenBSD"];
    "OpenBSD -current" [label="OpenBSD -current", color=yellow, style=filled];
    "OpenBSD" -> "OpenBSD -current";
  }
  "NetBSD" -> "OpenBSD";

  subgraph cluster3{
    label="(Mac OS X)";
    color=lightgray;

    "Rhapsody" [label="Rhapsody", color=lightblue, style=filled];
    "Darwin/Mac OS X" [label="Darwin/Mac OS X", color=lightblue, style=filled];
    "Mac OS X" [label="Mac OS X", color=lightblue, style=filled];
    "Rhapsody" -> "Darwin/Mac OS X" -> "Mac OS X";
  }
  "FreeBSD" -> "Darwin/Mac OS X" [label="FreeBSD 3.2", fontcolor=blue, fontsize=9];
  "NetBSD" -> "Darwin/Mac OS X" [label="NetBSD 1.4 (?)", style=dotted, fontcolor=blue, fontsize=9];
  "4.4BSD" -> Rhapsody;
}
コードの補足

上のコードについて、少し説明しておきます。

ノード

今回の題材では、

  • "4.4BSD" (違反:数字で始まっている)
  • "FreeBSD 9 -current" (違反:禁止文字(空白,ハイフン)を含む)

のように、そのままではノード名に使えない名詞が多いため、全てダブルクォートで囲っています。

"4.3BSD NET/2" [label="4.3BSD NET/2", shape=box];
エッジ

エッジも修飾可能です。

"FreeBSD" -> "DragonFly"  [label="FreeBSD 4.8", fontcolor=blue, fontsize=9];

デフォルトではフォントサイズ:14ですが、ここでは少し小さめのサイズ:9を指定しています。またフォントカラーに青色を指定しています。

サブグラフ

また、subgraph 機能を使って、いくつかのサブグラフを指定しています。
またサブグラフのIDを“cluster”で始めると、枠を描画してくれます。

  subgraph cluster0{
    ...
  }
変換結果

このスクリプトをdotコマンドで変換すると、以下のような結果を得られます。

bsdtree.png

正しい使い方

ここまでの説明で、がんばれば凝ったグラフを作成できることは分かって頂けたと思いますが、 VISIOとかで書いた方が楽じゃんと思った人もいるかもしれません …それは正しいです。

人がスクリプトをごりごり書くのではなく、下の図のようにプログラムで自動生成したdotスクリプトからグラフを自動生成というのがGraphvizの正しい使い方と思います。(たぶん)

dot_process

この図もGraphvizを使って作成しています。ソースコード

日本語も無事通ってますね。ドキュメントによるとUTF-8をサポートしています。

どうやって使うの?

普通はユーザーが知らない間にソフトウェアが裏でこっそりGraphvizを使ってグラフを自動生成 …というパターンになります。

私がお世話になっている以下のソフトウェアでも Graphvizを利用しています。

  • doxygen

    ソースコードからドキュメントを自動生成するツールです。
    UML図は、関数呼び出し図などの作成に利用しています。

  • KCachegrind

    Valgrind/Callgrind(プログラムのプロファイル用ツール)をアシストするデータ視覚化ツールです。
    プロファイル情報を視覚化して表示してくれます。

  • visitors

    WEBサーバのアクセスログの解析ツールです。
    ユーザのページ遷移をグラフ化してくれます。

上で挙げたツールは全て技術者向けなので「裏でこっそり」とはいかず、ユーザーはGraphvizの存在を意識することになりますが…
(さすがに、自動生成するdotスクリプトの中身までは読む必要はありませんが)

正しく使ってみよう

裏でこっそりやってくれるんなら関係ないや…という結論だと後が続かないので、ここは一つ裏でこっそりやってくれるプログラムを作ってみましょう。

プログラムの仕様

今回はXMLファイルを題材としたサンプルを作ってみます。

仕様

今回作成するプログラムの仕様は次の通りです。

XMLファイルを読み込んで、要素(エレメント)をdotのノードに変換して、dotスクリプトを出力する。
ただし、全てのエレメントの親子関係を線で結ぶこと。

親子関係を表現するには、Rootエレメントを起点に、全エレメントを “親エレメント -> 子エレメント;” と継いで出力すれば可能です。

このプログラムを使ったグラフ作成の流れは次の様になります。赤い部分が今回の作成対象です。

xmlviz_process

期待する動作

入力

例えば、次のようなXMLファイルを受けとると、

addressbook.xml
<?xml version="1.0" encoding="UTF-8"?>
<addressbook>
    アドレス帳
    <person>
      <name>foo</name>
      <address>osaka</address>
      <phone>0120-xxx-xxx</phone>
    </person>
    <person>
      <name>hoge hoge</name>
      <address>kobe</address>
      <phone>0120-yyy-yyy</phone>
    </person>
</addressbook>
結果

dotスクリプトを出力し、それをdotコマンドで変換すると次のような結果が得られます。

addressbook.png

addressbook.png

注意事項
  1. dotでは、同じノード名は同じノードと扱うので、同じエレメント名が複数回出現したとき、それぞれを違うノード名を割り当てる必要があります。
  2. XMLのエレメントで使えるが、dotのノード名で使えない文字があります。
    例えば、dotではノード名にハイフン('-')は使えません。出現したら何らかの対処が必要です。

今回はプログラムで自動生成する(=人が介在しない)ので、ノード名にはXMLエレメント名と関係ないユニークなIDをつける事にします。表示するXMLエレメント名はlabel属性で指定します。

サンプルプログラム

せっかく入力がXMLなので、XSLTスタイルシートで作成しました。

xml2dot.xml
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet
   xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
   version="1.0">

  <xsl:strip-space elements="*" />
  <xsl:output method="text" encoding="UTF-8"></xsl:output>

  <xsl:template match="/">
    <xsl:text>digraph sample{ graph [rankdir = LR];
</xsl:text>
    <xsl:apply-templates></xsl:apply-templates>
    <xsl:text>}</xsl:text>
  </xsl:template>

  <xsl:template match="*">
    <xsl:param name="id"><xsl:value-of select="generate-id()"></xsl:value-of></xsl:param>
    <xsl:param name="parent-id"></xsl:param>

    <xsl:value-of select="$id"></xsl:value-of><xsl:text>[label = "</xsl:text>
    <xsl:value-of select="name()"></xsl:value-of>
    <xsl:text>", color=cyan, style=filled]; </xsl:text>
    <xsl:if test="../..">
      <xsl:value-of select="$parent-id"></xsl:value-of>
      <xsl:text> -> </xsl:text>
      <xsl:value-of select="$id"></xsl:value-of>
      <xsl:text>; </xsl:text>
    </xsl:if>
    <xsl:text>
</xsl:text>
    <xsl:apply-templates>
      <xsl:with-param name="parent-id"><xsl:value-of select="$id"></xsl:value-of></xsl:with-param>
    </xsl:apply-templates>

  </xsl:template>

  <xsl:template match="text()">
    <xsl:param name="id"><xsl:value-of select="generate-id()"></xsl:value-of></xsl:param>
    <xsl:param name="parent-id"></xsl:param>

    <xsl:value-of select="$id"></xsl:value-of>
    <xsl:text>_text [label = "</xsl:text>
    <xsl:value-of select="normalize-space()"></xsl:value-of>
    <xsl:text>", shape=box, color=yellow, style=filled];
</xsl:text>
    <xsl:value-of select="$parent-id"></xsl:value-of>
    <xsl:text> -> </xsl:text>
    <xsl:value-of select="$id"></xsl:value-of>
    <xsl:text>_text; </xsl:text>
    <xsl:text>
</xsl:text>
  </xsl:template>

</xsl:stylesheet>

使い方

実行にはXSLTプロセッサが必要です。ここでは2種類(libxml, MSXSL) のXSLTプロセッサでの実行方法について説明します。

libxml

Unix系, Windowsの両方で使用可能です。

$ xsltproc  -o [出力ファイル名]  [XSLTスタイルシート]  [入力XMLファイル]
引数説明
  • -o 出力ファイル名
    生成したdotファイル名の保存先を指定します。
    -o オプションを省略すると標準出力に出力します。
  • XSLTスタイルシート
    xml2dot.xmlを指定します。
  • 入力XMLファイル
    addressbook.xml を指定します。

Windowsユーザーでlibxmlを試したい方はlibxmlの公式サイトから取得してください。

MSXSL (Windows only)

Microsoft製のXSLTプロセッサで、Windows限定です。
libxmlと引数の順番が異なるので注意して下さい。

$ msxsl  [入力XMLファイル]  [XSLTスタイルシート]  -o [出力ファイル名]

Microsoft Download Centerから取得できます。

実行例

次のように実行します。

libxml
$ xsltproc -o addressbook.dot xml2dot.xsl addressbook.xml
MSXSL
$ msxsl addressbook.xml xml2dot.xsl -o addressbook.dot

成功すれば、次のようなファイルが作成されます。ただし、生成する度にノード名は違う値になっていると思います。

addressbook.dot
digraph sample{ graph [rankdir = LR];
id2273096 [label = "addressbook", color=cyan, style=filled];
id2273047_text [label = "アドレス帳", shape=box, color=yellow, style=filled]; id2273096 -> id2273047_text;
id2272492 [label = "person", color=cyan, style=filled]; id2273096 -> id2272492;
id2273073 [label = "name", color=cyan, style=filled]; id2272492 -> id2273073;
id2273057_text [label = "foo", shape=box, color=yellow, style=filled]; id2273073 -> id2273057_text;
id2273123 [label = "address", color=cyan, style=filled]; id2272492 -> id2273123;
id2273124_text [label = "osaka", shape=box, color=yellow, style=filled]; id2273123 -> id2273124_text;
id2273121 [label = "phone", color=cyan, style=filled]; id2272492 -> id2273121;
id2272599_text [label = "0120-xxx-xxx", shape=box, color=yellow, style=filled]; id2273121 -> id2272599_text;
id2272603 [label = "person", color=cyan, style=filled]; id2273096 -> id2272603;
id2272938 [label = "name", color=cyan, style=filled]; id2272603 -> id2272938;
id2272939_text [label = "hoge hoge", shape=box, color=yellow, style=filled]; id2272938 -> id2272939_text;
id2272941 [label = "address", color=cyan, style=filled]; id2272603 -> id2272941;
id2272942_text [label = "kobe", shape=box, color=yellow, style=filled]; id2272941 -> id2272942_text;
id2272944 [label = "phone", color=cyan, style=filled]; id2272603 -> id2272944;
id2272945_text [label = "0120-yyy-yyy", shape=box, color=yellow, style=filled]; id2272944 -> id2272945_text;
}

これをdotコマンドを使って画像ファイルに変換します。

$ dot -Tpng addressbook.dot -o addressbook.png

出来た画像ファイルをブラウザ等で開いて確認して下さい。

今回作成したXSLTスタイルシート(xml2dot.xml)を使えば色々なXMLファイルが変換可能です。
皆さんの手元にあるXMLファイルで実験してみて下さい。

別の実行方法

以下のように変換プログラムとdotコマンドをパイプで連結して1行で処理することもできます。

$ xsltproc  xml2dot.xsl  addressbook.xml  | dot -Tpng  -o addressbook.png

最後に

今回は、いかにGraphvizを実務に適用するかに焦点を絞って説明しました。

Graphvizを使ってグラフを作成するメリットとして、以下のような事が挙げられると思います。

  1. レイアウトの自動化

    ノードが増えても、Graphvizが賢くレイアウトを整えてくれます。私はこれが嬉しいです。

  2. ソースコードのシンプル化

    よくある描画ライブラリのように、線を一本ずつ書いたり、色をつけたり、dot位置を調整する必要がありません。

有向/無向グラフにターゲットを絞ったツールなので万能という訳には行きませんが、適用できれば非常に便利なツールと思います。
機会があれば、ぜひ使ってみてください。

(追記)
  1. 2010/06/10
    追加の記事:Graphvizによる有向グラフの自動生成 (2)で本記事のサンプルの改良版を作成しました。

Comments are closed.