RhodeCode

      const CostVector &_cost;

      const IntVector  &_state;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      // Pivot rule data

      int _next_arc;

    public:

      // Constructor

      FirstEligiblePivotRule(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)

      {}

      // Find next entering arc

      bool findEnteringArc() {

        Cost c;

        for (int e = _next_arc; e < _search_arc_num; ++e) {

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

          if (c < 0) {

            _in_arc = e;

            _next_arc = e + 1;

            return true;

          }

        }

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

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

          if (c < 0) {

            _in_arc = e;

            _next_arc = e + 1;

            return true;

          }

        }

        return false;

      }

    }; //class FirstEligiblePivotRule

    // Implementation of the Best Eligible pivot rule

    class BestEligiblePivotRule

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const IntVector  &_state;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

    public:

      // Constructor

      BestEligiblePivotRule(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)

      {}

      // Find next entering arc

      bool findEnteringArc() {

        Cost c, min = 0;

        for (int e = 0; e < _search_arc_num; ++e) {

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

          if (c < min) {

            min = c;

            _in_arc = e;

          }

        }

        return min < 0;

      }

    }; //class BestEligiblePivotRule

    // Implementation of the Block Search pivot rule

    class BlockSearchPivotRule

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const IntVector  &_state;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      // Pivot rule data

      int _block_size;

      int _next_arc;

    public:

      // Constructor

      BlockSearchPivotRule(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)

      {

        // The main parameters of the pivot rule

        const double BLOCK_SIZE_FACTOR = 0.5;

        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;

        for (e = _next_arc; e < _search_arc_num; ++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;

          }

        }

        for (e = 0; e < _next_arc; ++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;

          }

        }

        if (min >= 0) return false;

      search_end:

        _next_arc = e;

        return true;

      }

    }; //class BlockSearchPivotRule

    // Implementation of the Candidate List pivot rule

    class CandidateListPivotRule

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const IntVector  &_state;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      // Pivot rule data

      IntVector _candidates;

      int _list_length, _minor_limit;

      int _curr_length, _minor_count;

      int _next_arc;

    public:

      /// Constructor

      CandidateListPivotRule(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)

      {

        // The main parameters of the pivot rule

        const double LIST_LENGTH_FACTOR = 0.25;

        const int MIN_LIST_LENGTH = 10;

        const double MINOR_LIMIT_FACTOR = 0.1;

        const int MIN_MINOR_LIMIT = 3;

        _list_length = std::max( int(LIST_LENGTH_FACTOR *

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

                                 MIN_LIST_LENGTH );

        _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),

                                 MIN_MINOR_LIMIT );

        _curr_length = _minor_count = 0;

        _candidates.resize(_list_length);

      }

      /// Find next entering arc

      bool findEnteringArc() {

        Cost min, c;

        int e;

        if (_curr_length > 0 && _minor_count < _minor_limit) {

          // Minor iteration: select the best eligible arc from the

          // current candidate list

          ++_minor_count;

          min = 0;

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

            e = _candidates[i];

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

            if (c < min) {

              min = c;

              _in_arc = e;

            }

            else if (c >= 0) {

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

            }

          }

          if (min < 0) return true;

        }

        // Major iteration: build a new candidate list

        min = 0;

        _curr_length = 0;

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

          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;

          }

        }

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

          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;

          }

        }

        if (_curr_length == 0) return false;

      search_end:        

        _minor_count = 1;

        _next_arc = e;

        return true;

      }

    }; //class CandidateListPivotRule

    // Implementation of the Altering Candidate List pivot rule

    class AlteringListPivotRule

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const IntVector  &_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) {

          return _map[left] > _map[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 double HEAD_LENGTH_FACTOR = 0.1;

        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;

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

          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;

        for (e = _next_arc; e < _search_arc_num; ++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;

          }

        }

        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;

      }

      }

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

    ///

    /// \param map An arc map storing the upper bounds.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    ///

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

    template<typename UpperMap>

    NetworkSimplex& upperMap(const UpperMap& map) {

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

        _upper[_arc_id[a]] = map[a];

      }

      return *this;

    }

    /// \brief Set the costs of the arcs.

    ///

    /// This function sets the costs of the arcs.

    /// If it is not used before calling \ref run(), the costs

    /// will be set to \c 1 on all arcs.

    ///

    /// \param map An arc map storing the costs.

    /// Its \c Value type must be convertible to the \c Cost type

    /// of the algorithm.

    ///

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

    template<typename CostMap>

    NetworkSimplex& costMap(const CostMap& map) {

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

        _cost[_arc_id[a]] = map[a];

      }

      return *this;

    }

    /// \brief Set the supply values of the nodes.

    ///

    /// This function sets the supply values of the nodes.

    /// If neither this function nor \ref stSupply() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    /// (It makes sense only if non-zero lower bounds are given.)

    ///

    /// \param map A node map storing the supply values.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    ///

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

    template<typename SupplyMap>

    NetworkSimplex& supplyMap(const SupplyMap& map) {

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

        _supply[_node_id[n]] = map[n];

      }

      return *this;

    }

    /// \brief Set single source and target nodes and a supply value.

    ///

    /// This function sets a single source node and a single target node

    /// and the required flow value.

    /// If neither this function nor \ref supplyMap() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    /// (It makes sense only if non-zero lower bounds are given.)

    ///

    /// Using this function has the same effect as using \ref supplyMap()

    /// with such a map in which \c k is assigned to \c s, \c -k is

    /// assigned to \c t and all other nodes have zero supply value.

    ///

    /// \param s The source node.

    /// \param t The target node.

    /// \param k The required amount of flow from node \c s to node \c t

    /// (i.e. the supply of \c s and the demand of \c t).

    ///

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

    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {

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

        _supply[i] = 0;

      }

      _supply[_node_id[s]] =  k;

      _supply[_node_id[t]] = -k;

      return *this;

    }

    /// \brief Set the type of the supply constraints.

    ///

    /// This function sets the type of the supply/demand constraints.

    /// If it is not used before calling \ref run(), the \ref GEQ supply

    /// type will be used.

    ///

    /// For more information see \ref SupplyType.

    ///

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

    NetworkSimplex& supplyType(SupplyType supply_type) {

      _stype = supply_type;

      return *this;

    }

    /// @}

    /// \name Execution Control

    /// The algorithm can be executed using \ref run().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    /// The paramters can be specified using functions \ref lowerMap(),

    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 

    /// \ref supplyType().

    /// For example,

    /// \code

    ///   NetworkSimplex<ListDigraph> ns(graph);

    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)

    ///     .supplyMap(sup).run();

    /// \endcode

    ///

    /// This function can be called more than once. All the parameters

    /// that have been given are kept for the next call, unless

    /// \ref reset() is called, thus only the modified parameters

    /// have to be set again. See \ref reset() for examples.

    /// However the underlying digraph must not be modified after this

    /// class have been constructed, since it copies and extends the graph.

    ///

    /// \param pivot_rule The pivot rule that will be used during the

    /// algorithm. For more information see \ref PivotRule.

    ///

    /// \return \c INFEASIBLE if no feasible flow exists,

    /// \n \c OPTIMAL if the problem has optimal solution

    /// (i.e. it is feasible and bounded), and the algorithm has found

    /// optimal flow and node potentials (primal and dual solutions),

    /// \n \c UNBOUNDED if the objective function of the problem is

    /// unbounded, i.e. there is a directed cycle having negative total

    /// cost and infinite upper bound.

    ///

    /// \see ProblemType, PivotRule

    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {

      if (!init()) return INFEASIBLE;

      return start(pivot_rule);

    }

    /// \brief Reset all the parameters that have been given before.

    ///

    /// This function resets all the paramaters that have been given

    /// before using functions \ref lowerMap(), \ref upperMap(),

    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().

    ///

    /// It is useful for multiple run() calls. If this function is not

    /// used, all the parameters given before are kept for the next

    /// \ref run() call.

    /// However the underlying digraph must not be modified after this

    /// class have been constructed, since it copies and extends the graph.

    ///

    /// For example,

    /// \code

    ///   NetworkSimplex<ListDigraph> ns(graph);

    ///

    ///   // First run

    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)

    ///     .supplyMap(sup).run();

    ///

    ///   // Run again with modified cost map (reset() is not called,

    ///   // so only the cost map have to be set again)

    ///   cost[e] += 100;

    ///   ns.costMap(cost).run();

    ///

    ///   // Run again from scratch using reset()

    ///   // (the lower bounds will be set to zero on all arcs)

    ///   ns.reset();

    ///   ns.upperMap(capacity).costMap(cost)

    ///     .supplyMap(sup).run();

    /// \endcode

    ///

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

    NetworkSimplex& reset() {

      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;

      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;

    }

