Open
Graph Drawing
Framework

 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);
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.

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