lemon-1.2: comparison lemon/network

equal deleted inserted replaced

-:1ebf5bd3e6d8
+:74e94fceb4fd
 ///
 /// 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.
-/// \tparam V The value type used in the algorithm.
+/// \tparam F The value type used for flow amounts, capacity bounds
-/// By default it is \c int.
+/// and supply values in the algorithm. By default it is \c int.
+/// \tparam C The value type used for costs and potentials in the
+/// algorithm. By default it is the same as \c F.
 ///
-/// \warning The value type must be a signed integer type.
+/// \warning Both value types must be signed integer types.
 ///
 /// \note %NetworkSimplex provides five different pivot rule
 /// implementations. For more information see \ref PivotRule.
-template <typename GR, typename V = int>
+template <typename GR, typename F = int, typename C = F>
 class NetworkSimplex
 {
 public:
-/// The value type of the algorithm
+/// The flow type of the algorithm
-typedef V Value;
+typedef F Flow;
+/// The cost type of the algorithm
+typedef C Cost;
 /// The type of the flow map
-typedef typename GR::template ArcMap<Value> FlowMap;
+typedef typename GR::template ArcMap<Flow> FlowMap;
 /// The type of the potential map
-typedef typename GR::template NodeMap<Value> PotentialMap;
+typedef typename GR::template NodeMap<Cost> PotentialMap;
 public:
 /// \brief Enum type for selecting the pivot rule.
 ///
 private:
 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
-typedef typename GR::template ArcMap<Value> ValueArcMap;
+typedef typename GR::template ArcMap<Flow> FlowArcMap;
-typedef typename GR::template NodeMap<Value> ValueNodeMap;
+typedef typename GR::template ArcMap<Cost> CostArcMap;
+typedef typename GR::template NodeMap<Flow> FlowNodeMap;
 typedef std::vector<Arc> ArcVector;
 typedef std::vector<Node> NodeVector;
 typedef std::vector<int> IntVector;
 typedef std::vector<bool> BoolVector;
-typedef std::vector<Value> ValueVector;
+typedef std::vector<Flow> FlowVector;
+typedef std::vector<Cost> CostVector;
 // State constants for arcs
 enum ArcStateEnum {
 STATE_UPPER = -1,
 STATE_TREE  =  0,
 const GR &_graph;
 int _node_num;
 int _arc_num;
 // Parameters of the problem
-ValueArcMap *_plower;
+FlowArcMap *_plower;
-ValueArcMap *_pupper;
+FlowArcMap *_pupper;
-ValueArcMap *_pcost;
+CostArcMap *_pcost;
-ValueNodeMap *_psupply;
+FlowNodeMap *_psupply;
 bool _pstsup;
 Node _psource, _ptarget;
-Value _pstflow;
+Flow _pstflow;
 // Result maps
 FlowMap *_flow_map;
 PotentialMap *_potential_map;
 bool _local_flow;
 ArcVector _arc_ref;
 IntVector _source;
 IntVector _target;
 // Node and arc data
-ValueVector _cap;
+FlowVector _cap;
-ValueVector _cost;
+CostVector _cost;
-ValueVector _supply;
+FlowVector _supply;
-ValueVector _flow;
+FlowVector _flow;
-ValueVector _pi;
+CostVector _pi;
 // Data for storing the spanning tree structure
 IntVector _parent;
 IntVector _pred;
 IntVector _thread;
 // 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;
-Value delta;
+Flow delta;
 private:
 // Implementation of the First Eligible pivot rule
 class FirstEligiblePivotRule
 private:
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
-const ValueVector &_cost;
+const CostVector &_cost;
 const IntVector  &_state;
-const ValueVector &_pi;
+const CostVector &_pi;
 int &_in_arc;
 int _arc_num;
 // Pivot rule data
 int _next_arc;
 _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
 {}
 // Find next entering arc
 bool findEnteringArc() {
-Value c;
+Cost c;
 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;
 private:
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
-const ValueVector &_cost;
+const CostVector &_cost;
 const IntVector  &_state;
-const ValueVector &_pi;
+const CostVector &_pi;
 int &_in_arc;
 int _arc_num;
 public:
 _in_arc(ns.in_arc), _arc_num(ns._arc_num)
 {}
 // Find next entering arc
 bool findEnteringArc() {
-Value c, min = 0;
+Cost c, min = 0;
 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 ValueVector &_cost;
+const CostVector &_cost;
 const IntVector  &_state;
-const ValueVector &_pi;
+const CostVector &_pi;
 int &_in_arc;
 int _arc_num;
 // Pivot rule data
 int _block_size;
 MIN_BLOCK_SIZE );
 }
 // Find next entering arc
 bool findEnteringArc() {
-Value c, min = 0;
+Cost c, min = 0;
 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) {
 private:
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
-const ValueVector &_cost;
+const CostVector &_cost;
 const IntVector  &_state;
-const ValueVector &_pi;
+const CostVector &_pi;
 int &_in_arc;
 int _arc_num;
 // Pivot rule data
 IntVector _candidates;
 _candidates.resize(_list_length);
 }
 /// Find next entering arc
 bool findEnteringArc() {
-Value min, c;
+Cost min, c;
 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;
 private:
 // References to the NetworkSimplex class
 const IntVector  &_source;
 const IntVector  &_target;
-const ValueVector &_cost;
+const CostVector &_cost;
 const IntVector  &_state;
-const ValueVector &_pi;
+const CostVector &_pi;
 int &_in_arc;
 int _arc_num;
 // Pivot rule data
 int _block_size, _head_length, _curr_length;
 int _next_arc;
 IntVector _candidates;
-ValueVector _cand_cost;
+CostVector _cand_cost;
 // Functor class to compare arcs during sort of the candidate list
 class SortFunc
 {
 private:
-const ValueVector &_map;
+const CostVector &_map;
 public:
-SortFunc(const ValueVector &map) : _map(map) {}
+SortFunc(const CostVector &map) : _map(map) {}
 bool operator()(int left, int right) {
 return _map[left] > _map[right];
 }
 };
 _psupply(NULL), _pstsup(false),
 _flow_map(NULL), _potential_map(NULL),
 _local_flow(false), _local_potential(false),
 _node_id(graph)
 {
-LEMON_ASSERT(std::numeric_limits<Value>::is_integer &&
+LEMON_ASSERT(std::numeric_limits<Flow>::is_integer &&
-std::numeric_limits<Value>::is_signed,
+std::numeric_limits<Flow>::is_signed,
-"The value type of NetworkSimplex must be a signed integer");
+"The flow type of NetworkSimplex must be signed integer");
+LEMON_ASSERT(std::numeric_limits<Cost>::is_integer &&
+std::numeric_limits<Cost>::is_signed,
+"The cost type of NetworkSimplex must be signed integer");
 }
 /// Destructor.
 ~NetworkSimplex() {
 if (_local_flow) delete _flow_map;
 /// 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
+/// Its \c Value type must be convertible to the \c Flow type
 /// of the algorithm.
 ///
 /// \return <tt>(*this)</tt>
 template <typename LOWER>
 NetworkSimplex& lowerMap(const LOWER& map) {
 delete _plower;
-_plower = new ValueArcMap(_graph);
+_plower = new FlowArcMap(_graph);
 for (ArcIt a(_graph); a != INVALID; ++a) {
 (*_plower)[a] = map[a];
 }
 return *this;
 }
 ///
 /// 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.
+/// \c std::numeric_limits<Flow>::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
+/// Its \c Value type must be convertible to the \c Flow type
 /// of the algorithm.
 ///
 /// \return <tt>(*this)</tt>
 template<typename UPPER>
 NetworkSimplex& upperMap(const UPPER& map) {
 delete _pupper;
-_pupper = new ValueArcMap(_graph);
+_pupper = new FlowArcMap(_graph);
 for (ArcIt a(_graph); a != INVALID; ++a) {
 (*_pupper)[a] = map[a];
 }
 return *this;
 }
 /// 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.
+/// \c std::numeric_limits<Flow>::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.
+/// \c Flow type of the algorithm.
 ///
 /// \note This function is just a shortcut of calling \ref lowerMap()
 /// and \ref upperMap() separately.
 ///
 /// \return <tt>(*this)</tt>
 /// 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
+/// Its \c Value type must be convertible to the \c Cost type
 /// of the algorithm.
 ///
 /// \return <tt>(*this)</tt>
 template<typename COST>
 NetworkSimplex& costMap(const COST& map) {
 delete _pcost;
-_pcost = new ValueArcMap(_graph);
+_pcost = new CostArcMap(_graph);
 for (ArcIt a(_graph); a != INVALID; ++a) {
 (*_pcost)[a] = map[a];
 }
 return *this;
 }
 /// 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
+/// Its \c Value type must be convertible to the \c Flow type
 /// of the algorithm.
 ///
 /// \return <tt>(*this)</tt>
 template<typename SUP>
 NetworkSimplex& supplyMap(const SUP& map) {
 delete _psupply;
 _pstsup = false;
-_psupply = new ValueNodeMap(_graph);
+_psupply = new FlowNodeMap(_graph);
 for (NodeIt n(_graph); n != INVALID; ++n) {
 (*_psupply)[n] = map[n];
 }
 return *this;
 }
 /// \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) {
+NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
 delete _psupply;
 _psupply = NULL;
 _pstsup = true;
 _psource = s;
 _ptarget = t;
 /// @{
 /// \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$.
+/// The complexity of the function 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 Value
+/// 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 Num>
 }
 return c;
 }
 #ifndef DOXYGEN
-Value totalCost() const {
+Cost totalCost() const {
-return totalCost<Value>();
+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 {
+Flow flow(const Arc& a) const {
 return (*_flow_map)[a];
 }
 /// \brief Return a const reference to the flow map.
 ///
 ///
 /// 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 {
+Cost potential(const Node& n) const {
 return (*_potential_map)[n];
 }
 /// \brief Return a const reference to the potential map
 /// (the dual solution).
 _pstsup = true;
 _psource = _ptarget = NodeIt(_graph);
 _pstflow = 0;
 }
 if (_psupply) {
-Value sum = 0;
+Flow sum = 0;
 int i = 0;
 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 _node_id[n] = i;
 _supply[i] = (*_psupply)[n];
 sum += _supply[i];
 _arc_ref[i] = e;
 if ((i += k) >= _arc_num) i = (i % k) + 1;
 }
 // Initialize arc maps
+Flow max_cap = std::numeric_limits<Flow>::max();
+Cost max_cost = std::numeric_limits<Cost>::max() / 4;
 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)];
 }
 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;
+_cap[i] = max_cap;
 }
 if (_pcost) {
 for (int i = 0; i != _arc_num; ++i)
 _cost[i] = (*_pcost)[_arc_ref[i]];
 } else {
 }
 // Remove non-zero lower bounds
 if (_plower) {
 for (int i = 0; i != _arc_num; ++i) {
-Value c = (*_plower)[_arc_ref[i]];
+Flow c = (*_plower)[_arc_ref[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
-Value max_cap = std::numeric_limits<Value>::max();
-Value max_cost = std::numeric_limits<Value>::max() / 4;
 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;
 first  = _target[in_arc];
 second = _source[in_arc];
 }
 delta = _cap[in_arc];
 int result = 0;
-Value d;
+Flow d;
 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];
 // Change _flow and _state vectors
 void changeFlow(bool change) {
 // Augment along the cycle
 if (delta > 0) {
-Value val = _state[in_arc] * delta;
+Flow val = _state[in_arc] * delta;
 _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]) {
 }
 }
 // Update potentials
 void updatePotential() {
-Value sigma = _forward[u_in] ?
+Cost sigma = _forward[u_in] ?
 _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];

changeset 607	9ad8d2122b50
parent 606	c7d160f73d52
child 608	6ac5d9ae1d3d