RhodeCode

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

  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;

        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {

          int ra = _reverse[a];

          _res_cap[a] = 1;

          _res_cap[ra] = 0;

          _cost[a] = 0;

          _cost[ra] = 0;

        }

      }

      // Initialize delta value

      if (_factor > 1) {

        // With scaling

          Value ex = _excess[i];

          if ( ex > max_sup) max_sup =  ex;

          if (-ex > max_dem) max_dem = -ex;

        }

        max_sup = std::min(std::min(max_sup, max_dem), max_cap);

        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;

      } else {

        // Without scaling

        _delta = 1;

      }

      return OPTIMAL;

    }

    ProblemType start() {

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

  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 {

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

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

    LargeCostVector _cost;

    LargeCostVector _pi;

    ValueVector _excess;

    IntVector _next_out;

    std::deque<int> _active_nodes;

    // Data for scaling

    LargeCost _epsilon;

    int _alpha;

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

    ///

          int j = _arc_idf[a];

          Value c = _lower[j];

          cap[a] = _upper[j] - c;

          sup[_graph.source(a)] -= c;

          sup[_graph.target(a)] += c;

        }

      } else {

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

          cap[a] = _upper[_arc_idf[a]];

        }

      }

      // Find a feasible flow using Circulation

      Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap>

        circ(_graph, low, cap, sup);

      if (!circ.flowMap(flow).run()) return INFEASIBLE;

      // Set residual capacities and handle GEQ supply type

      if (_sum_supply < 0) {

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

          Value fa = flow[a];

          _res_cap[_arc_idf[a]] = cap[a] - fa;

          _res_cap[_arc_idb[a]] = fa;

          sup[_graph.source(a)] -= fa;

          _cost[a] = 0;

          _cost[ra] = 0;

          _excess[u] = 0;

        }

      } else {

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

          Value fa = flow[a];

          _res_cap[_arc_idf[a]] = cap[a] - fa;

          _res_cap[_arc_idb[a]] = fa;

        }

        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {

          int ra = _reverse[a];

          _res_cap[ra] = 0;

          _cost[a] = 0;

          _cost[ra] = 0;

        }

      }

      return OPTIMAL;

    }

    // Execute the algorithm and transform the results

    void start(Method method) {

      // Maximum path length for partial augment

      const int MAX_PATH_LENGTH = 4;

      // Execute the algorithm

      switch (method) {

        case PUSH:

          startPush();

          break;

        case AUGMENT:

          startAugment();

          break;

        case PARTIAL_AUGMENT:

          startAugment(MAX_PATH_LENGTH);

          break;

      }

      bf.distMap(_pi_map);

      bf.init(0);

      bf.start();

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

        }

      }

    }

    /// Execute the algorithm performing augment and relabel operations

    void startAugment(int max_length = std::numeric_limits<int>::max()) {

      // Paramters for heuristics

      // Perform cost scaling phases

      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?

                                        1 : _epsilon / _alpha )

      {

        }

        // Perform partial augment and relabel operations

        while (true) {

          // Select an active node (FIFO selection)

          while (_active_nodes.size() > 0 &&

                 _excess[_active_nodes.front()] <= 0) {

            _active_nodes.pop_front();

          }

          if (_active_nodes.size() == 0) break;

          int start = _active_nodes.front();

          // Find an augmenting path from the start node

          int tip = start;

            int u;

            for (int a = _next_out[tip]; a != last_out; ++a) {

                _next_out[tip] = a;

                tip = u;

                goto next_step;

              }

            }

            // Relabel tip node

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

              if (_res_cap[a] > 0 && rc < min_red_cost) {

                min_red_cost = rc;

              }

            }

            _pi[tip] -= min_red_cost + _epsilon;

            _next_out[tip] = _first_out[tip];

            // Step back

            if (tip != start) {

            }

          next_step: ;

          }

          // Augment along the found path (as much flow as possible)

          Value delta;

            u = v;

            delta = std::min(_res_cap[pa], _excess[u]);

            _res_cap[pa] -= delta;

            _res_cap[_reverse[pa]] += delta;

            _excess[u] -= delta;

            _excess[v] += delta;

            if (_excess[v] > 0 && _excess[v] <= delta)

              _active_nodes.push_back(v);

          }

        }

      }

    }

    /// Execute the algorithm performing push and relabel operations

    void startPush() {

      // Paramters for heuristics

      // Perform cost scaling phases

      BoolVector hyper(_res_node_num, false);

      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?

                                        1 : _epsilon / _alpha )

      {

        }

        // Perform push and relabel operations

        while (_active_nodes.size() > 0) {

          Value delta;

          int n, t, a, last_out = _res_arc_num;

          // Select an active node (FIFO selection)

          n = _active_nodes.front();

          // Perform push operations if there are admissible arcs

          if (_excess[n] > 0) {

            for (a = _next_out[n]; a != last_out; ++a) {

              if (_res_cap[a] > 0 &&

                delta = std::min(_res_cap[a], _excess[n]);

                t = _target[a];

                // Push-look-ahead heuristic

                Value ahead = -_excess[t];

                for (int ta = _next_out[t]; ta != last_out_t; ++ta) {

                  if (_res_cap[ta] > 0 && 

                    ahead += _res_cap[ta];

                  if (ahead >= delta) break;

                }

                if (ahead < 0) ahead = 0;

                // Push flow along the arc

                  _res_cap[a] -= ahead;

                  _res_cap[_reverse[a]] += ahead;

                  _excess[n] -= ahead;

                  _excess[t] += ahead;

                  _active_nodes.push_front(t);

                  hyper[t] = true;

                  _next_out[n] = a;

                  goto next_node;

                } else {

                  _res_cap[a] -= delta;

                  _res_cap[_reverse[a]] += delta;

                  _excess[n] -= delta;

                  _excess[t] += delta;

                  if (_excess[t] > 0 && _excess[t] <= delta)

                    _active_nodes.push_back(t);

                }

                if (_excess[n] == 0) {

                  _next_out[n] = a;

                  goto remove_nodes;

                }

              }

            }

            _next_out[n] = a;

          }

          // Relabel the node if it is still active (or hyper)

          if (_excess[n] > 0 || hyper[n]) {

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

              if (_res_cap[a] > 0 && rc < min_red_cost) {

                min_red_cost = rc;

              }

            }

            _pi[n] -= min_red_cost + _epsilon;

            hyper[n] = false;

          }

          // Remove nodes that are not active nor hyper

        remove_nodes:

          while ( _active_nodes.size() > 0 &&

                  _excess[_active_nodes.front()] <= 0 &&

                  !hyper[_active_nodes.front()] ) {

            _active_nodes.pop_front();

          }

        }

      }

    }

  }; //class CostScaling

  ///@}

} //namespace lemon

