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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

// Copyright (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/>
//

//! Maximum Network Flow algorithms.

use {Graph, IndexGraph, IndexNetwork, EdgeSlice, EdgeVec};

use num::traits::{Num, NumAssign};

/// Trait for max flow algorithms.
pub trait MaxFlow<'a> {
    /// Type of the underlying graph.
    type Graph: IndexGraph<'a>;

    /// Type of flows.
    type Flow : Num + Ord;

    /// Create a new maxflow algorithm instance for a graph.
    fn new(g: &'a Self::Graph) -> Self;

    /// Return the underlying graph.
    fn as_graph(&self) -> &'a Self::Graph;

    /// Return the value of the latest computed maximum flow.
    fn value(&self) -> Self::Flow;

    /// The flow of an Edge.
    fn flow(&self, a: <Self::Graph as Graph<'a>>::Edge) -> Self::Flow;

    /// The flow as vector.
    fn flow_vec(&self) -> EdgeVec<'a, Self::Graph, Self::Flow> {
        let g = self.as_graph();
        edgevec![g, g.edges().map(|e| self.flow(e)).collect()]
    }

    /// Solve the maxflow problem.
    ///
    /// The method solves the max flow problem from the source nodes
    /// `src` to the sink node `snk` with the given `upper` bounds on
    /// the edges.
    fn solve<'b>(&mut self,
                 src: <Self::Graph as Graph<'a>>::Node,
                 snk: <Self::Graph as Graph<'a>>::Node,
                 upper: &EdgeSlice<'a, 'b, Self::Graph, Self::Flow>);

    /// Return the mincut associated with the current flow.
    fn mincut(&self) -> Vec<<Self::Graph as Graph<'a>>::Node>;
}

/// Solve the maxflow problem using the specified algorithm.
///
/// The method solves the max flow problem from the source nodes
/// `src` to the sink node `snk` with the given `upper` bounds on
/// the edges.
///
/// The function returns the flow value, the flow on each edge and the
/// minimal cut containing the source.
pub fn solve<'a, 'b, G, F, M>(g: &'a G,
                              src: G::Node, snk: G::Node,
                              upper: &EdgeSlice<'a, 'b, G, F>)
                              -> (F, EdgeVec<'a, G, F>, Vec<G::Node>)
    where G: IndexGraph<'a>,
          F: Num + Ord + Copy,
          M: MaxFlow<'a, Graph=G, Flow=F>
{
    let mut maxflow = M::new(g);
    maxflow.solve(src, snk, upper);
    (maxflow.value(), maxflow.flow_vec(), maxflow.mincut())
}

/// Solve the maxflow problem using the algorithm of Edmonds-Karp.
pub fn edmondskarp<'a, 'b, G, F>(g: &'a G,
                                 src: G::Node, snk: G::Node,
                                 upper: &EdgeSlice<'a, 'b, G, F>)
                                 -> (F, EdgeVec<'a, G, F>, Vec<G::Node>)
    where G: IndexNetwork<'a>,
          F: NumAssign + Ord + Copy,
{
    solve::<G, F, EdmondsKarp<G, F>>(g, src, snk, upper)
}

/// Solve the maxflow problem using Dinic' algorithm.
pub fn dinic<'a, 'b, G, F>(g: &'a G,
                           src: G::Node, snk: G::Node,
                           upper: &EdgeSlice<'a, 'b, G, F>)
                           -> (F, EdgeVec<'a, G, F>, Vec<G::Node>)
    where G: IndexNetwork<'a>,
          F: NumAssign + Ord + Copy,
{
    solve::<G, F, Dinic<G, F>>(g, src, snk, upper)
}

/// Solve the maxflow problem using Dinic' algorithm.
pub fn pushrelabel<'a, 'b, G, F>(g: &'a G,
                                 src: G::Node, snk: G::Node,
                                 upper: &EdgeSlice<'a, 'b, G, F>)
                           -> (F, EdgeVec<'a, G, F>, Vec<G::Node>)
    where G: IndexNetwork<'a>,
          F: NumAssign + Ord + Copy,
{
    solve::<G, F, PushRelabel<G, F>>(g, src, snk, upper)
}


pub mod edmondskarp;
pub use self::edmondskarp::EdmondsKarp;

pub mod dinic;
pub use self::dinic::Dinic;

pub mod pushrelabel;
pub use self::pushrelabel::PushRelabel;