toolbox-rs 0.6.0

A toolbox of basic data structures and algorithms
Documentation 
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

use std::sync::{Arc, atomic::AtomicI32};

use crate::{
    edge::{EdgeWithData, InputEdge},
    graph::NodeID,
};
use bitvec::vec::BitVec;
use log::debug;

#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct ResidualEdgeData {
    pub capacity: i32,
}

impl ResidualEdgeData {
    pub fn new(capacity: i32) -> ResidualEdgeData {
        ResidualEdgeData { capacity }
    }
}

pub trait MaxFlow {
    fn run(&mut self);
    fn run_with_upper_bound(&mut self, bound: Arc<AtomicI32>);
    fn max_flow(&self) -> Result<i32, String>;
    fn assignment(&self, source: NodeID) -> Result<BitVec, String>;
    fn from_edge_list(
        edges: Vec<InputEdge<ResidualEdgeData>>,
        source: NodeID,
        sink: NodeID,
    ) -> Self;
    fn from_generic_edge_list<E: EdgeWithData>(
        input_edges: &[E],
        source: NodeID,
        target: NodeID,
        function: impl Fn(&E) -> ResidualEdgeData,
    ) -> Self
    where
        Self: Sized,
    {
        debug_assert!(!input_edges.is_empty());
        debug!("instantiating max-flow solver");
        let edge_list: Vec<InputEdge<ResidualEdgeData>> = input_edges
            .iter()
            .map(move |edge| InputEdge {
                source: edge.source(),
                target: edge.target(),
                data: function(edge),
            })
            .collect();

        debug!("created {} ff edges", edge_list.len());
        Self::from_edge_list(edge_list, source, target)
    }
}