gomory_hu_tree/algorithms/
gusfield.rs

1use crate::flow::{MaxFlowError, MaxFlowSolver, OriginalGraphView};
2use crate::tree::{GomoryHuTree, TreeEdge};
3
4/// Errors that can occur during the construction of a Gomory-Hu tree.
5#[derive(Debug, thiserror::Error)]
6pub enum GomoryHuError {
7    /// Error originated from an underlying max-flow computation.
8    #[error("Max-flow computation failed: {0}")]
9    MaxFlowComputationError(#[from] MaxFlowError),
10    /// Indicates an invalid graph structure was encountered (e.g., inconsistent vertex count).
11    #[error("Invalid graph structure: {0}")]
12    InvalidGraph(String),
13    /// Indicates a vertex was not found during a pre-computation check (not typically raised by `gusfield_tree` itself).
14    #[error("Vertex {0} not found in graph (pre-computation check)")]
15    VertexNotFoundPreCheck(usize),
16}
17
18/// Constructs a Gomory-Hu tree for the given graph using Gusfield's algorithm.
19///
20/// Gusfield's algorithm (1990) provides a simplified method for building the Gomory-Hu tree
21/// by performing N-1 max-flow computations, without requiring graph contractions.
22///
23/// # Arguments
24/// * `graph`: A reference to a graph implementing `OriginalGraphView`. The graph is treated as undirected;
25///   if using a directed `AdjacencyListFlowGraph`, ensure edges `(u,v)` and `(v,u)` are added
26///   with the same capacity to model undirected edges.
27/// * `solver`: A reference to a max-flow solver instance (e.g., `DinicSolver`) that implements
28///   `MaxFlowSolver<G, Flow = f64>`. The flow values must be `f64`.
29///
30/// # Returns
31/// A `Result` containing the `GomoryHuTree` if successful, or a `GomoryHuError` if an error occurs
32/// (e.g., during a max-flow computation).
33///
34/// # Complexity
35/// The algorithm performs N-1 calls to the max-flow solver. If T_max_flow is the time complexity
36/// of one max-flow computation, Gusfield's algorithm is O(N * T_max_flow).
37///
38/// # Panics
39/// This function may panic if the max-flow solver panics, or if there are unexpected issues
40/// with vertex indices (though most vertex index issues should be caught by the solver or result in errors).
41// TODO: Implement parallel execution for N-1 max-flow computations when 'parallel' feature is enabled.
42// This would likely involve Rayon scopes within the main loop, if solver instances are Send/Sync
43// or can be created per-thread. Each of the N-1 flow computations is independent.
44pub fn gusfield_tree<G, S>(graph: &G, solver: &S) -> Result<GomoryHuTree, GomoryHuError>
45where
46    G: OriginalGraphView,
47    S: MaxFlowSolver<G, Flow = f64>,
48{
49    let n = graph.vertex_count();
50
51    if n == 0 {
52        return Ok(GomoryHuTree::new(Vec::new(), 0));
53    }
54    if n == 1 {
55        return Ok(GomoryHuTree::new(Vec::new(), 1));
56    }
57
58    // parent[i] stores the node to which vertex i is currently "contracted" or connected
59    // in the context of the algorithm's evolving partitions. Initially, all nodes belong to
60    // the component of vertex 0.
61    let mut parent = vec![0; n];
62    let mut tree_edges = Vec::with_capacity(n - 1);
63
64    // Iterate from vertex 1 to n-1 (s_i in Gusfield's paper notation, using i here).
65    for i in 1..n {
66        // Calculate max flow between vertex `i` and its current parent `parent[i]`.
67        // The `min_cut` result contains the partition of vertices on the `i`-side of the cut.
68        let (flow_value, min_cut) = solver.max_flow_min_cut(graph, i, parent[i])?;
69
70        // Add an edge to the Gomory-Hu tree between `i` and `parent[i]` with capacity `flow_value`.
71        tree_edges.push(TreeEdge::new(i, parent[i], flow_value));
72
73        // Update parent pointers for nodes that are on the same side of the cut as `i`
74        // and were previously associated with `parent[i]`.
75        // These nodes now effectively "contract" onto `i` for subsequent iterations
76        // involving them as the `i` (source) parameter.
77        for j in (i + 1)..n {
78            if parent[j] == parent[i] && min_cut.same_side(j, i) {
79                parent[j] = i;
80            }
81        }
82    }
83
84    Ok(GomoryHuTree::new(tree_edges, n))
85}
gomory_hu_tree/algorithms/gusfield.rs

gomory_hu_tree/algorithms/
gusfield.rs
