Open Graph Drawing Framework
current version:
v.2015.05 (Baobab)
     

Hierarchical Layout with Predefined Layering

Topic

Load a graph from a GML file, apply Sugiyama Layout with given layer for each node, and write the graph with layout information back to a file.

Source-Code

#include <ogdf/layered/SugiyamaLayout.h>
#include <ogdf/layered/MedianHeuristic.h>
#include <ogdf/layered/OptimalHierarchyLayout.h>
#include <ogdf/fileformats/GraphIO.h>
 
using namespace ogdf;
 
int r[] = {
	0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 10, 10, 11, 12, 12,
	13, 14, 14, 15, 16, 17, 18, 18, 19, 19, 20, 21, 22, 22,
	22, 23, 23, 23, 23, 24, 25, 26, 27, 27, 27, 28, 29, 29,
	29, 30, 30, 31, 31, 31, 32, 33, 33, 34, 34, 35, 35, 35,
	35, 0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18,
	19, 20, 21, 22, 23, 25, 27, 29, 30, 31, 32, 33, 34, 35, -1
};
 
int main()
{
	Graph G;
	GraphAttributes GA(G,
	  GraphAttributes::nodeGraphics |
	  GraphAttributes::edgeGraphics |
	  GraphAttributes::nodeLabel |
	  GraphAttributes::edgeStyle |
	  GraphAttributes::nodeStyle |
	  GraphAttributes::nodeTemplate);
	if (!GraphIO::readGML(GA, G, "unix-history-time.gml") ) {
		cerr << "Could not load unix-history-time.gml" << endl;
		return 1;
	}
 
	NodeArray<int> rank(G);
	int i = 0;
	node v;
	forall_nodes(v,G)
		rank[v] = r[i++];
 
	SugiyamaLayout SL;
	SL.setCrossMin(new MedianHeuristic);
	SL.arrangeCCs(false);
 
	OptimalHierarchyLayout *ohl = new OptimalHierarchyLayout;
	ohl->layerDistance(30.0);
	ohl->nodeDistance(25.0);
	ohl->weightBalancing(0.7);
	SL.setLayout(ohl);
 
	SL.call(GA, rank);
	GraphIO::writeGML(GA, "unix-history-time-layout.gml");
 
	return 0;
}

Example graph: unix-history-time.gml

Explanation

This example is similar to the Hierarchical Layout example, with the difference that we predefine on which layer each node lies. We start by defining an array r of ranks for each node. Then we declare a Graph G with GraphAttributes GA storing the layout information of the graph, and load the graph from GML file unix-history-time.gml; we also check if loading was successful and exit in the unsuccessful case.

In the next step, we need to create a node array defining the nodes' ranks. The ranks that we stored in the global array r are in the same order as the corresponding nodes in the GML file, so that we can simply iterate over all nodes v and assign the rank r[i] to rank[v].

Since we want to call the Sugiyama layout algorithm, we declare an instance SL of SugiyamaLayout and set some parameter. We set the two-layer crossing minimization heuristic to MedianHeuristic (the default BarycenterHeuristic would also do). The next option is important for our example. The graph we want to lay out consists of several connected components and the rank of a node corresponds to a certain time (year); one of the connected components is in fact the time-line. Hence, it is important that all nodes with the same rank are on the same horizontal line, even if they are in different connected components. The default setting of arrangeCCs is true, which means each connected component is laid out separately and the resulting drawings are arranged afterwards using a packing algorithm. Therefore, we need to change it to false.

Finally, we create a new instance of OptimalHierarchyLayout and set the desired spacing values. Observe, that we first create an instance of the hierarchy layout module, then set the spacing parameters in this module, and finally pass it as module option to SL. For each module option holds that the passed module has to be allocated by new and is not deleted by the user (it will be deleted by the module option itself if a new module is set or the destructor of the module option is called).

Now we are ready to call Sugiyama layout. We choose the call method with the additional parameter for the node ranks, and write the resulting layout back to the file unix-history-time-layout.gml. The resulting output is also shown below as images.

Output

Graph layout:
unix-history-time-layout.gml

Drawing:
unix-history-time-layout.svg

 
tech/howto/hierlr.txt · Last modified: 2015/05/31 16:53 by stephan
This page is driven by DokuWiki