Topological Sort

Topological Sort

This algorithm creates an linear ordering of the vertices (or edges) in a Directed Acyclic Graph (DAG) such that each vertex comes before its outbound vertices. A typical example of the topological sort is the build dependencies ordering.

The topological sort is simply computed using the TopologicalSortAlgorithm class, which uses the DepthFirstSearchAlgorithm internally.

TopologicalSort is an extension method of AlgorithmExtensions to simplify this task:

IVertexListGraph<TVertex, TEdge> graph = ...;
// Iterating over the sorted vertices
foreach(TVertex vertex in graph.TopologicalSort())
{
...
}

QuikGraph contains a second topological sort algorithm that sorts vertices by increasing in-degree such that source vertices are taken first. It is implemented by SourceFirstTopologicalSortAlgorithm and wrapped by the extension method AlgorithmExtensions.SourceFirstTopologicalSort.