RhodeCode

/**

@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

/**

@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

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

@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).

*/

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.

/**

\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.

\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

  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 =      {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,

  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,

}

  /// @{

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

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