RhodeCode

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

    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;

  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 {

    /// @}

  protected:

    CostScaling() {}

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

      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

      _forward.resize(_res_arc_num);

      _source.resize(_res_arc_num);

      _target.resize(_res_arc_num);

      _reverse.resize(_res_arc_num);

      _lower.resize(_res_arc_num);

      _upper.resize(_res_arc_num);

      _scost.resize(_res_arc_num);

      _supply.resize(_res_node_num);

      _res_cap.resize(_res_arc_num);

      _cost.resize(_res_arc_num);

      _pi.resize(_res_node_num);

      _excess.resize(_res_node_num);

      _next_out.resize(_res_node_num);

      // Copy the graph

      int i = 0, j = 0, k = 2 * _arc_num + _node_num;

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

        _node_id[n] = i;

      }

      i = 0;

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

        _first_out[i] = j;

        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {

          _arc_idf[a] = j;

          _forward[j] = true;

          _source[j] = i;

          _target[j] = _node_id[_graph.runningNode(a)];

        }

        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {

          _arc_idb[a] = j;

    // Execute the algorithm and transform the results

    void start(Method method) {

      const int MAX_PARTIAL_PATH_LENGTH = 4;

      switch (method) {

        case PUSH:

          startPush();

          break;

        case AUGMENT:

          startAugment(_res_node_num - 1);

          break;

        case PARTIAL_AUGMENT:

          startAugment(MAX_PARTIAL_PATH_LENGTH);

          break;

      }

        }

      }

      // Handle non-zero lower bounds

      if (_have_lower) {

        int limit = _first_out[_root];

        for (int j = 0; j != limit; ++j) {

          if (!_forward[j]) _res_cap[j] += _lower[j];

        }

      }

    }

    // Initialize a cost scaling phase

    void initPhase() {

      // Saturate arcs not satisfying the optimality condition

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

        int last_out = _first_out[u+1];

        LargeCost pi_u = _pi[u];