rs-graph 0.14.1

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

/*
 * Copyright (c) 2015, 2016, 2017, 2018 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/>
 */

extern crate num_traits;
extern crate rs_graph as graph;
extern crate time;

#[macro_use]
extern crate rustop;

use graph::dimacs::maxflow::Instance;
use graph::maxflow::{Dinic, MaxFlow};
use graph::{Digraph, EdgeMap, Graph, IndexEdgeSlice, IndexNetwork, LinkedListGraph};

use std::fmt::Display;

fn run<'a, G, F, Us>(g: &mut Dinic<'a, G, F>, src: G::Node, snk: G::Node, upper: Us, niter: usize)
where
    G: 'a + IndexNetwork<'a>,
    F: Display + num_traits::NumAssign + Ord + Copy,
    Us: EdgeMap<'a, G, F> + Copy,
{
    {
        let tstart = time::precise_time_ns();
        for _ in 0..niter {
            g.solve(src, snk, upper);
        }
        let tend = time::precise_time_ns();
        println!("Time: {}", (tend - tstart) as f64 / 1e9);
        println!("Flow: {}", g.value());
    }
}

fn main() {
    let (args, _) = opts! {
        synopsis "Solve max-flow problem with Dinic's algorithm.";
        opt num:usize=1, desc:"Number of times the algorithm is repeated.";
        param file:String, desc:"Instance file name";
    }.parse_or_exit();

    let tstart = time::precise_time_ns();
    let instance = Instance::<_, i32, _>::read(&args.file).unwrap();

    let g: LinkedListGraph = instance.graph;
    let s = instance.src;
    let t = instance.snk;
    let upper = IndexEdgeSlice::new(&g, &instance.upper);

    let tend = time::precise_time_ns();
    println!("Time: {}", (tend - tstart) as f64 / 1e9);
    println!("  graph: LinkedListGraph");
    println!("  number of nodes: {}", g.num_nodes());
    println!("  number of arcs: {}", g.num_edges());

    let mut d = Dinic::new(&g);
    run(&mut d, s, t, upper, args.num);

    assert!(g.edges().all(|e| d.flow(e) >= 0 && d.flow(e) <= upper[e]));
    assert!(g.nodes().filter(|&u| u != s && u != t).all(
        |u| g.outedges(u).map(|(e, _)| d.flow(e)).sum::<i32>() == g.inedges(u).map(|(e, _)| d.flow(e)).sum::<i32>()
    ));
    assert_eq!(
        g.outedges(s).map(|(e, _)| d.flow(e)).sum::<i32>() - g.inedges(s).map(|(e, _)| d.flow(e)).sum::<i32>(),
        d.value()
    );
}