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
126
127
128
129
130
131
132

// Copyright (c) 2015, 2016, 2017, 2018, 2020 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 crate::num::traits::{Num, NumAssign};
use crate::traits::{GraphType, IndexDigraph, IndexGraph};
use crate::vec::EdgeVec;

/// 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 GraphType<'a>>::Edge) -> Self::Flow;

    /// The flow as vector.
    fn flow_vec(&self) -> EdgeVec<'a, &'a Self::Graph, Self::Flow> {
        EdgeVec::new_with(self.as_graph(), |e| self.flow(e))
    }

    /// 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<Us>(
        &mut self,
        src: <Self::Graph as GraphType<'a>>::Node,
        snk: <Self::Graph as GraphType<'a>>::Node,
        upper: Us,
    ) where
        Us: Fn(<Self::Graph as GraphType<'a>>::Edge) -> Self::Flow;

    /// Return the mincut associated with the current flow.
    fn mincut(&self) -> Vec<<Self::Graph as GraphType<'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, G, F, Us, M>(g: &'a G, src: G::Node, snk: G::Node, upper: Us) -> (F, EdgeVec<&'a G, F>, Vec<G::Node>)
where
    G: IndexGraph<'a>,
    F: Num + Ord + Copy,
    Us: Fn(G::Edge) -> F,
    M: 'a + 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, G, F, Us>(
    g: &'a G,
    src: G::Node,
    snk: G::Node,
    upper: Us,
) -> (F, EdgeVec<&'a G, F>, Vec<G::Node>)
where
    G: IndexDigraph<'a>,
    F: 'a + NumAssign + Ord + Copy,
    Us: Fn(G::Edge) -> F,
{
    solve::<G, F, Us, EdmondsKarp<G, F>>(g, src, snk, upper)
}

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

/// Solve the maxflow problem using the push-relabel algorithm.
pub fn pushrelabel<'a, G, F, Us>(
    g: &'a G,
    src: G::Node,
    snk: G::Node,
    upper: Us,
) -> (F, EdgeVec<&'a G, F>, Vec<G::Node>)
where
    G: IndexDigraph<'a>,
    F: 'a + NumAssign + Ord + Copy,
    Us: Fn(G::Edge) -> F,
{
    solve::<G, F, Us, 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;