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

Graph classes

This page gives an overview on the most important graph classes, which most users are likely to require or stumble over. Please follow the doxygen-links to find out more about these classes and their base classes, sibling classes, sub-classes, etc. not described on this page.

Basic Graph Classes
Graph This is the “normal” Graph class which forms the base of the other graph classes. It holds all structural information of a graph (nodes, edges), including the ordering of edges around nodes, etc. This is achieved by a rich implementation following the adjacency list representation and allowing dynamic graphs. In OGDF all edges are per default directed arcs, but can be interpreted as undirected edges.
GraphAttributes The graph only holds pure structural information. In order to store layout information (node positions, sizes, colors, etc.) we use such attribute-objects which are attached to a graph. We can attach multiple such attribute objects to a single graph. When constructing such an object, we specify the attributes which we want to manage through this object (e.g. node color). Note that even if the underlying graph is modified (e.g. addition of a new node), the attributes are modified such that this new node also has a color-entry in the attribute-object.
CombinatorialEmbedding For planar graphs, we can attach a combinatorial embedding onto a graph. Although the graph itself is capable of representing a combinatorial embedding through the edge orderings, this class offers a set of convenience functionality. It defines faces analogous to nodes and edges and lets you traverse and look-up these faces. It also offers easier embedding-preserving modification routines for planar graphs, like splitFace, joinFace, splitNode, etc.
GraphCopy, GraphCopySimple Often we do not want to change the original graph, but only a copy of it. Still, what we need is a mapping between the original graph and its copy. These classes do exactly that: they offer the same interface as a normal graph, but define a bijective mapping for all original and copied nodes. This mapping is updated accordingly whenever one of the graphs is modified (addition/deletion of nodes/edges).
The non-simple version of this class furthermore allows the splitting of edges (as, e.g., necessary in planarization routines. Thereby an edge in the copy is replaced by a path; all these new edge segments then automatically map to the same original edge. Vice versa, the mapping from an original edge then gives a whole list of edges in the copy.
GraphCopyAttributes This is a convenience class which can be attached to a GraphCopy to easily read/modify the position and node-size attributes of the underlying original graph.
PlanRep The class name is an abbreviation of PlanarRepresentation. It represents a special type of GraphCopy which offers additional functionality for the use in planarization-based layout algorithms. It always represents only a single of its connected components.
Helper Graph Classes
NodeElement, EdgeElement,
AdjElement, FaceElement
Normally we only deal with these objects through pointers. The pointers to them have the C++ names node, edge, adjEntry, and face respectively.
All these elements automatically offer indices. Note that, in contrast to e.g. LEDA, these objects are active in the sense that you can directly query them for their incident elements, without requiring a pointer to their graph.
NodeArray, EdgeArray,
We can attach arrays to a graph, such that we can use the nodes or edges, respectively, directly as indices of the array. Of course, the array grows automatically when new nodes/edges are added to the graph etc. Analogously, we can attach a FaceArray to a CombinatorialEmbedding.
NodeSet, FaceSet These classes represent sets of nodes or faces, which provide constant time query, insert, and remove methods.
Additional Graph Classes
DualGraph Given a CombinatorialEmbedding of a planar graph, this graph represents the embedded dual graph, including a bijective mapping between nodes and faces, etc.
GraphReduction This class is a special type of GraphCopy: when created, all chains, i.e. paths where all inner vertices have degree 2, are reduced to a single edge. We then have a bijective mapping between the graph's original and copied nodes and edges. A copied edge thereby gives a list of original edges that were shrunken into the single edge. This class can be of interest for simple preprocessing schemes.
Cluster Graph Classes
ClusterGraph This class is attached to a normal graph and represents a clustered structure. Hence it, together with its underlying graph, represents a clustered graph, and offers according functionality.
ClusterElement, ClusterArray Similar to NodeElement, we also have ClusterElements, pointers thereto are denoted simply as clusters. Analogously, we can have arrays attached to a ClusterGraph, which use clusters as indices.
These are versions of the corresponding classes for normal graphs, which are specially adopted for the use with clustered graphs.
HyperGraph This class implements a hypergraph. In a hypergraph edges are not limited to connect just two nodes, but they can connect an arbitrary set of nodes.
tech/graphclasses.txt · Last modified: 2014/12/16 12:20 (external edit)
This page is driven by DokuWiki