Expand description
Discrete graph algorithms.
This crate hosts graph value types, traversal, connectivity, MST, shortest paths, the graph <-> matrix bridge, and certificate-producing verifiers. 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 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 edge::Directedness;pub use edge::Edge;pub use error::GraphError;pub use graph::Graph;pub use graph::Neighbor;pub use intring::IntRing;pub use mst::kruskals_mst;pub use mst::prims_mst;pub use path::PathResult;pub use path::all_pairs_shortest_paths;pub use path::bellman_ford;pub use path::dijkstra;pub use path::reachability;pub use traversal::Traversal;pub use traversal::bfs;pub use traversal::dfs;
Modules§
- 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.
- 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. - mst
- Minimum spanning tree via Prim’s and Kruskal’s algorithms.
- path
- Shortest paths: single-source Dijkstra and Bellman-Ford, plus all-pairs and reachability as thin wrappers over the algebra spine’s semiring closure.
- traversal
- Deterministic breadth-first and depth-first traversal.