グラフとは、リンクの集合で
接続されたエンティティー (ノードと呼ばれます) の集合を表すデータ構造です。ノードは頂点と
呼ばれることもあります。リンクはエッジまたは接続
とも呼ばれます。実際のアプリケーションでは、
コンピューター・ネットワーク、ソフトウェア・プログラム構造、プロジェクト管理図など、
さまざまなものをモデル化するためにグラフがよく使用されます。グラフ理論研究の成果を
アプリケーションで利用できるため、
グラフは強力なモデルです。例えば、2 個のノード間の最短パスを
見つけるものや、最小コストのパスを見つけるものなど、効率的な
さまざまなメソッドが利用可能です。
グラフのレイアウト
グラフ・レイアウトは、グラフ・モデルを表示する必要のあるアプリケーションの
グラフィカル・ユーザー・インターフェースにおいて使用されます。グラフをレイアウトするという
ことは、適切で読みやすい表示が生成されるようにグラフを
描画することを意味します。そのためには、基本的に、ノードの位置と
リンクの形状を決定することが必要です。アプリケーションによっては、
ノードの位置が既に分かっています (例えば、ノードの地理的な位置に
基づいている場合など)。 また他のアプリケーションでは、
位置が不明であるか (純粋な「論理的」グラフ)、あるいは使用しても、
既知の位置は判読できないグラフを描画することになります。このような場合は、
ノードの位置を計算する必要があります。
グラフの「適切な」描画とは何を意味する
のでしょうか? 実際のアプリケーションではよくあることですが、
グラフ描画には一定の品質基準を順守する必要があります。これらの基準は、
アプリケーション分野によって、または、指定された表現の標準
によって変わります。優れたレイアウトがどういったものから構成されるのかを
一概に言うことは困難です。レイアウトを「優れている」と
認める主観的な基準は、ユーザーによって異なるでしょう。しかし、
すべての基準および標準に共通する 1 つの目標があります。
それは、描画は理解しやすく、グラフの複雑な構造の中を簡単に
ナビゲーションできるものでなければならないということです。
良いレイアウトとは?
さまざまなアプリケーションの多様なニーズに対応するため、
多数のグラフ・レイアウト・アルゴリズムのクラスが開発されました。グラフをレイアウトする際、
レイアウト・アルゴリズムは、そのアルゴリズムの機能およびグラフのタイプに
基づいて、1 つ以上の品質基準に対処します。
最も一般的な基準は、次のとおりです。
- リンク交差の数を最小化する
- 全体の描画領域を最小化する
- 曲折点の数を最小化する (直交描画の場合)
- 連続する付随リンクが形成する最小の角度を最大化する
- 表示の対称性を最大化する
レイアウト・アルゴリズムはこれらの品質基準および表現の標準
のそれぞれをどのように満足できるのでしょうか? 個々の基準を見てみると、
一部の基準は、少なくともいくつかのグラフのクラスでは、簡単に満たすことができます。他のクラスの場合は、基準を満たす描画を生成するのは難しいように思われます。例えば、
ツリー (すなわち、環状のないグラフ) の場合、リンク交差の数を最小化する
ことは、比較的単純です。しかし、一般的なグラフの場合、
リンク交差の数を最小化することは、数学的な NP 完全問題となります (すなわち、既知のすべてのアルゴリズムで、レイアウトを実行するのに要する時間はグラフのサイズとともに
長くなります)。
同時にいくつかの基準を満たしたくても、基準の多くは互いに
矛盾するため、個々の基準について個別の最適の解決策
は存在しない可能性があります。時間かかるトレードオフが
必要になることがあります。さらに、各基準に重みを
割り当てることも、簡単な作業ではありません。ほとんどの場合、複数基準の最適化
は、実装するにはあまりにも複雑であり、時間がかかりすぎます。これらの理由から、
レイアウト・アルゴリズムはヒューリスティックに基づくことが多く、1 つ以上の基準に
関して最善ではないソリューションを提供する場合もあります。
それでも、実際的には、レイアウト・アルゴリズムは多くの場合は適度に
読みやすい描画を提供します。
レイアウト・アルゴリズムを使用するためのメソッド
各種のアプリケーションにおいて、さまざまな方法でレイアウト・アルゴリズムを
使用できます。最も一般的なアルゴリズム使用方法は次のとおりです。
-
使用するレイアウト・アルゴリズムの選択だけは必要かもしれませんが、それ以外はユーザー介入なしで、 レイアウト・アルゴリズムがすべてを行います。場合によっては、レイアウトする特定タイプのグラフに 最も適したレイアウト・アルゴリズムを自動的 (かつ動的) に選択するための一連のルールを コーディングできます。
-
アプリケーション・ユーザーは、自動レイアウト・プロシージャーの結果を自由に 手作業で改善できます。場合によっては、この ユーザーは望みの位置にノードを移動し、固定した後で、レイアウトをもう一度実行 することができます。また、グラフの一部が自動的に「読み取り専用」に設定され、 ユーザーはレイアウトの残りの部分だけを変更できる場合もあります。
- 初めからの レイアウトレイアウト・アルゴリズム は、グラフが変更されるたびに完全に (「初めから」) やり直されます。
- インクリメンタル・レイアウトレイアウト・アルゴリズムは、 変更後のグラフに対して 2 回目に実行されるとき、 できるだけレイアウトの安定度を保持しようとします。レイアウトは最初からやり直される わけではありません。また、レイアウト・アルゴリズムは、初期ソリューションとして前のレイアウトを 使用することで CPU 時間を節約しようとします。 一部のレイアウト・アルゴリズムおよびレイアウト・スタイルは、本質的にインクリメンタルです。 それ以外の場合、インクリメンタル・レイアウトは不可能です。