rs-graph 0.20.0

/*
 * Copyright (c) 2017-2021 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.
//!
//! # Example
//!
//! ```
//! use rs_graph::traits::*;
//! use rs_graph::maxflow::edmondskarp;
//! use rs_graph::{EdgeVec, Net};
//! use rs_graph::string::{Data, from_ascii};
//!
//! let Data { graph: g, weights: upper, nodes } = from_ascii::<Net>(r"
//!      a---2-->b
//!     @|\      ^\
//!    / | \     | 4
//!   5  |  \    |  \
//!  /   |   |   |   @
//! s    1   1   2    t
//!  \   |   |   |   @
//!   5  |    \  |  /
//!    \ |     \ | 5
//!     @v      @|/
//!      c---2-->d
//!     ").unwrap();
//!
//! let s = nodes[&'s'];
//! let t = nodes[&'t'];
//! let v1 = nodes[&'a'];
//! let v2 = nodes[&'b'];
//! let v3 = nodes[&'c'];
//! let v4 = nodes[&'d'];
//!
//! let (value, flow, mut mincut) = edmondskarp(&g, s, t, |e| upper[e.index()]);
//!
//! assert_eq!(value, 5);
//! assert!(g.edges().all(|e| flow[e] >= 0 && flow[e] <= upper[e.index()]));
//! assert!(g.nodes().filter(|&u| u != s && u != t).all(|u| {
//!     g.outedges(u).map(|(e,_)| flow[e]).sum::<usize>() ==
//!     g.inedges(u).map(|(e,_)| flow[e]).sum::<usize>()
//! }));
//!
//! mincut.sort_by_key(|u| u.index());
//! assert_eq!(mincut, vec![v1, s, v3]);
//! ```
//!
//! ```
//! use rs_graph::traits::*;
//! use rs_graph::maxflow::edmondskarp;
//! use rs_graph::{EdgeVec, Net};
//! use rs_graph::string::{Data, from_ascii};
//!
//! let Data { graph: g, weights: upper, nodes } = from_ascii::<Net>(r"
//!                ---8-->a---10---
//!               /       |        \
//!              /        1  --3--  |
//!             /         | /     \ |
//!            /          v@       \v
//!      ---->b-----9---->c----8--->d----
//!     /      \         @         @^    \
//!   18        ---6--  /         / |     33
//!   /               \/         /  |      \
//!  /                /\    -----   |       @
//! s           --5--- |   /        |        t
//!  \         /       |  /         |       @
//!   27      |  ----2-|--         /       /
//!    \      | /      |  /----8---       6
//!     \     |/       @  |              /
//!      ---->e----9-->f------6---->g----
//!            \          |        @
//!             \         |       /
//!              --5----->h---4---
//!     ").unwrap();
//!
//! let s = nodes[&'s'];
//! let t = nodes[&'t'];
//!
//! assert_eq!(g.num_edges(), 18);
//!
//! let (value, flow, mut mincut) = edmondskarp(&g, s, t, |e| upper[e.index()]);
//! assert_eq!(value, 29);
//!
//! mincut.sort_by_key(|u| u.index());
//! assert_eq!(mincut, "bcsef".chars().map(|v| nodes[&v]).collect::<Vec<_>>());
//! ```

use crate::maxflow::MaxFlow;

use crate::adapters::{Network, NetworkEdge};
use crate::traits::{Directed, GraphSize, IndexDigraph, IndexGraph};
use crate::vec::{EdgeVec, NodeVec};

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

use crate::num::traits::NumAssign;

/// Max-flow algorithm of Edmonds and Karp.
pub struct EdmondsKarp<'a, G, F>
where
    G: 'a + IndexDigraph<'a>,
{
    g: Network<'a, G>,
    pred: NodeVec<'a, Network<'a, G>, Option<NetworkEdge<G::Edge>>>,
    flow: EdgeVec<'a, Network<'a, G>, F>,
    queue: VecDeque<G::Node>,
    value: F,
}

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

    type Flow = F;

    fn new(g: &'a G) -> Self {
        EdmondsKarp {
            g: Network::new(g),
            pred: NodeVec::new(Network::new(g), None),
            flow: EdgeVec::new(Network::new(g), F::zero()),
            queue: VecDeque::with_capacity(g.num_nodes()),
            value: F::zero(),
        }
    }

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

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

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

    fn solve<Us>(&mut self, src: G::Node, snk: G::Node, upper: Us)
    where
        Us: Fn(G::Edge) -> Self::Flow,
    {
        assert_ne!(
            self.g.node_id(src),
            self.g.node_id(snk),
            "Source and sink node must not be equal"
        );

        // initialize network flow
        for e in self.g.edges() {
            self.flow[e] = if e.is_forward() { F::zero() } else { upper(e.edge()) };
        }
        self.value = F::zero();

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

        loop {
            // do bfs from source to sink
            for u in self.g.nodes() {
                self.pred[u] = None
            }
            // just some dummy edge
            self.pred[src] = Some(self.g.id2edge(0));
            self.queue.clear();
            self.queue.push_back(src);
            'bfs: while let Some(u) = self.queue.pop_front() {
                for (e, v) in self.g.outedges(u) {
                    if self.pred[v].is_none() && !self.flow[e.reverse()].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 v = snk;
            let e = self.pred[v].unwrap();
            let mut df = self.flow[e.reverse()];
            v = self.g.src(e);
            while v != src {
                let e = self.pred[v].unwrap();
                df = min(df, self.flow[e.reverse()]);
                v = self.g.src(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[e.reverse()] -= df;
                v = self.g.src(e);
            }

            self.value += df;
        }
    }

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