RhodeCode

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:

- \ref EdmondsKarp Edmonds-Karp algorithm.

- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.

- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.

- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.

In most cases the \ref Preflow "Preflow" algorithm provides the

fastest method for computing a maximum flow. All implementations

*/

/**

@defgroup min_cost_flow 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

circulations.

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)

and arc costs.

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

  matching in bipartite graphs.

- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating

  maximum cardinality matching in general graphs.

- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating

  maximum weighted matching in general graphs.

- \ref MaxWeightedPerfectMatching

  Edmond's blossom shrinking algorithm for calculating maximum weighted

  perfect matching in general graphs.

\image html bipartite_matching.png

\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth

*/

/**

@defgroup spantree Minimum Spanning Tree Algorithms

@ingroup algs

*/

/**

@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 approx Approximation Algorithms

@ingroup algs

\brief Approximation algorithms.

and <b>O</b>ptimization in <b>N</b>etworks.

It is a C++ template

library aimed at combinatorial optimization tasks which

often involve in working

with graphs.

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

\subsection howtoread How to read the documentation

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

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

*/

          (*_matching)[u] = _graph.direct(e, true);

          (*_status)[u] = MATCHED;

          Node v = _graph.v(e);

          if ((*_matching)[v] != INVALID) return false;

          (*_matching)[v] = _graph.direct(e, false);

          (*_status)[v] = MATCHED;

        }

      }

      return true;

    }

    /// \brief Start Edmonds' algorithm

    ///

    /// This function runs the original Edmonds' algorithm.

    ///

    /// called before using this function.

    void startSparse() {

      for(NodeIt n(_graph); n != INVALID; ++n) {

        if ((*_status)[n] == UNMATCHED) {

          (*_blossom_rep)[_blossom_set->insert(n)] = n;

          _tree_set->insert(n);

          (*_status)[n] = EVEN;

          processSparse(n);

        }

      }

    }

    /// \brief Start Edmonds' algorithm with a heuristic improvement 

    /// for dense graphs

    ///

    /// This function runs Edmonds' algorithm with a heuristic of postponing

    /// shrinks, therefore resulting in a faster algorithm for dense graphs.

    ///

    /// called before using this function.

    void startDense() {

      for(NodeIt n(_graph); n != INVALID; ++n) {

        if ((*_status)[n] == UNMATCHED) {

          (*_blossom_rep)[_blossom_set->insert(n)] = n;

          _tree_set->insert(n);

          (*_status)[n] = EVEN;

          processDense(n);

        }

      }

    }

    /// \brief Run Edmonds' algorithm

    ///

    /// This function runs Edmonds' algorithm. An additional heuristic of