GraphAlgorithms Class

Definition

Namespace

Bodu.Collections.Generic.Graphs

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

GraphAlgorithms.ConnectedComponents.cs

Provides traversal, ordering, connectivity, and shortest-path algorithms over Graph<T>.

public static class GraphAlgorithms

Inheritance

object

GraphAlgorithms

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Remarks

The algorithms reuse the library's existing primitives - Deque<T> for breadth-first frontiers and IndexedPriorityQueue<TElement, TPriority> for Dijkstra relaxation - and evaluate iteratively so they do not overflow the stack on large or deep graphs.

Methods

BreadthFirstSearch<T>(IReadOnlyGraph<T>, T)

Enumerates the vertices reachable from the specified source in breadth-first order.

public static IEnumerable<T> BreadthFirstSearch<T>(IReadOnlyGraph<T> graph, T source) where T : notnull

Parameters

graph IReadOnlyGraph<T>

The graph to traverse.

source T

The vertex at which traversal starts.

Returns

IEnumerable<T>

A lazily evaluated sequence of reachable vertices, beginning with source.

Type Parameters

T

The vertex type.

Examples

var graph = new Graph<int>(GraphKind.Directed);
graph.AddEdge(1, 2);
graph.AddEdge(1, 3);
graph.AddEdge(2, 4);

// Breadth-first visits the source, then its neighbors, then theirs: 1, 2, 3, 4.
var order = GraphAlgorithms.BreadthFirstSearch(graph, 1).ToList();

Exceptions

ArgumentNullException

graph or source is null.

ArgumentException

source is not in the graph.

ConnectedComponents<T>(IReadOnlyGraph<T>)

Groups the vertices of the graph into connected components, treating every edge as undirected.

public static IReadOnlyList<IReadOnlyList<T>> ConnectedComponents<T>(IReadOnlyGraph<T> graph) where T : notnull

Parameters

graph IReadOnlyGraph<T>

The graph to partition.

Returns

IReadOnlyList<IReadOnlyList<T>>

A list of components, each containing the vertices that are mutually reachable.

Type Parameters

T

The vertex type.

Examples

var graph = new Graph<int>(GraphKind.Undirected);
graph.AddEdge(1, 2);
graph.AddEdge(2, 3);
graph.AddEdge(10, 11);
graph.AddVertex(20);   // isolated vertex

// Three components: { 1, 2, 3 }, { 10, 11 }, { 20 }.
var components = GraphAlgorithms.ConnectedComponents(graph);

Remarks

For a directed graph this yields the weakly connected components - vertices are grouped without regard to edge direction. The partition is computed with a DisjointSet<T> over the graph's edges.

Exceptions

ArgumentNullException

graph is null.

DepthFirstSearch<T>(IReadOnlyGraph<T>, T)

Enumerates the vertices reachable from the specified source in depth-first order.

public static IEnumerable<T> DepthFirstSearch<T>(IReadOnlyGraph<T> graph, T source) where T : notnull

Parameters

graph IReadOnlyGraph<T>

The graph to traverse.

source T

The vertex at which traversal starts.

Returns

IEnumerable<T>

A lazily evaluated sequence of reachable vertices, beginning with source.

Type Parameters

T

The vertex type.

Examples

var graph = new Graph<int>(GraphKind.Directed);
graph.AddEdge(1, 2);
graph.AddEdge(1, 3);
graph.AddEdge(2, 4);

// Depth-first dives down one branch before backtracking, e.g. 1, 3, 2, 4.
var order = GraphAlgorithms.DepthFirstSearch(graph, 1).ToList();

Exceptions

ArgumentNullException

graph or source is null.

ArgumentException

source is not in the graph.

ShortestPathLengths<T>(IReadOnlyWeightedGraph<T>, T)

Computes the shortest distance from the specified source to every reachable vertex using Dijkstra's algorithm.

public static IReadOnlyDictionary<T, double> ShortestPathLengths<T>(IReadOnlyWeightedGraph<T> graph, T source) where T : notnull

Parameters

graph IReadOnlyWeightedGraph<T>

The graph to search.

source T

The starting vertex.

Returns

IReadOnlyDictionary<T, double>

A map from each reachable vertex to its shortest distance from source. Unreachable vertices are omitted.

Type Parameters

T

The vertex type.

Examples

var graph = new Graph<string>(GraphKind.Directed);
graph.AddEdge("A", "B", 1);
graph.AddEdge("B", "C", 2);

// Distance from A to every reachable vertex: { A: 0, B: 1, C: 3 }.
IReadOnlyDictionary<string, double> distances = GraphAlgorithms.ShortestPathLengths(graph, "A");

Exceptions

ArgumentNullException

graph or source is null.

ArgumentException

