概要

学生にオートマトンなどの計算理論を教える機会があったのですが、そのとき結構面倒だったのが、講義スライドや演習の例題のオートマトンの状態遷移図を書くことでした。結局、PowerPointで作図しましたが、書くときの柔軟性はあるし、それなりにきれいに書けるという点では良いのですが、遷移を表すエッジと状態を表すノードをつなぎ直したり、エッジをちょうどいい感じに書いたりする等が面倒で、かなりの時間を費やしました（徐々にノウハウがたまって速くかけるようにはなりましたが）。オートマトンの状態遷移図は、そのフォーマット自体は確立しているのに、それを書くツールはみつからず、UMLを書くツールでも対応はしていないと思います。書く良い方法を探したのですが、見つけられませんでした。そこで少しツールを調査して結局、Cytoscapeを使って書く方法がよさげかなと思ったので紹介します（超ニッチな需要とは思いますが）。

オートマトンの状態遷移図とその特徴

オートマトンの状態遷移図は、以下のようなものです（下図）。

状態をノード、遷移をエッジとするグラフ（ネットワーク）
状態を表すノードの形は円で、円の中には状態を識別する記号が書かれる
遷移を表すエッジは有向で、遷移をもたらすアルファベットがラベルとしてつく
遷移が開始する開始状態を識別するために、その状態にのみ接続しているエッジを使う
系列が受理される状態である受理状態は二重円

なので、それを表示するツールには以下の条件が求められます。

（当然だが）グラフ表示ができる
ノードとエッジのプロパティをそれぞれ、ノードの中とエッジのラベルにマッピングできる
円・二重円でノードを表せる
片側だけノードにつながるエッジがかける

状態遷移図を書くツール

この記事によると、　ネットーワークの可視化ではCytoscapeとGephiの2強であるということ。Cytoscapeのほうが、REST APIによる連携や、Cytoscape.jsがあることから、ノウハウをWebアプリにも持っていけそうだったので、Cytoscapeを使うことにしました。また、グラフデータベースNeo4jのNeo4j Browserを使うことも考えたのですが、カスタマイズがほとんどできなかったので、今回はあきらめることにしました。

Cytoscapeをどう使ったか

Cytoscapeはスタイルを自分で定義することができます。スタイルは、ノードとエッジのプロパティをそのままスルーでマッピングさせたり（例えば、nameプロパティをノードに表示する等に使う）、プロパティの値毎にどの色・太さなどを使うかというマッピングも可能です。そこで、オートマトンの状態遷移図向けのスタイルを作成しました。スタイルはサンプルとまとめてここにおきました。多少の工夫が必要でした。

ノードの種別はtypeプロパティで区別する。
開始状態の課題は、出側のノードのVisible属性をfalseにすればよいのではと考えたが、そうすると、そのノードにつながるエッジはすべてunvisibleになってしまうので断念。出側のノードのラベルとボーダーを透明に設定することで対応した。その見えないノードのtypeプロパティはstartである
終了状態はtypeプロパティがacceptedであるものである。終了状態の二重丸は、当初ノードのボーダーを二重線にしようかと思ったが、うまく二重丸にならなかった。それで二重丸の画像をマッピングすることにした（この画像も上記の例に入っている）。

書いた結果は下図のようになりました。

状態遷移図の作成手順

では実際に書きたい図があるときに書く手順であるが、Cytoscapeのインポート・アウトポート形式であるsif形式が、純粋なグラフの論理構造を記述できるのでそれを使うのが良さそうである。最初にsif形式でグラフの論理構造を定義し、それとスタイルファイルをインポートし（スタイルファイルはデフォルトに入れてしまえば最初の一回入れるだけよい）、Cytoscapeおまかせで配置させる。その場合、forceレイアウト（ばねモデル）がたいてい適用されるが、きれいには並べられないので、自前でノードを並び替えればできあがり、その状態で保存すればレイアウトも保存される。

おわりに

便利になったかは微妙なところである。オートマトンをうまく並べてくれるレイアウトアルゴリズムがあるとよいのだが。