gdsl 0.2.1

GDSL is a graph data-structure library including graph containers, connected node strutures and efficient algorithms on those structures. Nodes are independent of a graph container and can be used as connected smart pointers.
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
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

// # Edmonds–Karp algorithm for maximum flow.
//
// https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
//
// An algorithm for finding a maximum flow in a flow network.

use gdsl::{digraph::*, digraph_connect as connect, digraph_node as node};

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

type N = Node<usize, (), FlowEdge>;
type G = Graph<usize, (), FlowEdge>;

#[derive(Clone, Copy)]
struct Flow(u64, u64);

#[derive(Clone)]
struct FlowEdge(Rc<Cell<Flow>>, Weak<Cell<Flow>>);

impl FlowEdge {
    // Connect two nodes with a flow.
    fn connect(s: &N, t: &N, max: u64) {
        // Create a forward and a reverse flow.
        let mut fflow = FlowEdge(Rc::new(Cell::new(Flow(max, 0))), Weak::new());
        let mut rflow = FlowEdge(Rc::new(Cell::new(Flow(max, max))), Weak::new());

        // Cross-connect the flows.
        fflow.1 = Rc::downgrade(&rflow.0);
        rflow.1 = Rc::downgrade(&fflow.0);

        // Connect the flows to the nodes.
        connect!(s => t, fflow);
        connect!(t => s, rflow);
    }

    // Update flow with the augmenting flow.
    fn update(&self, aug_flow: u64) {
        // Decompose the flow parameters.
        let (fflow, rflow) = (&self.0, &self.1.upgrade().unwrap());
        let Flow(fmax, fcur) = fflow.get();
        let Flow(rmax, rcur) = rflow.get();

        // Increase the flow in the forward direction and decrease
        // the flow in the reverse direction.
        fflow.set(Flow(fmax, fcur + aug_flow));
        rflow.set(Flow(rmax, rcur - aug_flow));
    }

    // Get the max flow.
    fn max(&self) -> u64 {
        self.0.get().0
    }

    // Get the current flow.
    fn cur(&self) -> u64 {
        self.0.get().1
    }
}

fn max_flow(g: &G) -> u64 {
    // 1. We loop breadth-first until there is no more paths to explore.
    let mut max_flow: u64 = 0;

    while let Some(path) = g[0]
        .dfs()
        .target(&5)
        // 2. We exclude saturated edges from the search.
        .filter(&mut |Edge(_, _, e)| e.cur() < e.max())
        .search_path()
    {
        let mut aug_flow = std::u64::MAX;

        // 3. We find the minimum augmenting flow along the path.
        for Edge(_, _, flow) in path.iter_edges() {
            if flow.max() - flow.cur() < aug_flow {
                aug_flow = flow.max() - flow.cur();
            }
        }

        // 4. We update the flow along the path.
        for Edge(_, _, flow) in path.iter_edges() {
            flow.update(aug_flow);
        }

        // 5. We update the maximum flow.
        max_flow += aug_flow;
    }
    max_flow
}

fn main() {
    // Generate an example Graph with a max flow of 23 from 0 to 5.
    let mut g = Graph::new();

    g.insert(node!(0));
    g.insert(node!(1));
    g.insert(node!(2));
    g.insert(node!(3));
    g.insert(node!(4));
    g.insert(node!(5));

    FlowEdge::connect(&g[0], &g[1], 16);
    FlowEdge::connect(&g[0], &g[2], 13);
    FlowEdge::connect(&g[1], &g[2], 10);
    FlowEdge::connect(&g[1], &g[3], 12);
    FlowEdge::connect(&g[2], &g[1], 4);
    FlowEdge::connect(&g[2], &g[4], 14);
    FlowEdge::connect(&g[3], &g[2], 9);
    FlowEdge::connect(&g[3], &g[5], 20);
    FlowEdge::connect(&g[4], &g[3], 7);
    FlowEdge::connect(&g[4], &g[5], 4);

    // For this Graph we expect the maximum flow from 0 -> 5 to be 23
    assert!(max_flow(&g) == 23);
}