Graph proxy and component objects

Attributes and attribute pools

An attribute denotes an object to store array like data. In fact, it is composed from an STL vector which is memory layout compatible with a plain C arrays. This vector is augmented by some functionality:

• Default values: The method attribute<T>::GetValue() returns a default value for every index outside the vector index range
• Maxima and minima: It is possible to retrieve the indices at which extremal values are achieved. These indices are computed only on demand, maintained as long as this is efficient, and safely invalidated otherwise

Basically, attributes have been designed to store data indexed by graph arc and node indices. With respect to constant attribute values (e.g. all node demands equal to one), it is possible to keep the representational vector size zero. There are variants of the manipulation procedures known for STL vectors which exclude constant attributes.

Graph attributes are collected into attributePool objects in which they can be addressed by a so-called token. This denotes an index in the TPoolTable array which is associated with this attribute pool. The pool table lists clear text names, type and size info of all possible attributes. In practice, only few of the listed attributes are allocated.

All managed graph attributes conform with manipulations of the incidence structure. To allocate attributes of the correct vetor length, it takes the method abstractMixedGraph::SizeInfo() which reports about the problem dimensions.

Direct access to attributes definetely improves the performance. In order to extract attributes, the contained vectors or the contained arrays from the managing pool object, represented graph objects grant public access to all its compound attribute pools:

• abstractMixedGraph::Registers(): For all graph objects, the pool of register data (usually the algorithmic solutions).
• abstractMixedGraph::RepresentationalData(): For represented graphs only, the attributes which are input to optimization methods such as: arc capacity bounds, node demands, arc orientations.
• abstractMixedGraph::Geometry(): For represented graphs only, all node coordinates.
• abstractMixedGraph::LayoutData(): For represented graphs only, all layout parameters, and all arc routing information.

But observe that direct manipulation of attributes can corrupt the graph representation. For example, reducing an upper arc capacity bound might be incompatible with the lower bound and the subgraph multiplicity. Manipulating attributes by means of the representational object preserves data integrity.

[See API]

Index sets

An index set is an object specifying a certain set of integer values. Such objects are in particular useful for algorithms which apply to arbitrary graph node or edge subsets (e.g. for multi terminal problems like T-joins). Of course, the concept of index set is not restricted to applications on graphs.

For all index set subclasses, the operation indexSet::IsMember(i) verifies the membership of the index i in constant time. Particular subclasses may or may not provide efficient methods to enumerate the contained indices. The default implementations of indexSet::First() and indexSet::Successor() scan the full index range. For the current applications, this is not performance-critical since the graph algorithms run over the full index range anyway, for sake of initialization.

There are indexSet derivates which are absolutely generic, namely to specify empty sets, full index intervals 0,1,..,r-1, or singleton sets. There are classes to define the union, meet or difference of two index sets, and index set complements. Other index set objects refer to the nodes or the arcs of a particular graph with a certain property.

It is worth to note that contiguous memory stacks and queues also work as index sets.

[See API]

Investigators

An investigator object basically represents an iterator on the incidence list of each node of a particular graph. Investigators are useful whenever the graph has to be search in any order different from BFS. The only need to deal with investigators explicitly is when a new graph searching algorithm has to be encoded.

Most graphs can be handled by the default implementation iGraph, but some graph classes come with an own investigator class. There is a factory method abstractMixedGraph::NewInvestigator() which supplies with investigator objects of the correct type.

According to the frequent investigator applications in the library, there is a mechanism to cache iterator ojbects instead of new / delete operations. Iterators taken from the cache are called managed investigators. So, a typical application code does not contain constructor or factory method calls but only calls to abstractMixedGraph::Investigate() which tries to avoid memory allocations.

[See API]

Return to main page