图层次布局算法 [英] Graph Hierarchical Layout Algorithm

问题描述

有许多工具和SDK可以布置图形. ogdf，GraphViz，mxGraph，yEd ...

There are many tools and SDKs which layout a graph. ogdf, GraphViz, mxGraph, yEd...

有用的布局之一是分层布局".但是，没有纯算法或伪代码来描述它.甚至，对于这种类型的布局也没有明确的定义.有人知道该算法吗?

One of useful layouts is "Hierarchical Layout". But there is no pure algorithm or pseudo code to describe it. Even, There is not a clear definition of this type of layout. Is anyone know about the algorithm?

推荐答案

_{(来源: yworks. com )}

_{(source: yworks.com)}

简单的分层布局算法是ASAP调度算法的可视化(请查看本讲座

Simple hierarchical layout algorithm is visualisation of the ASAP sheduling algorithm (check this lecture [link]), so it'd be better to read it, on my view.

顺便说一句，您的图片并不完全正确-建议的可视化效果只是其中一种可能.

BTW your picture is not fully correct - the proposed visualisation is only one of the possible ones.

想象一下，您拥有节点列表，并且知道它们之间的依赖关系.

Imagine, that you have list of node and you know dependence between them.

节点列表

node4
node2
node5
node1
node3
node6

依赖列表

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

• 第一步，您应该找到没有依赖关系的节点-这 将是您的layer#1节点.画出来.
• 然后找到所有依赖于第1层节点的节点-这将是您的第2层节点.

• 与第二层等相同. 最后，您将获得:

  • As your first step, you should find nodes with no dependance - this would be your layer#1 nodes. Draw them.
  • Then find all nodes that depends on layer#1 nodes - this would be your layer#2 nodes.

  • And the same thing for the layer#2 and etc. Finally, you'll get:

             node1
            /     \
          node2  node3
           /     /   \
        node4 node5 node6
    

  这仅适用于非循环有向图.对于非定向算法，您应该稍作修改(以随机节点为根)，但是我认为主要思想是可以理解的.

  This will work only for non-cyclic directed graphs. For the undirected ones you should modify the algorithm a bit (take random node as root), but the main idea, I think, is understandable.

  这篇关于图层次布局算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！