RhodeCode

          if (c < 0) {

            _cand_cost[e] = c;

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

    /// mixed order in the internal data structure.

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

      _arc_mixing(arc_mixing),

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

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

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

    {

      // Check the number 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");

      // Reset data structures

      reset();

    }

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

    /// \ref supplyType().

    ///

    /// It is useful for multiple \ref run() calls. Basically, all the given

    /// parameters are kept for the next \ref run() call, unless

    /// \ref resetParams() or \ref reset() is used.

    /// If the underlying digraph was also modified after the construction

    /// of the class or the last \ref reset() call, then the \ref reset()

    /// function must be used, otherwise \ref resetParams() is sufficient.

    ///

    /// See \ref resetParams() for examples.

    ///

    /// \return <tt>(*this)</tt>

    ///

    /// \see resetParams(), run()

    NetworkSimplex& reset() {

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

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

      // Copy the graph

      int i = 0;

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

        _node_id[n] = i;

      }

      if (_arc_mixing) {

        // Store the arcs in a mixed order

        int i = 0, j = 0;

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

        }

      } else {

        // Store the arcs in the original order

        int i = 0;

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

          _arc_id[a] = i;

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

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

        }

      }

      // Reset parameters

      resetParams();

      return *this;

    }

    /// @}

    /// \name Query Functions

    /// The results of the algorithm can be obtained using these

    /// functions.\n

    /// The \ref run() function must be called before using them.

    /// @{

    /// \brief Return the total cost of the found flow.

    ///

    /// This function returns the total cost of the found flow.

    /// Its complexity is O(e).

    ///

    /// \note The return type of the function can be specified as a

    /// template parameter. For example,

    /// \code

    ///   ns.totalCost<double>();

    /// \endcode

    /// It is useful if the total cost cannot be stored in the \c Cost

    /// type of the algorithm, which is the default return type of the

    /// function.

    ///

    /// \pre \ref run() must be called before using this function.

    template <typename Number>

    Number totalCost() const {

      Number c = 0;

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

        int i = _arc_id[a];

        c += Number(_flow[i]) * Number(_cost[i]);

      }

      return c;