Graph Hierarchical Layout Algorithm

Question

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

enter image description here

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?

Glorfindel · Accepted Answer · 2019-08-28 03:38:25Z

12

_{(source: yworks.com)}

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.

Node list

node4
node2
node5
node1
node3
node6

Dependency list

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

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.

edited Aug 28, 2019 at 3:38

Glorfindel

22.8k13 gold badges97 silver badges124 bronze badges

answered Dec 13, 2012 at 14:09

Evgeny Gavrin

7,8451 gold badge24 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

B--rian Over a year ago

I check for cycles first with a modified Depth First Search (DFS), e.g. geeksforgeeks.org/detect-cycle-in-a-graph As BPMN networks are likely to have a few cycles when gateways are involved, you may run a pruning algorithm before the DFS to ignore the flows from a gateway back to a previous activity for the layouting (only).

Collectives™ on Stack Overflow

Graph Hierarchical Layout Algorithm

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related