1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

pub mod bipartite_check;
pub mod dfs_capacity_scaling;
pub use dfs_capacity_scaling::DfsCapacityScalingSolver;
pub mod dinic;
pub use dinic::DinicSolver;
pub mod edmonds_karp;
pub use edmonds_karp::EdmondsKarpSolver;
pub mod ford_fulkerson_dfs;

use std::cell::RefCell;
use std::rc::{Rc, Weak};

/// This edge type is designed specifically for networkflow graphs.
#[derive(Debug, Clone)]
pub struct Edge {
    pub from: usize,
    pub to: usize,
    pub flow: i32,
    pub capacity: i32,
    /// a weak reference to the residual edge that's pointing in the opposite direction
    pub residual: Weak<RefCell<Edge>>,
    pub cost: i32,
    pub original_cost: i32,
}
impl Edge {
    pub fn new(from: usize, to: usize, capacity: i32) -> [Rc<RefCell<Self>>; 2] {
        Self::new_with_cost(from, to, capacity, 0)
    }
    pub fn new_with_cost(
        from: usize,
        to: usize,
        capacity: i32,
        cost: i32,
    ) -> [Rc<RefCell<Self>>; 2] {
        let e1 = Rc::new(RefCell::new(Edge {
            from,
            to,
            capacity,
            flow: 0,
            residual: Weak::default(),
            cost,
            original_cost: cost,
        }));
        let e2 = Rc::new(RefCell::new(Edge {
            from: to,
            to: from,
            capacity: 0,
            flow: 0,
            residual: Weak::default(),
            cost: -cost,
            original_cost: -cost,
        }));
        e1.borrow_mut().residual = Rc::downgrade(&e2);
        e2.borrow_mut().residual = Rc::downgrade(&e1);
        [e1, e2]
    }
    pub fn is_residual(&self) -> bool {
        self.capacity == 0
    }
    pub fn reamaining_capacity(&self) -> i32 {
        self.capacity - self.flow
    }
    pub fn augment(&mut self, bottleneck: i32) {
        self.flow += bottleneck;
        self.residual.upgrade().unwrap().borrow_mut().flow -= bottleneck;
    }
}

#[derive(Debug)]
pub struct NetworkFlowAdjacencyList {
    edges: Vec<Vec<Rc<RefCell<Edge>>>>,
    pub source: usize,
    pub sink: usize,
}

impl NetworkFlowAdjacencyList {
    /// Initialize an empty adjacency list that can hold up to n nodes.
    pub fn with_size(n: usize) -> Self {
        Self {
            edges: vec![vec![]; n],
            source: n - 1,
            sink: n - 2,
        }
    }
    pub fn and_source_sink(mut self, source: usize, sink: usize) -> Self {
        self.source = source;
        self.sink = sink;
        self
    }
    pub fn is_empty(&self) -> bool {
        self.edges.is_empty()
    }
    pub fn add_edge(&mut self, from: usize, to: usize, capacity: i32) {
        self.add_edge_with_cost(from, to, capacity, 0);
    }
    pub fn add_edge_with_cost(&mut self, from: usize, to: usize, capacity: i32, cost: i32) {
        let [e1, e2] = Edge::new_with_cost(from, to, capacity, cost);
        self.edges[from].push(e1);
        self.edges[to].push(e2);
    }
    pub fn from_edges(size: usize, edges: &[(usize, usize, i32)]) -> Self {
        let mut graph = Self::with_size(size);
        for &(a, b, c) in edges.iter() {
            graph.add_edge(a, b, c);
        }
        graph
    }
    pub fn from_edges_with_cost(size: usize, edges: &[(usize, usize, i32, i32)]) -> Self {
        let mut graph = Self::with_size(size);
        for &(a, b, c, d) in edges.iter() {
            graph.add_edge_with_cost(a, b, c, d);
        }
        graph
    }
    pub fn edges(&self) -> impl Iterator<Item = (usize, &Rc<RefCell<Edge>>)> {
        self.edges
            .iter()
            .enumerate()
            .flat_map(|(a, edges)| edges.iter().map(move |b| (a, b)))
    }
    pub fn edges_count(&self) -> usize {
        self.edges().count()
    }
    pub fn vertices(&self) -> impl Iterator<Item = (usize, &Vec<Rc<RefCell<Edge>>>)> {
        self.edges.iter().enumerate()
    }
    pub fn vertices_count(&self) -> usize {
        self.edges.len()
    }
}

impl std::ops::Index<usize> for NetworkFlowAdjacencyList {
    type Output = Vec<Rc<RefCell<Edge>>>;
    fn index(&self, index: usize) -> &Self::Output {
        &self.edges[index]
    }
}

impl std::ops::IndexMut<usize> for NetworkFlowAdjacencyList {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.edges[index]
    }
}

pub trait MaxFlowSolver {
    fn max_flow(graph: &mut NetworkFlowAdjacencyList) -> i32;
}