algorithms_edu/algo/graph/
network_flow.rs

1pub mod dfs_capacity_scaling;
2pub use dfs_capacity_scaling::DfsCapacityScalingSolver;
3pub mod dinic;
4pub use dinic::DinicSolver;
5pub mod edmonds_karp;
6pub use edmonds_karp::EdmondsKarpSolver;
7pub mod ford_fulkerson_dfs;
8
9use std::cell::RefCell;
10use std::rc::{Rc, Weak};
11
12/// This edge type is designed specifically for networkflow graphs.
13#[derive(Debug, Clone)]
14pub struct Edge {
15    pub from: usize,
16    pub to: usize,
17    pub flow: i32,
18    pub capacity: i32,
19    /// a weak reference to the residual edge that's pointing in the opposite direction
20    pub residual: Weak<RefCell<Edge>>,
21    pub cost: i32,
22    pub original_cost: i32,
23}
24impl Edge {
25    pub fn new(from: usize, to: usize, capacity: i32) -> [Rc<RefCell<Self>>; 2] {
26        Self::new_with_cost(from, to, capacity, 0)
27    }
28    pub fn new_with_cost(
29        from: usize,
30        to: usize,
31        capacity: i32,
32        cost: i32,
33    ) -> [Rc<RefCell<Self>>; 2] {
34        let e1 = Rc::new(RefCell::new(Edge {
35            from,
36            to,
37            capacity,
38            flow: 0,
39            residual: Weak::default(),
40            cost,
41            original_cost: cost,
42        }));
43        let e2 = Rc::new(RefCell::new(Edge {
44            from: to,
45            to: from,
46            capacity: 0,
47            flow: 0,
48            residual: Weak::default(),
49            cost: -cost,
50            original_cost: -cost,
51        }));
52        e1.borrow_mut().residual = Rc::downgrade(&e2);
53        e2.borrow_mut().residual = Rc::downgrade(&e1);
54        [e1, e2]
55    }
56    pub fn is_residual(&self) -> bool {
57        self.capacity == 0
58    }
59    pub fn reamaining_capacity(&self) -> i32 {
60        self.capacity - self.flow
61    }
62    pub fn augment(&mut self, bottleneck: i32) {
63        self.flow += bottleneck;
64        self.residual.upgrade().unwrap().borrow_mut().flow -= bottleneck;
65    }
66}
67
68#[derive(Debug)]
69pub struct NetworkFlowAdjacencyList {
70    edges: Vec<Vec<Rc<RefCell<Edge>>>>,
71    pub source: usize,
72    pub sink: usize,
73}
74
75impl NetworkFlowAdjacencyList {
76    /// Initialize an empty adjacency list that can hold up to n nodes.
77    pub fn with_size(n: usize) -> Self {
78        Self {
79            edges: vec![vec![]; n],
80            source: n - 1,
81            sink: n - 2,
82        }
83    }
84    pub fn and_source_sink(mut self, source: usize, sink: usize) -> Self {
85        self.source = source;
86        self.sink = sink;
87        self
88    }
89    pub fn is_empty(&self) -> bool {
90        self.edges.is_empty()
91    }
92    pub fn add_edge(&mut self, from: usize, to: usize, capacity: i32) {
93        self.add_edge_with_cost(from, to, capacity, 0);
94    }
95    pub fn add_edge_with_cost(&mut self, from: usize, to: usize, capacity: i32, cost: i32) {
96        let [e1, e2] = Edge::new_with_cost(from, to, capacity, cost);
97        self.edges[from].push(e1);
98        self.edges[to].push(e2);
99    }
100    pub fn from_edges(size: usize, edges: &[(usize, usize, i32)]) -> Self {
101        let mut graph = Self::with_size(size);
102        for &(a, b, c) in edges.iter() {
103            graph.add_edge(a, b, c);
104        }
105        graph
106    }
107    pub fn from_edges_with_cost(size: usize, edges: &[(usize, usize, i32, i32)]) -> Self {
108        let mut graph = Self::with_size(size);
109        for &(a, b, c, d) in edges.iter() {
110            graph.add_edge_with_cost(a, b, c, d);
111        }
112        graph
113    }
114    pub fn edges(&self) -> impl Iterator<Item = (usize, &Rc<RefCell<Edge>>)> {
115        self.edges
116            .iter()
117            .enumerate()
118            .flat_map(|(a, edges)| edges.iter().map(move |b| (a, b)))
119    }
120    pub fn edge_count(&self) -> usize {
121        self.edges().count()
122    }
123    pub fn nodes(&self) -> impl Iterator<Item = (usize, &Vec<Rc<RefCell<Edge>>>)> {
124        self.edges.iter().enumerate()
125    }
126    pub fn node_count(&self) -> usize {
127        self.edges.len()
128    }
129}
130
131impl std::ops::Index<usize> for NetworkFlowAdjacencyList {
132    type Output = Vec<Rc<RefCell<Edge>>>;
133    fn index(&self, index: usize) -> &Self::Output {
134        &self.edges[index]
135    }
136}
137
138impl std::ops::IndexMut<usize> for NetworkFlowAdjacencyList {
139    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
140        &mut self.edges[index]
141    }
142}
143
144pub trait MaxFlowSolver {
145    fn max_flow(graph: &mut NetworkFlowAdjacencyList) -> i32;
146}
algorithms_edu/algo/graph/network_flow.rs

algorithms_edu/algo/graph/
network_flow.rs
