graph_traversal/lib.rs
1#![warn(missing_docs)]
2
3//! # graph-traversal
4//!
5//! Traversal algorithms built on top of [`graph_core`]'s [`Graph`] trait.
6//!
7//! Every function accepts any type that implements `Graph`, so it works with
8//! both [`AdjacencyList`] and [`AdjacencyMatrix`] out of the box.
9//!
10//! ## Algorithms
11//!
12//! | Module | Algorithms |
13//! |--------|-----------|
14//! | [`mod@dfs`] | Recursive DFS, iterative DFS, DFS tree |
15//! | [`mod@bfs`] | BFS with distances, BFS tree |
16//! | [`mod@topo`] | Topological sort (DFS-based and Kahn's) |
17//! | [`mod@cycle`] | Cycle detection (directed and undirected) |
18//! | [`mod@components`] | Connected components |
19//! | [`mod@bipartite`] | Bipartite check and 2-colouring |
20//! | [`mod@paths`] | Path reconstruction from parent maps |
21//!
22//! [`Graph`]: graph_core::Graph
23//! [`AdjacencyList`]: graph_core::AdjacencyList
24//! [`AdjacencyMatrix`]: graph_core::AdjacencyMatrix
25
26/// Breadth-first search with distances and BFS tree.
27pub mod bfs;
28/// Bipartite check and 2-colouring via BFS.
29pub mod bipartite;
30/// Connected components via BFS seeding.
31pub mod components;
32/// Cycle detection for directed and undirected graphs.
33pub mod cycle;
34/// Recursive and iterative depth-first search.
35pub mod dfs;
36/// Path reconstruction from BFS/DFS parent maps.
37pub mod paths;
38/// Topological sort: DFS finish-order and Kahn's algorithm.
39pub mod topo;
40
41pub use bfs::{bfs, bfs_tree};
42pub use bipartite::is_bipartite;
43pub use components::connected_components;
44pub use cycle::{has_cycle_directed, has_cycle_undirected};
45pub use dfs::{dfs_iterative, dfs_recursive};
46pub use paths::reconstruct_path;
47pub use topo::{topological_sort_dfs, topological_sort_kahn};