Skip to main content

Crate tpt_math_graph

Crate tpt_math_graph 

Source
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

§Features

  • std (default) — enable the std support 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§

EdgeIndex
Edge identifier.
Graph
Graph<N, E, Ty, Ix> is a graph datastructure using an adjacency list representation.
GraphMap
GraphMap<N, E, Ty> is a graph datastructure using an associative array of its node weights N.
MaxFlow
The result of a max_flow computation.
NodeIndex
Node identifier.
StableGraph
StableGraph<N, E, Ty, Ix> is a graph datastructure using an adjacency list representation.

Enums§

Directed
Marker type for a directed graph.
GraphError
Errors returned by the graph algorithms in this crate.
Undirected
Marker type for an undirected graph.

Functions§

astar
A* shortest path from start to the first node satisfying is_goal, using edge weights as costs and heuristic as the admissible estimate. Returns (cost, path) or None if no path exists.
bfs_order
Nodes reachable from start in breadth-first order, start first.
connected_components
The number of connected components of an undirected graph.
dfs_order
Nodes reachable from start in depth-first (preorder) order, start first.
dijkstra
Shortest-path distance from source to target via Dijkstra, using edge weights as non-negative costs. Returns None if target is unreachable.
dijkstra_path
Shortest path from source to target, as its total cost and the node sequence source, …, target.
has_path
Whether a directed path from from to to exists (from == to is true).
is_cyclic
Whether the directed graph contains a cycle.
max_flow
Compute the maximum flow from source to sink in a directed Graph whose 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§

AStarPath
The cost and node sequence of a shortest path found by A*.
ShortestPath
A path as its total cost and the node sequence from source to target.