RhodeCode

  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;

        }

      }

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

  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:

    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;

    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;

      } 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

          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;

        }

      }

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

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

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

        }

      }

    }

        // Saturate arcs not satisfying the optimality condition

            Value delta = _res_cap[a];

            _res_cap[a] = 0;

            _res_cap[_reverse[a]] += delta;

          }

        }

        // Find active nodes (i.e. nodes with positive excess)

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

          if (_excess[u] > 0) _active_nodes.push_back(u);

        }

        // Initialize the next arcs

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

          _next_out[u] = _first_out[u];

        }

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

                u = _target[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;

            }

            _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

  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:

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

      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

  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

    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;

    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;

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

          }

    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:

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

          }

        }

    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;

        _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) {

    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;

          if (min < 0) return true;

        }

        // Major iteration: build a new candidate list

        min = 0;

        _curr_length = 0;

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

          if (c < 0) {

            _candidates[_curr_length++] = e;

            if (c < min) {

              min = c;

              _in_arc = e;

            }

            if (_curr_length == _list_length) goto search_end;

          }

        }

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

          if (c < 0) {

            _candidates[_curr_length++] = e;

            if (c < min) {

              min = c;

              _in_arc = e;

    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, _head_length, _curr_length;

      }

      // Find next entering arc

      bool findEnteringArc() {

        // Check the current candidate list

        int e;

          e = _candidates[i];

          _cand_cost[e] = _state[e] *

            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (_cand_cost[e] >= 0) {

            _candidates[i--] = _candidates[--_curr_length];

          }

        }

        // Extend the list

        int cnt = _block_size;

        int limit = _head_length;

          _cand_cost[e] = _state[e] *

            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (_cand_cost[e] < 0) {

            _candidates[_curr_length++] = e;

          }

          if (--cnt == 0) {

            if (_curr_length > limit) goto search_end;

            limit = 0;

            cnt = _block_size;

          }

        }

          _cand_cost[e] = _state[e] *

            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (_cand_cost[e] < 0) {

            _candidates[_curr_length++] = e;

          }

          if (--cnt == 0) {

      if (old_rev_thread != v_in) {

        _thread[old_rev_thread] = right;

        _rev_thread[right] = old_rev_thread;

      }

      // Update _rev_thread using the new _thread values

        u = _dirty_revs[i];

        _rev_thread[_thread[u]] = u;

      }

      // Update _pred, _forward, _last_succ and _succ_num for the

      // stem nodes from u_out to u_in

      int end = _thread[_last_succ[u_in]];

      for (int u = u_in; u != end; u = _thread[u]) {

        _pi[u] += sigma;

      }

    }

    // Execute the algorithm

    ProblemType start(PivotRule pivot_rule) {

      // Select the pivot rule implementation

      switch (pivot_rule) {

        case FIRST_ELIGIBLE:

          return start<FirstEligiblePivotRule>();

    }

    template <typename PivotRuleImpl>

    ProblemType start() {

      PivotRuleImpl pivot(*this);

      // Execute the Network Simplex algorithm

      while (pivot.findEnteringArc()) {

        findJoinNode();

        bool change = findLeavingArc();

        if (delta >= MAX) return UNBOUNDED;

        changeFlow(change);