RhodeCode

*/

/**

@defgroup auxdat Auxiliary Data Structures

@ingroup datas

\brief Auxiliary data structures implemented in LEMON.

This group contains some data structures implemented in LEMON in

order to make it easier to implement combinatorial algorithms.

*/

/**

@defgroup geomdat Geometric Data Structures

@ingroup auxdat

\brief Geometric data structures implemented in LEMON.

This group contains geometric data structures implemented in LEMON.

 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional

   vector with the usual operations.

 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the

   rectangular bounding box of a set of \ref lemon::dim2::Point

   "dim2::Point"'s.

*/

/**

@defgroup matrices Matrices

@ingroup auxdat

\brief Two dimensional data storages implemented in LEMON.

This group contains two dimensional data storages implemented in LEMON.

*/

/**

@defgroup algs Algorithms

\brief This group contains the several algorithms

implemented in LEMON.

This group contains the several algorithms

implemented in LEMON.

*/

/**

@defgroup search Graph Search

@ingroup algs

\brief Common graph search algorithms.

This group contains the common graph search algorithms, namely

*/

/**

@defgroup shortest_path Shortest Path Algorithms

@ingroup algs

\brief Algorithms for finding shortest paths.

 - \ref Dijkstra algorithm for finding shortest paths from a source node

   when all arc lengths are non-negative.

 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths

   from a source node when arc lenghts can be either positive or negative,

   but the digraph should not contain directed cycles with negative total

   length.

 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms

   for solving the \e all-pairs \e shortest \e paths \e problem when arc

   lenghts can be either positive or negative, but the digraph should

   not contain directed cycles with negative total length.

 - \ref Suurballe A successive shortest path algorithm for finding

   arc-disjoint paths between two nodes having minimum total length.

*/

/**

@defgroup spantree Minimum Spanning Tree Algorithms

@ingroup algs

\brief Algorithms for finding minimum cost spanning trees and arborescences.

This group contains the algorithms for finding minimum cost spanning

*/

/**

@defgroup max_flow Maximum Flow Algorithms

@ingroup algs

\brief Algorithms for finding maximum flows.

This group contains the algorithms for finding maximum flows and

The \e maximum \e flow \e problem is to find a flow of maximum value between

a single source and a single target. Formally, there is a \f$G=(V,A)\f$

digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and

\f$s, t \in V\f$ source and target nodes.

A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the

following optimization problem.

\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]

\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)

    \quad \forall u\in V\setminus\{s,t\} \f]

\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]

LEMON contains several algorithms for solving maximum flow problems:

fastest method for computing a maximum flow. All implementations

also provide functions to query the minimum cut, which is the dual

problem of maximum flow.

\ref Circulation is a preflow push-relabel algorithm implemented directly 

for finding feasible circulations, which is a somewhat different problem,

but it is strongly related to maximum flow.

For more information, see \ref Circulation.

*/

/**

@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms

@ingroup algs

\brief Algorithms for finding minimum cost flows and circulations.

This group contains the algorithms for finding minimum cost flows and

LEMON contains several algorithms for this problem.

 - \ref NetworkSimplex Primal Network Simplex algorithm with various

 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on

 - \ref CapacityScaling Successive Shortest %Path algorithm with optional

In general NetworkSimplex is the most efficient implementation,

but in special cases other algorithms could be faster.

For example, if the total supply and/or capacities are rather small,

CapacityScaling is usually the fastest algorithm (without effective scaling).

*/

/**

@defgroup min_cut Minimum Cut Algorithms

@ingroup algs

\brief Algorithms for finding minimum cut in graphs.

This group contains the algorithms for finding minimum cut in graphs.

The \e minimum \e cut \e problem is to find a non-empty and non-complete

\f$X\f$ subset of the nodes with minimum overall capacity on

outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a

\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

cut is the \f$X\f$ solution of the next optimization problem:

\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}

    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]

LEMON contains several algorithms related to minimum cut problems:

- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut

  in directed graphs.

- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for

  calculating minimum cut in undirected graphs.

- \ref GomoryHu "Gomory-Hu tree computation" for calculating

  all-pairs minimum cut in undirected graphs.

If you want to find minimum cut just between two distinict nodes,

see the \ref max_flow "maximum flow problem".

*/

