Container objects

A container is a data structure to store other data objects. Most container applications in this library concern queuing of nodes and arcs by their indices, and eliminating indices from queues in certain order.

Some algorithms can be equipped with different kinds of queues, so the push/relabel method for min-cost flow. To this end, there is a common interface class goblinQueue with methods for insertion and deletion of members.

[See API]

Fixed index range containers

Fixed index range containers are functional equivalent with the STL stack<TIndex> and STL queue<TIndex> classes. Other than in the STL, fixed index range containers are not really sequential. That is, the physical memory representation does not conform with the logical order of elements. The containers can only store unsigned integers (indices) of a range 0,1,..,r-1 which must be specified at the time of instanciation. The advantages are following:

[See API]

Priority queues

A priority queue stores indices with a numeric key value. Elements are deleted in the order of increasing key value. Key values are assigned when elements are added, but can also be modified later. In general, this goblinQueue::ChangeKey() method cannot be reduced to goblinQueue::Insert() / goblinQueue::Delete() pairs. All these operations roughly run in logarithmic time, depending on the actual goblinQueue::Cardinality(), not on the index range.

[See API]

Return to main page