Class GraphTopologicalSortExtensions

Namespace: Graph1x.Algorithms

Assembly: Graph1x.dll

Topological ordering of directed acyclic graphs using Kahn's algorithm.

public static class GraphTopologicalSortExtensions

Inheritance: object

GraphTopologicalSortExtensions

Inherited Members: object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

TopologicalSort<TVertex, TEdge>(IDirectedGraph<TVertex, TEdge>)

Computes a topological order of the graph: every edge's source appears before its target. Ties are broken by vertex insertion order (FIFO), so the result is deterministic for a given construction sequence.

public static IReadOnlyList<TVertex> TopologicalSort<TVertex, TEdge>(this IDirectedGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IDirectedGraph<TVertex, TEdge>: The directed graph to sort.

Returns

IReadOnlyList<TVertex>: The vertices in topological order.

Type Parameters

TVertex: The vertex type.
TEdge: The edge type.

Exceptions

GraphCycleException: The graph contains a cycle; the exception carries one offending cycle.