tpt-math-graph
Graph mathematics for the tpt-math substrate.
- Thin wrap over
petgraph(dualApache-2.0 OR MIT,no_std+alloc): adjacency structures (Graph/StableGraph/GraphMap), directions (Directed/Undirected),NodeIndex/EdgeIndex, and topological sort (toposort). - In-house max-flow (
max_flow, Edmonds–Karp) built on top of the wrapped directedGraphwithf64edge capacities —petgraphhas no built-in max-flow (an upstream feature request has been open since 2021). - In-house shortest-path helpers (
dijkstra,astar) with ano_std-safe implementation (onstdthey delegate topetgraph's algorithms).dijkstraandastarpanic on negative or NaN weights.try_dijkstraandtry_astarreturnResultwithGraphError::InvalidWeightinstead.dijkstra_pathreturns the node route as well as the cost. - Traversal and structure —
bfs_orderanddfs_order(preorder),has_path,is_cyclic,connected_components(weakly connected for directed graphs),strongly_connected_components(Tarjan) andminimum_spanning_tree(Kruskal, returned as(source, target, weight)triples). These are thin wraps overpetgraph.
max_flow rejects negative, NaN or infinite capacities.
Usage
use ;
let mut g: = new;
let s = g.add_node;
let t = g.add_node;
let a = g.add_node;
g.add_edge;
g.add_edge;
let mf = max_flow.unwrap;
assert_eq!;
Features
std(default) — enable thestdsupport of dependencies.alloc— signal allocator availability (the algorithms need it).
License
Dual-licensed under either of MIT or Apache-2.0 at your option.