tpt-math-graph 0.2.0

Graph mathematics for the tpt-math substrate. Thin wrap over petgraph (dual Apache-2.0 OR MIT, no_std + alloc) for adjacency / topological sort / shortest paths, plus an in-house max-flow solver.
Documentation

tpt-math-graph

Graph mathematics for the tpt-math substrate.

  • Thin wrap over petgraph (dual Apache-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 directed Graph with f64 edge capacities — petgraph has no built-in max-flow (an upstream feature request has been open since 2021).
  • In-house shortest-path helpers (dijkstra, astar) with a no_std-safe implementation (on std they delegate to petgraph's algorithms). dijkstra and astar panic on negative or NaN weights. try_dijkstra and try_astar return Result with GraphError::InvalidWeight instead. dijkstra_path returns the node route as well as the cost.
  • Traversal and structure — bfs_order and dfs_order (preorder), has_path, is_cyclic, connected_components (weakly connected for directed graphs), strongly_connected_components (Tarjan) and minimum_spanning_tree (Kruskal, returned as (source, target, weight) triples). These are thin wraps over petgraph.

max_flow rejects negative, NaN or infinite capacities.

Usage

use tpt_math_graph::{Graph, Directed, NodeIndex, max_flow};

let mut g: Graph<&str, f64> = Graph::new();
let s = g.add_node("s");
let t = g.add_node("t");
let a = g.add_node("a");
g.add_edge(s, a, 3.0);
g.add_edge(a, t, 3.0);
let mf = max_flow(&g, s, t).unwrap();
assert_eq!(mf.value, 3.0);

Features

  • std (default) — enable the std support of dependencies.
  • alloc — signal allocator availability (the algorithms need it).

License

Dual-licensed under either of MIT or Apache-2.0 at your option.