RhodeCode

@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

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.

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

  ///

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

  ///

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