RhodeCode

  ///

  /// \ref CapacityScaling implements the capacity scaling version

  /// of the successive shortest path algorithm for finding a

  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,

  /// \ref edmondskarp72theoretical. It is an efficient dual

  /// solution method.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

  /// \tparam GR The digraph type the algorithm runs on.

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// and supply values in the algorithm. By default, it is \c int.

  /// \tparam C The number type used for costs and potentials in the

  /// algorithm. By default, it is the same as \c V.

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits

  /// "CapacityScalingDefaultTraits<GR, V, C>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

  ///

  /// \warning Both \c V and \c C must be signed number types.

  /// \warning This algorithm does not support negative costs for

  /// arcs having infinite upper bound.

#ifdef DOXYGEN

  template <typename GR, typename V, typename C, typename TR>

#else

  template < typename GR, typename V = int, typename C = V,

             typename TR = CapacityScalingDefaultTraits<GR, V, C> >

#endif

  class CapacityScaling

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef typename TR::Value Value;

    /// The type of the arc costs

    typedef typename TR::Cost Cost;

    /// The type of the heap used for internal Dijkstra computations

    typedef typename TR::Heap Heap;

    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

    /// \brief Constants for selecting the type of the supply constraints.

    ///

    /// Enum type containing constants for selecting the supply type,

    /// i.e. the direction of the inequalities in the supply/demand

    /// constraints of the \ref min_cost_flow "minimum cost flow problem".

    ///

    /// The default supply type is \c GEQ, the \c LEQ type can be

    /// selected using \ref supplyType().

    /// The equality form is a special case of both supply types.

    enum SupplyType {

      /// This option means that there are <em>"greater or equal"</em>

      /// supply/demand constraints in the definition of the problem.

      GEQ,

      /// This option means that there are <em>"less or equal"</em>

      /// supply/demand constraints in the definition of the problem.

      LEQ

    };

    /// \brief Constants for selecting the pivot rule.

    ///

    /// Enum type containing constants for selecting the pivot rule for

    /// the \ref run() function.

    ///

    /// of the algorithm.

    enum PivotRule {

      /// The \e First \e Eligible pivot rule.

      /// The next eligible arc is selected in a wraparound fashion

      /// in every iteration.

      FIRST_ELIGIBLE,

      /// The \e Best \e Eligible pivot rule.

      /// The best eligible arc is selected in every iteration.

      BEST_ELIGIBLE,

      /// The \e Block \e Search pivot rule.

      /// A specified number of arcs are examined in every iteration

      /// in a wraparound fashion and the best eligible arc is selected

      /// from this block.

      BLOCK_SEARCH,

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

      /// In a major iteration a candidate list is built from eligible arcs

      /// in a wraparound fashion and in the following minor iterations

      /// the best eligible arc is selected from this list.

      CANDIDATE_LIST,

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

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

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

    typedef std::vector<signed char> CharVector;

    // Note: vector<signed char> is used instead of vector<ArcState> and

    // vector<ArcDirection> for efficiency reasons

    // State constants for arcs

    enum ArcState {

      STATE_UPPER = -1,

      STATE_TREE  =  0,

      STATE_LOWER =  1

    };

    // Direction constants for tree arcs

    enum ArcDirection {

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CharVector &_state;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      // Pivot rule data

      int _block_size, _head_length, _curr_length;

      int _next_arc;

      IntVector _candidates;

      CostVector _cand_cost;

      // Functor class to compare arcs during sort of the candidate list

      class SortFunc

      {

      private:

        const CostVector &_map;

      public:

        SortFunc(const CostVector &map) : _map(map) {}

        bool operator()(int left, int right) {

        }

      };

      SortFunc _sort_func;

    public:

      // Constructor

      AlteringListPivotRule(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), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)

      {

        // The main parameters of the pivot rule

        const double BLOCK_SIZE_FACTOR = 1.0;

        const int MIN_BLOCK_SIZE = 10;

        const int MIN_HEAD_LENGTH = 3;

        _block_size = std::max( int(BLOCK_SIZE_FACTOR *

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

                                MIN_BLOCK_SIZE );

        _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),

                                 MIN_HEAD_LENGTH );

        _candidates.resize(_head_length + _block_size);

        _curr_length = 0;

      }

      // Find next entering arc

      bool findEnteringArc() {

        // Check the current candidate list

        int e;

        Cost c;

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

          e = _candidates[i];

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

          if (c < 0) {

            _cand_cost[e] = c;

          } else {

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

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

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

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

        _in_arc = _candidates[0];

        _next_arc = e;

        return true;

      }

    }; //class AlteringListPivotRule

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

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

    /// \param arc_mixing Indicate if the arcs will be stored in a

    /// mixed order in the internal data structure.

    /// In general, it leads to similar performance as using the original

    /// arc order, but it makes the algorithm more robust and in special

    /// cases, even significantly faster. Therefore, it is enabled by default.

    NetworkSimplex(const GR& graph, bool arc_mixing = true) :

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

    {