Hierarchical Layout

Back to List of Examples

Load a graph from a GML file, apply customized Sugiyama Layout, and write the graph with layout information back to a file.

Requires: Coin Osi

#include <ogdf/layered/SugiyamaLayout.h>
#include <ogdf/layered/OptimalRanking.h>
#include <ogdf/layered/MedianHeuristic.h>
#include <ogdf/layered/OptimalHierarchyLayout.h>
 
using namespace ogdf;
 
int main()
{
    Graph G;
    GraphAttributes GA(G,
        GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics |
        GraphAttributes::nodeLabel | GraphAttributes::nodeColor | 
        GraphAttributes::edgeColor | GraphAttributes::edgeStyle | 
        GraphAttributes::nodeStyle | GraphAttributes::nodeTemplate);
    if( !GA.readGML(G,"unix-history.gml") ) {
        cerr << "Could not load unix-history.gml" << endl;
        return 1;
    }
 
    SugiyamaLayout SL;
    SL.setRanking(new OptimalRanking);
    SL.setCrossMin(new MedianHeuristic);
 
    OptimalHierarchyLayout *ohl = new OptimalHierarchyLayout;
    ohl->layerDistance(30.0);
    ohl->nodeDistance(25.0);
    ohl->weightBalancing(0.8);
    SL.setLayout(ohl);
 
    SL.call(GA);
    GA.writeGML("unix-history-layout.gml");
 
    return 0;
}

Example graph: unix-history.gml

We first declare a Graph G and load it from the GML-file unix-history.gml. The class Graph does not store a graph’s layout information; these information is maintained by GraphAttributes. Therefore, we generate an instance GA that holds the layout information of G. The constructor of GraphAttributes allows to select which attributes shall be stored. We decided to store various graphics attributes for nodes and edges; the example GML file contains a graph with format information.

We then create an instance SL of SugiyamaLayout that represents the Sugiyama Layout algorithm. This instance allows to customize each phase of the Sugiyama algorithm using module options. Initially, these options have default values, so it is not required to set these options; in our example, we customize all three module options.

SugiyamaLayout offers three module options corresponding to the three phases of the Sugiyama algorithm:

1. Ranking implements the layer assignment phase which assigns each node a layer. It requires a module of type RankingModule. By default, LongestPathRanking is used.
2. CrossMin implements two-layer crossing minimization and requires a module of type TwoLayerCrossMin. Such a module solves the two-layer crossing minimization problem with one layer fixed. The default is BarycenterHeuristic. Alternatives are MedianHeuristic and SplitHeuristic.
3. Layout implements the coordinate assignment phase which assigns each node its (x,y)-coordinates and determines the routing of edges. It requires a module of type HierarchyLayoutModule. The default is FastHierarchyLayout, an alternative is OptimalHierarchyLayout.

We set these module options to OptimalRanking, MedianHeuristic, and OptimalHierarchyLayout, respectively. Note, that both OptimalRanking and OptimalHierarchyLayout require that you have compiled OGDF with COIN support. Additionally, we set some options in the hierarchy layout module ohl, including minimum distance values. You should always adjust these values with respect to the nodes’ sizes.

The algorithm is then applied with SL.call(GA). The computed layout information is stored in GA, the graph G itself is not modified. Finally, we write the graph with its computed layout information to the GML-file unix-history-layout.gml.

Graph layout:
unix-history-layout.gml

Drawing: