gomory_hu_tree/flow/
traits.rs

1/// A trait for basic graph structures used in flow algorithms.
2///
3/// Graphs implementing this trait provide essential information like vertex count.
4pub trait FlowGraph {
5    /// Returns the number of vertices in the graph.
6    fn vertex_count(&self) -> usize;
7    // Potential future methods:
8    // fn edge_count(&self) -> usize;
9    // fn get_capacity(&self, u: usize, v: usize) -> Option<f64>;
10}
11
12/// Represents a min-cut partition in a graph.
13///
14/// The partition divides the graph's vertices into two sets, typically the source-side
15/// (S) and the sink-side (T) of the cut.
16#[derive(Debug, Clone)]
17pub struct MinCut {
18    /// A boolean vector where `partition[i]` is true if vertex `i` is on the source-side
19    /// of the cut, and false otherwise (meaning it's on the sink-side).
20    /// The length of this vector should be equal to the number of vertices in the graph.
21    pub partition: Vec<bool>,
22}
23
24impl MinCut {
25    /// Creates a new `MinCut` from a given partition.
26    ///
27    /// # Arguments
28    /// * `partition`: A vector where `partition[i]` indicates if vertex `i` is on the
29    ///   source-side of the cut.
30    pub fn new(partition: Vec<bool>) -> Self {
31        Self { partition }
32    }
33
34    /// Checks if a vertex `v` is on the same side of the cut as a representative vertex `s_representative`.
35    ///
36    /// Typically, `s_representative` is the source node used in the max-flow computation that yielded this cut.
37    ///
38    /// # Arguments
39    /// * `v`: The vertex index to check.
40    /// * `s_representative`: The vertex index of the representative (e.g., the source node `s`).
41    ///
42    /// # Returns
43    /// `true` if `v` is on the same side of the cut as `s_representative`, `false` otherwise.
44    ///
45    /// # Panics
46    /// Panics if `v` or `s_representative` are out of bounds for the partition data.
47    pub fn same_side(&self, v: usize, s_representative: usize) -> bool {
48        if v >= self.partition.len() || s_representative >= self.partition.len() {
49            panic!("Vertex index out of bounds in MinCut::same_side. v: {}, s_rep: {}, partition_len: {}",
50                   v, s_representative, self.partition.len());
51        }
52        // If partition[s_representative] is true, it means "true" denotes the s-side.
53        // So, v is on s-side if partition[v] is also true.
54        // If partition[s_representative] is false, it means "false" denotes the s-side (unexpected, but possible).
55        // So, v is on s-side if partition[v] is also false.
56        // This is equivalent to checking if their boolean values are the same.
57        self.partition[v] == self.partition[s_representative]
58    }
59}
60
61/// Errors that can occur during max-flow computations.
62#[derive(Debug, Clone, thiserror::Error)]
63pub enum MaxFlowError {
64    /// The source and sink vertices are the same.
65    #[error("Source and sink are the same vertex (s: {0}, t: {0})")]
66    SourceEqualsSink(usize),
67    /// A specified vertex was not found in the graph (e.g., index out of bounds).
68    #[error("Vertex {0} not found in graph")]
69    VertexNotFound(usize),
70    /// The algorithm reached its maximum allowed iterations before completion.
71    /// This might indicate a very complex graph or an iteration limit that is too low.
72    #[error("Maximum iterations ({0}) reached in max-flow computation")]
73    MaxIterationsReached(usize),
74    /// The graph has no vertices, making max-flow undefined.
75    #[error("Graph has 0 vertices, max-flow is undefined")]
76    EmptyGraph,
77    /// An unspecified internal error occurred within the max-flow algorithm.
78    #[error("Internal max-flow error: {0}")]
79    InternalError(String),
80}
81
82/// A trait for max-flow algorithms.
83///
84/// Implementors of this trait can compute the maximum flow and corresponding minimum cut
85/// in a given flow network (graph).
86/// `G` is the type of the graph, which must implement `FlowGraph`.
87pub trait MaxFlowSolver<G: FlowGraph> {
88    /// The type used for representing flow values (e.g., `f64`, `i32`).
89    /// Must support basic arithmetic, comparison, and debugging.
90    type Flow: Copy + Default + PartialOrd + std::ops::AddAssign + std::fmt::Debug;
91
92    /// Computes the maximum flow from a `source` to a `sink` in the given `graph`.
93    ///
94    /// # Arguments
95    /// * `graph`: A reference to the graph implementing `FlowGraph`.
96    /// * `source`: The source vertex index.
97    /// * `sink`: The sink vertex index.
98    ///
99    /// # Returns
100    /// A `Result` containing a tuple `(max_flow_value, min_cut_partition)` if successful.
101    /// The `min_cut_partition` (a `MinCut` struct) identifies nodes on the source-side of one minimum cut.
102    /// Returns `MaxFlowError` if an issue occurs.
103    fn max_flow_min_cut(
104        &self,
105        graph: &G,
106        source: usize,
107        sink: usize,
108    ) -> Result<(Self::Flow, MinCut), MaxFlowError>;
109}
110
111/// A trait for graph views that provide access to all original edges.
112///
113/// This is used by algorithms like Dinic's to construct an initial residual graph.
114/// It extends `FlowGraph`.
115pub trait OriginalGraphView: FlowGraph {
116    /// Returns an iterator over all edges in the graph.
117    /// Each item is a tuple `(source_vertex_idx, target_vertex_idx, capacity)`.
118    /// For undirected graphs, an edge `u-v` with capacity `C` might be represented
119    /// by two directed edges `(u,v,C)` and `(v,u,C)` from this iterator if the underlying
120    /// graph implementation is directed (like `AdjacencyListFlowGraph`).
121    fn all_edges(&self) -> Box<dyn Iterator<Item = (usize, usize, f64)> + '_>;
122}
gomory_hu_tree/flow/traits.rs

gomory_hu_tree/flow/
traits.rs
