Graphs are objects from discrete geometry which consist of so-called nodes and edges. Graphs may be either undirected (where edges are unordered pairs of nodes), directed (where edges are ordered pairs), or mixed from directed and undirected edges. To this mathematic definition, we refer as the incidence structure or the graph skeleton.
Most graph optimization problems require further input, usually numeric values associated with the graph edges. For the time being, the library does not support arbitrary tags on the graph nodes and edges, but attributes which either assign a value to all nodes or to all edges.
There are so-called attribute pools to manage attributes with predefined roles, and to make them persistent:
All graph objects provide consistent interfaces to retrieve values of the attributes in these pools. The attribute values are either virtual (functional dependent on another graph object) or represented in memory. Register attributes are always represented, even for graph objects which result from a combinatorial problem transformation.
A graph object is called represented if all of the managed attributes are represented. If the graph skeleton is also represented by data structures, the graph representation is called sparse (and dense otherwise).
The distinction between directed, undirected and mixed graphs is reflected by the library class hierarchy. All high level methods are associated with according abstract classes. From the abstract class, a sparse and a dense representation subclass is derived.
The class abstractMixedGraph is the base class for all kinds of graph objects. It implements all layout and optimization methods which do not impose restrictions on the graph skeleton, which can ignore edge orientations or which can handle both the directed and the undirected case.
[See abstract base class]
[See sparse implementation]
The class abstractDiGraph is the base class for all digraph objects. It implements most of the network flow code and everything about DAGs.
[See abstract base class]
[See sparse implementation]
[See dense implementation]
The class abstractGraph is the base class for all undirected graphs. It implements the matching and T-join solvers, and specialized methods for TSP, max-cut and Steiner trees.
[See abstract base class]
[See sparse implementation]
[See dense implementation]
Bigraphs divide the node set into two parts such that edges run from one part to the other. For several optimization problems, the bipartite case is either trivial (e.g. node colouring, stable set) or at least, there are special algorithms (e.g. matching, edge colouring).
[See abstract base class]
[See sparse implementation]
[See dense implementation]
Representational attributes denote the data which must be added to a plain graph in order to obtain a network programming problem instance. That are so far:
- Lower and upper edge capacity bounds which restrict the set of feasible subgraphs
- Edge length labels which define linear objective functions
- Node demands which define terminal or source node sets
The edge length labels are special in the following sense: In geometric problem instances, the edge lengths are functional dependent on the node coordinate values irrespective of what is set in the physical edge length attribute.
[See API]
To the nodes of a represented graph, coordinate values can be assigned. Coordinate values form part of the graph drawing, but also can define the edge length labels. The latter depends on the TokGeoMetric attribute value. Currently, there no distinction between display coordinates and length defining coordinates.
When coordinate values exist, one says that the graph is geometrically embedded. All nodes have the same dimension, and this dimension is either 0 or 2. Three-dimensional embeddings are not well-supported yet since all layout methods produce 2D drawings.
Coordinate values are also provided for all potential layout points. But note that these coordinate values might be relative to graph node coordinates.
[See API]
Return to main page