RhodeCode

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

    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 {

    int _arc_num;

    // Parameters of the problem

    bool _pstsup;

    Node _psource, _ptarget;

    // Result maps

    FlowMap *_flow_map;

    IntVector _target;

    // Node and arc data

    // Data for storing the spanning tree structure

    IntVector _parent;

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

    int first, second, right, last;

    int stem, par_stem, new_stem;

  private:

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

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

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

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

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      // Find next entering arc

      bool findEnteringArc() {

        int cnt = _block_size;

        int e, min_arc = _next_arc;

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

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

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

      // References to the NetworkSimplex class

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

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

        }

      _local_flow(false), _local_potential(false),

      _node_id(graph)

    {

    }

    /// Destructor.

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

      }

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

      }

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

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

      }

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

    NetworkSimplex& supplyMap(const SUP& map) {

      delete _psupply;

      _pstsup = false;

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

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

      }

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

    ///

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

      delete _psupply;

      _psupply = NULL;

      _pstsup = true;

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

    ///

    }

#ifndef DOXYGEN

    }

#endif

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

    ///

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

      return (*_flow_map)[a];

    }

    /// given node.

    ///

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

      return (*_potential_map)[n];

    }

        _pstflow = 0;

      }

      if (_psupply) {

        int i = 0;

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

          _node_id[n] = i;

      }

      // Initialize arc maps

      if (_pupper && _pcost) {

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

          Arc e = _arc_ref[i];

          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)

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

      }

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

      }

      delta = _cap[in_arc];

      int result = 0;

      int e;

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

    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;

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

// Check the interface of an MCF algorithm

class McfClassConcept

{

public:

    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;

{

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