Class GraphCycleExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Cycle detection for directed graphs (three-color depth-first search) and undirected graphs (depth-first search with parent-edge tracking, so parallel edges in multigraphs are correctly recognized as cycles).

public static class GraphCycleExtensions

Inheritance

object

GraphCycleExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

FindCycle<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Finds a cycle in the graph, if any. The result lists the cycle's vertices in order: each vertex connects to the next, and the last connects back to the first. A self-loop yields a single-vertex cycle.

public static IReadOnlyList<TVertex>? FindCycle<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to inspect.

Returns

IReadOnlyList<TVertex>

The cycle's vertices, or null when the graph is acyclic.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

HasCycle<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Determines whether the graph contains at least one cycle.

public static bool HasCycle<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to inspect.

Returns

bool

true if a cycle exists.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.