Class SingleDfsSinkBasedTopologicalSort

An ITopologicalSort implementation which assigns topological order to vertices by identifing a sink vertex at each iteration in a deterministic way, by running DFS once on the entire graph and storing the post order.

Inheritance
System.Object
SingleDfsSinkBasedTopologicalSort
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 SingleDfsSinkBasedTopologicalSort : ITopologicalSort
Remarks

ADVANTAGES AND DISADVANTAGES
- This implementation is a conceptual improvement over both AnyPathToSinkBasedTopologicalSort and DfsOnEachVertexSinkBasedTopologicalSort.
- The optimization is based on the observation that a lot of the DFS traversal, done by DfsOnEachVertexSinkBasedTopologicalSort to populate its "reachability dictionary", is shared between many of the vertices connected together, and doesn't need to be repeated every time.
- For example, in a simple graph A1 -> A2 -> ... -> An, the DFS on A1 and the DFS on A2 share the path A2 -> ... -> An, the DFS on A1 and A3 share the path A3 -> ... -> An, etc.
- While AnyPathToSinkBasedTopologicalSort doesn't explicitely use a DepthFirstSearchFromVertex(IGraph, Int32), its strategy can be seen as a DFS traversal if the initial vertex and the path followed at each iteration are taken consistently.
- Therefore, this implementation is an improvement of both previously mentioned implementations.
- Moreover, if the DFS traversal is deterministic, this algorithm also is.

ALGORITHM
- A full DFS traversal of the entire DAG is performed via DepthFirstSearchOfGraph(IGraph) on a IVisitStrategy built by the VisitStrategyBuilder provided in the constructor.
- Before running the DFS traversal, a post-visit event handler is attached to VisitedVertex, running a post-order counter which is incremented at every visit.
- The value of the post-order counter is stored in an array TS of v integers, where v is the number of vertices in the graph, at a position defined by the id of the vertex.
- Finally, the array TS is returned.

COMPLEXITY
- Running DFS for the entire graph via DepthFirstSearchFromVertex(IGraph, Int32) is a generally expensive operation, which has a Time and Space Complexity which depends on the specific IVisitStrategy used.
- However, unlike in DfsOnEachVertexSinkBasedTopologicalSort, it is performed once, and not for each vertex.
- Instantiating the TS array is a O(v) operation, both in time and space.
- Storing, updating and assigning the post-order counter to the right item of TS are all constant-time operations.
- Therefore Time Complexity is O(Tdfs + v) and Space Complexity is O(Sdfs + v).
- Using FullyIterativeHashSetBasedGraphVisit as IVisitStrategy and assuming GetAdjacentVerticesAndEdges(Int32, Boolean) can be computed in constant time, Tdfs and Sdfs becomes linear in v and e.
- In this case, Time Complexity becomes O(v + e) and Space Complexity becomes O(v).

Constructors

| Improve this Doc View Source

SingleDfsSinkBasedTopologicalSort(Func<IVisitStrategy>)

Declaration
public SingleDfsSinkBasedTopologicalSort(Func<IVisitStrategy> visitStrategyBuilder)
Parameters
Type Name Description
Func<IVisitStrategy> visitStrategyBuilder

Remarks

Properties

| Improve this Doc View Source

VisitStrategyBuilder

A visitor builder, to be used to build the IVisitStrategy instance needed to identify sink vertices, by running a Depth First Search on the graph.

Declaration
public Func<IVisitStrategy> VisitStrategyBuilder { get; }
Property Value
Type Description
Func<IVisitStrategy>

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