source is not in the graph, or a negative edge weight is encountered during the search (Dijkstra's algorithm requires non-negative weights).

ShortestPath<T>(IReadOnlyWeightedGraph<T>, T, T)

Computes the shortest path between two vertices using Dijkstra's algorithm over the non-negative edge weights.

public static IReadOnlyList<T> ShortestPath<T>(IReadOnlyWeightedGraph<T> graph, T source, T target) where T : notnull

Parameters

graph IReadOnlyWeightedGraph<T>

The graph to search.

source T

The starting vertex.

target T

The destination vertex.

Returns

IReadOnlyList<T>

The vertices of the shortest path from source to target inclusive, or an empty list when no path exists.

Type Parameters

T

The vertex type.

Examples

var graph = new Graph<string>(GraphKind.Directed);
graph.AddEdge("A", "B", 1);
graph.AddEdge("B", "C", 2);
graph.AddEdge("A", "C", 5);

// Cheapest route A -> B -> C (total 3) beats the direct A -> C (5).
var path = GraphAlgorithms.ShortestPath(graph, "A", "C"); // [A, B, C]

Remarks

This is a convenience wrapper over TryShortestPath<T>(IReadOnlyWeightedGraph<T>, T, T); use that overload when the path distance or a reachability flag is also needed.

Exceptions

ArgumentNullException

Any argument is null.

ArgumentException

source or target is not in the graph, or a negative edge weight is encountered during the search (Dijkstra's algorithm requires non-negative weights).

TopologicalSort<T>(IReadOnlyGraph<T>)

Produces a topological ordering of the vertices of a directed acyclic graph using Kahn's algorithm.

public static IReadOnlyList<T> TopologicalSort<T>(IReadOnlyGraph<T> graph) where T : notnull

Parameters

graph IReadOnlyGraph<T>

The directed graph to order.

Returns

IReadOnlyList<T>

The vertices in an order where every edge points from an earlier vertex to a later one.

Type Parameters

T

The vertex type.

Examples

var graph = new Graph<string>(GraphKind.Directed);
graph.AddEdge("a", "b");
graph.AddEdge("b", "c");
graph.AddEdge("c", "a");   // introduces a cycle

// Throws InvalidOperationException because the graph is cyclic.
var order = GraphAlgorithms.TopologicalSort(graph);

Exceptions

ArgumentNullException

graph is null.

InvalidOperationException

The graph is undirected, or it contains a cycle.

TryShortestPath<T>(IReadOnlyWeightedGraph<T>, T, T)

Attempts to compute the shortest path between two vertices using Dijkstra's algorithm, reporting the path, its total distance, and whether the target is reachable.

public static ShortestPathResult<T> TryShortestPath<T>(IReadOnlyWeightedGraph<T> graph, T source, T target) where T : notnull

Parameters

graph IReadOnlyWeightedGraph<T>

The graph to search.

source T

The starting vertex.

target T

The destination vertex.

Returns

ShortestPathResult<T>

A ShortestPathResult<TVertex> describing the path. When no path exists, the result is not found, its distance is PositiveInfinity, and its path is empty.

Type Parameters

T

The vertex type.

Examples

var graph = new Graph<string>(GraphKind.Directed);
graph.AddEdge("A", "B", 1);
graph.AddVertex("Z");   // present but unreachable from A

ShortestPathResult<string> result = GraphAlgorithms.TryShortestPath(graph, "A", "Z");
// result.Found is false, result.Distance is double.PositiveInfinity, result.Path is empty

Exceptions

ArgumentNullException

Any argument is null.

ArgumentException

source or target is not in the graph, or a negative edge weight is encountered during the search (Dijkstra's algorithm requires non-negative weights).

TryTopologicalSort<T>(IReadOnlyGraph<T>, out IReadOnlyList<T>)

Attempts to produce a topological ordering of the vertices of a directed graph.

public static bool TryTopologicalSort<T>(IReadOnlyGraph<T> graph, out IReadOnlyList<T> order) where T : notnull

Parameters

graph IReadOnlyGraph<T>

The directed graph to order.

order IReadOnlyList<T>

When this method returns, contains the topological ordering, or an empty list if the graph contains a cycle.

Returns

bool

true if an ordering was produced; false if the graph contains a cycle.

Type Parameters

T

The vertex type.

Examples

var graph = new Graph<string>(GraphKind.Directed);
graph.AddEdge("compile", "link");
graph.AddEdge("link", "run");

if (GraphAlgorithms.TryTopologicalSort(graph, out var order))
{
    // order respects every edge, e.g. compile, link, run.
}

Exceptions

ArgumentNullException

graph is null.

InvalidOperationException

The graph is undirected.

Applies to

Product	Versions
.NET	8, 10