RhodeCode

  /// It is one of the most efficient solution methods.

  ///

  /// In general this class is the fastest implementation available

  /// in LEMON for the minimum cost flow problem.

  ///

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

  ///

  ///

  /// \note %NetworkSimplex provides five different pivot rule

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

  class NetworkSimplex

  {

  public:

    /// The type of the flow map

    /// The type of the potential map

  public:

    /// \brief Enum type for selecting the pivot rule.

    ///

    /// Enum type for selecting the pivot rule for the \ref run()

    };

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef std::vector<Arc> ArcVector;

    typedef std::vector<Node> NodeVector;

    typedef std::vector<int> IntVector;

    typedef std::vector<bool> BoolVector;

    // State constants for arcs

    enum ArcStateEnum {

      STATE_UPPER = -1,

      STATE_TREE  =  0,

      STATE_LOWER =  1

    // Data related to the underlying digraph

    const GR &_graph;

    int _node_num;

    int _arc_num;

    // Parameters of the problem

    bool _pstsup;

    Node _psource, _ptarget;

    // Result maps

    FlowMap *_flow_map;

    PotentialMap *_potential_map;

    bool _local_flow;

    bool _local_potential;

    IntNodeMap _node_id;

    ArcVector _arc_ref;

    IntVector _source;

    IntVector _target;

    // Node and arc data

    // Data for storing the spanning tree structure

    IntVector _parent;

    IntVector _pred;

    IntVector _thread;

    IntVector _rev_thread;

    int _root;

    // Temporary data used in the current pivot iteration

    int in_arc, join, u_in, v_in, u_out, v_out;

    int first, second, right, last;

    int stem, par_stem, new_stem;

  private:

    // Implementation of the First Eligible pivot rule

    class FirstEligiblePivotRule

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      // Pivot rule data

      int _next_arc;

        _cost(ns._cost), _state(ns._state), _pi(ns._pi),

        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)

      {}

      // Find next entering arc

      bool findEnteringArc() {

        for (int e = _next_arc; e < _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;

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

    public:

      // Constructor

        _cost(ns._cost), _state(ns._state), _pi(ns._pi),

        _in_arc(ns.in_arc), _arc_num(ns._arc_num)

      {}

      // Find next entering arc

      bool findEnteringArc() {

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

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

          if (c < min) {

            min = c;

            _in_arc = e;

          }

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      // Pivot rule data

      int _block_size;

      int _next_arc;

        _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)),

                                MIN_BLOCK_SIZE );

      }

      // Find next entering arc

      bool findEnteringArc() {

        int cnt = _block_size;

        int e, min_arc = _next_arc;

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

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

          if (c < min) {

            min = c;

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      // Pivot rule data

      IntVector _candidates;

      int _list_length, _minor_limit;

        _curr_length = _minor_count = 0;

        _candidates.resize(_list_length);

      }

      /// Find next entering arc

      bool findEnteringArc() {

        int e, min_arc = _next_arc;

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

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

          // current candidate list

          ++_minor_count;

          min = 0;

    {

    private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      // Pivot rule data

      int _block_size, _head_length, _curr_length;

      int _next_arc;

      IntVector _candidates;

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

      class SortFunc

      {

      private:

      public:

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

          return _map[left] > _map[right];

        }

      };

      SortFunc _sort_func;

      _plower(NULL), _pupper(NULL), _pcost(NULL),

      _psupply(NULL), _pstsup(false),

      _flow_map(NULL), _potential_map(NULL),

      _local_flow(false), _local_potential(false),

      _node_id(graph)

    {

    }

    /// Destructor.

    ~NetworkSimplex() {

      if (_local_flow) delete _flow_map;

      if (_local_potential) delete _potential_map;

    /// This function sets the lower bounds on the arcs.

    /// If neither this function nor \ref boundMaps() is 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.

    /// of the algorithm.

    ///

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

    template <typename LOWER>

    NetworkSimplex& lowerMap(const LOWER& map) {

      delete _plower;

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

        (*_plower)[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 none of the functions \ref upperMap(), \ref capacityMap()

    /// and \ref boundMaps() is used before calling \ref run(),

    /// the upper bounds (capacities) will be set to

    ///

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

    /// of the algorithm.

    ///

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

    template<typename UPPER>

    NetworkSimplex& upperMap(const UPPER& map) {

      delete _pupper;

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

        (*_pupper)[a] = map[a];

      }

      return *this;

    }

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

    /// calling \ref run(), the lower bounds will be set to zero

    /// on all arcs.

    /// If none of the functions \ref upperMap(), \ref capacityMap()

    /// and \ref boundMaps() is used before calling \ref run(),

    /// the upper bounds (capacities) will be set to

    ///

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

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

    ///

    /// The \c Value type of the maps must be convertible to the

    ///

    /// \note This function is just a shortcut of calling \ref lowerMap()

    /// and \ref upperMap() separately.

    ///

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

    template <typename LOWER, typename UPPER>

    ///

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

    /// of the algorithm.

    ///

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

    template<typename COST>

    NetworkSimplex& costMap(const COST& map) {

      delete _pcost;

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

        (*_pcost)[a] = map[a];

      }

      return *this;

    }

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

    /// of the algorithm.

    ///

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

    template<typename SUP>

    NetworkSimplex& supplyMap(const SUP& map) {

      delete _psupply;

      _pstsup = false;

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

        (*_psupply)[n] = map[n];

      }

      return *this;

    }

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

      delete _psupply;

      _psupply = NULL;

      _pstsup = true;

      _psource = s;

      _ptarget = t;

      _pstflow = k;

    /// @{

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

    ///

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

    ///

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

    /// template parameter. For example,

    /// \code

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

    /// \endcode

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

    Num totalCost() const {

          c += (*_flow_map)[e];

      }

      return c;

    }

#ifndef DOXYGEN

    }

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

      return (*_flow_map)[a];

    }

    /// \brief Return a const reference to the flow map.

    ///

    /// This function returns a const reference to an arc map storing

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

      return (*_potential_map)[n];

    }

    /// \brief Return a const reference to the potential map

    /// (the dual solution).

    ///

      if (!_pstsup && !_psupply) {

        _pstsup = true;

        _psource = _ptarget = NodeIt(_graph);

        _pstflow = 0;

      }

      if (_psupply) {

        int i = 0;

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

          _node_id[n] = i;

          _supply[i] = (*_psupply)[n];

          sum += _supply[i];

        }

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

        _arc_ref[i] = e;

        if ((i += k) >= _arc_num) i = (i % k) + 1;

      }

      // Initialize arc maps

      if (_pupper && _pcost) {

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

          Arc e = _arc_ref[i];

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

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

          _cap[i] = (*_pupper)[e];

          _state[i] = STATE_LOWER;

        }

        if (_pupper) {

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

            _cap[i] = (*_pupper)[_arc_ref[i]];

        } else {

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

        }

        if (_pcost) {

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

            _cost[i] = (*_pcost)[_arc_ref[i]];

        } else {

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

        }

      }

      // Remove non-zero lower bounds

      if (_plower) {

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

          if (c != 0) {

            _cap[i] -= c;

            _supply[_source[i]] -= c;

            _supply[_target[i]] += c;

          }

        }

      }

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

      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {

        _thread[u] = u + 1;

        _rev_thread[u + 1] = u;

        _succ_num[u] = 1;

        _last_succ[u] = u;

        _parent[u] = _root;

      } else {

        first  = _target[in_arc];

        second = _source[in_arc];

      }

      delta = _cap[in_arc];

      int result = 0;

      int e;

      // Search the cycle along the path form the first node to the root

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

        e = _pred[u];

        d = _forward[u] ? _flow[e] : _cap[e] - _flow[e];

    }

    // Change _flow and _state vectors

    void changeFlow(bool change) {

      // Augment along the cycle

      if (delta > 0) {

        _flow[in_arc] += val;

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

          _flow[_pred[u]] += _forward[u] ? -val : val;

        }

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

          _flow[_pred[u]] += _forward[u] ? val : -val;

        _succ_num[u] -= old_succ_num;

      }

    }

    // Update potentials

    void updatePotential() {

        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :

        _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];

      if (_succ_num[u_in] > _node_num / 2) {

        // Update in the upper subtree (which contains the root)

        int before = _rev_thread[u_in];

        int after = _thread[_last_succ[u_in]];

  "@attributes\n"

  "source 1\n"

  "target 12\n";

// Check the interface of an MCF algorithm

class McfClassConcept

{

public:

  template <typename MCF>

  struct Constraints {

      ignore_unused_variable_warning(pm);

      ignore_unused_variable_warning(x);

    }

    typedef typename GR::Node Node;

    typedef typename GR::Arc Arc;

    const GR &g;

    const NM ⊃

    const Node &n;

    const Arc &a;

    bool b;

    typename MCF::FlowMap &flow;

    typename MCF::PotentialMap &pot;

  };

}

int main()

{

  // Check the interfaces

  {

    // TODO: This typedef should be enabled if the standard maps are

    // reference maps in the graph concepts (See #190).

/**/

    //typedef concepts::Digraph GR;

    typedef ListDigraph GR;

/**/

  }

  // Run various MCF tests

  typedef ListDigraph Digraph;

  DIGRAPH_TYPEDEFS(ListDigraph);