Topological Sort

This algorithm creates an linear ordering of the vertices (or edges) in a Directed Acyclic Graph 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 DepthFirstSearchVertexAlgorithm internaly.

TopologicalSort is an extension method of AlgorithmExtensions to simplify this task:
IVertexListGraph<Vertex,Edge> g;
// iterating over the sorted vertices
foreach(Vertex v in g.TopologialSort())
{…}

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

Last edited Mar 29, 2009 at 9:06 PM by pelikhan, version 6

Comments

No comments yet.