rs-graph 0.6.0

/*
 * Copyright (c) 2017 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/>
 */

//! This module implements the max flow algorithm of Edmonds-Karp.

use maxflow::MaxFlow;

use graph::IndexNetwork;
use vec::{NodeVec, BiEdgeVec, EdgeSlice};

use std::collections::VecDeque;
use std::cmp::min;

use num::traits::NumAssign;

/// The dinic max-flow algorithm.
pub struct EdmondsKarp<'a, G, F>
    where G: 'a + IndexNetwork<'a>
{
    g: &'a G,
    pred: NodeVec<'a, G, Option<G::Edge>>,
    flow: BiEdgeVec<'a, G, F>,
    queue: VecDeque<G::Node>,
    value: F,
}

impl<'a, G, F> MaxFlow<'a> for EdmondsKarp<'a, G, F>
    where G: IndexNetwork<'a>,
          F: NumAssign + Ord + Copy,
{
    type Graph = G;

    type Flow = F;

    fn new(g: &'a G) -> Self {
        EdmondsKarp {
            g: g,
            pred: nodevec![g; None],
            flow: biedgevec![g; F::zero()],
            queue: VecDeque::with_capacity(g.num_nodes()),
            value: F::zero(),
        }
    }

    fn as_graph(&self) -> &'a Self::Graph {
        self.g
    }

    fn value(&self) -> F {
        self.value
    }

    fn flow(&self, e: G::Edge) -> F {
        self.flow[self.g.forward(e)]
    }

    fn solve<'b>(&mut self,
                 src: G::Node, snk: G::Node,
                 upper: &EdgeSlice<'a, 'b, G, F>)
    {
        assert_ne!(self.g.node_id(src), self.g.node_id(snk), "Source and sink node must not be equal");
        assert!(self.g.num_nodes() <= usize::max_value(),
                "Too many nodes for internal integer type");
        assert!(self.g.num_edges() <= usize::max_value(),
                "Too many edges for internal integer type");

        // initialize network flow
        for e in self.g.edges() {
            self.flow[e] = F::zero();
            self.flow[self.g.reverse(e)] = upper[e];
        }

        // nothing to do if there is no edge
        if self.g.num_edges() == 0 { return }

        // some arbitrary edge, just a marker
        let src_e = self.g.id2edge(0);

        // the maximal augmentation bound is the maximal upper bound
        let bound = *upper.iter().max().unwrap();

        self.value = F::zero();
        loop {
            /// do bfs from source to sink
            for u in self.g.nodes() { self.pred[u] = None }
            self.pred[src] = Some(src_e);
            self.queue.clear();
            self.queue.push_back(src);
            'bfs: while let Some(u) = self.queue.pop_front() {
                for (e,v) in self.g.neighs(u) {
                    if self.pred[v].is_none() && !self.flow[self.g.reverse(e)].is_zero() {
                        self.pred[v] = Some(e);
                        self.queue.push_back(v);
                        if v == snk { break 'bfs; }
                    }
                }
            }

            if self.pred[snk].is_none() { break }

            /// compute augmentation value
            let mut df = bound;
            let mut v = snk;
            while v != src {
                let e = self.pred[v].unwrap();
                df = min(df, self.flow[self.g.reverse(e)]);
                v = self.g.bisrc(e);
            }

            debug_assert!(!df.is_zero());

            /// now augment the flow
            let mut v = snk;
            while v != src {
                let e = self.pred[v].unwrap();
                self.flow[e] += df;
                self.flow[self.g.reverse(e)] -= df;
                v = self.g.bisrc(e);
            }

            self.value += df;
        }
    }

    fn mincut(&self) -> Vec<G::Node> {
        self.g.nodes().filter(|&u| self.pred[u].is_some()).collect()
    }
}

#[cfg(test)]
mod tests {
    use {Net, Graph, Digraph, EdgeSlice, Builder};
    use maxflow::edmondskarp;

    #[test]
    fn test_edmondskarp() {
        let mut g = Net::new();
        let mut upper = vec![];
        let s = g.add_node();
        let t = g.add_node();
        let v1 = g.add_node();
        let v2 = g.add_node();
        let v3 = g.add_node();
        let v4 = g.add_node();
        g.add_edge(s, v1);  upper.push(5);
        g.add_edge(s, v3);  upper.push(5);
        g.add_edge(v1, v2); upper.push(2);
        g.add_edge(v1, v3); upper.push(1);
        g.add_edge(v1, v4); upper.push(1);
        g.add_edge(v2, t);  upper.push(4);
        g.add_edge(v3, v4); upper.push(2);
        g.add_edge(v4, v2); upper.push(2);
        g.add_edge(v4, t);  upper.push(5);
        let upper = EdgeSlice::new(&g, &upper);

        let (value, flow, mut mincut) = edmondskarp(&g, s, t, &upper);

        assert_eq!(value, 5);
        assert!(g.edges().all(|e| flow[e] >= 0 && flow[e] <= upper[e]));
        assert!(g.nodes().filter(|&u| u != s && u != t).all(|u| {
            g.outedges(u).map(|(e,_)| flow[e]).sum::<isize>() == g.inedges(u).map(|(e,_)| flow[e]).sum::<isize>()
        }));
        mincut.sort_by_key(|u| u.index());
        assert_eq!(mincut, vec![s, v1, v3]);
    }
}