sim-lib-discrete-graph 0.1.0-rc.1

Discrete graph algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#![forbid(unsafe_code)]
#![deny(missing_docs)]
//! 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`.

pub mod bridge;
pub mod cards;
pub mod certificate;
pub mod connectivity;
pub mod edge;
pub mod error;
pub mod graph;
pub mod intring;
pub mod mst;
pub mod path;
pub mod traversal;
mod unionfind;

pub use bridge::{
    GraphMatrixMap, MultiedgePolicy, graph_to_bool_adjacency, graph_to_incidence,
    graph_to_laplacian, graph_to_minplus_adjacency, graph_to_sparse_adjacency,
    minplus_adjacency_to_graph,
};
pub use cards::CardSpec;
pub use certificate::{
    MstCertificate, ShortestPathCertificate, SpanningTree, verify_mst, verify_shortest_paths,
};
pub use connectivity::{
    connected_components, strongly_connected_components, weakly_connected_components,
};
pub use edge::{Directedness, Edge};
pub use error::GraphError;
pub use graph::{Graph, Neighbor};
pub use intring::IntRing;
pub use mst::{kruskals_mst, prims_mst};
pub use path::{PathResult, all_pairs_shortest_paths, bellman_ford, dijkstra, reachability};
pub use traversal::{Traversal, bfs, dfs};