Expand description
Graph mathematics for the tpt-math substrate.
tpt-math-graph wraps petgraph (dual Apache-2.0 OR MIT, no_std +
alloc) for the adjacency structures, topological sort and shortest-path
algorithms, and builds the max-flow solver in-house on top (petgraph
has no built-in max-flow — an upstream feature request has been open since
2021).
§Wrap-vs-in-house split
- Thin wrap —
Graph,StableGraph,GraphMap,NodeIndex,EdgeIndex,Directed/Undirected, andtoposortare re-exported directly frompetgraph. - In-house —
max_flow(Edmonds–Karp) is implemented here, operating onpetgraph’s directedGraphwithf64edge capacities.
§Features
std(default) — enable thestdsupport of dependencies.alloc— signal allocator availability (the algorithms need it).
§Examples
use tpt_math_graph::{Graph, Directed, NodeIndex};
let mut g: Graph<&str, f64> = Graph::new();
let a = g.add_node("a");
let b = g.add_node("b");
g.add_edge(a, b, 1.0);
assert_eq!(g.node_count(), 2);Re-exports§
pub use petgraph;
Structs§
- Edge
Index - Edge identifier.
- Graph
Graph<N, E, Ty, Ix>is a graph datastructure using an adjacency list representation.- Graph
Map GraphMap<N, E, Ty>is a graph datastructure using an associative array of its node weightsN.- MaxFlow
- The result of a
max_flowcomputation. - Node
Index - Node identifier.
- Stable
Graph StableGraph<N, E, Ty, Ix>is a graph datastructure using an adjacency list representation.
Enums§
- Directed
- Marker type for a directed graph.
- Graph
Error - Errors returned by the graph algorithms in this crate.
- Undirected
- Marker type for an undirected graph.
Functions§
- astar
- A* shortest path from
startto the first node satisfyingis_goal, using edge weights as costs andheuristicas the admissible estimate. Returns(cost, path)orNoneif no path exists. - bfs_
order - Nodes reachable from
startin breadth-first order,startfirst. - connected_
components - The number of connected components of an undirected graph.
- dfs_
order - Nodes reachable from
startin depth-first (preorder) order,startfirst. - dijkstra
- Shortest-path distance from
sourcetotargetvia Dijkstra, using edge weights as non-negative costs. ReturnsNoneiftargetis unreachable. - dijkstra_
path - Shortest path from
sourcetotarget, as its total cost and the node sequencesource, …, target. - has_
path - Whether a directed path from
fromtotoexists (from == toistrue). - is_
cyclic - Whether the directed graph contains a cycle.
- max_
flow - Compute the maximum flow from
sourcetosinkin a directedGraphwhose edge weights are capacities (f64). - minimum_
spanning_ tree - A minimum spanning forest, as
(source, target, weight)triples. - strongly_
connected_ components - The strongly connected components of a directed graph, in reverse topological order of the condensation (Tarjan’s algorithm).
- toposort
- Perform a topological sort of a directed graph.
- try_
astar - Fallible
astar. - try_
dijkstra - Fallible
dijkstra.
Type Aliases§
- AStar
Path - The cost and node sequence of a shortest path found by A*.
- Shortest
Path - A path as its total cost and the node sequence from source to target.