/**

@defgroup matching Matching Algorithms

@ingroup algs

\brief Algorithms for finding matchings in graphs and bipartite graphs.

This group contains the algorithms for calculating

matchings in graphs and bipartite graphs. The general matching problem is

finding a subset of the edges for which each node has at most one incident

edge.

There are several different algorithms for calculate matchings in

This group contains the algorithms for discovering the graph properties

like connectivity, bipartiteness, euler property, simplicity etc.

\image html connected_components.png

\image latex connected_components.eps "Connected components" width=\textwidth

*/

/**

@defgroup planar Planarity Embedding and Drawing

@ingroup algs

\brief Algorithms for planarity checking, embedding and drawing

This group contains the algorithms for planarity checking,

embedding and drawing.

\image html planar.png

\image latex planar.eps "Plane graph" width=\textwidth

*/

/**

@defgroup approx Approximation Algorithms

@ingroup algs

\brief Approximation algorithms.

This group contains the approximation and heuristic algorithms

implemented in LEMON.

*/

/**

@defgroup auxalg Auxiliary Algorithms

@ingroup algs

\brief Auxiliary algorithms implemented in LEMON.

This group contains some algorithms implemented in LEMON

in order to make it easier to implement complex algorithms.

*/

/**

@defgroup gen_opt_group General Optimization Tools

\brief This group contains some general optimization frameworks

implemented in LEMON.

This group contains some general optimization frameworks

implemented in LEMON.

*/

/**

@ingroup gen_opt_group

*/

/**

@defgroup lp_utils Tools for Lp and Mip Solvers

@ingroup lp_group

\brief Helper tools to the Lp and Mip solvers.

This group adds some helper tools to general optimization framework

implemented in LEMON.

*/

/**

@defgroup metah Metaheuristics

@ingroup gen_opt_group

\brief Metaheuristics for LEMON library.

This group contains some metaheuristic optimization tools.

*/

/**

@defgroup utils Tools and Utilities

\brief Tools and utilities for programming in LEMON

Tools and utilities for programming in LEMON.

*/

/**

@defgroup gutils Basic Graph Utilities

@ingroup utils

\brief Simple basic graph utilities.

This group contains some simple basic graph utilities.

*/

/**

@defgroup misc Miscellaneous Tools

@ingroup utils

\brief Tools for development, debugging and testing.

This group contains several useful tools for development,

debugging and testing.

*/

/**

@defgroup timecount Time Measuring and Counting

@ingroup misc

\brief Simple tools for measuring the performance of algorithms.

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

/**

\mainpage LEMON Documentation

\section intro Introduction

<b>

LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>

project.

You are free to use it in your commercial or

non-commercial applications under very permissive

\ref license "license terms".

</b>

If you would like to get to know the library, see

<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.

If you know what you are looking for, then try to find it under the

<a class="el" href="modules.html">Modules</a> section.

If you are a user of the old (0.x) series of LEMON, please check out the

\ref migration "Migration Guide" for the backward incompatibilities.

*/

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