#ifndef DOXYGEN

    Cost totalCost() const {

      return totalCost<Cost>();

    }

#endif

    /// \brief Return the flow on the given arc.

    ///

    /// This function returns the flow on the given arc.

    ///

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

    Value flow(const Arc& a) const {

      return _flow[_arc_id[a]];

    }

    /// \brief Return the flow map (the primal solution).

    ///

    /// This function copies the flow value on each arc into the given

    /// map. The \c Value type of the algorithm must be convertible to

    /// the \c Value type of the map.

    ///

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

    template <typename FlowMap>

    void flowMap(FlowMap &map) const {

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

        map.set(a, _flow[_arc_id[a]]);

      }

    }

    /// \brief Return the potential (dual value) of the given node.

    ///

    /// This function returns the potential (dual value) of the

    /// given node.

    ///

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

    Cost potential(const Node& n) const {

      return _pi[_node_id[n]];

    }

    /// \brief Return the potential map (the dual solution).

    ///

    /// This function copies the potential (dual value) of each node

    /// into the given map.

    /// The \c Cost type of the algorithm must be convertible to the

    /// \c Value type of the map.

    ///

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

    template <typename PotentialMap>

    void potentialMap(PotentialMap &map) const {

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

        map.set(n, _pi[_node_id[n]]);

      }

    }

    /// @}

  private:

    // Initialize internal data structures

    bool init() {

      if (_node_num == 0) return false;

      // Check the sum of supply values

      _sum_supply = 0;

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

        _sum_supply += _supply[i];

      }

      if ( !((_stype == GEQ && _sum_supply <= 0) ||

             (_stype == LEQ && _sum_supply >= 0)) ) return false;

      // Remove non-zero lower bounds

      if (_have_lower) {

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

          Value c = _lower[i];

          if (c >= 0) {

            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;

          } else {

            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;

          }

          _supply[_source[i]] -= c;

          _supply[_target[i]] += c;

        }

      } else {

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

          _cap[i] = _upper[i];

        }

      }

      // Initialize artifical cost

      Cost ART_COST;

      if (std::numeric_limits<Cost>::is_exact) {

        ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;

      } else {

        ART_COST = std::numeric_limits<Cost>::min();

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

          if (_cost[i] > ART_COST) ART_COST = _cost[i];

        }

        ART_COST = (ART_COST + 1) * _node_num;

      }

      // Initialize arc maps

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

        _flow[i] = 0;

        _state[i] = STATE_LOWER;

      }

      // Set data for the artificial root node

      _root = _node_num;

      _parent[_root] = -1;

      _pred[_root] = -1;

      _thread[_root] = 0;

      _rev_thread[0] = _root;

      _succ_num[_root] = _node_num + 1;

      _last_succ[_root] = _root - 1;

      _supply[_root] = -_sum_supply;

      _pi[_root] = 0;

      // Add artificial arcs and initialize the spanning tree data structure