Graphvizドットアルゴリズム

Question

Graphvizライブラリ内のドットからアルゴリズムに関する文書（完全な疑似コード？）はありますか？

部分疑似コードの一部のドキュメントしか見つかりませんでした。

Answer 1

ここにあなたの参考資料がいくつかあります。最も完全な（ドットソースコードそのものの短い）ものはおそらく＃2であり、これはGraphizの貢献者自身によって書かれた論文「描画指向技術」です。

（1）Drawing graphs with dotで

"ドットとのグラフを描く"、ドットのレイアウトアルゴリズムは次のように記載されている：

ドットは4つの主なフェーズでグラフを描きます。これを知ることで、どのようなレイアウトのドットが作成され、どのようにドットを制御できるかを理解するのに役立ちます。ドットによって使用されるレイアウト手順は、グラフが非周期的であることに依存する。したがって、第1のステップは、ある周期的なエッジの内部方向を反転させることによって、入力グラフ内に生じる任意のサイクルを壊すことである。次のステップでは、ノードを個別のランクまたはレベルに割り当てます。上から下の図では、ランクによってY座標が決定されます。複数のランクにまたがるエッジは、「仮想」ノードおよび単位長の辺のチェーンに分割されます。第3のステップは、交差を回避するためにランク内のノードを順序付ける。第4ステップでは、ノードのX座標を設定してエッジを短くし、最後のステップでエッジスプラインをルーティングします。これはWarfield [War77]、Carpano [Car80]、Sugiyama [STT81]の作業に基づいて、ほとんどの階層グラフ描画プログラムと同じ一般的なアプローチです。我々は[GKNV93】ドットのアルゴリズムの完全な説明のために

を読者に参照し、その段落で引用した論文は、これらは、次のとおり

• [Car80] M. Carpano。コンピュータ支援決定分析のための階層化されたグラフの自動表示。ソフトウェア工学に関するIEEEトランザクション、SE-12（4）：（。購入hereのため明らかに利用可能）538から546まで、4月1980年は

• [GKNV93]エムデンR. Gansner、エレフテリオスKoutsofios、スティーブン・C.北、およびKiem-Phong Vo。指向グラフを描く技術。 IEEE Trans。 （Graphviz.orgサイトでhereが利用可能）。

• [STT81] K.杉山、田川、および戸田。階層的システム構造の視覚的理解のための方法。 SMC-11（2）：109-125、1981年2月のIEEEトランザクション。here

• [War77] John Warfield。システム、人およびサイバネティックスのIEEEトランザクション、交差理論と階層マッピング。 IEEEトランザクションシステム、人、およびサイバネティクスに、SMC-7（7）：505から523、7月1977年には（購入hereについて明らかに利用できる。）

（2） "描画有向グラフのための技術"

ドットのアルゴリズムは、（Graphviz.orgサイト上で無料で、利用可能な）1993年にソフトウェアエンジニアリングにジャーナルIEEEトランザクションに掲載された論文"A Technique for Drawing Directed Graphs"、に詳細に記載されています。上記の「[GKNV93]」のソースです。

抽象的には、それは価値がある何のために、これは次のようになります。

私たちは、有向グラフを描くための4つのパスアルゴリズムを記述します。第1のパスは、ネットワークシンプレックスアルゴリズムを使用して最適なランク割り当てを見つける。第2のパスは、交差点を減少させるために、新しい重み関数と局所的な転置とを組み入れた反復ヒューリスティックによってランク内の頂点順序を設定する。第3パスでは、補助グラフを作成してランク付けすることにより、ノードの最適座標が求められます。 4番目のパスはスプラインでエッジを描きます。このアルゴリズムは優れた描画を行い、高速で実行されます。

（3） "ライブラリとしてGraphvizのを使う"

"Using Graphviz as a Library" 3.1節内の各レイアウトエンジンの的アルゴリズムの概要を提供します。ドットの説明の一部は、次のとおりです。

ドットアルゴリズムは、可能であれば、エッジ方向を考慮したグラフのランク付けされたレイアウトを生成します。これは、階層または有向非循環グラフを表示するのに特に適しています。基本的なレイアウトスキームは、Sugiyamaら[STT81]によるものである。ドットによって使用される特定のアルゴリズムは、Gansnerら[GKNV93]によって記述されたステップに従う[GKNV93]

ドットレイアウトのステップは、1） 3）最小交差4）位置5）同一ポート6）スプライン7）compoundEdges

初期化後、アルゴリズムは整数プログラムを使用して離散階数（階数）に各ノードを割り当てて、離散エッジ長の合計を最小限に抑えます。次のステップ（mincross）は、エッジ交差を減らすためにランク内のノードを再配置します。これに続いて、実際の座標のノードへの割り当て（位置）があり、別の整数プログラムを使用してグラフを圧縮し、エッジをまっすぐにします。この時点で、すべてのノードはcoord属性に設定された位置になります。さらに、すべてのクラスタのバウンディングボックスbb属性が設定されます。

「[GKNV93]」の参照は、上にリンクされているように、「描画されたグラフを描く技術」です。

「[STT81]」の参照は、上記の「階層型システム構造の視覚的理解のための方法」です。

（4）また、に興味があるかもしれない：

• Graphviz's Documentation Index、詳細なマニュアルおよびその他の背景資料へのリンクを持っています。

• Graphviz's "Theory" pageさらに多くの背景資料にリンクしています。

• raw source code for dotは、GitHubで利用可能です。

• d3.js Google Groupに関するいくつかの関連する議論。