c# - グラフ階層レイアウトアルゴリズム

Question

グラフをレイアウトするツールやSDKはたくさんあります。ogdf、GraphViz、mxGraph、yEd ..

便利なレイアウトの1つは、「階層レイアウト」です。しかし、それを説明するための純粋なアルゴリズムや擬似コードはありません。でも、このタイプのレイアウトの明確な定義はありません。誰かがアルゴリズムについて知っていますか？

Answer 1

_{(出典: yworks.com )}

単純な階層レイアウト アルゴリズムは、ASAP スケジューリング アルゴリズム (この講義[リンク]を参照) を視覚化したものなので、それを読んだほうがよいと思います。

ところで、あなたの写真は完全に正しいわけではありません - 提案された視覚化は可能なものの1つにすぎません。

ノードのリストがあり、それらの間の依存関係を知っていると想像してください。

ノードリスト

node4
node2
node5
node1
node3
node6

依存リスト

node1 -> node2
node2 -> node4
node3 -> node5
node1 -> node3
node3 -> node6

• 最初のステップとして、依存関係のないノードを見つける必要があります。これがレイヤー#1 ノードになります。それらを描きます。
• 次に、レイヤー#1 ノードに依存するすべてのノードを見つけます。これがレイヤー#2 ノードになります。

• レイヤー＃2などについても同じです。最終的に、次のようになります。

           node1
          /     \
        node2  node3
         /     /   \
      node4 node5 node6
  

これは、非巡回有向グラフに対してのみ機能します。無向のものについては、アルゴリズムを少し変更する必要があります (ランダムノードをルートとして使用します) が、主なアイデアは理解できると思います。