push_relabel 0.1.0

A Push–Relabel maximum-flow implementation in Rust with gap and global-relabel heuristics.
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
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

use push_relabel::PushRelabel;
use std::time::Instant;

/// Build and run a flow instance, printing nodes, edges, flow, and elapsed time.
fn build_and_run(n: usize, edges: &[(usize, usize, i64, i64)], s: usize, t: usize) {
    let mut pr = PushRelabel::new(n);
    for &(u, v, cap, rcap) in edges {
        pr.add_edge(u, v, cap, rcap);
    }
    let start = Instant::now();
    let flow = pr.max_flow(s, t);
    let duration = start.elapsed();
    println!(
        "n={}, m={} → flow={} (took {:?})",
        n,
        edges.len(),
        flow,
        duration
    );
}

fn main() {
    // 100×100 grid, ~10k nodes, ~20k edges + 200
    let w = 100;
    let h = 100;
    let s = w * h;
    let t = s + 1;
    let n = t + 1;
    let mut edges = Vec::with_capacity(w * h * 2 + w * 2);
    // source to top row
    for c in 0..w {
        edges.push((s, c, 1, 0));
    }
    // bottom row to sink
    for c in 0..w {
        edges.push(((h - 1) * w + c, t, 1, 0));
    }
    // grid edges right and down
    for r in 0..h {
        for c in 0..w {
            let u = r * w + c;
            if r + 1 < h {
                edges.push((u, (r + 1) * w + c, 1, 0));
            }
            if c + 1 < w {
                edges.push((u, r * w + (c + 1), 1, 0));
            }
        }
    }
    build_and_run(n, &edges, s, t);

    // 50 layers × width 100 → 5000 nodes, ~500k edges
    let layers = 50;
    let width = 100;
    let mut next_id = 1;
    let mut layers_vec = vec![vec![0]]; // source=0
    for _ in 1..layers {
        let layer: Vec<usize> = (0..width)
            .map(|_| {
                let id = next_id;
                next_id += 1;
                id
            })
            .collect();
        layers_vec.push(layer);
    }
    let sink = next_id;
    let n = sink + 1;
    let mut edges = Vec::with_capacity((layers - 1) * width * width + width);
    // connect layers fully
    for l in 0..(layers - 1) {
        for &u in &layers_vec[l] {
            for &v in &layers_vec[l + 1] {
                edges.push((u, v, 1, 0));
            }
        }
    }
    // connect last layer to sink
    for &u in &layers_vec[layers - 1] {
        edges.push((u, sink, 1, 0));
    }
    build_and_run(n, &edges, 0, sink);

    // n=500, ~125k edges deterministically half of pairs
    let n = 500;
    let mut edges = Vec::new();
    for u in 0..n {
        for v in (u + 1)..n {
            if (u ^ v) % 2 == 0 {
                edges.push((u, v, 1, 0));
            }
        }
    }
    build_and_run(n, &edges, 0, n - 1);

    // K_{500,500}, ~1000 nodes, ~250k edges
    let left = 500;
    let right = 500;
    let source = 0;
    let mut next = 1;
    let left_ids: Vec<usize> = (0..left)
        .map(|_| {
            let id = next;
            next += 1;
            id
        })
        .collect();
    let right_ids: Vec<usize> = (0..right)
        .map(|_| {
            let id = next;
            next += 1;
            id
        })
        .collect();
    let sink = next;
    let n = sink + 1;
    let mut edges = Vec::with_capacity(left * right + left + right);
    for &u in &left_ids {
        edges.push((source, u, 1, 0));
    }
    for &u in &left_ids {
        for &v in &right_ids {
            edges.push((u, v, 1, 0));
        }
    }
    for &v in &right_ids {
        edges.push((v, sink, 1, 0));
    }
    build_and_run(n, &edges, source, sink);

    // star of 100k leaves from source, only one path to sink via chain
    let leaves = 100_000;
    let sink = 1;
    let source = 0;
    let mut edges = Vec::with_capacity(leaves * 2 + 1);
    // main chain 0->sink
    edges.push((source, sink, 1, 0));
    // add many dead ends
    for i in 2..(2 + leaves) {
        edges.push((source, i, 1, 0));
        edges.push((i, source, 0, 0));
    }
    let n = 2 + leaves;
    build_and_run(n, &edges, source, sink);
}