Graph Drawing

 v. 2020.02 (Catalpa)

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.

using namespace ogdf;
int main()
randomSimpleGraph(G, 10, 20);
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.

using namespace ogdf;
int main()
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);
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.

using namespace ogdf;
int main()
randomSimpleGraph(G, 100, 150);
int crossNum;
PlanRep PR(G);, 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.
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
Declaration of class VariablEmbeddingInserter.
Stores additional attributes of a graph (like layout information).
Definition: GraphAttributes.h:67
Declaration of class GraphAttributes which extends a Graph by additional attributes.
Declaration of graph generators.
Planarized representations (of a connected component) of a graph.
Definition: PlanRep.h:59
static bool writeGML(const Graph &G, std::ostream &os)
Writes graph G in GML format to output stream os.
static bool drawSVG(const GraphAttributes &A, std::ostream &os, const SVGSettings &settings)
Optimal edge insertion module.
Definition: VariableEmbeddingInserter.h:52
Polylines with PointType points.
Definition: geometry.h:263
Declaration of the PlanarSubgraphFast.
Declaration of class SubgraphPlanarizer.
void setInserter(EdgeInsertionModule *pInserter)
Sets the module option for the edge insertion module.
Definition: SubgraphPlanarizer.h:140
Computation of a planar subgraph using PQ-trees.
Definition: PlanarSubgraphFast.h:68
Declares class GraphIO which provides access to all graph read and write functionality.
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:492
DFS-based algorithm for computing a maximal acyclic subgraph.
Definition: DfsAcyclicSubgraph.h:43
ReturnType call(PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=nullptr, const EdgeArray< bool > *pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr)
Computes a planarized representation of the input graph.
Definition: CrossingMinimizationModule.h:72
static bool write(const Graph &G, const string &filename, WriterFunc writer)
Writes arbitrary format to a file specified by name.
Definition: GraphIO.h:178
GenericPoint< double > DPoint
Representing two-dimensional point with real coordinates.
Definition: geometry.h:244
static const long edgeGraphics
Corresponds to edge attribute bends(edge).
Definition: GraphAttributes.h:119
void setSubgraph(PlanarSubgraphModule< int > *pSubgraph)
Sets the module option for the computation of the planar subgraph.
Definition: SubgraphPlanarizer.h:135
The planarization approach for crossing minimization.
Definition: SubgraphPlanarizer.h:106
Declaration of class DfsAcyclicSubgraph.
Class for the representation of edges.
Definition: Graph_d.h:292
Class for the representation of nodes.
Definition: Graph_d.h:169
void callAndReverse(Graph &G, List< edge > &reversed)
Makes G acyclic by reversing edges.
bool randomSimpleGraph(Graph &G, int n, int m)
Creates a random simple graph.
static const long nodeGraphics
Corresponds to node attributes x(node), y(node), width(node), height(node), and shape(node).
Definition: GraphAttributes.h:116
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1373