株式会社エス・スリー・フォー

Graphvizを使った有向グラフの自動生成

Graphvizとは

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

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

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

基本的な使い方

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

作成手順

DOT言語のスクリプトを作成し
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 [出力ファイル名]

-Tで画像形式を指定します。
bmp, jpeg, png, tiff, その他が指定できます。どんな形式で出力可能かは、Graphviz公式サイト Output Formatsを参照して下さい。
-o で出力ファイル名を指定します。指定しない場合、標準出力に出力します。
その他、細かいオプションは、Graphviz公式サイト Command-line Invocationを参照して下さい。

実行例

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

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

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

変換結果：dottest.png

dotスクリプトの説明

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

digraph sample{
  ...
}

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

  graph [rankdir = LR];

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

  one -> two;

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

 five -> six -> seven;

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

ノード名

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

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

上記のルールに抵触するノード名を表示したい場合、ノード名は上記のルールに従った上で、

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

のように、label属性で表示文字列を指定します。

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

少し凝ったスクリプト

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

題材はBSDの系譜図です。

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

digraph BSD{
  graph [rankdir = LR];

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

  _44BSD [label="4.4BSD"];
  _43BSD_NET2 -> _44BSD;

  BSD386 [label="BSD/386"];
  _43BSD_NET2 -> BSD386;
  _43BSD_NET2 -> NetBSD;

  subgraph cluster0{
    label="(NetBSD)";
    color=lightgray;
    NetBSD [label="NetBSD"];
    NetBSD_current [label="NetBSD -current", color=yellow, style=filled];
    NetBSD -> NetBSD_current;
  }
  _386BSD -> NetBSD;
  _44BSD -> NetBSD;

  subgraph cluster1{
    label="(FreeBSD)";
    color=lightgray;
    FreeBSD [label="FreeBSD"];
    FreeBSD_current [label="FreeBSD 9 -current", color=yellow, style=filled];
    FreeBSD -> FreeBSD_current;
  }
  _386BSD -> FreeBSD;
  _44BSD -> FreeBSD;

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

  BSD_OS [label="BSD/OS"];
  BSD386 -> BSD_OS;
  _44BSD -> 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 [label="Darwin/Mac OS X", color=lightblue, style=filled];
    MacOSX [label="Mac OS X", color=lightblue, style=filled];
    Rhapsody -> Darwin -> MacOSX;
  }
  FreeBSD -> Darwin [label="FreeBSD 3.2", fontcolor=blue, fontsize=9];
  NetBSD -> Darwin [label="NetBSD 1.4 (?)", style=dotted, fontcolor=blue, fontsize=9];
  _44BSD -> Rhapsody;
}

コードの補足

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

ノード

今回の題材では、

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

のように、そのままではノード名に使えない名詞が多いため、アンダースコア('_')に置き換えたりして制限を回避しています。全く違う名称に置き換えても良いのですが、自分で書いてて混乱しそうなので元の名称を参考にしました。

グラフに表示するテキストはlabel属性で指定しています。

_43BSD_NET2 [label="4.3BSD NET/2", shape=box];

ノードの属性を指定する時は、上記のように先にノード情報のみを定義しておきます。

ノードとノードの連結は、別の行で定義します。

_43BSD_NET2 -> _44BSD;

エッジ

エッジも修飾可能です。

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

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

サブグラフ

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

  subgraph cluster0{
    ...
  }

変換結果

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

正しい使い方

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

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

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

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

どうやって使うの？

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

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

doxygen
ソースコードからドキュメントを自動生成するツールです。
UML図は、関数呼び出し図などの作成に利用しています。
KCachegrind
Valgrind/Callgrind(プログラムのプロファイル用ツール)をアシストするデータ視覚化ツールです。
プロファイル情報を視覚化して表示してくれます。
visitors
WEBサーバのアクセスログの解析ツールです。
ユーザのページ遷移をグラフ化してくれます。

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

正しく使ってみよう

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

プログラムの仕様

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

仕様

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

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

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

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

期待する動作

入力

例えば、次のような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

注意事項

dotでは、同じノード名は同じノードと扱うので、同じエレメント名が複数回出現したとき、それぞれを違うノード名を割り当てる必要があります。
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を使ってグラフを作成するメリットとして、以下のような事が挙げられると思います。

レイアウトの自動化
ノードが増えても、Graphvizが賢くレイアウトを整えてくれます。私はこれが嬉しいです。
ソースコードのシンプル化
よくある描画ライブラリのように、線を一本ずつ書いたり、色をつけたり、dot位置を調整する必要がありません。

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

This entry was posted on Wednesday, January 13th, 2010 at 4:29 pm and is filed under S34 Lab. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

この記事の投稿者: 宮村

Graphvizを使った有向グラフの自動生成

Graphvizとは

基本的な使い方

作成手順

使ってみよう

dottest.dot

dotコマンドの書式

実行例

変換結果：dottest.png

dotスクリプトの説明

ノード名

少し凝ったスクリプト

コードの補足

ノード

エッジ

サブグラフ

変換結果

正しい使い方

どうやって使うの？

正しく使ってみよう

プログラムの仕様

仕様

期待する動作

入力

addressbook.xml

結果

addressbook.png

注意事項

サンプルプログラム

xml2dot.xml

使い方

libxml

引数説明

MSXSL (Windows only)

実行例

libxml

MSXSL

addressbook.dot

別の実行方法

最後に

Pages

Archives

Categories

Tags

Categories