gomory_hu_tree/lib.rs
1//! # Gomory-Hu Tree Construction (`gomory-hu-tree`)
2//!
3//! [](https://crates.io/crates/gomory-hu-tree) <!-- TODO: Update when published -->
4//! [](https://docs.rs/gomory-hu-tree) <!-- TODO: Update when published -->
5//! <!-- [](https://github.com/username/gomory-hu-tree/actions) -->
6//! <!-- [](https://codecov.io/gh/username/gomory-hu-tree) -->
7//!
8//! A Rust implementation of **Gomory-Hu Cut Tree Construction**, providing efficient
9//! all-pairs minimum cut queries. After an initial preprocessing step to build the tree
10//! (typically O(N * MaxFlowTime)), the minimum cut value between any pair of nodes
11//! can be queried efficiently (currently O(N) in this implementation via BFS on tree edges).
12//!
13//! ## Features
14//!
15//! * **Gusfield's Algorithm**: Implements the simplified algorithm by Gusfield (1990) for tree construction.
16//! * **Max-Flow Backend**: Uses Dinic's algorithm as the default max-flow solver.
17//! * **Graph Representation**: Includes a basic directed graph representation (`AdjacencyListFlowGraph`)
18//! suitable for flow algorithms, using `petgraph` internally.
19//! * **Query API**: Allows querying min-cut values between vertex pairs using the constructed tree.
20//! * **Property-Based Testing**: Includes comprehensive tests to ensure correctness.
21//! * **Benchmarking**: Performance benchmarks for construction and queries are available.
22//!
23//! ## Quick Start
24//!
25//! Add to your `Cargo.toml`:
26//! ```toml
27//! [dependencies]
28//! gomory_hu_tree = "0.1.0" // Replace with the actual version from crates.io
29//! ```
30//!
31//! Basic usage with a simple line graph:
32//! ```rust
33//! use gomory_hu_tree::{gusfield_tree, DinicSolver, AdjacencyListFlowGraph, GomoryHuError};
34//!
35//! fn main() -> Result<(), GomoryHuError> {
36//! // 1. Create a graph (e.g., a line graph 0-1-2)
37//! let mut graph = AdjacencyListFlowGraph::new();
38//! let n0 = graph.add_node(()); // node 0
39//! let n1 = graph.add_node(()); // node 1
40//! let n2 = graph.add_node(()); // node 2
41//!
42//! // Add undirected edges (as pairs of directed edges with same capacity)
43//! graph.add_edge(n0, n1, 10.0); graph.add_edge(n1, n0, 10.0); // 0-1 with capacity 10
44//! graph.add_edge(n1, n2, 5.0); graph.add_edge(n2, n1, 5.0); // 1-2 with capacity 5
45//!
46//! // 2. Initialize a MaxFlowSolver
47//! let solver = DinicSolver::new();
48//!
49//! // 3. Build Gomory-Hu tree
50//! let gh_tree = gusfield_tree(&graph, &solver)?;
51//!
52//! // 4. Query minimum cut values
53//! // For the line graph 0 --10-- 1 --5-- 2:
54//! // Min-cut(0,1) = 10.0
55//! // Min-cut(1,2) = 5.0
56//! // Min-cut(0,2) = 5.0 (bottleneck on path 0-1-2)
57//!
58//! // Note: Comparing floats requires care, typically using an epsilon.
59//! // For this example, direct assertion might fail due to tiny float inaccuracies.
60//! // let epsilon = 1e-9;
61//! // assert!((gh_tree.min_cut_value(n0, n1) - 10.0).abs() < epsilon);
62//! // assert!((gh_tree.min_cut_value(n1, n2) - 5.0).abs() < epsilon);
63//! // assert!((gh_tree.min_cut_value(n0, n2) - 5.0).abs() < epsilon);
64//!
65//! println!("Min-cut between node {} and {}: {}", n0, n1, gh_tree.min_cut_value(n0,n1));
66//! println!("Min-cut between node {} and {}: {}", n1, n2, gh_tree.min_cut_value(n1,n2));
67//! println!("Min-cut between node {} and {}: {}", n0, n2, gh_tree.min_cut_value(n0,n2));
68//!
69//! // To visualize the tree (e.g., print in DOT format):
70//! // println!("\nGraphviz DOT format of the Gomory-Hu tree:\n{}", gh_tree.to_dot());
71//! Ok(())
72//! }
73//! ```
74//!
75//! ## Algorithm Background
76//! The **Gomory-Hu Cut Tree** (R. E. Gomory and T. C. Hu, 1961) is a data structure
77//! that represents the minimum s-t cuts for all N(N-1)/2 vertex pairs in an undirected graph.
78//! It is a weighted tree where edges correspond to min-cuts in the original graph.
79//! The min-cut value between any two nodes `s` and `t` in the original graph is equal to
80//! the minimum capacity of any edge on the unique path between `s` and `t` in the Gomory-Hu tree.
81//!
82//! This implementation uses **Gusfield's simplified algorithm** (D. Gusfield, 1990),
83//! which requires N-1 max-flow computations, avoiding graph contractions used in the original Gomory-Hu method.
84//!
85//! ## Current Implementation Details
86//! * **Query Complexity**: `min_cut_value` is currently O(N) due to BFS/DFS on tree edges.
87//! Future optimizations could use LCA algorithms for O(log N) or O(alpha(N)) queries.
88//! * **Error Handling**: Errors from max-flow computations or graph inconsistencies are propagated
89//! via `MaxFlowError` and `GomoryHuError`.
90//! * **Graph Input**: The primary graph input `AdjacencyListFlowGraph` is a directed graph.
91//! To model undirected edges for Gomory-Hu construction, users should add pairs of directed edges
92//! (i.e., `u->v` and `v->u` with the same capacity).
93
94// --- Public API Re-exports ---
95
96pub mod algorithms;
97pub mod flow;
98pub mod tree;
99pub mod utils;
100
101// Core data structures for the Gomory-Hu tree itself
102pub use tree::{GomoryHuTree, TreeEdge};
103
104// Main algorithm for constructing the Gomory-Hu tree and its associated error type
105pub use algorithms::{gusfield_tree, GomoryHuError};
106
107// Max-flow solvers, traits, errors, and graph representation
108pub use flow::{
109 AdjacencyListFlowGraph, // Graph data structure compatible with the solvers
110 // MinCut, FlowGraph, OriginalGraphView might be used internally or by users building custom graphs/solvers
111 // but are not essential for basic Gomory-Hu tree usage.
112 DinicSolver, // A concrete max-flow solver using Dinic's algorithm
113 MaxFlowError, // Error type for max-flow computations
114 MaxFlowSolver, // Trait for max-flow algorithms
115};
116
117// (utils module is currently empty or internal, so not re-exporting anything from it yet)