RhodeCode

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef std::vector<int> IntVector;

    typedef std::vector<Value> ValueVector;

    typedef std::vector<Cost> CostVector;

    // State constants for arcs

    enum ArcState {

      STATE_UPPER = -1,

      STATE_TREE  =  0,

      STATE_LOWER =  1

    };

  private:

    // Data related to the underlying digraph

    const GR &_graph;

    int _node_num;

    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;

    Value delta;

    const Value MAX;

  public:

    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;

    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:

    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;

    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;

    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;

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

          e = _candidates[i];

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

          }

        }

        // Extend the list

        int cnt = _block_size;

        int limit = _head_length;

        for (e = _next_arc; e != _search_arc_num; ++e) {

            _candidates[_curr_length++] = e;

          }

          if (--cnt == 0) {

            if (_curr_length > limit) goto search_end;

            limit = 0;

            cnt = _block_size;

      _supply.resize(all_node_num);

      _flow.resize(max_arc_num);

      _pi.resize(all_node_num);

      _parent.resize(all_node_num);

      _pred.resize(all_node_num);

      _thread.resize(all_node_num);

      _rev_thread.resize(all_node_num);

      _succ_num.resize(all_node_num);

      _last_succ.resize(all_node_num);

      _state.resize(max_arc_num);

          _rev_thread[u + 1] = u;

          _succ_num[u] = 1;

          _last_succ[u] = u;

          _cap[e] = INF;

          _state[e] = STATE_TREE;

          if (_supply[u] >= 0) {

            _pi[u] = 0;

            _source[e] = u;

            _target[e] = _root;

            _flow[e] = _supply[u];

            _cost[e] = 0;

          } else {

            _pi[u] = ART_COST;

            _source[e] = _root;

            _target[e] = u;

            _flow[e] = -_supply[u];

            _cost[e] = ART_COST;

          }

          _parent[u] = _root;

          _thread[u] = u + 1;

          _rev_thread[u + 1] = u;

          _succ_num[u] = 1;

          _last_succ[u] = u;

          if (_supply[u] >= 0) {

            _pi[u] = 0;

            _pred[u] = e;

            _source[e] = u;

            _target[e] = _root;

            _cap[e] = INF;

            _flow[e] = _supply[u];

            _cost[e] = 0;

            _state[e] = STATE_TREE;

          } else {

            _pi[u] = ART_COST;

            _pred[u] = f;

            _source[f] = _root;

            _target[f] = u;

            _cap[f] = INF;

            _flow[f] = -_supply[u];

          _parent[u] = _root;

          _thread[u] = u + 1;

          _rev_thread[u + 1] = u;

          _succ_num[u] = 1;

          _last_succ[u] = u;

          if (_supply[u] <= 0) {

            _pi[u] = 0;

            _pred[u] = e;

            _source[e] = _root;

            _target[e] = u;

            _cap[e] = INF;

            _flow[e] = -_supply[u];

            _cost[e] = 0;

            _state[e] = STATE_TREE;

          } else {

            _pi[u] = -ART_COST;

            _pred[u] = f;

            _source[f] = u;

            _target[f] = _root;

            _cap[f] = INF;

            _flow[f] = _supply[u];

    // Find the leaving arc of the cycle and returns true if the

    // leaving arc is not the same as the entering arc

    bool findLeavingArc() {

      // Initialize first and second nodes according to the direction

      // of the cycle

      if (_state[in_arc] == STATE_LOWER) {

        first  = _source[in_arc];

        second = _target[in_arc];

      } else {

        first  = _target[in_arc];

        second = _source[in_arc];

      }

      delta = _cap[in_arc];

      int result = 0;

      int e;

      for (int u = first; u != join; u = _parent[u]) {

        e = _pred[u];

        if (d < delta) {

          delta = d;

          u_out = u;

          result = 1;

        }

      }

      for (int u = second; u != join; u = _parent[u]) {

        e = _pred[u];

        if (d <= delta) {

          delta = d;

          u_out = u;

          result = 2;

        }

      }

    void changeFlow(bool change) {

      // Augment along the cycle

      if (delta > 0) {

        Value val = _state[in_arc] * delta;

        _flow[in_arc] += val;

        for (int u = _source[in_arc]; u != join; u = _parent[u]) {

        }

        for (int u = _target[in_arc]; u != join; u = _parent[u]) {

        }

      }

      // Update the state of the entering and leaving arcs

      if (change) {

        _state[in_arc] = STATE_TREE;

        _state[_pred[u_out]] =

        _state[in_arc] = -_state[in_arc];

      }

    }

    // Update the tree structure

    void updateTreeStructure() {

      int old_rev_thread = _rev_thread[u_out];

      int old_succ_num = _succ_num[u_out];

      int old_last_succ = _last_succ[u_out];

      v_out = _parent[u_out];

      } else {

      }

      // Update _last_succ from v_in towards the root

      }

      // Update _last_succ from v_out towards the root

      if (join != old_rev_thread && v_in != old_rev_thread) {

             u = _parent[u]) {

          _last_succ[u] = old_rev_thread;

        }

             u = _parent[u]) {

        }

      }

      // Update _succ_num from v_in to join

        _succ_num[u] += old_succ_num;

      }

      // Update _succ_num from v_out to join

        _succ_num[u] -= old_succ_num;

      }

    }

    void updatePotential() {

      int end = _thread[_last_succ[u_in]];

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

        _pi[u] += sigma;

      }

    }