rs-graph 0.21.0

A library for graph algorithms and combinatorial optimization
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

/*
 * Copyright (c) 2020, 2021, 2022 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

use rs_graph::dimacs;
use rs_graph::maxflow::{dinic, edmondskarp, PushRelabel};
use rs_graph::traits::IndexGraph;
use rs_graph::LinkedListGraph;

use num_traits::ToPrimitive;
use std::error::Error;

const TESTS: &'static [(&'static str, i32, bool)] = &[
    ("tests/maxflow_test1.dat", 211846, false),
    ("tests/maxflow_test2.dat", 2135, false),
    ("tests/maxflow_test3.dat", 351015, true),
    ("tests/maxflow_test4.dat", 2344, true),
];

#[test]
fn test_edmondskarp() -> Result<(), Box<dyn Error>> {
    for &(file, expected, hard) in TESTS {
        if hard {
            continue;
        }
        let instance = dimacs::max::read_from_file(file)?;
        let g: LinkedListGraph = instance.graph;
        let s = g.id2node(instance.src);
        let t = g.id2node(instance.snk);
        let upper = instance.upper;

        let (value, _, _) = edmondskarp(&g, s, t, |e| upper[g.edge_id(e)].to_i32().unwrap());
        assert_eq!(value, expected);
    }

    Ok(())
}

#[test]
fn test_dinic() -> Result<(), Box<dyn Error>> {
    for &(file, expected, _) in TESTS {
        let instance = dimacs::max::read_from_file(file)?;
        let g: LinkedListGraph = instance.graph;
        let s = g.id2node(instance.src);
        let t = g.id2node(instance.snk);
        let upper = instance.upper;

        let (value, _, _) = dinic(&g, s, t, |e| upper[g.edge_id(e)].to_i32().unwrap());
        assert_eq!(value, expected);
    }

    Ok(())
}

#[test]
fn test_pushrelabel() -> Result<(), Box<dyn Error>> {
    for &use_relabelling in &[true, false] {
        for &(file, expected, _) in TESTS {
            let instance = dimacs::max::read_from_file(file)?;
            let g: LinkedListGraph = instance.graph;
            let s = g.id2node(instance.src);
            let t = g.id2node(instance.snk);
            let upper = instance.upper;

            let mut pr = PushRelabel::new(&g);
            pr.use_global_relabelling = use_relabelling;
            pr.solve(s, t, |e| upper[g.edge_id(e)].to_i32().unwrap());
            assert_eq!(
                pr.value(),
                expected,
                "Instance: {} relabelling: {}",
                file,
                use_relabelling
            );
        }
    }

    Ok(())
}