Interface ITopologicalSort

An algorithm performing a topological sort on the provided IGraph.

Namespace: MoreStructures.Graphs.Sorting
Assembly: MoreStructures.dll
Syntax
public interface ITopologicalSort
Remarks

DEFINITION
Given a DAG G(V, E), where V is the set of vertices of G and E is the set of directed edges of G, the topological sort of G, indicated here as TS, is a of the first non-negative |V| System.Int32 values, such that for all couples (v1, v2) of V^2, if there is a directed path from v1 to v2, then TS[v1] < TS[v2].
The topological sort defines a linear order of the vertices V of the DAG G.
The definition only makes sense when G is a DAG (Direct Acyclic Graph), because: - a generic graph may have cycles, which make impossible to define a topological sort for any vertex on the cycle (since such vertex would be at the same time predecessor and successor of any other vertex of the cycle);
- an undirected graph doesn't make distinction between the two different traversal directions of an edge, making each edge a cycle of two edges (1 edge if it is a loop).
The topological sort is in general not unique, i.e. multiple orders are possible, which satisfy the definition above. Look at the documentation of the Sort(IGraph) method for some examples.

Methods

| Improve this Doc View Source

Sort(IGraph)

Performs the topological sort of the provided dag.

Declaration
IList<int> Sort(IGraph dag)
Parameters
Type Name Description
IGraph dag

The IGraph instance representing a DAG (Direct Acyclic Graph).
Returns
Type Description
IList<System.Int32>

A list TS, of the first n non-negative distinct integers, where n is the number of vertices in dag. TS[i] represents the position of the vertex i in the topological sort.
Remarks

Examples

The followin graph:

 0 --> 1 <==> 3
| ^   ^     /
| |  /     /
| | /     /
v |/     /
 2 <-----

is NOT a DAG and doesn't have any valid topological sort.

The followin graph:

 0 --> 1 --< 3
 |          /
 |         /
 |        /
 v       /
 2 <----

is a DAG and has a single valid topological sort order: new[] { 0, 1, 3, 2 }).

The followin graph:

 0 --> 1 --< 3
 |
 |
 |
 v
 2

is a DAG and has two valid topological sort orders:

  • new[] { 0, 1, 3, 2 });
  • new[] { 0, 2, 1, 3 }).

Extension Methods