デザインテクノロジーの最前線 - 桐山孝司

m.c.t.ホーム > エクスペリエンスマガジン > デザインテクノロジーの最前線 - 桐山孝司 > 接続グラフのレイアウト

2007.10.10接続グラフのレイアウト

接続グラフは電子部品の配線図や地下鉄の路線図、そしてソーシャルネットワーキングの関連図まで、 要素のつながり方を表す必要のあるところで使われている。この場合のグラフは棒グラフや円グラフとは違って、関連するものを要素(ノード) で、それらの間の接続関係を枝(エッジ)で視覚的に表したものという意味である。 特に接続関係が一方通行の場合は有向グラフと言ってエッジに矢印をつけて表している。

最近、接続グラフをコンピュータで自動的に作る機会があり、その方法についてもデザイナーから質問を受けることがあった。 接続グラフはエッジの数が少なければ手作業で作ることができるが、数が多くなるとノードを適切な位置に配置するのが難しくなる。 ノードの位置が不適切だと、エッジ同士の交差が多くて表示が込み入ってしまい、エッジを目で追うのが難しいという問題が起こる。従って、 ある程度複雑になったグラフを見やすくレイアウトできることは有用な技術である。日常よく見る接続グラフだが、 ツールを使って自分でレイアウトをする方法を紹介する。

接続グラフの例として、6種類の演算(+5、+8、×3、×7、-4、÷2)を何度でも必要な回数だけ使って、与えられた初期値(2, 5,8など)をゴールの数字(73)にするというゲームを考える。例えば2から始めると、

経路(1) 2×3=6 → 6+5=11 → 11×7=77 → 77-4=73

と4回の演算でゴールの73になる。この他にも5回の演算でゴールになる

経路(2) 2×3=6 → 6÷2=3 → 3+8=11 → 11×7=77 → 77-4=73

や、6回の演算でゴールになる

経路(3) 2×3=6 → 6÷2=3 → 3×3=9 → 9×7=63 → 63+5=68 → 68+5=73

経路(4) 2×3=6 → 6÷2=3 → 3×7=21 → 21×3=63 → 63+5=68 → 68+5=73

なども答えになる。これらの経路をばらばらに書くと関連性がわかりにくい。しかし図1のように数字の変化(状態遷移という) をグラフにすると、経路(2)は経路(1)の途中から3に寄り道してまた戻るために1回多くなっていること、 最後の2つの経路は×3と×7の順番が入れ替わっていることなど、関連性が一目瞭然である。

この例のグラフは、エッジの流れが完全に一方向になっているのでレイアウトしやすい。すべての経路の出発点であるノード「2」 と終点であるノード「73」を両端にして、その間を結ぶように経路を表示すればよい。一度そのレイアウトをしておいて、終点ノード「73」 に最短で何回エッジをたどればよいかという観点でノードをグループに分けると、「68、77」は1回、「11、63」は2回、「3、6、9、 21」は3回、「2」は4回となる。そのグループごとにノードが並ぶようにレイアウトを少し修正すると、図2のように初期値の「2」 から始めてゴールの「73」に近づいていく様子がよくわかるようになる。この場合、何回エッジを通るとゴールの「73」に到達するかを、 グラフ上の距離と呼んでいる。

グラフの構造を扱うグラフ理論は、ネットワークの信頼性や生産工程の計画、流通コストの配分など様々な分野に応用されている。 そのグラフ理論の基本概念の一つが上記の距離である。その他の重要な概念として切断点というものがあり、 これはある1つのノードを取り除くとグラフが2つ以上の部分に切り離されてしまうような点である。 また同時に取り除くとグラフが切り離されてしまうような点の集合をカットセットという。 切断点やカットセットはそこを通らないとグラフ内の一方から他方に移動できないため、ボトルネックの原因になる重要な点である。 このような特徴のある箇所が見分けやすいようなレイアウトにすることも応用的に大事である。

グラフがもっと複雑になった場合はどうなるだろうか。例えば「4回以内の演算でゴールの73に到着できるすべての数」であれば、 そのような数が全部で172、ゴールに至る経路を表すには304のエッジが必要になる。このように大きくなってくると、 最初にツールを使って自動的にレイアウトをして、それから必要に応じて手で修正する方が手際がよくなる。 大規模な有向グラフのレイアウトを扱えるツールとして、AT&T研究所が開発してオープンソースになっているGraphVizを使い、 上記の問題のグラフを自動的にレイアウトしたものが図3である。ここでは図が込み入っているので、エッジにラベルをつける代わりに、 演算ごとに違う色で区別している。

GraphVisもレイアウトの際には距離の考え方を使い、入っていくエッジがないような根元に相当するノードを最初に探して、 そこからの距離が同じノード同士を一緒に並べていくという手順を取っている。 ただ大規模になるとどうしても一周して戻ってくるようなループができるので、それらを仮に切り離すなどの操作を内部でしている。 また同じノードの配置でもエッジの交差が少なくなるようにするなど、いくつものルールを使っている。 実は接続グラフを描く決定的なアルゴリズムはなく、それ自体が研究分野になっている程なのだが、 我々としてはツールを通してその成果を利用しつつ、試行錯誤を含めて応用上有用なグラフを作っていくということになるようである。


図1:単純なレイアウトfig1-simple

 

 

 

 

図2:ゴールからの距離が同じノードの位置を揃えたレイアウトfig2-aligned

 

 

 

 

 

 

 

 

図3:「4回以内の演算でゴールの73に到着できるすべての数」のレイアウト
fig3-distance4