Expand description
Discrete graph algorithms.
This crate hosts graph value types, traversal, connectivity, MST, shortest paths, minimum-cost bipartite assignment, staged dynamic programming, edit/DTW alignment, the graph <-> matrix bridge, and certificate-producing verifiers. Expensive assignment and dynamic-programming APIs expose explicit cell/edge work, memory, deadline, and cancellation control. All-pairs shortest paths and reachability are thin wrappers over the algebra spine’s semiring closure, never re-implemented here.
Boundary: depends on sim-lib-discrete-algebra; never on sim-lib-rank.
Re-exports§
pub use alignment::Alignment;pub use alignment::AlignmentBoundary;pub use alignment::AlignmentCell;pub use alignment::AlignmentCertificate;pub use alignment::AlignmentMemory;pub use alignment::AlignmentMove;pub use alignment::AlignmentStep;pub use alignment::AlignmentWindow;pub use alignment::DtwPolicy;pub use alignment::GapPolicy;pub use alignment::dynamic_time_warp;pub use alignment::dynamic_time_warp_with_control;pub use alignment::verify_alignment;pub use assignment::Assignment;pub use assignment::AssignmentCertificate;pub use assignment::AssignmentCost;pub use assignment::AssignmentOperation;pub use assignment::AssignmentPolicy;pub use assignment::CostMatrix;pub use assignment::DoublingPolicy;pub use assignment::VoiceCrossingPolicy;pub use assignment::min_cost_assignment;pub use assignment::min_cost_assignment_with_control;pub use assignment::verify_assignment;pub use bridge::GraphMatrixMap;pub use bridge::MultiedgePolicy;pub use bridge::graph_to_bool_adjacency;pub use bridge::graph_to_incidence;pub use bridge::graph_to_laplacian;pub use bridge::graph_to_minplus_adjacency;pub use bridge::graph_to_sparse_adjacency;pub use bridge::minplus_adjacency_to_graph;pub use cards::CardSpec;pub use certificate::MstCertificate;pub use certificate::ShortestPathCertificate;pub use certificate::SpanningTree;pub use certificate::verify_mst;pub use certificate::verify_shortest_paths;pub use connectivity::connected_components;pub use connectivity::strongly_connected_components;pub use connectivity::weakly_connected_components;pub use control::AlgorithmControl;pub use control::AlgorithmInterrupt;pub use control::AlgorithmReceipt;pub use control::AlgorithmWorkCosts;pub use control::NeverInterrupt;pub use cookbook::AlignmentCompositionDemo;pub use cookbook::TinyGraphDemo;pub use cookbook::alignment_composition_demo;pub use cookbook::tiny_graph_demo;pub use cost::FiniteCost;pub use edge::Directedness;pub use edge::Edge;pub use error::GraphError;pub use graph::Graph;pub use graph::Neighbor;pub use intring::IntRing;pub use layered::LayeredCell;pub use layered::LayeredCertificate;pub use layered::LayeredPath;pub use layered::layered_shortest_path;pub use layered::layered_shortest_path_with_control;pub use layered::verify_layered_path;pub use mst::MstWeight;pub use mst::kruskals_mst;pub use mst::prims_mst;pub use path::PathResult;pub use path::ShortestPath;pub use path::all_pairs_shortest_paths;pub use path::bellman_ford;pub use path::dijkstra;pub use path::reachability;pub use path::shortest_path;pub use traversal::Traversal;pub use traversal::bfs;pub use traversal::dfs;
Modules§
- alignment
- Certified dynamic-time-warp and edit alignment.
- assignment
- Certified minimum-cost bipartite assignment.
- bridge
- Graph <-> matrix conversions: adjacency (boolean, min-plus, sparse), incidence, and Laplacian, with explicit multiedge policies and a mapping witness.
- cards
- Browse/help card content for the graph family, as kernel-free static data.
- certificate
- Verifiable certificates for MST and shortest-path results.
- connectivity
- Connected components (undirected / weak) and strongly connected components.
- control
- Work, memory, deadline, and cancellation control for graph algorithms.
- cookbook
- Deterministic cookbook builders for discrete graph recipes.
- cost
- Finite additive costs shared by graph dynamic programs.
- edge
- Edge records and graph directedness.
- error
- Error type for discrete graph algorithms.
- graph
- The weighted graph value type and its adjacency expansion.
- intring
- A plain integer ring as a
Semiring, for signed structural matrices. - layered
- Certified shortest paths through staged state layers.
- mst
- Minimum spanning tree via Prim’s and Kruskal’s algorithms.
- path
- Shortest paths: single-source Dijkstra and Bellman-Ford, checked all-pairs shortest paths, and reachability over the algebra spine’s semiring closure.
- traversal
- Deterministic breadth-first and depth-first traversal.
Statics§
- RECIPES
- Cookbook recipes for this lib, embedded at build time.