graph_advanced/lib.rs
1#![warn(missing_docs)]
2
3//! # graph-advanced
4//!
5//! Advanced graph algorithms built on [`graph_core`]'s [`Graph`] trait.
6//!
7//! ## Algorithms
8//!
9//! | Module | Algorithm | Complexity |
10//! |---------------------|--------------------------------------------|-------------------|
11//! | [`mod@tarjan_scc`] | Tarjan's Strongly Connected Components | O(V + E) |
12//! | [`mod@kosaraju_scc`] | Kosaraju's SCC (two-pass DFS) | O(V + E) |
13//! | [`mod@condensation`] | DAG condensation of SCC graph | O(V + E) |
14//! | [`mod@euler`] | Euler path / circuit (Hierholzer's) | O(E) |
15//! | [`mod@hamiltonian`] | Hamiltonian path (backtracking) | O(V!) |
16//! | [`mod@tsp`] | Travelling Salesman — Held-Karp bitmask DP | O(2^V · V²) |
17//!
18//! ## Design note: SCC algorithms
19//!
20//! Both [`tarjan_scc()`] and [`kosaraju_scc()`] solve the same problem in O(V + E).
21//! Tarjan's algorithm completes in a single DFS pass using a stack and low-link
22//! values. Kosaraju's algorithm is conceptually simpler — two DFS passes on the
23//! original and transposed graph — but requires building a transposed graph.
24//! Implement both and compare their output on the same graphs to verify they agree.
25//!
26//! [`Graph`]: graph_core::Graph
27
28/// DAG condensation: contract each SCC into a single super-node.
29pub mod condensation;
30/// Euler path and circuit via Hierholzer's algorithm.
31pub mod euler;
32/// Hamiltonian path via backtracking (exact, exponential).
33pub mod hamiltonian;
34/// Kosaraju's two-pass SCC algorithm.
35pub mod kosaraju_scc;
36/// Tarjan's single-pass SCC algorithm using DFS low-link values.
37pub mod tarjan_scc;
38/// Travelling Salesman Problem via Held-Karp bitmask DP.
39pub mod tsp;
40
41pub use condensation::{condensation, CondensedGraph};
42pub use euler::{euler_circuit, euler_path, EulerError};
43pub use hamiltonian::hamiltonian_path;
44pub use kosaraju_scc::kosaraju_scc;
45pub use tarjan_scc::tarjan_scc;
46pub use tsp::tsp_held_karp;