RhodeCode

    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The digraph contains an arc of negative cost and infinite

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

    };

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef std::vector<int> IntVector;

    typedef std::vector<Value> ValueVector;

    typedef std::vector<Cost> CostVector;

    typedef std::vector<char> BoolVector;

    // Note: vector<char> is used instead of vector<bool> for efficiency reasons

  private:

    // Data related to the underlying digraph

    const GR &_graph;

    int _node_num;

    int _arc_num;

    int _res_arc_num;

    int _root;

    // Parameters of the problem

    bool _have_lower;

    Value _sum_supply;

    // Data structures for storing the digraph

    IntNodeMap _node_id;

    IntArcMap _arc_idf;

    IntArcMap _arc_idb;

    IntVector _first_out;

    BoolVector _forward;

    IntVector _source;

    IntVector _target;

    IntVector _reverse;

    // Node and arc data

    ValueVector _lower;

    ValueVector _upper;

    CostVector _cost;

    ValueVector _supply;

    ValueVector _res_cap;

    CostVector _pi;

    ValueVector _excess;

    IntVector _excess_nodes;

    IntVector _deficit_nodes;

    Value _delta;

    int _factor;

    IntVector _pred;

  public:

    /// \brief Constant for infinite upper bounds (capacities).

    ///

    /// Constant for infinite upper bounds (capacities).

    /// It is \c std::numeric_limits<Value>::infinity() if available,

    /// \c std::numeric_limits<Value>::max() otherwise.

    const Value INF;

  private:

    // Special implementation of the Dijkstra algorithm for finding

    // shortest paths in the residual network of the digraph with

    // respect to the reduced arc costs and modifying the node

    // potentials according to the found distance labels.

    class ResidualDijkstra

    {

    private:

      int _node_num;

      bool _geq;

      const IntVector &_first_out;

      const IntVector &_target;

      const CostVector &_cost;

      const ValueVector &_res_cap;

      const ValueVector &_excess;

      CostVector &_pi;

      IntVector &_pred;

      IntVector _proc_nodes;

      CostVector _dist;

    public:

      ResidualDijkstra(CapacityScaling& cs) :

        _node_num(cs._node_num), _geq(cs._sum_supply < 0),

        _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),

        _res_cap(cs._res_cap), _excess(cs._excess), _pi(cs._pi),

        _pred(cs._pred), _dist(cs._node_num)

      {}

      int run(int s, Value delta = 1) {

        RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP);

        Heap heap(heap_cross_ref);

        heap.push(s, 0);

        _pred[s] = -1;

        _proc_nodes.clear();

        // Process nodes

        while (!heap.empty() && _excess[heap.top()] > -delta) {

          int u = heap.top(), v;

          Cost d = heap.prio() + _pi[u], dn;

          _dist[u] = heap.prio();

          _proc_nodes.push_back(u);

          heap.pop();

          // Traverse outgoing residual arcs

          int last_out = _geq ? _first_out[u+1] : _first_out[u+1] - 1;

          for (int a = _first_out[u]; a != last_out; ++a) {

            if (_res_cap[a] < delta) continue;

            v = _target[a];

            switch (heap.state(v)) {

              case Heap::PRE_HEAP:

                heap.push(v, d + _cost[a] - _pi[v]);

                _pred[v] = a;

                break;

              case Heap::IN_HEAP:

                dn = d + _cost[a] - _pi[v];

                if (dn < heap[v]) {

                  heap.decrease(v, dn);

                  _pred[v] = a;

                }

                break;

              case Heap::POST_HEAP:

                break;

            }

          }

        }

        if (heap.empty()) return -1;

        // Update potentials of processed nodes

        int t = heap.top();

        Cost dt = heap.prio();

        for (int i = 0; i < int(_proc_nodes.size()); ++i) {

          _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - dt;

        }

        return t;

      }

    }; //class ResidualDijkstra

  public:

    /// \name Named Template Parameters

    /// @{

    template <typename T>

    struct SetHeapTraits : public Traits {

      typedef T Heap;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c Heap type.

    ///

    /// \ref named-templ-param "Named parameter" for setting \c Heap

    /// type, which is used for internal Dijkstra computations.

    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,

    /// its priority type must be \c Cost and its cross reference type

    /// must be \ref RangeMap "RangeMap<int>".

    template <typename T>

    struct SetHeap

      : public CapacityScaling<GR, V, C, SetHeapTraits<T> > {

      typedef  CapacityScaling<GR, V, C, SetHeapTraits<T> > Create;

    };

    /// @}

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

    /// \param graph The digraph the algorithm runs on.

    CapacityScaling(const GR& graph) :

      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),

      INF(std::numeric_limits<Value>::has_infinity ?

          std::numeric_limits<Value>::infinity() :

          std::numeric_limits<Value>::max())

    {

      // Check the number types

      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,

        "The flow type of CapacityScaling must be signed");

      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,

        "The cost type of CapacityScaling must be signed");

      // Reset data structures

      reset();

    }

    /// \name Parameters

    /// The parameters of the algorithm can be specified using these

    /// functions.

    /// @{

    /// \brief Set the lower bounds on the arcs.

    ///

    /// This function sets the lower bounds on the arcs.

    /// If it is not used before calling \ref run(), the lower bounds

    /// will be set to zero on all arcs.

    ///

    /// \param map An arc map storing the lower bounds.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    template <typename LowerMap>

    CapacityScaling& lowerMap(const LowerMap& map) {

      _have_lower = true;

      for (ArcIt a(_graph); a != INVALID; ++a) {

        _lower[_arc_idf[a]] = map[a];

        _lower[_arc_idb[a]] = map[a];

      }

      return *this;

    }

    /// \brief Set the upper bounds (capacities) on the arcs.

    ///

    /// This function sets the upper bounds (capacities) on the arcs.

    /// If it is not used before calling \ref run(), the upper bounds

    /// will be set to \ref INF on all arcs (i.e. the flow value will be

    /// unbounded from above).

    ///

    /// \param map An arc map storing the upper bounds.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    template<typename UpperMap>

    CapacityScaling& upperMap(const UpperMap& map) {

      for (ArcIt a(_graph); a != INVALID; ++a) {

        _upper[_arc_idf[a]] = map[a];

      }

      return *this;

    }

    /// \brief Set the costs of the arcs.

    ///

    /// This function sets the costs of the arcs.

    /// If it is not used before calling \ref run(), the costs

    /// will be set to \c 1 on all arcs.

    ///

    /// \param map An arc map storing the costs.

    /// Its \c Value type must be convertible to the \c Cost type

    /// of the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    template<typename CostMap>

    CapacityScaling& costMap(const CostMap& map) {

      for (ArcIt a(_graph); a != INVALID; ++a) {

        _cost[_arc_idf[a]] =  map[a];

        _cost[_arc_idb[a]] = -map[a];

      }

      return *this;

    }

    /// \brief Set the supply values of the nodes.

    ///

    /// This function sets the supply values of the nodes.

    /// If neither this function nor \ref stSupply() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    ///

    /// \param map A node map storing the supply values.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    template<typename SupplyMap>

    CapacityScaling& supplyMap(const SupplyMap& map) {

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

        _supply[_node_id[n]] = map[n];

      }

      return *this;

    }

    /// \brief Set single source and target nodes and a supply value.

    ///

    /// This function sets a single source node and a single target node

    /// and the required flow value.

    /// If neither this function nor \ref supplyMap() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    ///

    /// Using this function has the same effect as using \ref supplyMap()

    /// with such a map in which \c k is assigned to \c s, \c -k is

    /// assigned to \c t and all other nodes have zero supply value.

    ///

    /// \param s The source node.

    /// \param t The target node.

    /// \param k The required amount of flow from node \c s to node \c t

    /// (i.e. the supply of \c s and the demand of \c t).

    ///

    /// \return <tt>(*this)</tt>

    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {

      for (int i = 0; i != _node_num; ++i) {

        _supply[i] = 0;

      }

      _supply[_node_id[s]] =  k;

      _supply[_node_id[t]] = -k;

      return *this;

    }

    /// @}

    /// \name Execution control

    /// The algorithm can be executed using \ref run().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    /// The paramters can be specified using functions \ref lowerMap(),

    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().

    /// For example,

    /// \code

    ///   CapacityScaling<ListDigraph> cs(graph);

    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)

    ///     .supplyMap(sup).run();

    /// \endcode

    ///

    /// This function can be called more than once. All the given parameters

    /// are kept for the next call, unless \ref resetParams() or \ref reset()

    /// is used, thus only the modified parameters have to be set again.

    /// If the underlying digraph was also modified after the construction

    /// of the class (or the last \ref reset() call), then the \ref reset()

    /// function must be called.

    ///

    /// \param factor The capacity scaling factor. It must be larger than

    /// one to use scaling. If it is less or equal to one, then scaling

    /// will be disabled.

    ///

    /// \return \c INFEASIBLE if no feasible flow exists,

    /// \n \c OPTIMAL if the problem has optimal solution

    /// (i.e. it is feasible and bounded), and the algorithm has found

    /// optimal flow and node potentials (primal and dual solutions),

    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost

    /// and infinite 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.

    ///

    /// \see ProblemType

    /// \see resetParams(), reset()

    ProblemType run(int factor = 4) {

      _factor = factor;

      ProblemType pt = init();

      if (pt != OPTIMAL) return pt;

      return start();

    }

    /// \brief Reset all the parameters that have been given before.

    ///

    /// This function resets all the paramaters that have been given

    /// before using functions \ref lowerMap(), \ref upperMap(),

    /// \ref costMap(), \ref supplyMap(), \ref stSupply().

    ///

    /// It is useful for multiple \ref run() calls. Basically, all the given

    /// parameters are kept for the next \ref run() call, unless

    /// The type of the flow amounts, capacity bounds and supply values

    typedef typename TR::Value Value;

    /// The type of the arc costs

    typedef typename TR::Cost Cost;

    /// \brief The large cost type

    ///

    /// The large cost type used for internal computations.

    /// By default, it is \c long \c long if the \c Cost type is integer,

    /// otherwise it is \c double.

    typedef typename TR::LargeCost LargeCost;

    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The digraph contains an arc of negative cost and infinite

      /// 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 internal method.

    ///

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

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

    ///

    /// \ref CostScaling provides three internal methods that differ mainly

    /// in their base operations, which are used in conjunction with the

    /// relabel operation.

    /// By default, the so called \ref PARTIAL_AUGMENT

    /// "Partial Augment-Relabel" method 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 {

      /// Local push operations are used, i.e. flow is moved only on one

      /// admissible arc at once.

      PUSH,

      /// Augment operations are used, i.e. flow is moved on admissible

      /// paths from a node with excess to a node with deficit.

      AUGMENT,

      /// Partial augment operations are used, i.e. flow is moved on 

      /// admissible paths started from a node with excess, but the

      /// lengths of these paths are limited. This method can be viewed

      /// as a combined version of the previous two operations.

      PARTIAL_AUGMENT

    };

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef std::vector<int> IntVector;

    typedef std::vector<Value> ValueVector;

    typedef std::vector<Cost> CostVector;

    typedef std::vector<LargeCost> LargeCostVector;

    typedef std::vector<char> BoolVector;

    // Note: vector<char> is used instead of vector<bool> for efficiency reasons

  private:

    template <typename KT, typename VT>

    class StaticVectorMap {

    public:

      typedef KT Key;

      typedef VT Value;

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

      const Value& operator[](const Key& key) const {

        return _v[StaticDigraph::id(key)];

      }

      Value& operator[](const Key& key) {

        return _v[StaticDigraph::id(key)];

      }

      void set(const Key& key, const Value& val) {

        _v[StaticDigraph::id(key)] = val;

      }

    private:

      std::vector<Value>& _v;

    };

    typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;

    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;

  private:

    // Data related to the underlying digraph

    const GR &_graph;

    int _node_num;

    int _arc_num;

    int _res_node_num;

    int _res_arc_num;

    int _root;

    // Parameters of the problem

    bool _have_lower;

    Value _sum_supply;

    int _sup_node_num;

    // Data structures for storing the digraph

    IntNodeMap _node_id;

    IntArcMap _arc_idf;

    IntArcMap _arc_idb;

    IntVector _first_out;

    BoolVector _forward;

    IntVector _source;

    IntVector _target;

    IntVector _reverse;

    // Node and arc data

    ValueVector _lower;

    ValueVector _upper;

    CostVector _scost;

    ValueVector _supply;

    ValueVector _res_cap;

    LargeCostVector _cost;

    LargeCostVector _pi;

    ValueVector _excess;

    IntVector _next_out;

    std::deque<int> _active_nodes;

    // Data for scaling

    LargeCost _epsilon;

    int _alpha;

    IntVector _buckets;

    IntVector _bucket_next;

    IntVector _bucket_prev;

    IntVector _rank;

    int _max_rank;

    // Data for a StaticDigraph structure

    typedef std::pair<int, int> IntPair;

    StaticDigraph _sgr;

    std::vector<IntPair> _arc_vec;

    std::vector<LargeCost> _cost_vec;

    LargeCostArcMap _cost_map;

    LargeCostNodeMap _pi_map;

  public:

    /// \brief Constant for infinite upper bounds (capacities).

    ///

    /// Constant for infinite upper bounds (capacities).

    /// It is \c std::numeric_limits<Value>::infinity() if available,

    /// \c std::numeric_limits<Value>::max() otherwise.

    const Value INF;

  public:

    /// \name Named Template Parameters

    /// @{

    template <typename T>

    struct SetLargeCostTraits : public Traits {

      typedef T LargeCost;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c LargeCost type.

    ///

    /// \ref named-templ-param "Named parameter" for setting \c LargeCost

    /// type, which is used for internal computations in the algorithm.

    /// \c Cost must be convertible to \c LargeCost.

    template <typename T>

    struct SetLargeCost

      : public CostScaling<GR, V, C, SetLargeCostTraits<T> > {

      typedef  CostScaling<GR, V, C, SetLargeCostTraits<T> > Create;

    };

    /// @}

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

    /// \param graph The digraph the algorithm runs on.

    CostScaling(const GR& graph) :

      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),

      _cost_map(_cost_vec), _pi_map(_pi),

      INF(std::numeric_limits<Value>::has_infinity ?

          std::numeric_limits<Value>::infinity() :

          std::numeric_limits<Value>::max())

    {

      // Check the number types

      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,

        "The flow type of CostScaling must be signed");

      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,

        "The cost type of CostScaling must be signed");

      // Reset data structures

      reset();

    }

    /// \name Parameters

    /// The parameters of the algorithm can be specified using these

    /// functions.

    /// @{

    /// \brief Set the lower bounds on the arcs.

    ///

    /// This function sets the lower bounds on the arcs.

    /// If it is not used before calling \ref run(), the lower bounds

    /// will be set to zero on all arcs.

    ///

    /// \param map An arc map storing the lower bounds.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    template <typename LowerMap>

    CostScaling& lowerMap(const LowerMap& map) {

      _have_lower = true;

      for (ArcIt a(_graph); a != INVALID; ++a) {

        _lower[_arc_idf[a]] = map[a];

        _lower[_arc_idb[a]] = map[a];

      }

      return *this;

    }

    /// \brief Set the upper bounds (capacities) on the arcs.

    ///

    /// This function sets the upper bounds (capacities) on the arcs.

    /// If it is not used before calling \ref run(), the upper bounds

    /// will be set to \ref INF on all arcs (i.e. the flow value will be

    /// unbounded from above).

    ///

    /// \param map An arc map storing the upper bounds.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    template<typename UpperMap>

    CostScaling& upperMap(const UpperMap& map) {

      for (ArcIt a(_graph); a != INVALID; ++a) {

        _upper[_arc_idf[a]] = map[a];

      }

      return *this;

    }

    /// \brief Set the costs of the arcs.

    ///

    /// This function sets the costs of the arcs.

    /// If it is not used before calling \ref run(), the costs

    /// will be set to \c 1 on all arcs.

    ///

    /// \param map An arc map storing the costs.

    /// Its \c Value type must be convertible to the \c Cost type

    /// of the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    template<typename CostMap>

    CostScaling& costMap(const CostMap& map) {

      for (ArcIt a(_graph); a != INVALID; ++a) {

        _scost[_arc_idf[a]] =  map[a];

        _scost[_arc_idb[a]] = -map[a];

      }

      return *this;

    }

    /// \brief Set the supply values of the nodes.

    ///

    /// This function sets the supply values of the nodes.

    /// If neither this function nor \ref stSupply() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    ///

    /// \param map A node map storing the supply values.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    template<typename SupplyMap>

    CostScaling& supplyMap(const SupplyMap& map) {

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

        _supply[_node_id[n]] = map[n];

      }

      return *this;

    }

    /// \brief Set single source and target nodes and a supply value.

    ///

    /// This function sets a single source node and a single target node

    /// and the required flow value.

    /// If neither this function nor \ref supplyMap() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    ///

    /// Using this function has the same effect as using \ref supplyMap()

    /// with such a map in which \c k is assigned to \c s, \c -k is

    /// assigned to \c t and all other nodes have zero supply value.

    ///

    /// \param s The source node.

    /// \param t The target node.

    /// \param k The required amount of flow from node \c s to node \c t

    /// (i.e. the supply of \c s and the demand of \c t).

    ///

    /// \return <tt>(*this)</tt>

    CostScaling& stSupply(const Node& s, const Node& t, Value k) {

      for (int i = 0; i != _res_node_num; ++i) {

        _supply[i] = 0;

      }

      _supply[_node_id[s]] =  k;

      _supply[_node_id[t]] = -k;

      return *this;

    }

    /// @}

    /// \name Execution control

    /// The algorithm can be executed using \ref run().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    /// The paramters can be specified using functions \ref lowerMap(),

    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().

    /// For example,

    /// \code

    ///   CostScaling<ListDigraph> cs(graph);

    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)

    ///     .supplyMap(sup).run();

    /// \endcode

    ///

    /// This function can be called more than once. All the given parameters

    /// are kept for the next call, unless \ref resetParams() or \ref reset()

    /// is used, thus only the modified parameters have to be set again.

    /// If the underlying digraph was also modified after the construction

    /// of the class (or the last \ref reset() call), then the \ref reset()

    /// function must be called.

    ///

    /// \param method The internal method that will be used in the

    /// algorithm. For more information, see \ref Method.

    /// \param factor The cost scaling factor. It must be larger than one.

    ///

    /// \return \c INFEASIBLE if no feasible flow exists,

    /// \n \c OPTIMAL if the problem has optimal solution

    /// (i.e. it is feasible and bounded), and the algorithm has found

    /// optimal flow and node potentials (primal and dual solutions),

    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost

    /// and infinite 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.

    ///

    /// \see ProblemType, Method

    /// \see resetParams(), reset()

    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {

      _alpha = factor;

      ProblemType pt = init();

      if (pt != OPTIMAL) return pt;

      start(method);

      return OPTIMAL;

    }

    /// \brief Reset all the parameters that have been given before.

    ///

    /// This function resets all the paramaters that have been given

    /// before using functions \ref lowerMap(), \ref upperMap(),

    /// \ref costMap(), \ref supplyMap(), \ref stSupply().

    ///

    /// The type of the length map

    typedef LEN LengthMap;

    /// The type of the arc lengths

    typedef typename LengthMap::Value Value;

    /// \brief The large value type used for internal computations

    ///

    /// The large value type used for internal computations.

    /// It is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    /// \c Value must be convertible to \c LargeValue.

    typedef double LargeValue;

    /// The tolerance type used for internal computations

    typedef lemon::Tolerance<LargeValue> Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addFront() function.

    typedef lemon::Path<Digraph> Path;

  };

  // Default traits class for integer value types

  template <typename GR, typename LEN>

  struct HartmannOrlinDefaultTraits<GR, LEN, true>

  {

    typedef GR Digraph;

    typedef LEN LengthMap;

    typedef typename LengthMap::Value Value;

#ifdef LEMON_HAVE_LONG_LONG

    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

  /// a directed cycle of minimum mean length (cost) in a digraph

  /// \ref amo93networkflows, \ref dasdan98minmeancycle.

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

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits

  /// "HartmannOrlinDefaultTraits<GR, LEN>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

#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

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the length map

    typedef typename TR::LengthMap LengthMap;

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// By default, it is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",

    /// it is \ref lemon::Path "Path<Digraph>".

    typedef typename TR::Path Path;

    /// The \ref HartmannOrlinDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    // Data sturcture for path data

    struct PathData

    {

      LargeValue dist;

      Arc pred;

      PathData(LargeValue d, Arc p = INVALID) :

        dist(d), pred(p) {}

    };

    typedef typename Digraph::template NodeMap<std::vector<PathData> >

      PathDataNodeMap;

  private:

    // The digraph the algorithm runs on

    const Digraph &_gr;

    // The length of the arcs

    const LengthMap &_length;

    // Data for storing the strongly connected components

    int _comp_num;

    typename Digraph::template NodeMap<int> _comp;

    std::vector<std::vector<Node> > _comp_nodes;

    std::vector<Node>* _nodes;

    typename Digraph::template NodeMap<std::vector<Arc> > _out_arcs;

    // Data for the found cycles

    bool _curr_found, _best_found;

    LargeValue _curr_length, _best_length;

    int _curr_size, _best_size;

    Node _curr_node, _best_node;

    int _curr_level, _best_level;

    Path *_cycle_path;

    bool _local_path;

    // Node map for storing path data

    PathDataNodeMap _data;

    // The processed nodes in the last round

    std::vector<Node> _process;

    Tolerance _tolerance;

    // Infinite constant

    const LargeValue INF;

  public:

    /// \name Named Template Parameters

    /// @{

    template <typename T>

    struct SetLargeValueTraits : public Traits {

      typedef T LargeValue;

      typedef lemon::Tolerance<T> Tolerance;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c LargeValue type.

    ///

    /// \ref named-templ-param "Named parameter" for setting \c LargeValue

    /// type. It is used for internal computations in the algorithm.

    template <typename T>

    struct SetLargeValue

      : public HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > {

      typedef HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > Create;

    };

    template <typename T>

    struct SetPathTraits : public Traits {

      typedef T Path;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c %Path type.

    ///

    /// \ref named-templ-param "Named parameter" for setting the \c %Path

    /// type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addFront() function.

    template <typename T>

    struct SetPath

      : public HartmannOrlin<GR, LEN, SetPathTraits<T> > {

      typedef HartmannOrlin<GR, LEN, SetPathTraits<T> > Create;

    };

    /// @}

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

    /// \param digraph The digraph the algorithm runs on.

    /// \param length The lengths (costs) of the arcs.

    HartmannOrlin( const Digraph &digraph,

                   const LengthMap &length ) :

      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),

      _best_found(false), _best_length(0), _best_size(1),

      _cycle_path(NULL), _local_path(false), _data(digraph),

      INF(std::numeric_limits<LargeValue>::has_infinity ?

          std::numeric_limits<LargeValue>::infinity() :

          std::numeric_limits<LargeValue>::max())

    {}

    /// Destructor.

    ~HartmannOrlin() {

      if (_local_path) delete _cycle_path;

    }

    /// \brief Set the path structure for storing the found cycle.

    ///

    /// This function sets an external path structure for storing the

    /// found cycle.

    ///

    /// If you don't call this function before calling \ref run() or

    /// \ref findMinMean(), it will allocate a local \ref Path "path"

    /// structure. The destuctor deallocates this automatically

    /// allocated object, of course.

    ///

    /// \note The algorithm calls only the \ref lemon::Path::addFront()

    /// "addFront()" function of the given path structure.

    ///

    /// \return <tt>(*this)</tt>

    HartmannOrlin& cycle(Path &path) {

      if (_local_path) {

        delete _cycle_path;

        _local_path = false;

      }

      _cycle_path = &path;

      return *this;

    }

    /// \brief Set the tolerance used by the algorithm.

    ///

    /// This function sets the tolerance object used by the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    HartmannOrlin& tolerance(const Tolerance& tolerance) {

      _tolerance = tolerance;

      return *this;

    }

    /// \brief Return a const reference to the tolerance.

    ///

    /// This function returns a const reference to the tolerance object

    /// used by the algorithm.

    const Tolerance& tolerance() const {

      return _tolerance;

    }

    /// \name Execution control

    /// The simplest way to execute the algorithm is to call the \ref run()

    /// function.\n

    /// If you only need the minimum mean length, you may call

    /// \ref findMinMean().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    /// It can be called more than once (e.g. if the underlying digraph

    /// and/or the arc lengths have been modified).

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.

    /// \code

    ///   return mmc.findMinMean() && mmc.findCycle();

    /// \endcode

    bool run() {

      return findMinMean() && findCycle();

    }

    /// \brief Find the minimum cycle mean.

    ///

    /// This function finds the minimum mean length of the directed

    /// cycles in the digraph.

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    bool findMinMean() {

      // Initialization and find strongly connected components

      init();

      findComponents();

      // Find the minimum cycle mean in the components

      for (int comp = 0; comp < _comp_num; ++comp) {

        if (!initComponent(comp)) continue;

        processRounds();

        // Update the best cycle (global minimum mean cycle)

        if ( _curr_found && (!_best_found || 

             _curr_length * _best_size < _best_length * _curr_size) ) {

          _best_found = true;

          _best_length = _curr_length;

          _best_size = _curr_size;

          _best_node = _curr_node;

          _best_level = _curr_level;

        }

      }

      return _best_found;

    }

    /// \brief Find a minimum mean directed cycle.

    ///

    /// This function finds a directed cycle of minimum mean length

    /// in the digraph using the data computed by findMinMean().

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \pre \ref findMinMean() must be called before using this function.

    bool findCycle() {

      if (!_best_found) return false;

      IntNodeMap reached(_gr, -1);

      int r = _best_level + 1;

      Node u = _best_node;

      while (reached[u] < 0) {

        reached[u] = --r;