Definition
An instance algorithm of class GIT_TOPOSORT< OutAdjIt, Indeg, Queuetype > is an implementation of an algorithm that iterates over all nodes in some topological order, if the underlying graph is acyclic. An object of this class maintains an internal queue, which contains all nodes (in form of adjacency iterators where the current node is equal to the fixed node) that are not yet passed, but all its predecessors have been passed.
Iterator version: There is an iterator version of this algorithm: TOPO_It. Usage is similar to that of node iterators without the ability to go backward in the sequence and only a graph is allowed at creation time. Additionally there is TOPO_rev_It which traverses the graph in reversed topological order.
#include < LEDA/graph/graph_iterator.h >
Creation
GIT_TOPOSORT< OutAdjIt, Indeg, Queuetype > | algorithm(Indeg& indegree) | |
creates an instance algorithm of this class bound to indeg. The internal queue of adjacency iterators is empty. |
Preconditions:
Operations
void | algorithm.next() | Performs one iteration of the core loop of the algorithm. More specifically, the first element of get_queue() is removed from the queue, and every immediate successor n of this node for which currently holds get(indeg,n)==0 is inserted in get_queue(). |
void | algorithm.finish_algo() | executes the algorithm until finished() is true, i.e. exactly if the queue is empty. |
bool | algorithm.finished() | returns true if the internal queue is empty. |
OutAdjIt | algorithm.current() | returns the current adjacency iterator. |
Queuetype& | algorithm.get_queue() | gives direct access to internal queue. |
bool | algorithm.cycle_found() | returns true if a cycle was found. |
void | algorithm.reset_acyclic() | resets the internal flag that a cycle was found. |
Implementation
The asymptotic complexity is (m + n) , where m is the number of edges and n the number of nodes.
Example
This algorithm performs a normal topological sort if the queue is initialized by the set of all nodes with indegree zero:
Definition of algorithm, where indeg is a data accessor that provides full data access to the number of incoming edges for each node:
GIT_TOPOSORT<OutAdjIt,Indeg,Queuetype<Nodehandle> > algorithm(indeg);Initialization of get_queue() with all nodes of type OutAdjIt::nodetype that have zero indegree, i.e. get(indeg,it)==indeg.value_null.
while ( !algorithm.finished() ) { // do something reasonable with algo.current() algo.next(); }The source code of function toposort_count() is implemented according to this pattern and may serve as a concrete example.