Module prelude 

Brings the entire graph-rs public API into scope.

use graph::prelude::*;

Modules

astar

A* goal-directed shortest path with a caller-supplied heuristic.

bellman_ford

Bellman-Ford single-source shortest path; handles negative weights.

bfs

Breadth-first search with distances and BFS tree.

bipartite

Bipartite check and 2-colouring via BFS.

bridges

Bridge finding (cut edges) via Tarjan’s DFS disc/low-link algorithm.

components

Connected components via BFS seeding.

condensation

DAG condensation: contract each SCC into a single super-node.

cycle

Cycle detection for directed and undirected graphs.

dfs

Recursive and iterative depth-first search.

dijkstra

Dijkstra’s single-source shortest path for non-negative weights.

edmonds_karp

Edmonds-Karp maximum flow using BFS augmenting paths. Edmonds-Karp maximum flow via BFS augmenting paths.

euler

Euler path and circuit via Hierholzer’s algorithm.

flow_graph

Index-based flow graph (residual graph) used by all flow algorithms. Index-based residual graph for flow algorithms.

floyd_warshall

Floyd-Warshall all-pairs shortest path.

ford_fulkerson

Ford-Fulkerson maximum flow using DFS augmenting paths. Ford-Fulkerson maximum flow via DFS augmenting paths.

hamiltonian

Hamiltonian path via backtracking (exact, exponential).

hopcroft_karp

Hopcroft-Karp maximum bipartite matching. Hopcroft-Karp maximum bipartite matching.

kosaraju_scc

Kosaraju’s two-pass SCC algorithm.

kruskal

Kruskal’s minimum spanning tree: sort edges, union-find cycle check.

min_cut

Minimum s-t cut extracted from a completed max-flow computation. Minimum s-t cut from a completed max-flow computation.

paths

Path reconstruction from BFS/DFS parent maps.

prim

Prim’s minimum spanning tree: priority-queue edge relaxation.

tarjan_scc

Tarjan’s single-pass SCC algorithm using DFS low-link values.

topo

Topological sort: DFS finish-order and Kahn’s algorithm.

tsp

Travelling Salesman Problem via Held-Karp bitmask DP.

Structs

AdjacencyList

A sparse graph representation backed by an adjacency list.

AdjacencyMatrix

A dense graph representation backed by a 2-D adjacency matrix.

BellmanFordResult

Result of a Bellman-Ford shortest-path search.

CondensedGraph

The result of condensing a directed graph into its SCC DAG.

Deque

A double-ended queue (deque) backed by VecDeque.

DijkstraResult

Result of a Dijkstra shortest-path search from one source node.

DisjointSet

Union-Find (disjoint set union) with union-by-rank.

Edge

A directed edge from source to target carrying a weight of type W.

EdgeId

A type-safe edge identifier.

FlowGraph

An index-based directed flow network supporting residual graph operations.

GraphBuilder

A fluent builder for constructing graphs from either representation.

MinCut

The result of a minimum s-t cut computation.

MinHeap

A binary min-heap backed by a Vec.

NodeId

A type-safe node identifier.

PriorityQueue

A keyed priority queue that pops by lowest priority first.

Queue

A FIFO queue backed by VecDeque.

SpanningTree

The result of a minimum spanning tree computation.

Stack

A LIFO stack backed by a Vec.

Enums

EulerError

Errors returned by Euler path/circuit algorithms.

GraphError

Errors that can arise from graph operations.

Traits

Graph

The central graph abstraction that every algorithm in graph-rs operates on.

Functions

articulation_points

Finds all articulation points (cut vertices) in an undirected graph.

astar

Finds the shortest path from start to goal using the A* search algorithm with a caller-supplied heuristic function.

bellman_ford

Runs the Bellman-Ford algorithm from source.

bfs

Runs a breadth-first search from start and returns a map of NodeId → shortest hop distance from start.

bfs_tree

Runs BFS from start and returns a BfsTree with distances and parents.

bridges

Finds all bridges in an undirected graph using Tarjan’s algorithm.

condensation

Condenses a directed graph into its SCC DAG.

connected_components

Returns all connected components of the graph as a Vec<Vec<NodeId>>.

dfs_iterative

Runs an iterative depth-first search from start using an explicit Stack, calling visitor the first time each node is discovered.

dfs_recursive

Runs a recursive depth-first search from start, calling visitor the first time each node is discovered.

dijkstra

Runs Dijkstra’s algorithm from source and returns shortest distances and the parent map.

edmonds_karp

Computes the maximum flow from source to sink using the Edmonds-Karp algorithm (Ford-Fulkerson with BFS augmenting paths).

euler_circuit

Finds an Euler circuit in an undirected graph using Hierholzer’s algorithm.

euler_path

Finds an Euler path in an undirected graph using Hierholzer’s algorithm.

floyd_warshall

Runs the Floyd-Warshall all-pairs shortest-path algorithm.

ford_fulkerson

Computes the maximum flow from source to sink using the Ford-Fulkerson algorithm with DFS augmenting paths.

hamiltonian_path

Finds a Hamiltonian path starting from start using backtracking.

has_cycle_directed

Returns true if the directed graph contains at least one cycle.

has_cycle_undirected

Returns true if the undirected graph contains at least one cycle.

hopcroft_karp

Computes the maximum bipartite matching using the Hopcroft-Karp algorithm.

is_bipartite

Checks whether the graph is bipartite and returns its 2-colouring.

kosaraju_scc

Finds all Strongly Connected Components (SCCs) using Kosaraju’s algorithm.

kruskal

Computes a Minimum Spanning Tree using Kruskal’s algorithm.

min_cut

Computes the minimum s-t cut from a FlowGraph on which a max-flow algorithm has already been run.

prim

Computes a Minimum Spanning Tree using Prim’s algorithm.

reconstruct_path

Reconstructs the path from start to end using a parent map produced by BFS or DFS.

tarjan_scc

Finds all Strongly Connected Components (SCCs) using Tarjan’s algorithm.

topological_sort_dfs

Returns a topological ordering of the nodes using DFS finish order.

topological_sort_kahn

Returns a topological ordering using Kahn’s algorithm (in-degree BFS).

tsp_held_karp

Solves the Travelling Salesman Problem exactly using the Held-Karp bitmask dynamic programming algorithm.

Type Aliases

UnweightedEdge

An unweighted directed edge (weight type ()).

WeightedEdge

A weighted directed edge with f64 weights.