Class GraphTraversalExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Lazy breadth-first and depth-first traversals over any graph. All traversals are implemented iteratively, so arbitrarily deep graphs cannot overflow the call stack, and results are streamed on demand.

public static class GraphTraversalExtensions

Inheritance

object

GraphTraversalExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

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

Enumerates the vertices reachable from start in breadth-first order. On directed graphs only out-edges are followed.

public static IEnumerable<TVertex> BreadthFirstSearch<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, TVertex start) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to traverse.

start TVertex

The vertex to start from.

Returns

IEnumerable<TVertex>

A lazy sequence of vertices, each visited once.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentException

start is not in the graph.

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

Enumerates the vertices reachable from start in depth-first post-order (a vertex is yielded after all its descendants). On directed graphs only out-edges are followed.

public static IEnumerable<TVertex> DepthFirstSearchPostOrder<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, TVertex start) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to traverse.

start TVertex

The vertex to start from.

Returns

IEnumerable<TVertex>

A lazy sequence of vertices, each visited once.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentException

start is not in the graph.

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

Enumerates the vertices reachable from start in depth-first pre-order (a vertex is yielded when first discovered). On directed graphs only out-edges are followed.

public static IEnumerable<TVertex> DepthFirstSearch<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, TVertex start) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to traverse.

start TVertex

The vertex to start from.

Returns

IEnumerable<TVertex>

A lazy sequence of vertices, each visited once.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentException

start is not in the graph.