Class AnyPathToSinkBasedTopologicalSort

An ITopologicalSort implementation which assigns topological order to vertices by identifing a sink vertex at each iteration in a non-deterministic way, picking some start vertex and following some path to a sink.

Inheritance
System.Object
AnyPathToSinkBasedTopologicalSort
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Graphs.Sorting
Assembly: MoreStructures.dll
Syntax
public class AnyPathToSinkBasedTopologicalSort : ITopologicalSort
Remarks

ADVANTAGES AND DISADVANTAGES
- Compared to DfsOnEachVertexSinkBasedTopologicalSort, it has better runtime (quadratic, rather than cubic, over the number of vertices on the graph).
- However, the algorithm picks a vertex and follows a path at random (using the LINQ method on a , which is not sorted and doesn't provide any guarantee about ordering).
- Therefore, unlike DfsOnEachVertexSinkBasedTopologicalSort, the topological order produced when multiple results are possible, is not defined.

ALGORITHM
- The number of vertices v in the DAG is computed via GetNumberOfVertices().
- Then, a set of the integers from 0 to v-1 is instantiated, keeping the remaining vertices not sorted yet, together with an array TS of v integers, to accomodate the topological sort value for each of the vertices.
- Then, the main loop of the algorithm is executed, while there are still unsorted vertices.
- Any of the sorted vertices v is taken, and a directed path v is followed until a sink vertex s is found.
- If, while following a path, a loop is detected (i.e. a vertex is visited again), an exception is thrown.
- Otherwise, the found sink can be assigned the highest unassigned sort value (v-1 down to 0), and the loop repeats.
- When all vertices have been sorted, TS can be returned as result.

COMPLEXITY
- Getting the number of vertices is a constant-time operation in most IGraph implementations.
- Instantiating the set of unsorted vertices, instantiating the output array, and getting the first available vertex from the set of unsorted vertices are all O(v) operations, both in time and space.
- The main loop of the algorithm is executed v times.
- Each iteration can potentially explore the entire graph, so a path of O(v) vertices and O(v) edges.
- Therefore, Time Complexity is O(v^2) and Space Complexity is O(v).

Methods

| Improve this Doc View Source

Sort(IGraph)

Declaration
public IList<int> Sort(IGraph dag)
Parameters
Type Name Description
IGraph dag
Returns
Type Description
IList<System.Int32>
Remarks

Implements

Extension Methods