Bodu.Collections.Generic.Graphs Namespace

Package: Bodu.Collections 1.0.0

Bodu.Collections.Generic.Graphs

Purpose

Bodu.Collections.Generic.Graphs is a small, self-contained graph toolkit in the Bodu.Collections package (which depends on Bodu.Core): a vertex-and-edge container, a static catalogue of classic graph algorithms, and a union-find (disjoint-set) structure. It is built for in-memory adjacency-list graphs of arbitrary vertex types - integers, strings, or your own value/reference types - with optional non-negative edge weights.

The container, Graph<T>, stores an adjacency map and is fixed as either directed or undirected at construction via GraphKind. The algorithms in GraphAlgorithms - breadth-first and depth-first traversal, Dijkstra shortest path, Kahn topological sort, and connected components - are decoupled from the container: they accept the read-only interfaces IReadOnlyGraph<TVertex> and IReadOnlyWeightedGraph<TVertex>, so they run over any conforming representation. The algorithms reuse the library's own primitives - Deque<T> for breadth-first frontiers and Kahn's ready queue, and IndexedPriorityQueue<TElement, TPriority> for Dijkstra relaxation - and evaluate iteratively so they do not overflow the stack on deep graphs.

Static documentation

Bodu.Collections introduction - the headline collections and where the graph types sit among them.
Graphs and graph algorithms - build a graph, run a traversal or shortest path, sort topologically, find components, and use union-find.

Key types

Graph container

Graph<T> - the adjacency-list graph. Construct with a GraphKind and an optional vertex comparer; mutate with AddVertex / RemoveVertex / AddEdge (unweighted or weighted) / TryAddEdge / RemoveEdge / Clear; query with Vertices, Neighbors, WeightedNeighbors, ContainsVertex, ContainsEdge, TryGetEdgeWeight, Degree, VertexCount, EdgeCount, and IsDirected. Implements IReadOnlyWeightedGraph<TVertex> (double weights).
GraphKind - Undirected (the default; an edge makes each vertex a neighbor of the other) or Directed (an edge does not imply its reverse).

Read-only views (algorithm inputs)

IReadOnlyGraph<TVertex> - the unweighted topology surface (IsDirected, VertexCount, EdgeCount, Comparer, Vertices, ContainsVertex, Neighbors, Degree) that traversal, topological sort, and connectivity accept.
IReadOnlyWeightedGraph<TVertex> - extends the above with WeightedNeighbors, ContainsEdge, and TryGetEdgeWeight; the input to the shortest-path algorithms.

Algorithms

GraphAlgorithms - a static class with BreadthFirstSearch / DepthFirstSearch (lazy reachability sequences), ShortestPath / TryShortestPath / ShortestPathLengths (Dijkstra over non-negative weights), TopologicalSort / TryTopologicalSort (Kahn's algorithm, directed graphs only), and ConnectedComponents (weakly connected components via union-find).
ShortestPathResult<TVertex> - the readonly record struct returned by TryShortestPath: Found, Distance, and Path.

Union-find (disjoint set)

DisjointSet<T> - an element-keyed union-find for arbitrary non-nullable keys: MakeSet / Add, Contains, Union, Find / TryFind, AreConnected, SizeOf, Clear, with an optional IEqualityComparer<T>. Path-halving compression with union by size, amortized near-constant per operation.

Example

using Bodu.Collections.Generic.Graphs;

// Build a small weighted directed graph; referenced vertices are created on demand.
var graph = new Graph<string>(GraphKind.Directed);
graph.AddEdge("A", "B", 1.0);
graph.AddEdge("B", "C", 2.0);
graph.AddEdge("A", "C", 5.0);

// Breadth-first reachability from A.
var reachable = GraphAlgorithms.BreadthFirstSearch(graph, "A").ToList();

// Cheapest route A -> B -> C (total 3) beats the direct A -> C (5).
ShortestPathResult<string> result = GraphAlgorithms.TryShortestPath(graph, "A", "C");
// result.Found is true, result.Distance is 3.0, result.Path is [A, B, C]

Notes

Directedness is fixed at construction. Choose GraphKind when you create the graph. In an undirected graph each edge is stored symmetrically, so one AddEdge makes both vertices mutual neighbors and EdgeCount counts the connection once.
Weights are finite and non-negative. Edges default to weight 1.0; AddEdge and TryAddEdge reject NaN, infinity, and negative weights with ArgumentOutOfRangeException. Algorithms that ignore weight treat the graph as unweighted. Dijkstra requires non-negative weights - there is no Bellman-Ford for negative edges.
Vertex identity follows the comparer. Pass an IEqualityComparer<T> at construction (for example, StringComparer.OrdinalIgnoreCase) to control how vertices are deduplicated; the same comparer flows into the algorithms' internal sets.
Algorithms take the interfaces, not the concrete graph. Because they accept IReadOnlyGraph<TVertex> / IReadOnlyWeightedGraph<TVertex>, you can run them over a custom graph representation as well as the built-in Graph<T>.
Topological sort is directed-only. TopologicalSort / TryTopologicalSort throw InvalidOperationException on an undirected graph; TopologicalSort additionally throws on a cycle, while TryTopologicalSort returns false and an empty list.
Connected components are weakly connected. ConnectedComponents treats every edge as undirected and partitions with a DisjointSet<T>; for a directed graph the result is the weakly connected components.
Not thread-safe. A Graph<T> is not safe for concurrent mutation; coordinate writes externally.
See also: the Bodu.Collections introduction and the graphs guide.

Classes

DisjointSet<T>: Provides an element-keyed disjoint-set (union-find) structure that tracks a partition of added elements into disjoint subsets and supports near-constant-time union and connectivity queries.

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

Graph<T>: Represents a graph of vertices connected by weighted edges, backed by an adjacency list and supporting either directed or undirected edge semantics.

Structs

ShortestPathResult<TVertex>: Represents the outcome of a shortest-path search: whether the target was reachable, the total distance, and the reconstructed path.

Interfaces

IReadOnlyGraph<TVertex>: Defines a read-only view over a vertex-and-edge graph: the topology queries the graph algorithms depend on, independent of how the graph is stored.

IReadOnlyWeightedGraph<TVertex>: Defines a read-only view over a graph whose edges carry double weights, extending IReadOnlyGraph<TVertex> with weight queries.

Enums

GraphKind: Specifies whether a Graph<T> treats its edges as directed or undirected.

Table of Contents