RhodeCode

/// \brief Cycle-canceling algorithms for finding a minimum cost flow.

#include <vector>

#include <limits>

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/path.h>

#include <lemon/math.h>

#include <lemon/static_graph.h>

#include <lemon/adaptors.h>

#include <lemon/circulation.h>

#include <lemon/bellman_ford.h>

#include <lemon/howard.h>

namespace lemon {

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of cycle-canceling algorithms for

  /// finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref CycleCanceling implements three different cycle-canceling

  /// The most efficent one (both theoretically and practically)

  /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,

  /// thus it is the default method.

  /// It is strongly polynomial, but in practice, it is typically much

  /// slower than the scaling algorithms and NetworkSimplex.

  ///

  /// 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 number type used for flow amounts, capacity bounds

  /// and supply values in the algorithm. By default, it is \c int.

  /// \tparam C The number type used for costs and potentials in the

  /// algorithm. By default, it is the same as \c V.

  ///

  /// \warning Both number types must be signed and all input data must

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

  ///

  /// \note For more information about the three available methods,

  /// see \ref Method.

      /// upper bound. It means that the objective function is unbounded

      /// on that arc, however, note that it could actually be bounded

      /// over the feasible flows, but this algroithm cannot handle

      /// these cases.

      UNBOUNDED

    };

    /// \brief Constants for selecting the used method.

    ///

    /// Enum type containing constants for selecting the used method

    /// for the \ref run() function.

    ///

    /// \ref CycleCanceling provides three different cycle-canceling

    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"

    /// is used, which proved to be the most efficient and the most robust

    /// on various test inputs.

    /// However, the other methods can be selected using the \ref run()

    /// function with the proper parameter.

    enum Method {

      /// A simple cycle-canceling method, which uses the

      /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration

      /// number for detecting negative cycles in the residual network.

      SIMPLE_CYCLE_CANCELING,

      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a

      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.

      /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).

      MINIMUM_MEAN_CYCLE_CANCELING,

      /// The "Cancel And Tighten" algorithm, which can be viewed as an

      /// It is faster both in theory and in practice, its running time

      /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).

      CANCEL_AND_TIGHTEN

    };

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef std::vector<int> IntVector;

    typedef std::vector<char> CharVector;

    typedef std::vector<double> DoubleVector;

    typedef std::vector<Value> ValueVector;

    typedef std::vector<Cost> CostVector;

  private:

    template <typename KT, typename VT>

    class VectorMap {

    public:

      typedef KT Key;

      typedef VT Value;

      VectorMap(std::vector<Value>& v) : _v(v) {}