RhodeCode

- \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 min_mean_cycle Minimum Mean Cycle Algorithms

@ingroup algs

\brief Algorithms for finding minimum mean cycles.

The \e minimum \e mean \e cycle \e problem is to find a directed cycle

of minimum mean length (cost) in a digraph.

The mean length of a cycle is the average length of its arcs, i.e. the

ratio between the total length of the cycle and the number of arcs on it.

This problem has an important connection to \e conservative \e length

\e functions, too. A length function on the arcs of a digraph is called

conservative if and only if there is no directed cycle of negative total

length. For an arbitrary length function, the negative of the minimum

cycle mean is the smallest \f$\epsilon\f$ value so that increasing the

arc lengths uniformly by \f$\epsilon\f$ results in a conservative length

function.

LEMON contains three algorithms for solving the minimum mean cycle problem:

- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved

In practice, the Howard algorithm proved to be by far the most efficient

one, though the best known theoretical bound on its running time is

exponential.

Both Karp and HartmannOrlin algorithms run in time O(ne) and use space

O(n<sup>2</sup>+e), but the latter one is typically faster due to the

applied early termination scheme.

*/

/**

@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

    typedef long long LargeValue;

#else

    typedef long LargeValue;

#endif

    typedef lemon::Tolerance<LargeValue> Tolerance;

    typedef lemon::Path<Digraph> Path;

  };

  /// \addtogroup min_mean_cycle

  /// @{

  /// \brief Implementation of the Hartmann-Orlin algorithm for finding

  /// a minimum mean cycle.

  ///

  /// This class implements the Hartmann-Orlin algorithm for finding

  /// It is an improved version of \ref Karp "Karp"'s original algorithm,

  /// it applies an efficient early termination scheme.

  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

  ///

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

  /// \tparam LEN The type of the length map. The default

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

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

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

             typename TR = HartmannOrlinDefaultTraits<GR, LEN> >

#endif

  class HartmannOrlin

  {

    typedef long long LargeValue;

#else

    typedef long LargeValue;

#endif

    typedef lemon::Tolerance<LargeValue> Tolerance;

    typedef lemon::Path<Digraph> Path;

  };

  /// \addtogroup min_mean_cycle

  /// @{

  /// \brief Implementation of Howard's algorithm for finding a minimum

  /// mean cycle.

  ///

  /// This class implements Howard's policy iteration algorithm for finding

  /// This class provides the most efficient algorithm for the

  /// minimum mean cycle problem, though the best known theoretical

  /// bound on its running time is exponential.

  ///

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

  /// \tparam LEN The type of the length map. The default

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

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

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

             typename TR = HowardDefaultTraits<GR, LEN> >

#endif

  class Howard

  {

    typedef long long LargeValue;

#else

    typedef long LargeValue;

#endif

    typedef lemon::Tolerance<LargeValue> Tolerance;

    typedef lemon::Path<Digraph> Path;

  };

  /// \addtogroup min_mean_cycle

  /// @{

  /// \brief Implementation of Karp's algorithm for finding a minimum

  /// mean cycle.

  ///

  /// This class implements Karp's algorithm for finding a directed

  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

  ///

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

  /// \tparam LEN The type of the length map. The default

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

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

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

             typename TR = KarpDefaultTraits<GR, LEN> >

#endif

  class Karp

  {

  public: