RhodeCode

/**

@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]

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.

/* -*- 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.

*/

 * 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,

}

@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},

  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,

}

#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

    /// \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;