#endif //LEMON_COST_SCALING_H

      /// improved version of the previous method

      /// \ref goldberg89cyclecanceling.

      /// 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<double> DoubleVector;

    typedef std::vector<Value> ValueVector;

    typedef std::vector<Cost> CostVector;

  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 {

    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;

    IntVector _source;

    IntVector _target;

    IntVector _reverse;

    // Node and arc data

    ValueVector _lower;

    ValueVector _upper;

    CostVector _cost;

    ValueVector _supply;

    ValueVector _res_cap;

    CostVector _pi;

      }

    }

    // Execute the "Cancel And Tighten" method

    void startCancelAndTighten() {

      // Constants for the min mean cycle computations

      const double LIMIT_FACTOR = 1.0;

      const int MIN_LIMIT = 5;

      // Contruct auxiliary data vectors

      DoubleVector pi(_res_node_num, 0.0);

      IntVector level(_res_node_num);

      IntVector pred_node(_res_node_num);

      IntVector pred_arc(_res_node_num);

      std::vector<int> stack(_res_node_num);

      std::vector<int> proc_vector(_res_node_num);

      // Initialize epsilon

      double epsilon = 0;

      for (int a = 0; a != _res_arc_num; ++a) {

        if (_res_cap[a] > 0 && -_cost[a] > epsilon)

          epsilon = -_cost[a];

      }

      /// The \e Altering \e Candidate \e List pivot rule.

      /// It is a modified version of the Candidate List method.

      /// It keeps only the several best eligible arcs from the former

      /// candidate list and extends this list in every iteration.

      ALTERING_LIST

    };

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef std::vector<int> IntVector;

    typedef std::vector<Value> ValueVector;

    typedef std::vector<Cost> CostVector;

    // State constants for arcs

    enum ArcStateEnum {

      STATE_UPPER = -1,

      STATE_TREE  =  0,

      STATE_LOWER =  1

    };

  private:

    // Data related to the underlying digraph

    const GR &_graph;

    ValueVector _supply;

    ValueVector _flow;

    CostVector _pi;

    // Data for storing the spanning tree structure

    IntVector _parent;

    IntVector _pred;

    IntVector _thread;

    IntVector _rev_thread;

    IntVector _succ_num;

    IntVector _last_succ;

    IntVector _dirty_revs;

    int _root;

    // Temporary data used in the current pivot iteration

    int in_arc, join, u_in, v_in, u_out, v_out;

    int first, second, right, last;

    int stem, par_stem, new_stem;

    Value delta;

    const Value MAX;

  public:

  private:

    // Implementation of the First Eligible pivot rule

    class FirstEligiblePivotRule

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      // Pivot rule data

      int _next_arc;

    public:

      // Constructor

      FirstEligiblePivotRule(NetworkSimplex &ns) :

        _source(ns._source), _target(ns._target),

        _cost(ns._cost), _state(ns._state), _pi(ns._pi),

        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),

        _next_arc(0)

      {}

      // Find next entering arc

      bool findEnteringArc() {

        Cost c;

          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (c < 0) {

            _in_arc = e;

            _next_arc = e + 1;

            return true;

          }

        }

          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (c < 0) {

            _in_arc = e;

            _next_arc = e + 1;

            return true;

          }

        }

        return false;

      }

    }; //class FirstEligiblePivotRule

    // Implementation of the Best Eligible pivot rule

    class BestEligiblePivotRule

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

    public:

      // Constructor

      BestEligiblePivotRule(NetworkSimplex &ns) :

        _source(ns._source), _target(ns._target),

        _cost(ns._cost), _state(ns._state), _pi(ns._pi),

        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num)

      {}

      // Find next entering arc

      bool findEnteringArc() {

        Cost c, min = 0;

          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (c < min) {

            min = c;

            _in_arc = e;

          }

        }

        return min < 0;

      }

    }; //class BestEligiblePivotRule

    // Implementation of the Block Search pivot rule

    class BlockSearchPivotRule

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      // Pivot rule data

      int _block_size;

      int _next_arc;

    public:

      // Constructor

      BlockSearchPivotRule(NetworkSimplex &ns) :

        _source(ns._source), _target(ns._target),

        _cost(ns._cost), _state(ns._state), _pi(ns._pi),

        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),

        _next_arc(0)

      {

        // The main parameters of the pivot rule

        const int MIN_BLOCK_SIZE = 10;

        _block_size = std::max( int(BLOCK_SIZE_FACTOR *

                                    std::sqrt(double(_search_arc_num))),

                                MIN_BLOCK_SIZE );

      }

      // Find next entering arc

      bool findEnteringArc() {

        Cost c, min = 0;

        int cnt = _block_size;

        int e;

          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (c < min) {

            min = c;

            _in_arc = e;

          }

          if (--cnt == 0) {

            if (min < 0) goto search_end;

            cnt = _block_size;

          }

        }

          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (c < min) {

            min = c;

            _in_arc = e;

          }

          if (--cnt == 0) {

            if (min < 0) goto search_end;

            cnt = _block_size;

          }

        }

        if (min >= 0) return false;

    }; //class BlockSearchPivotRule

    // Implementation of the Candidate List pivot rule

    class CandidateListPivotRule

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      // Pivot rule data

      IntVector _candidates;

      int _list_length, _minor_limit;

      int _curr_length, _minor_count;

      int _next_arc;

    public:

              _in_arc = e;

            }