toolbox_rs/
max_flow.rs

1use std::sync::{Arc, atomic::AtomicI32};
2
3use crate::{
4    edge::{EdgeWithData, InputEdge},
5    graph::NodeID,
6};
7use bitvec::vec::BitVec;
8use log::debug;
9
10#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
11pub struct ResidualEdgeData {
12    pub capacity: i32,
13}
14
15impl ResidualEdgeData {
16    pub fn new(capacity: i32) -> ResidualEdgeData {
17        ResidualEdgeData { capacity }
18    }
19}
20
21pub trait MaxFlow {
22    fn run(&mut self);
23    fn run_with_upper_bound(&mut self, bound: Arc<AtomicI32>);
24    fn max_flow(&self) -> Result<i32, String>;
25    fn assignment(&self, source: NodeID) -> Result<BitVec, String>;
26    fn from_edge_list(
27        edges: Vec<InputEdge<ResidualEdgeData>>,
28        source: NodeID,
29        sink: NodeID,
30    ) -> Self;
31    fn from_generic_edge_list<E: EdgeWithData>(
32        input_edges: &[E],
33        source: NodeID,
34        target: NodeID,
35        function: impl Fn(&E) -> ResidualEdgeData,
36    ) -> Self
37    where
38        Self: Sized,
39    {
40        debug_assert!(!input_edges.is_empty());
41        debug!("instantiating max-flow solver");
42        let edge_list: Vec<InputEdge<ResidualEdgeData>> = input_edges
43            .iter()
44            .map(move |edge| InputEdge {
45                source: edge.source(),
46                target: edge.target(),
47                data: function(edge),
48            })
49            .collect();
50
51        debug!("created {} ff edges", edge_list.len());
52        Self::from_edge_list(edge_list, source, target)
53    }
54}
toolbox_rs/max_flow.rs

toolbox_rs/
max_flow.rs
