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 paths,
6//! the graph <-> matrix bridge, and certificate-producing verifiers. All-pairs
7//! shortest paths and reachability are thin wrappers over the algebra spine's
8//! semiring closure, never re-implemented here.
9//!
10//! Boundary: depends on `sim-lib-discrete-algebra`; never on `sim-lib-rank`.
11
12pub mod bridge;
13pub mod cards;
14pub mod certificate;
15pub mod connectivity;
16pub mod edge;
17pub mod error;
18pub mod graph;
19pub mod intring;
20pub mod mst;
21pub mod path;
22pub mod traversal;
23mod unionfind;
24
25pub use bridge::{
26    GraphMatrixMap, MultiedgePolicy, graph_to_bool_adjacency, graph_to_incidence,
27    graph_to_laplacian, graph_to_minplus_adjacency, graph_to_sparse_adjacency,
28    minplus_adjacency_to_graph,
29};
30pub use cards::CardSpec;
31pub use certificate::{
32    MstCertificate, ShortestPathCertificate, SpanningTree, verify_mst, verify_shortest_paths,
33};
34pub use connectivity::{
35    connected_components, strongly_connected_components, weakly_connected_components,
36};
37pub use edge::{Directedness, Edge};
38pub use error::GraphError;
39pub use graph::{Graph, Neighbor};
40pub use intring::IntRing;
41pub use mst::{kruskals_mst, prims_mst};
42pub use path::{PathResult, all_pairs_shortest_paths, bellman_ford, dijkstra, reachability};
43pub use traversal::{Traversal, bfs, dfs};
44
45/// Cookbook recipes for this lib, embedded at build time.
46pub static RECIPES: sim_cookbook::EmbeddedDir =
47    include!(concat!(env!("OUT_DIR"), "/cookbook_recipes.rs"));
sim_lib_discrete_graph/lib.rs

sim_lib_discrete_graph/
lib.rs
