グラフ自動レイアウトアルゴリズム
1. 概要
このチュートリアルでは、グラフのレイアウトを設計するためのさまざまな手法を学習します。
まず、グラフを描くときに方向付ける必要のある便利さと美学のさまざまな原則について説明します。 次に、それらの代替表現のいくつかの可能なレイアウトを確認します。
最後に、平面内のグラフの自動レイアウトのための2つのアルゴリズムについても学習します。
このチュートリアルの最後では、グラフのレイアウトを設計するための基準に精通し、グラフを自動的に描画する方法を理解します。
2. 平面上のグラフの表現
2.1. 表現、人間の知覚、および意味
グラフの表現の問題は、画像は、人間の知覚では、理解を生み出すために解釈されなければならないという考えに関連しています。 画像自体は、実世界のオブジェクトに対する抽象的な表現であり、これにより、観察者はそれらのオブジェクトを頭に浮かび上がらせることができます。
しかし、それらの本質的な変動性のために、同じ現実世界のオブジェクトを表す異なる画像は、読者の心に異なる精神的なオブジェクトを呼び起こす可能性があります。 したがって、画像を実世界のオブジェクトへのマップとしてフレーム化すると、複数の画像が同じ現実にマップできるため、このマップは全射であると言えます。
これは、「地図は領土ではない」という古いアダージョの意味です。 この考慮事項をグラフに拡張したい場合は、「画像はグラフではなく、領域ではない」などの式を使用して行うことができます。
グラフを頂点のセットとエッジのセットとして表現できることがわかっています。 また、エッジリスト、隣接行列、隣接リストなど、それらの複数の正式な表現が存在することもわかっています。 この紹介セクションでは、次の隣接リストを含むサンプル有向グラフを使用します。
特に指定がない限り、エッジリストは変更されません。 同じグラフをさまざまな方法で表現する方法と、それに割り当てた解釈の結果はすぐにわかります。
2.2. しかし、それは単なるグラフです！
ただし、先ほど提示した概念フレームワークにも同意できない場合があります。 実際、グラフの任意の表現は、同じグラフの他の表現と同じくらい有益であると素朴に主張することができます。
これは、人間の知覚システムのナイーブリアリズムと呼ばれる理論です。 理論によれば、知覚の対象に関係なく、人間は予備処理や優先バイアスなしですぐにそれを理解します。
理論はまた、その後、任意の2人の人間が同じオブジェクトを知覚すると同じ理解を得るであろうことを意味します。
ただし、この理論は、理論的推論を通じて、また経験的にはグラフやチャートに関連して、すでに改ざんされています。 これはまた、平面上にグラフを描く場合、実際に使用する手法が重要であり、方法が異なれば読者との理解も異なることを意味します。
3. 幾何学的制約
3.1. これらの制約は何ですか？
グラフの表現は、まず第一に、グラフに課すことを決定した幾何学的制約によって制限されます。 これは、いかなる種類の制約も選択しなかった場合、可能な表現が無限に存在し、それぞれがエッジとノードの位置の特定の組み合わせに対応するためです。 代わりに、ある種の制限を適用する場合、その制約を考慮してグラフを最もよく強化する可能な表現の1つを選択できます。
複数のタイプの制約が存在します。 それらのいくつかは、グラフが占める水平方向または垂直方向のスペースの最小化に関連しています。 他のいくつか、総表面積の最小化に。
ただし、最も興味深いのは、エッジの配置または形状の制限に関するものです。 したがって、前のセクションで示したサンプルグラフに関して、エッジにどのクラスの幾何学的制約が存在するかを調べることができます。
3.2. 平面直線グラフ
以下では、制約がより直感的に理解できるため、平面グラフについてのみ説明します。 これらは、頂点とエッジがすべて同じ2次元平面にあり、それらのエッジが互いに交差しないグラフです。
私たちが課す最初の制限は、すべてのエッジが頂点間の直線セグメントを構成することです。
このタイプの表現は、平面直線描画の名前を取ります。 このタイプのグラフは、頂点が描画面の同じ領域に配置されるため、頂点間のサイクルの識別を簡素化します。
3.3. 直交グラフ
また、すべての線、エッジ、またはその一部が他の線と直交または平行でなければならないという制約を課すこともできます。
この表現は直交描画の名前を取ります。 直交グラフは、頂点への入射エッジの数を数えるのが非常に簡単であるため、各頂点の次数を強調表示します。 それらの主な制限は、少なくとも1つの頂点に次数がある場合、グラフを直交として表すことができないことです。
3.4. 直交および直線
同時に、直交性に準拠し、直線であるエッジを持つグラフを描くこともできます。 使用している特定のグラフではこの表現が許可されていないため、今回は最初のノードから2つのエッジを削除します。
このグラフは、平面直交直線グラフの名前を取ります。 この手法は、グラフのエッジによってバインドされる有限のサーフェスに対応するグラフの面の重要性を強調します。これには、グラフのエッジを囲む無限のサーフェスも含まれます。
3.5. 上向きのフローグラフ
頂点間の方向性のある流れを強調する方法でグラフを表すこともできます。
エッジの流れが上向きであることを考えると、グラフは上向き平面グラフの名前になります。 これらは、組織の階層を表すためによく使用されるため、文献では階層ネットワークと呼ばれることもあります。 ただし、階層ネットワークはスケールフリープロパティを持つネットワークであり、上向きのグラフには必ずしも含まれないため、これは誤った呼び方です。
3.6. 非平面グラフの制約
ここで見たものは、どのグラフ構造に従うかについての決定を方向付けるために使用する主要な幾何学的制約です。 これらの例に平面グラフを使用するという決定は、単に説明の目的であり、非平面グラフは同じタイプの制約を共有できることに注意してください。 ただし、その場合、グラフは2次元平面ではなく、超曲面で表す必要があります。
興味深いことに、3D空間の直交直線グラフでは、任意の頂点への最大数の入射エッジが6に等しくなります。 これは、グラフの頂点に最大入射エッジが4つ以上7つ未満の場合、それを3D直交直線グラフとして表すことを検討できることを意味します。
4. グラフ表現の美的基準
4.1. 美学とは何ですか？
また、特定の制約を考慮して、使用する特定の構成を決定するための基準も必要です。 これらの基準は、美的という名前が付けられています。これは、グラフ表現は単なる検証ではなく、知覚者の目の美しさの感覚にも訴える必要があるという考えに関連しているためです 。
美的基準は、上で説明した幾何学的制約とともに、別の表現ではなく特定の表現を決定するようになります。
4.2. エッジ交差の最小化
最初の美的基準は、エッジ間の交差の数を最小化することです。 この基準は、同じグラフに対して複数の表現が可能である場合、読みやすくするために、交差が最も少ない表現を選択する必要があることを示しています。
この場合、右側の表現が私たちが好むものです。
4.3. グラフ領域の最小化
2番目の基準は、グラフが占める領域の最小化です。 グラフの読みやすさとその表面積のコンパクトさの間には必要なトレードオフがあるため、この基準の適用に関してはある程度の柔軟性があります。
この例を見てみましょう：
これらのグラフは同等です。 右側のものは不必要に大きすぎる表面を占めていますが、中央のものは、特に私たちの読者が視力の病状を持っている場合、読みにくいかもしれません。 代わりに、左側のグラフは、領域の最小化と読みやすさの中間にあります。
4.4. ベンドの最小化
3番目の基準は、直交グラフのエッジの曲がりの最小化に関するものです。曲がりは、原則として、任意の数に増やすことができます：
ただし、この基準は、グラフを描画するために必要な最小限のに代わりにそれらを維持することを示唆しています。
4.5. 最小角度の最大化
次の基準は、グラフの任意の2つのエッジの間にある最小の角度をできるだけ大きくする必要があることを示しています。 次数4のこのグラフを調べてみましょう。
この場合、最小の角度は、2つのエッジの間、または同等にとの間で構成される角度です。 この角度は、頂点を適切に再配置することで拡張できます。
なぜなら、これはこの美的基準に関連して2番目の表現を好ましいものにするからです。
4.6. 示されている対称性の最大化
最後の基準は、グラフに存在する対称性の最大数の表示で構成されます。 この例を見てみましょう：
この写真は、エッジの交差が重なっていないことを示しているため、エッジの交差を最小限に抑えるという美的基準を尊重しています。 また、グラフが埋め込まれている正三角形の中央値である3つの対称軸も表示されます。
ただし、頂点を正方形の形に再配置すると、対称軸を4つに増やすことができます。
この最後の基準によれば、2番目の図面が最初の図面よりも好ましいはずです。 この段落で例示されているように、複数の基準を同時に尊重することが常に可能であるとは限らないことに注意してください。 結果として、グラフの表現において複数の美的基準が重要である場合は常に、それらの一部のみを使用するかどうかを選択するよう求められることがあります。
5. 自動レイアウトのアルゴリズム
幾何学的制約と美的基準を研究したので、それらの制約と特定した基準を前提として、平面上のノードの配置を自動化するアルゴリズムを見つけることができます。 これらのアルゴリズムは、大まかに次のカテゴリに分類されます。
ここでは、これらのクラスのアルゴリズムの最初の3つを学習します。
5.1. 二分木の再帰的アルゴリズム
描画しているグラフが二分木である場合、再帰的アルゴリズムを使用して、ノードを水平レイヤーに配置することができます。
これは、そのアルゴリズムによって生成されたツリーの例です。
5.2. 力ベースのアルゴリズム
グラフの一般的なクラスでは、代わりに力ベースの手法を使用できます。 これらは、グラフのエッジが頂点を引っ張ることができるバネとして機能するという考えに基づいています。 次に、グラフ表現は、利用可能な位置エネルギーを最小化するものです。
物理学では、スプリングは弾性材料であり、平衡長を持ち、圧縮または伸長すると、その変形に比例した力を発揮します。 グラフ理論では、エッジは平衡長がゼロのばねであり、その長さに比例する力を及ぼすと想像できます：
したがって、各頂点は、そのエッジの長さに依存する一連の力を受けると想像できます。 次に、頂点はこれらの力の組み合わせから生じる方向に移動します。 一部の頂点の位置を制限すると、システムを動的シミュレーションとして実行できます。
この場合、たとえば、頂点2と3を修正し、頂点1を移動します。
5.3. ベンドの最小化とネットワークフロー
グラフのレイアウトを直交グラフに変更するために使用できるもう1つのアルゴリズムは、いわゆるベンド最小化アルゴリズムです。 まず、平面グラフから始めます。
次に、それを高視認性フォームに変換します。これは、頂点を平行な水平線に変換することで構成されます。
次に、各頂点を対応する線の任意の場所に配置し、余分な線を曲がったエッジに置き換えます。
最後に、ベンドを伸ばして最小化することができます。
頂点の位置をデカルト平面の整数座標に制約すると、このアルゴリズムは時間内に計算できます。
6. 結論
この記事では、図面のグラフのレイアウトの背後にある原理を研究しました。
