Graph composition

Composition from scratch

The library comes with several constructor methods which grow graph objects from one or more numeric input parameters:

These classes apply as test cases for optimization and drawing methods, in particular when used as a seed for the composition principles which follow, and the randomization procedures described in Section Random manipulations.

Except for the triangular and the Mycielskian graphs (which do not admit readable drawings), all constructor methods provide the expectable geometric embeddings.

[See API]

Graph derivation

What follows is a list of well-known principles to construct graph objects from other graphs:

Other than the methods discussed further on, the constructors listed here work for general graph objects.

[See API]

Planar composition

The library provides several methods to generate planar graphs from other planar graphs. It is required that the original graph comes with a planar representation, and the new graph is generated with a respective planar representation. The composition methods generalize from construction principles for regular polyhedra.

Most important is the dualGraph construction. This takes the original regions as the node set, connecting nodes if the original faces share an edge. Actually, the edges are mapped one-to-one. The directedDual constructor works similar but assigns arc orientations acoording to the orientation of the original arc.

Observe that the dual of the dual is basically the original graph, provided that the graph is connected. In the directed case, the arc orientations are reverted.

A potential drawing of the original graph is mapped, but the quality of the resulting drawing is currently limited by the dual node representing the exterior face of the original graph (A special treatment of infinite nodes is missing). The following shows an outer-planar graph and its dual graph, with the exterior face displayed in the center:


Other constructors (vertexTruncation and planarLineGraph) replace the original nodes by faces. The constructor facetSeparation maintains the original faces and duplicates the original nodes for every adjacent face. Observe that all constructors yield node-regular graphs:

In order to obtain the full set of Platonian and Archimedian polyhedra, the constructor method polarGrid comes into play which is very flexible:

The following shows a polar grid with 4 rows, 11 columns and a single pole (to obtain this drawing, polarGrid::POLAR_CONE must be specified):


[See API]

DAG composition

In a directed graph, the arc set can be considered a relation of the graph nodes. According to that, the transitive closure of a digraph is the digraph with the same node set and with arcs uv if there is a directed uv-path in the original graph. If the original digraph is acyclic, the transitive closure defines a partially ordered set.

Of more practical importance is the reverse construction principle: An arc uv is called transitive if there is a directed uv-path with intermediate nodes. The intransitiveReduction constructor omits all transitive arcs of the original digraph. Observe that this subgraph is well-defined only if the original digraph is acyclic and simple. The so-called Hasse diagram of a DAG is obtained by taking the intransitive reduction and computing a layered drawing of it.

The following shows a directd acyclic graph, with the red arcs forming its intransitive reduction:


[See API]

Merging graphs

This addresses the methods which derive graph objects from two given input graphs. Actually, no new object is instanciated, but one graph is modified by means of the other. Two methods are available:

The facet identification method can be used to construct star solids from convex solids, and tilings (subdivisions of 2D grid graphs) as provided in earlier GOBLIN releases. This also includes the possibily of constructing non-planar graphs on a planar skeleton.

[See API]

Graph composition by node distances

Two constructor methods are provided which result in dense graph objects, whose edge length labels encode the node distances of the input graph:

There is also a sparse concept, voronoiDiagram, which takes a set of terminal nodes of the input graph, assigning the non-terminal nodes to the region of a nearest terminal. The Voronoi regions are the nodes of the new graph, and the edge lengths are the distances of the respective terminals.

[See API]

Random manipulations

All graph objects with a sparse representation can be randomly augmented to disturb the incidence structure. All methods augment by a specified number of arcs, either without any restrictions, by a closed walk, or such that no node exceeds a given degree bound.

[See API]

Mapping node and arc indices back

After a graph object has been derived from another data object, and computations have been done on the derived graph instance, it is often required to map back the computational results to the original graph. For this goal, two methods abstractMixedGraph::OriginalOfNode() and abstractMixedGraph::OriginalOfArc() are provided.

There is no global rule of what the index returned by abstractMixedGraph::OriginalOfNode(v) represents. It may be a node index, an arc index with or without the arc direction bit or any other entity which can be addressed by an index.

Backtransformations are maintained only if abstractMixedGraph::OPT_MAPPINGS is specified to the respective constructor method. Not all concrete classes support this feature at the time!

[See API]

Return to main page