Geek Answers Handbook

Graph hierarchical algorithm

There are many tools and SDKs that make up a chart. ogdf, GraphViz, mxGraph, yEd ...

enter image description here

One useful layout is Hierarchical Layout. But there is no pure algorithm or pseudocode to describe it. Even, there is no clear definition of this type of layout. Does anyone know about an algorithm?

+4
source share
1 answer

enter image description here
(source: yworks.com )

The simple hierarchical layout algorithm is a visualization of the ASAP scheduling algorithm (see this lecture [link] ), so it would be better to read it, in my opinion.

By the way, your picture is not entirely correct - the proposed visualization is only one of the possible ones.

Imagine that you have a list of nodes and you know the relationship between them.

List of nodes

node4 node2 node5 node1 node3 node6

Dependency list

 node1 -> node2 node2 -> node4 node3 -> node5 node1 -> node3 node3 -> node6
  • As a first step, you should find the nodes without dependency - this will be your # 1 layers of nodes. Draw them.
  • Then find all the nodes that depend on the level 1 nodes - these will be your level 2 nodes.

  • And the same for layer number 2, etc. Finally you get:

      node1 / \ node2 node3 / / \ node4 node5 node6

This will only work for non-cyclic directed graphs. For non-oriented ones, you need to slightly change the algorithm (take a random node as root), but the main idea, I think, is understandable.

+10
source

More articles:


All Articles