gomory_hu_tree/flow/
graph.rs

1use petgraph::graph::{Graph, NodeIndex};
2use petgraph::visit::EdgeRef;
3use petgraph::Directed;
4use std::marker::PhantomData;
5
6use super::traits::{FlowGraph, OriginalGraphView};
7
8/// An adapter for `petgraph::Graph` to be used as a `FlowGraph` and `OriginalGraphView`.
9///
10/// This graph is directed. Edge weights are `f64` representing capacities.
11/// Node weights are generic (`N`), defaulting to `()`.
12///
13/// It assumes that vertex indices used by algorithms (`usize`) correspond directly to
14/// `petgraph::NodeIndex::index()` values. This holds if nodes are added and not removed.
15#[derive(Debug, Clone)]
16pub struct AdjacencyListFlowGraph<N = ()>
17where
18    N: Clone + std::fmt::Debug,
19{
20    /// The internal `petgraph::Graph` instance.
21    graph: Graph<N, f64, Directed, u32>,
22    _phantom_n: PhantomData<N>,
23}
24
25impl<N> AdjacencyListFlowGraph<N>
26where
27    N: Clone + std::fmt::Debug,
28{
29    /// Creates a new, empty `AdjacencyListFlowGraph`.
30    pub fn new() -> Self {
31        Self {
32            graph: Graph::default(), // Graph::default() is Directed
33            _phantom_n: PhantomData,
34        }
35    }
36
37    /// Adds a new node with the given weight to the graph.
38    ///
39    /// # Arguments
40    /// * `weight`: The weight of the node (e.g., `()` if no specific data is needed).
41    ///
42    /// # Returns
43    /// The `usize` index of the newly added node. This index is what should be used
44    /// in `add_edge` calls and by flow algorithms.
45    pub fn add_node(&mut self, weight: N) -> usize {
46        self.graph.add_node(weight).index()
47    }
48
49    /// Adds a directed edge to the graph.
50    ///
51    /// # Arguments
52    /// * `u_idx`: The `usize` index of the source node (previously returned by `add_node`).
53    /// * `v_idx`: The `usize` index of the target node (previously returned by `add_node`).
54    /// * `capacity`: The capacity of the edge (must be `f64`).
55    ///
56    /// # Panics
57    /// Panics if `u_idx` or `v_idx` do not correspond to existing nodes in the graph,
58    /// or if they are out of bounds for the current node count.
59    /// `petgraph` itself panics if `NodeIndex`s are invalid.
60    pub fn add_edge(&mut self, u_idx: usize, v_idx: usize, capacity: f64) {
61        // Ensure indices are within the current node count before creating NodeIndex.
62        // This prevents panics from NodeIndex::new if idx is too large,
63        // though petgraph.add_edge would panic anyway if node doesn't exist.
64        let node_count = self.graph.node_count();
65        if u_idx >= node_count || v_idx >= node_count {
66            panic!("Attempted to add edge with out-of-bounds vertex index. u_idx: {u_idx}, v_idx: {v_idx}, node_count: {node_count}");
67        }
68        let u_node = NodeIndex::new(u_idx);
69        let v_node = NodeIndex::new(v_idx);
70
71        self.graph.add_edge(u_node, v_node, capacity);
72    }
73}
74
75/// Implements `FlowGraph` for `AdjacencyListFlowGraph`.
76impl<N> FlowGraph for AdjacencyListFlowGraph<N>
77where
78    N: Clone + std::fmt::Debug,
79{
80    /// Returns the number of vertices in the graph.
81    fn vertex_count(&self) -> usize {
82        self.graph.node_count()
83    }
84}
85
86/// Implements `OriginalGraphView` for `AdjacencyListFlowGraph`.
87impl<N> OriginalGraphView for AdjacencyListFlowGraph<N>
88where
89    N: Clone + std::fmt::Debug,
90{
91    /// Returns an iterator over all edges in the graph, yielding tuples of
92    /// `(source_idx, target_idx, capacity)`.
93    ///
94    /// Vertex indices are `usize`.
95    fn all_edges(&self) -> Box<dyn Iterator<Item = (usize, usize, f64)> + '_> {
96        Box::new(self.graph.edge_references().map(|edge_ref| {
97            (
98                edge_ref.source().index(), // NodeIndex::index() gives usize
99                edge_ref.target().index(), // NodeIndex::index() gives usize
100                *edge_ref.weight(),        // Dereference to get f64 capacity
101            )
102        }))
103    }
104}
105
106/// Default implementation for `AdjacencyListFlowGraph`.
107/// Creates an empty graph. Requires `N` to implement `Default`.
108impl<N> Default for AdjacencyListFlowGraph<N>
109where
110    N: Default + Clone + std::fmt::Debug,
111{
112    fn default() -> Self {
113        Self {
114            graph: Graph::default(),
115            _phantom_n: PhantomData,
116        }
117    }
118}
gomory_hu_tree/flow/graph.rs

gomory_hu_tree/flow/
graph.rs
