Basic Functionality

Generate an acyclic random graph

This example shows how to generate a random graph, make it acyclic by removing edges, and then store it as a GML file.

#include <ogdf/basic/Graph.h>
#include <ogdf/basic/graph_generators.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/layered/DfsAcyclicSubgraph.h>
#include <string>
 
using namespace ogdf;
 
int main()
{
    Graph G;
    randomSimpleGraph(G, 10, 20);
 
    DfsAcyclicSubgraph DAS;
    DAS.callAndReverse(G);
 
    GraphIO::write(G, "output-acyclic-graph.gml", GraphIO::writeGML);
 
    return 0;
}

Step-by-step explanation

1. We first have to include all header files declaring the classes and functions we want to use. OGDF's header files are contained in subdirectories of a common include directory ogdf.
2. We make use of ogdf::Graph, a class that represents the most basic features of a graph: nodes, edges and their adjacencies and nothing more (no weights, markers etc.). ogdf::Graph uses an adjacency list and is able to store directed multigraphs. Depending on the application, an ogdf::Graph may be simple and/or interpreted as undirected.
3. For now we will settle for a simple graph that we generate randomly using ogdf::randomSimpleGraph(). Other generators can be found in graph_generators.h and—like ogdf::randomSimpleGraph()—for the most part take the desired number of nodes and edges as input. As with virtually any function in the OGDF, the resulting graph is provided by a passed reference instead of a return value.
4. We then make use of an instance of the algorithm class ogdf::DfsAcyclicSubgraph which we call on G to make it acyclic by removing some of its edges.
5. Finally the resulting graph (i.e. its nodes and edges) is written to a file using ogdf::GraphIO::write. We specify the desired output format (GML) by passing it the correct writer function ogdf::GraphIO::writeGML.

Manual creation and layout of graphs

This example shows how to manually create a basic ogdf::Graph together with a drawing of this graph that is stored in an instance of ogdf::GraphAttributes.

#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/geometry.h>
#include <ogdf/fileformats/GraphIO.h>
#include <string>
 
using namespace ogdf;
 
int main()
{
    Graph G;
    GraphAttributes GA(G,
      GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics);
 
    const int LEN = 11;
    for(int i = 1; i < LEN; ++i) {
        node left = G.newNode();
        GA.x(left) = -5*(i+1);
        GA.y(left) = -20*i;
        GA.width(left) = 10*(i+1);
        GA.height(left) = 15;
 
        node bottom = G.newNode();
        GA.x(bottom) = 20*(LEN-i);
        GA.y(bottom) = 5*(LEN+1-i);
        GA.width(bottom) = 15;
        GA.height(bottom) = 10*(LEN+1-i);
 
        edge e = G.newEdge(left,bottom);
        DPolyline &p = GA.bends(e);
        p.pushBack(DPoint(10,-20*i));
        p.pushBack(DPoint(20*(LEN-i),-10));
    }
 
    GraphIO::write(GA, "output-manual.gml", GraphIO::writeGML);
    GraphIO::write(GA, "output-manual.svg", GraphIO::drawSVG);
 
    return 0;
}

Step-by-step explanation

1. Here, we show an exemplary use of ogdf::GraphAttributes. By associating GA with G we have a way of adding attributes to G without actually modifying it. Note that in order to use an attribute (i.e. the corresponding getters and setters) it must first be enabled. This can be done by passing the respective bitflags to the constructor or calling ogdf::GraphAttributes::addAttributes(). For an explanation of all the available flags and what they do, check the static member variables of ogdf::GraphAttributes.
2. We continue by adding some nodes and edges to the graph in a loop:
   1. ogdf::Graph::newNode() returns a handle of the newly created node which can then be used to retrieve and edit its attributes, in this case setting its 2D coordinates as well as its width and height. We can access these attributes because we enabled them before with the flag ogdf::GraphAttributes::nodeGraphics.
   2. Once we have two of those node handles we can create an edge connecting them. Recall that in the OGDF, every edge is directed and in case of undirected graphs, we simply provide an arbitrary orientation to ogdf::Graph::newEdge().
   3. Once again we retrieve a handle of the newly created edge and use it to edit its graphical representation stored in GA. We do this by adding two ogdf::DPoint to the ogdf::DPolyline representing the edge's bend points. Again, we are able to access those because we enabled ogdf::GraphAttributes::edgeGraphics beforehand.
3. After graph creation is finished we once again want to store the result. This time we have more information to store than our ogdf::Graph G contains, so we pass the ogdf::GraphAttributes GA instead. The specified output function ogdf::GraphIO::writeGML will automatically handle any enabled attribute.
4. Finally we use the same interface to output a visualization of the graph in SVG format.

Planarizing a graph

This example shows how to planarize a given graph by computing a drawing with few crossings and replacing theses crossings with new nodes.

#include <ogdf/basic/Graph.h>
#include <ogdf/basic/graph_generators.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/planarity/PlanRep.h>
#include <ogdf/planarity/PlanarSubgraphFast.h>
#include <ogdf/planarity/SubgraphPlanarizer.h>
#include <ogdf/planarity/VariableEmbeddingInserter.h>
#include <iostream>
#include <string>
 
using namespace ogdf;
 
int main()
{
    Graph G;
    randomSimpleGraph(G, 100, 150);
 
    SubgraphPlanarizer SP;
    SP.setSubgraph(new PlanarSubgraphFast<int>);
    SP.setInserter(new VariableEmbeddingInserter);
 
    int crossNum;
    PlanRep PR(G);
    SP.call(PR, 0, crossNum);
 
    std::cout << crossNum << " crossings" << std::endl;
    GraphIO::write(PR, "output-plan.gml", GraphIO::writeGML);
 
    return 0;
}

Step-by-step explanation

1. We randomly generate a simple graph.
2. Just like most algorithms in the ogdf library ogdf::SubgraphPlanarizer is modular and is configured by first creating an instance, and then passing it dynamically allocated configuration modules that derive from a base module class to overwrite the default settings for the algorithm. In this case we pass it:
   1. An ogdf::PlanarSubgraphModule which determines the way a planar subgraph is computed in the first phase of the planarization algorithm. We use ogdf::PlanarSubgraphFast for this.
   2. An ogdf::EdgeInsertionModule which determines how the remaining edges get inserted into the subgraph. We use ogdf::VariableEmbeddingInserter for this.
3. Next we create an ogdf::PlanRep, that is, a planar representation that will hold the result of the algorithm. It will contain dummy vertices with degree 4 at any remaining crossings.
4. After running the algorithm we output the number of remaining crossings to the console and conclude by saving the planar representation to a .gml file.