Topological sorting. More...
#include <GTL/topsort.h>
Inherits: dfs
Assigns to each node n
a number top_num
such
that for every edge (u,v)
top_num[u]
<
top_num[v]
, if possible, i.e. iff the directed graph is
acyclic.
Similar to the testing of biconnectivity, which extends DFS to calculate low-numbers, the topsort-algorithm extends DFS to calculate the new numbering (and thus to test whether such a numbering is possible).
In order to traverse all the nodes in the order of its top-numbers, a
new iterator, topsort_iterator
is provided.
[public]
default constructor; enables scanning of the whole_graph.
[public]
Number in topological order.
n | node. |
[public]
Tests if graph was acyclic.
[public]
Iterate through nodes in topsort-order.
[public]
Iterate through nodes in topsort-order.
[public virtual]
Preconditions:
G
is directed.
G | graph. |
algorithm::GTL_OK
if topsort may be applied to
G
. [public virtual]
Reset
Kdoc |