RhodeCode

/// \brief Network Simplex algorithm for finding a minimum cost flow.

  /// \brief Implementation of the primal Network Simplex algorithm

  /// \ref NetworkSimplex implements the primal Network Simplex algorithm

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

  /// \tparam V The value type used in the algorithm.

  /// By default it is \c int.

  /// \warning \c V must be a signed integer type.

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

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

  template <typename GR, typename V = int>

  public:

    /// The value type of the algorithm

    typedef V Value;

    /// The type of the flow map

    typedef typename GR::template ArcMap<Value> FlowMap;

    /// The type of the potential map

    typedef typename GR::template NodeMap<Value> PotentialMap;

  public:

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

    ///

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

    /// function.

    ///

    /// \ref NetworkSimplex provides five different pivot rule

    /// implementations that significantly affect the running time

    /// of the algorithm.

    /// By default \ref BLOCK_SEARCH "Block Search" is used, which

    /// proved to be the most efficient and the most robust on various

    /// test inputs according to our benchmark tests.

    /// However another pivot rule can be selected using the \ref run()

    /// function with the proper parameter.

    enum PivotRule {

      /// The First Eligible pivot rule.

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

      /// in every iteration.

      FIRST_ELIGIBLE,

      /// The Best Eligible pivot rule.

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

      BEST_ELIGIBLE,

      /// The Block 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 Candidate 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 Altering Candidate List pivot rule.

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

      /// It keeps only the several best eligible arcs from the former

      /// candidate list and extends this list in every iteration.

      ALTERING_LIST

    };

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef typename GR::template ArcMap<Value> ValueArcMap;

    typedef typename GR::template NodeMap<Value> ValueNodeMap;

    typedef std::vector<Value> ValueVector;

    // Data related to the underlying digraph

    const GR &_graph;

    int _node_num;

    int _arc_num;

    // Parameters of the problem

    ValueArcMap *_plower;

    ValueArcMap *_pupper;

    ValueArcMap *_pcost;

    ValueNodeMap *_psupply;

    bool _pstsup;

    Node _psource, _ptarget;

    Value _pstflow;

    // Data structures for storing the digraph

    // Node and arc data

    ValueVector _cap;

    ValueVector _cost;

    ValueVector _supply;

    ValueVector _flow;

    ValueVector _pi;

    Value delta;

    // Implementation of the First Eligible pivot rule

      const ValueVector &_cost;

      const ValueVector &_pi;

      // Constructor

      // Find next entering arc

        Value c;

    // Implementation of the Best Eligible pivot rule

      const ValueVector &_cost;

      const ValueVector &_pi;

      // Constructor

      // Find next entering arc

        Value c, min = 0;

    // Implementation of the Block Search pivot rule

      const ValueVector &_cost;

      const ValueVector &_pi;

      // Constructor

      // Find next entering arc

        Value c, min = 0;

    // Implementation of the Candidate List pivot rule

      const ValueVector &_cost;

      const ValueVector &_pi;

        Value min, c;

    // Implementation of the Altering Candidate List pivot rule

      const ValueVector &_cost;

      const ValueVector &_pi;

      ValueVector _cand_cost;

        const ValueVector &_map;

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

      // Constructor

      // Find next entering arc

    /// \brief Constructor.

    /// Constructor.

    NetworkSimplex(const GR& graph) :

      _graph(graph),

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

      _psupply(NULL), _pstsup(false),

    {

      LEMON_ASSERT(std::numeric_limits<Value>::is_integer &&

                   std::numeric_limits<Value>::is_signed,

        "The value type of NetworkSimplex must be a signed integer");

    }

    /// \brief Set the lower bounds on the arcs.

    ///

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

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

    /// of the algorithm.

    ///

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

    template <typename LOWER>

    NetworkSimplex& lowerMap(const LOWER& map) {

      delete _plower;

      _plower = new ValueArcMap(_graph);

      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

    /// \c std::numeric_limits<Value>::max() on all arcs.

    ///

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

    NetworkSimplex& upperMap(const UPPER& map) {

      delete _pupper;

      _pupper = new ValueArcMap(_graph);

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

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

      }

      return *this;

    }

    /// \brief Set the upper bounds (capacities) on the arcs.

    ///

    /// This function sets the upper bounds (capacities) on the arcs.

    /// It is just an alias for \ref upperMap().

    ///

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

    template<typename CAP>

    NetworkSimplex& capacityMap(const CAP& map) {

      return upperMap(map);

    }

    /// \brief Set the lower and upper bounds on the arcs.

    ///

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

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

    /// \c std::numeric_limits<Value>::max() on all arcs.

    ///

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

    /// \c Value type of the algorithm.

    ///

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

    /// and \ref upperMap() separately.

    ///

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

    template <typename LOWER, typename UPPER>

    NetworkSimplex& boundMaps(const LOWER& lower, const UPPER& upper) {

      return lowerMap(lower).upperMap(upper);

    }

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

    /// of the algorithm.

    ///

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

    template<typename COST>

    NetworkSimplex& costMap(const COST& map) {

      delete _pcost;

      _pcost = new ValueArcMap(_graph);

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

        (*_pcost)[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 SUP>

    NetworkSimplex& supplyMap(const SUP& map) {

      delete _psupply;

      _pstsup = false;

      _psupply = new ValueNodeMap(_graph);

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

        (*_psupply)[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.)

    ///

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

      delete _psupply;

      _psupply = NULL;

      _pstsup = true;

      _psource = s;

      _ptarget = t;

      _pstflow = k;

      return *this;

    }

    /// If it is not used before calling \ref run(), an instance will

    /// be allocated automatically. The destructor deallocates this

    /// automatically allocated map, of course.

    NetworkSimplex& flowMap(FlowMap& map) {

    /// This function sets the potential map, which is used for storing

    /// the dual solution.

    /// If it is not used before calling \ref run(), an instance will

    /// be allocated automatically. The destructor deallocates this

    /// automatically allocated map, of course.

    NetworkSimplex& potentialMap(PotentialMap& map) {

    /// \name Execution Control

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

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

    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), 

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

    /// functions. For example,

    /// \code

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

    ///   ns.boundMaps(lower, upper).costMap(cost)

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

    /// \endcode

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

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

    bool run(PivotRule pivot_rule = BLOCK_SEARCH) {

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

    /// The complexity of the function is \f$ O(e) \f$.

    ///

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

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

      Num c = 0;

      if (_pcost) {

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

          c += (*_flow_map)[e] * (*_pcost)[e];

      } else {

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

          c += (*_flow_map)[e];

      }

      return c;

    }

#ifndef DOXYGEN

    Value totalCost() const {

      return totalCost<Value>();

    }

#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_map)[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.

    Value potential(const Node& n) const {

      return (*_potential_map)[n];

    }

    /// the found potentials, which form the dual solution of the

    /// \ref min_cost_flow "minimum cost flow" problem.

      if (_node_num == 0) return false;

      if (!_pstsup && !_psupply) {

        _pstsup = true;

        _psource = _ptarget = NodeIt(_graph);

        _pstflow = 0;

      }

      if (_psupply) {

        Value sum = 0;

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

        _supply[_node_id[_psource]] =  _pstflow;

        _supply[_node_id[_ptarget]]   = -_pstflow;

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

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

        }

      } else {

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

        }

        if (_pupper) {

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

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

        } else {

          Value val = std::numeric_limits<Value>::max();

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

            _cap[i] = val;

        }

        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)

            _cost[i] = 1;

        }

      if (_plower) {

          Value c = (*_plower)[_arc_ref[i]];

      Value max_cap = std::numeric_limits<Value>::max();

      Value max_cost = std::numeric_limits<Value>::max() / 4;

      Value d;

        Value val = _state[in_arc] * delta;

      Value sigma = _forward[u_in] ?

    bool start(PivotRule pivot_rule) {

        case FIRST_ELIGIBLE:

        case BEST_ELIGIBLE:

        case BLOCK_SEARCH:

        case CANDIDATE_LIST:

        case ALTERING_LIST:

    template <typename PivotRuleImpl>

      PivotRuleImpl pivot(*this);

      // Execute the Network Simplex algorithm

      if (_plower) {

          _flow_map->set(e, (*_plower)[e] + _flow[i]);

      MCF mcf(g);

      b = mcf.lowerMap(lower)

             .upperMap(upper)

             .capacityMap(upper)

             .boundMaps(lower, upper)

             .costMap(cost)

             .supplyMap(sup)

             .stSupply(n, n, k)

             .run();

      const typename MCF::FlowMap &fm = mcf.flowMap();

      const typename MCF::PotentialMap &pm = mcf.potentialMap();

      v = mcf.totalCost();

      double x = mcf.template totalCost<double>();

      v = mcf.flow(a);

      v = mcf.potential(n);

      mcf.flowMap(flow);

      mcf.potentialMap(pot);

      ignore_unused_variable_warning(x);

    bool b;

// using the "Complementary Slackness" optimality condition

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

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

/**/

/**/

                  NetworkSimplex<GR, Value> >();

  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());

  // A. Test NetworkSimplex with the default pivot rule

    NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),

                            mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);

    checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),

             gr, l1, u, c, s1, true,  5240, "#A1");

    checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),

             gr, l1, u, c, s2, true,  7620, "#A2");

    checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(),

             gr, l2, u, c, s1, true,  5970, "#A3");