RhodeCode

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

          }

        }

        for (e = 0; e < _next_arc; ++e) {

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

          }

        }

        if (_curr_length == 0) return false;

      search_end:

        // Make heap of the candidate list (approximating a partial sort)

        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,

                   _sort_func );

        // Pop the first element of the heap

        _in_arc = _candidates[0];

        _next_arc = e;

        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,

                  _sort_func );

        _curr_length = std::min(_head_length, _curr_length - 1);

        return true;

      }

    }; //class AlteringListPivotRule

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

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

      _graph(graph), _node_id(graph), _arc_id(graph),

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

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

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

    {

      // Check the value types

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

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

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

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

      // Resize vectors

      _node_num = countNodes(_graph);

      _arc_num = countArcs(_graph);

      int all_node_num = _node_num + 1;

      int max_arc_num = _arc_num + 2 * _node_num;

      _source.resize(max_arc_num);

      _target.resize(max_arc_num);

      _lower.resize(_arc_num);

      _upper.resize(_arc_num);

      _cap.resize(max_arc_num);

      _cost.resize(max_arc_num);

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

      _forward.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);

      int i = 0;

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

        _node_id[n] = i;

      }

      int k = std::max(int(std::sqrt(double(_arc_num))), 10);

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

        _arc_id[a] = i;

        _source[i] = _node_id[_graph.source(a)];

        _target[i] = _node_id[_graph.target(a)];

      }

      // Initialize maps

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

        _supply[i] = 0;

      }

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

        _lower[i] = 0;

        _upper[i] = INF;

        _cost[i] = 1;

      }

      _have_lower = false;

      _stype = GEQ;

    }

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

    NetworkSimplex& lowerMap(const LowerMap& map) {

      _have_lower = true;

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

        _lower[_arc_id[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 on each arc).

    ///