7

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?

masoud
  • 55,379
  • 16
  • 141
  • 208

1 Answers1

12

enter image description here
(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.

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
Evgeny Gavrin
  • 7,627
  • 1
  • 22
  • 27
  • I check for cycles first with a modified Depth First Search (DFS), e.g. https://www.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). – B--rian Jan 02 '20 at 20:06