Registers denote a variety of graph attributes which are intended to store algorithmic results persistently. All registers are collected into a single attribute pool, and this pool can be accessed by the return of Registers().
Opposed to the other graph attributes, registers are available for all graph objects, not just for represented graphs. If a graph is represented, manipulations of its skeleton ensure that the register attributes are updated accordingly.
The node colour register assigns integer values to the graph nodes, with the intended value range [0,1,..,n-1] + {NoNode}. The applications are:
- Orderings of the node set (e.g. st-numberings)
- Partitions of the node set (e.g. clique partitions)
[See API]
The edge colour register assigns integer values to the graph arcs, with the intended value range [0,1,..,2m-1] + {NoArc}. The applications are:
- Orderings of the arc set (e.g. Euler cycles)
- Partitions of the arc set (e.g. partitions into 1-matchings)
- Implicit arc orientations (e.g. feedback arc sets) Other than the subgraph multiplicities, edge colours are stored by plain arrays. So, especially for geometric graph instances, the number of arcs is large relative to the size of memory representation. It is therefore recommended to handle subgraph incidence vectors by edge colours only if non-trivial lower capacity bounds prevent from using the subgraph multiplicities.
[See API]
The predecessor register assigns arc indices to the graph nodes. More particularly, the predecessor arc of a node is either undefined or points to this node.
Any directed path encoded into the predecessor labels can be backtracked from its end node without scanning the incidence lists of the intermediate nodes. So, whenever possible, subgraphs are stored by the predecessor register:
- Simple directed paths and cycles
- Rooted trees
- One-cycle trees consisting of a directed cycle and some trees pointing away from this cycle
- Any node disjoint union of the listed subgraph types
[See API]
The distance label register maintains the results of shortest path methods.
[See API]
The node potential register maintains the dual solutions for min-cost network flow problems. That is, network flow optimality can be verified at any time after a flow has been been computed, and later calls to the min-cost flow solver will take advantage of the dual solution.
[See API]
Return to main page