rs-graph 0.14.1

// G, Fopyright (c) 2015, 2016, 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 Dinic' max flow algorithm
//!
//! # Example
//!
//! ```
//! use rs_graph::{Builder, Graph, Digraph, Net, EdgeVec, NumberedNode};
//! use rs_graph::maxflow::dinic;
//!
//! 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: EdgeVec<_> = upper.into();
//!
//! let (value, flow, mut mincut) = dinic(&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]);
//! ```

use maxflow::MaxFlow;

use graph::{IndexBiEdgeVec, IndexNetwork, IndexNodeVec};
use EdgeMap;

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

use num::traits::NumAssign;

/// The dinic max-flow algorithm.
pub struct Dinic<'a, G, F>
where
    G: 'a + IndexNetwork<'a>,
{
    g: &'a G,
    nodes: IndexNodeVec<'a, G, NodeInfo<G::Edge>>,
    edges: IndexBiEdgeVec<'a, G, EdgeInfo<G::Edge, F>>,
    queue: VecDeque<G::Node>,
    value: F,
}

#[derive(Clone)]
struct NodeInfo<E> {
    dist: usize,
    first_lvl: Option<E>,
}

#[derive(Clone)]
struct EdgeInfo<E, F> {
    flow: F,
    next_lvl: Option<E>,
}

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

    type Flow = F;

    fn new(g: &'a G) -> Self {
        Dinic {
            g: g,
            nodes: idxnodevec![g; NodeInfo { dist: 0, first_lvl: None }],
            edges: idxbiedgevec![g; EdgeInfo { flow: F::zero(), next_lvl: None }],
            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.edges[self.g.forward(e)].flow
    }

    fn solve<Us>(&mut self, src: G::Node, snk: G::Node, upper: Us)
    where
        Us: EdgeMap<'a, G, F>,
    {
        assert_ne!(
            self.g.node_id(src),
            self.g.node_id(snk),
            "Source and sink node must not be equal"
        );

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

        // compute upper bound on flow
        let mut bound = F::zero();
        for (e, _) in self.g.outedges(src) {
            bound += upper[e];
        }

        self.value = F::zero();
        while self.search(src, snk) {
            self.value += self.augment(src, snk, bound);
        }
    }

    fn mincut(&self) -> Vec<G::Node> {
        let n = self.g.num_nodes();
        self.g.nodes().filter(|&u| self.nodes[u].dist < n).collect()
    }
}

impl<'a, G, F> Dinic<'a, G, F>
where
    G: IndexNetwork<'a>,
    F: NumAssign + Ord + Copy,
{
    fn search(&mut self, src: G::Node, snk: G::Node) -> bool {
        let n = self.g.num_nodes();

        for u in self.g.nodes() {
            self.nodes[u].dist = n;
            self.nodes[u].first_lvl = None;
        }
        self.nodes[src].dist = 0;

        self.queue.clear();
        self.queue.push_back(src);

        let mut snk_d = n;
        while let Some(u) = self.queue.pop_front() {
            let d = self.nodes[u].dist;

            if d >= snk_d {
                return true;
            }

            for (e, v) in self.g.neighs(u) {
                let f = self.g.reverse(e);
                if self.edges[f].flow > F::zero() {
                    if self.nodes[v].dist == n {
                        self.nodes[v].dist = d + 1;
                        self.queue.push_back(v);
                        if v == snk {
                            snk_d = d + 1
                        }
                    } else if self.nodes[v].dist != d + 1 {
                        continue;
                    }
                    self.edges[e].next_lvl = self.nodes[u].first_lvl;
                    self.nodes[u].first_lvl = Some(e);
                }
            }
        }

        false
    }

    fn augment(&mut self, src: G::Node, snk: G::Node, target_flow: F) -> F {
        if src == snk {
            return target_flow;
        }

        let mut df = F::zero();

        while let Some(e) = self.nodes[src].first_lvl {
            let f = self.g.reverse(e);
            let rem_cap = min(self.edges[f].flow, target_flow - df);
            if rem_cap > F::zero() {
                debug_assert!(self.g.bisrc(e) == src);
                debug_assert!(self.g.bisnk(e) != src);
                let cf = self.augment(self.g.bisnk(e), snk, rem_cap);
                self.edges[e].flow += cf;
                self.edges[f].flow -= cf;
                df += cf;
                if df == target_flow {
                    break;
                }
            }

            // edge is saturated or blocked
            self.nodes[src].first_lvl = self.edges[e].next_lvl;
        }

        if df.is_zero() {
            // nothing can be sent from this node, delete the node and
            // all adjacent edges (we just remove the outgoing edges
            // so that they won't be seen)
            self.nodes[src].first_lvl = None;
        }

        df
    }
}