namespace lemon {

/**

\page min_cost_flow Minimum Cost Flow Problem

\section mcf_def Definition (GEQ form)

The \e minimum \e cost \e flow \e problem is to find a feasible flow of

minimum total cost from a set of supply nodes to a set of demand nodes

in a network with capacity constraints (lower and upper bounds)

Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,

\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and

upper bounds for the flow values on the arcs, for which

\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,

\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow

on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the

signed supply values of the nodes.

If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$

supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with

\f$-sup(u)\f$ demand.

A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution

of the following optimization problem.

\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq

    sup(u) \quad \forall u\in V \f]

\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]

The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

zero or negative in order to have a feasible solution (since the sum

of the expressions on the left-hand side of the inequalities is zero).

It means that the total demand must be greater or equal to the total

supply and all the supplies have to be carried out from the supply nodes,

but there could be demands that are not satisfied.

If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand

constraints have to be satisfied with equality, i.e. all demands

have to be satisfied and all supplies have to be used.

\section mcf_algs Algorithms

LEMON contains several algorithms for solving this problem, for more

information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".

A feasible solution for this problem can be found using \ref Circulation.

\section mcf_dual Dual Solution

The dual solution of the minimum cost flow problem is represented by

node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.

An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal

if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials

the following \e complementary \e slackness optimality conditions hold.

 - For all \f$uv\in A\f$ arcs:

   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

  title =        {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented

                  {S}implex},

  url =          {http://soplex.zib.de/}

}

%%%%% General books %%%%%

@book{amo93networkflows,

  author =       {Ravindra K. Ahuja and Thomas L. Magnanti and James

                  B. Orlin},

  title =        {Network Flows: Theory, Algorithms, and Applications},

  publisher =    {Prentice-Hall, Inc.},

  year =         1993,

  month =        feb,

  isbn =         {978-0136175490}

}

@book{schrijver03combinatorial,

  author =       {Alexander Schrijver},

  title =        {Combinatorial Optimization: Polyhedra and Efficiency},

  publisher =    {Springer-Verlag},

  year =         2003,

  isbn =         {978-3540443896}

}

@book{clrs01algorithms,

  author =       {Thomas H. Cormen and Charles E. Leiserson and Ronald

                  L. Rivest and Clifford Stein},

  title =        {Introduction to Algorithms},

  publisher =    {The MIT Press},

  year =         2001,

  edition =      {2nd}

}

@book{stroustrup00cpp,

  author =       {Bjarne Stroustrup},

  title =        {The C++ Programming Language},

  edition =      {3rd},

  publisher =    {Addison-Wesley Professional},

  isbn =         0201700735,

  month =        {February},

  year =         2000

}

%%%%% Maximum flow algorithms %%%%%

  author =       {Andrew V. Goldberg and Robert E. Tarjan},

  title =        {A new approach to the maximum flow problem},

}

@article{dinic70algorithm,

  author =       {E. A. Dinic},

  title =        {Algorithm for solution of a problem of maximum flow

                  in a network with power estimation},

  journal =      {Soviet Math. Doklady},

  year =         1970,

  volume =       11,

  pages =        {1277-1280}

}

@article{goldberg08partial,

  author =       {Andrew V. Goldberg},

  title =        {The Partial Augment-Relabel Algorithm for the

                  Maximum Flow Problem},

  journal =      {16th Annual European Symposium on Algorithms},

  year =         2008,

  pages =        {466-477}

}

@article{sleator83dynamic,

  author =       {Daniel D. Sleator and Robert E. Tarjan},

  title =        {A data structure for dynamic trees},

  journal =      {Journal of Computer and System Sciences},

  year =         1983,

  volume =       26,

  number =       3,

  pages =        {362-391}

}

%%%%% Minimum mean cycle algorithms %%%%%

@article{karp78characterization,

  author =       {Richard M. Karp},

  title =        {A characterization of the minimum cycle mean in a

                  digraph},

  journal =      {Discrete Math.},

  year =         1978,

  volume =       23,

  pages =        {309-311}

}

@article{dasdan98minmeancycle,

  author =       {Ali Dasdan and Rajesh K. Gupta},

  title =        {Faster Maximum and Minimum Mean Cycle Alogrithms for

                  System Performance Analysis},

  journal =      {IEEE Transactions on Computer-Aided Design of

                  Integrated Circuits and Systems},

  year =         1998,

  volume =       17,

  number =       10,

  pages =        {889-899}

}

%%%%% Minimum cost flow algorithms %%%%%

@article{klein67primal,

  author =       {Morton Klein},

  title =        {A primal method for minimal cost flows with

                  applications to the assignment and transportation

                  problems},

  journal =      {Management Science},

  year =         1967,

  volume =       14,

  pages =        {205-220}

}

  author =       {Andrew V. Goldberg and Robert E. Tarjan},

  title =        {Finding minimum-cost circulations by canceling

                  negative cycles},

}

  author =       {Andrew V. Goldberg and Robert E. Tarjan},

  title =        {Finding Minimum-Cost Circulations by Successive

                  Approximation},

  journal =      {Mathematics of Operations Research},

  year =         1990,

  volume =       15,

  number =       3,

  pages =        {430-466}

}

@article{goldberg97efficient,

  author =       {Andrew V. Goldberg},

  title =        {An Efficient Implementation of a Scaling

                  Minimum-Cost Flow Algorithm},

  journal =      {Journal of Algorithms},

  year =         1997,

  volume =       22,

  number =       1,

  pages =        {1-29}

}

@article{bunnagel98efficient,

  author =       {Ursula B{\"u}nnagel and Bernhard Korte and Jens

                  Vygen},

  title =        {Efficient implementation of the {G}oldberg-{T}arjan

                  minimum-cost flow algorithm},

  journal =      {Optimization Methods and Software},

  year =         1998,

  volume =       10,

  pages =        {157-174}

}

@mastersthesis{kellyoneill91netsimplex,

  author =       {Damian J. Kelly and Garrett M. O'Neill},

  title =        {The Minimum Cost Flow Problem and The Network

                  Simplex Method},

  school =       {University College},

  address =      {Dublin, Ireland},

  year =         1991,

  month =        sep,

}

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_NETWORK_SIMPLEX_H

#define LEMON_NETWORK_SIMPLEX_H

/// \ingroup min_cost_flow_algs

///

/// \file

/// \brief Network Simplex algorithm for finding a minimum cost flow.

#include <vector>

#include <limits>

#include <algorithm>

#include <lemon/core.h>

#include <lemon/math.h>

namespace lemon {

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of the primal Network Simplex algorithm

  /// for finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref NetworkSimplex implements the primal Network Simplex algorithm

  /// This algorithm is a specialized version of the linear programming

  /// simplex method directly for the minimum cost flow problem.

  /// It is one of the most efficient solution methods.

  ///

  /// In general this class is the fastest implementation available

  /// in LEMON for the minimum cost flow problem.

  /// Moreover it supports both directions of the supply/demand inequality

  /// constraints. For more information see \ref SupplyType.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

  /// \tparam GR The digraph type the algorithm runs on.

  /// \tparam V The value type used for flow amounts, capacity bounds

  /// and supply values in the algorithm. By default it is \c int.

  /// \tparam C The value type used for costs and potentials in the

  /// algorithm. By default it is the same as \c V.

  ///

  /// \warning Both value types must be signed and all input data must

  /// be integer.

  ///

  /// \note %NetworkSimplex provides five different pivot rule

  /// implementations, from which the most efficient one is used

  /// by default. For more information see \ref PivotRule.

  template <typename GR, typename V = int, typename C = V>

  class NetworkSimplex

  {

  public:

    /// The type of the flow amounts, capacity bounds and supply values

    typedef V Value;

    /// The type of the arc costs

    typedef C Cost;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

#else

    typedef typename Digraph::template ArcMap<Value> FlowMap;

#endif

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// \param digraph The digraph for which we would like to define

    /// the flow map.

    static FlowMap* createFlowMap(const Digraph& digraph) {

      return new FlowMap(digraph);

    }

    /// \brief The elevator type used by Preflow algorithm.

    ///

    /// The elevator type used by Preflow algorithm.

    ///

    /// \sa Elevator, LinkedElevator

#ifdef DOXYGEN

    typedef lemon::Elevator<GR, GR::Node> Elevator;

#else

    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;

#endif

    /// \brief Instantiates an Elevator.

    ///

    /// This function instantiates an \ref Elevator.

    /// \param digraph The digraph for which we would like to define

    /// the elevator.

    /// \param max_level The maximum level of the elevator.

    static Elevator* createElevator(const Digraph& digraph, int max_level) {

      return new Elevator(digraph, max_level);

    }

    /// \brief The tolerance used by the algorithm

    ///

    /// The tolerance used by the algorithm to handle inexact computation.

    typedef lemon::Tolerance<Value> Tolerance;

  };

  /// \ingroup max_flow

  ///

  /// \brief %Preflow algorithm class.

  ///

  /// This class provides an implementation of Goldberg-Tarjan's \e preflow

  /// \e push-relabel algorithm producing a \ref max_flow

  /// The preflow algorithms are the fastest known maximum

  /// flow algorithms. The current implementation uses a mixture of the

  /// \e "highest label" and the \e "bound decrease" heuristics.

  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.

  ///

  /// The algorithm consists of two phases. After the first phase

  /// the maximum flow value and the minimum cut is obtained. The

  /// second phase constructs a feasible maximum flow on each arc.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam CAP The type of the capacity map. The default map

  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename CAP, typename TR>

#else

  template <typename GR,

            typename CAP = typename GR::template ArcMap<int>,

            typename TR = PreflowDefaultTraits<GR, CAP> >

#endif

  class Preflow {

  public:

    ///The \ref PreflowDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The type of the capacity map.

    typedef typename Traits::CapacityMap CapacityMap;

    ///The type of the flow values.

    typedef typename Traits::Value Value;

    ///The type of the flow map.

    typedef typename Traits::FlowMap FlowMap;

    ///The type of the elevator.

    typedef typename Traits::Elevator Elevator;

    ///The type of the tolerance.

    typedef typename Traits::Tolerance Tolerance;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    const Digraph& _graph;

    const CapacityMap* _capacity;

    int _node_num;

    Node _source, _target;