Namespace Graph1x.Algorithms
Classes
- AStarShortestPath<TVertex, TEdge, TWeight>
The A* shortest-path algorithm: Dijkstra guided by a caller-supplied heuristic estimating the remaining distance to the target. The heuristic must be consistent (never overestimate, and satisfy the triangle inequality) for the result to be optimal; a zero heuristic degrades to plain Dijkstra. Requires non-negative edge weights.
- AllPairsShortestPaths<TVertex, TWeight>
The result of a Floyd-Warshall computation: shortest distances and paths between every pair of vertices, queryable via Between(TVertex, TVertex).
- BellmanFordShortestPath<TVertex, TEdge, TWeight>
The Bellman-Ford shortest-path algorithm. Supports negative edge weights; throws NegativeCycleException when a negative cycle is reachable from the source. On undirected graphs each edge acts as two opposite arcs, so any negative undirected edge is itself a negative cycle.
- CondensationResult<TVertex>
The condensation of a directed graph: every strongly connected component collapsed into one integer vertex, yielding a DAG. Component indexes follow Tarjan's reverse-topological emission order, so every condensation edge points from a higher index to a lower one.
- DijkstraShortestPath<TVertex, TEdge, TWeight>
Dijkstra's shortest-path algorithm over a PriorityQueue<TElement, TPriority>. Requires non-negative edge weights; throws NegativeWeightException otherwise.
- DinicMaximumFlow<TVertex, TEdge, TWeight>
Dinic's maximum-flow algorithm: repeated BFS level graphs, each saturated by a blocking flow found with cursor-guided depth-first walks. O(V²·E) in general and substantially faster than Edmonds-Karp on large or dense networks (O(E·√V) on unit-capacity graphs); interchangeable with it behind IMaximumFlowAlgorithm<TVertex, TEdge, TWeight>.
- EdmondsKarpMaximumFlow<TVertex, TEdge, TWeight>
The Edmonds-Karp maximum-flow algorithm: Ford-Fulkerson with breadth-first augmenting paths, giving O(V·E²) independently of capacity values. With floating-point capacities, tiny rounding residues are possible — integer or decimal capacities are exact. For large or dense networks consider DinicMaximumFlow<TVertex, TEdge, TWeight>.
- FloydWarshallAllShortestPaths<TVertex, TEdge, TWeight>
The Floyd-Warshall all-pairs shortest-path algorithm. Supports negative edge weights; throws NegativeCycleException when any negative cycle exists. Reachability is tracked explicitly, so weight types without an infinity value (int, decimal, ...) work unchanged.
- GraphCentralityExtensions
Centrality measures: degree, closeness (Wasserman-Faust scaled, so disconnected graphs need no special casing), betweenness via Brandes' algorithm (breadth-first for hop counts, Dijkstra-based for weights, which requires strictly positive weights), PageRank for directed graphs, and the spectral pair — eigenvector and Katz — by power iteration. On multigraphs, parallel edges count as distinct shortest paths, which is the natural multigraph semantics.
- GraphCliqueExtensions
Maximal clique enumeration via Bron–Kerbosch with Tomita pivoting. Edge direction is ignored, self-loops never count, and on multigraphs neighbors are counted once regardless of parallel edges.
- GraphClusteringExtensions
Clustering coefficients: how close each vertex's neighborhood is to a clique. Edge direction is ignored, self-loops never count, and on multigraphs neighbors are counted once regardless of parallel edges.
- GraphColoringExtensions
Heuristic vertex coloring using DSatur (Brélaz): color the vertex with the highest saturation (most distinct neighbor colors) first, breaking ties by degree. Exact on bipartite graphs; an upper bound in general — computing the chromatic number exactly is NP-hard and out of scope.
- GraphColoring<TVertex>
A proper vertex coloring: adjacent vertices always receive different colors. Colors are contiguous integers starting at zero, and ColorCount is an upper bound on the chromatic number.
- GraphCondensationExtensions
Condensation: collapse each strongly connected component to a single vertex, producing a DAG on which DAG-only tools (topological sort, transitive reduction) become applicable to any directed graph.
- GraphConnectivityExtensions
Connectivity queries: connected components (edge direction ignored), weak connectivity for directed graphs, and strongly connected components via an iterative Tarjan algorithm.
- GraphCycleException
Thrown when an operation that requires an acyclic graph (such as topological sorting) encounters a cycle.
- GraphCycleExtensions
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).
- GraphDagPathExtensions
Shortest, longest, and critical paths on directed acyclic graphs: one topological pass with edge relaxation, so negative weights are fine (this is the fast answer when Dijkstra rejects them with NegativeWeightException). Cyclic input throws GraphCycleException.
- GraphDistanceExtensions
Distance metrics: eccentricity, diameter, radius, center, periphery, and average path length, computed from Dijkstra single-source runs. The graph must be connected (strongly connected when directed) — infinite distances are rejected up front instead of being encoded as sentinel values. Weighted overloads take a selector; the default counts hops.
- GraphEulerianExtensions
Eulerian trails: paths and circuits that use every edge exactly once. Existence follows the classic degree conditions (balanced in/out degrees for directed graphs; zero or two odd-degree vertices for undirected ones) plus a single edge-bearing component; construction is an iterative Hierholzer walk. Multigraphs are fully supported — parallel edges are tracked by instance, which is exactly the Königsberg setting.
- GraphMatchingExtensions
Convenience entry points for matching queries.
- GraphMaximumFlowExtensions
Convenience entry points for maximum-flow queries, defaulting to Edmonds-Karp.
- GraphMinimumSpanningTreeExtensions
Convenience entry points for minimum-spanning-forest queries. These default to Kruskal; instantiate PrimMinimumSpanningTree<TVertex, TEdge, TWeight> directly to use Prim.
- GraphOperationsExtensions
Graph set operations: induced subgraphs, unions, and complements. Every operation returns a new graph matching the source's direction and parallel-edge policy (comparer included); the inputs are never mutated.
- GraphShortestPathExtensions
Convenience entry points for shortest-path queries. These default to Dijkstra; instantiate BellmanFordShortestPath<TVertex, TEdge, TWeight>, AStarShortestPath<TVertex, TEdge, TWeight>, or FloydWarshallAllShortestPaths<TVertex, TEdge, TWeight> directly when negative weights, a heuristic, or all-pairs results are needed.
- GraphStructureExtensions
Structural queries: density, degree sequence, bipartiteness, and transpose.
- GraphTopologicalSortExtensions
Topological ordering of directed acyclic graphs using Kahn's algorithm.
- GraphTraversalExtensions
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.
- HopcroftKarpMatching<TVertex, TEdge>
The Hopcroft-Karp maximum-cardinality matching algorithm for undirected bipartite graphs, running in O(E·√V) by augmenting along maximal sets of shortest vertex-disjoint paths per phase. The bipartition is derived automatically; non-bipartite input is rejected. No strategy interface is introduced: with a single matching algorithm there is no swap point to justify one.
- KruskalMinimumSpanningTree<TVertex, TEdge, TWeight>
Kruskal's minimum-spanning-tree algorithm: edges are considered in ascending weight order and accepted when they join two different components, tracked with a union-find structure. Naturally yields a spanning forest on disconnected graphs; negative weights are fine.
- MaximumFlowResult<TVertex, TEdge, TWeight>
The outcome of a maximum-flow computation: the flow value, the flow carried by every edge, and a minimum source/sink cut certifying optimality (its capacity equals the flow value).
- NegativeCycleException
Thrown when a shortest-path computation detects a negative-weight cycle, which makes shortest distances undefined for the affected vertices.
- NegativeWeightException
Thrown when an edge weight falls outside the domain an algorithm requires: a negative weight where non-negative ones are needed (Dijkstra, A*, maximum flow), or a non-positive weight where strictly positive ones are needed (weighted betweenness centrality).
- PrimMinimumSpanningTree<TVertex, TEdge, TWeight>
Prim's minimum-spanning-tree algorithm (lazy variant): each tree grows from a root by repeatedly taking the cheapest edge crossing the frontier, using a priority queue. Every connected component gets its own tree, so disconnected graphs yield a spanning forest; negative weights are fine.
- ShortestPathResult<TVertex, TWeight>
The outcome of a shortest-path query: whether the target is reachable, the total distance, and the vertex path from source to target.
- SingleSourceShortestPaths<TVertex, TWeight>
The result of a single-source shortest-path computation: distances and a predecessor tree from one source to every reachable vertex, queryable per target without re-running the algorithm. The result is a snapshot of the graph at computation time.
Interfaces
- IMaximumFlowAlgorithm<TVertex, TEdge, TWeight>
A maximum-flow strategy for directed graphs with non-negative edge capacities. Implementations compute the maximum flow from a source to a sink together with a certifying minimum cut.
- IMinimumSpanningTreeAlgorithm<TVertex, TEdge, TWeight>
A minimum-spanning-tree strategy for undirected graphs. On disconnected graphs implementations return a minimum spanning forest (one tree per connected component). Kruskal and Prim are interchangeable behind this interface.
- IShortestPathAlgorithm<TVertex, TEdge, TWeight>
A single-pair shortest-path strategy. Implementations (Dijkstra, Bellman-Ford, A*) are interchangeable behind this interface; pick by the graph's weight profile (non-negative, negative edges, heuristic available).