sim_lib_discrete_graph/
lib.rs

1#![forbid(unsafe_code)]
2#![deny(missing_docs)]
3//! Discrete graph algorithms.
4//!
5//! This crate hosts graph value types, traversal, connectivity, MST, shortest
6//! paths, minimum-cost bipartite assignment, staged dynamic programming,
7//! edit/DTW alignment, the graph <-> matrix bridge, and certificate-producing
8//! verifiers. Expensive assignment and dynamic-programming APIs expose explicit
9//! cell/edge work, memory, deadline, and cancellation control. All-pairs
10//! shortest paths and reachability are thin wrappers over the algebra spine's
11//! semiring closure, never re-implemented here.
12//!
13//! Boundary: depends on `sim-lib-discrete-algebra`; never on `sim-lib-rank`.
14
15pub mod alignment;
16pub mod assignment;
17pub mod bridge;
18pub mod cards;
19pub mod certificate;
20pub mod connectivity;
21pub mod control;
22pub mod cookbook;
23pub mod cost;
24pub mod edge;
25pub mod error;
26pub mod graph;
27pub mod intring;
28pub mod layered;
29pub mod mst;
30pub mod path;
31pub mod traversal;
32mod unionfind;
33
34pub use alignment::{
35    Alignment, AlignmentBoundary, AlignmentCell, AlignmentCertificate, AlignmentMemory,
36    AlignmentMove, AlignmentStep, AlignmentWindow, DtwPolicy, GapPolicy, dynamic_time_warp,
37    dynamic_time_warp_with_control, verify_alignment,
38};
39pub use assignment::{
40    Assignment, AssignmentCertificate, AssignmentCost, AssignmentOperation, AssignmentPolicy,
41    CostMatrix, DoublingPolicy, VoiceCrossingPolicy, min_cost_assignment,
42    min_cost_assignment_with_control, verify_assignment,
43};
44pub use bridge::{
45    GraphMatrixMap, MultiedgePolicy, graph_to_bool_adjacency, graph_to_incidence,
46    graph_to_laplacian, graph_to_minplus_adjacency, graph_to_sparse_adjacency,
47    minplus_adjacency_to_graph,
48};
49pub use cards::CardSpec;
50pub use certificate::{
51    MstCertificate, ShortestPathCertificate, SpanningTree, verify_mst, verify_shortest_paths,
52};
53pub use connectivity::{
54    connected_components, strongly_connected_components, weakly_connected_components,
55};
56pub use control::{
57    AlgorithmControl, AlgorithmInterrupt, AlgorithmReceipt, AlgorithmWorkCosts, NeverInterrupt,
58};
59pub use cookbook::{
60    AlignmentCompositionDemo, TinyGraphDemo, alignment_composition_demo, tiny_graph_demo,
61};
62pub use cost::FiniteCost;
63pub use edge::{Directedness, Edge};
64pub use error::GraphError;
65pub use graph::{Graph, Neighbor};
66pub use intring::IntRing;
67pub use layered::{
68    LayeredCell, LayeredCertificate, LayeredPath, layered_shortest_path,
69    layered_shortest_path_with_control, verify_layered_path,
70};
71pub use mst::{MstWeight, kruskals_mst, prims_mst};
72pub use path::{
73    PathResult, ShortestPath, all_pairs_shortest_paths, bellman_ford, dijkstra, reachability,
74    shortest_path,
75};
76pub use traversal::{Traversal, bfs, dfs};
77
78/// Cookbook recipes for this lib, embedded at build time.
79pub static RECIPES: sim_cookbook::EmbeddedDir =
80    include!(concat!(env!("OUT_DIR"), "/cookbook_recipes.rs"));
sim_lib_discrete_graph/lib.rs

sim_lib_discrete_graph/
lib.rs
