| TopologicalX Class |
The TopologicalX class represents a data type for determining a topological order of a directed acyclic graph (DAG). Recall, a digraph has a topological order if and only if it is a DAG. The HasOrder operation determines whether the digraph has a topological order, and if so, the Order operation returns one.
This implementation uses a nonrecursive, queue-based algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the HasOrder and Rank operations takes constant time; the Order operation takes time proportional to V.
See , , and to compute a directed cycle if the digraph is not a DAG. See for a recursive version that uses depth-first search.
Inheritance HierarchyNamespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntaxpublic class TopologicalX
The TopologicalX type exposes the following members.
Constructors| Name | Description | |
|---|---|---|
 | TopologicalX(Digraph) |
Determines whether the digraph G has a topological order and, if so,
finds such a topological order.
|
| TopologicalX(EdgeWeightedDigraph) |
Determines whether the edge-weighted digraph G has a
topological order and, if so, finds such a topological order. |
Properties
Methods| Name | Description | |
|---|---|---|
 | MainTest |
Demo test the Topological data type. |
| Order |
Returns a topological order if the digraph has a topologial order,
and null otherwise. |
| Rank |
The the rank of vertex v in the topological order;
-1 if the digraph is not a DAG |
RemarksFor additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
This class is a C# port from the original Java class TopologicalX implementation by the respective authors.
See Also