1.1 --- a/lemon/network_simplex.h Wed Mar 25 21:37:50 2009 +0100
1.2 +++ b/lemon/network_simplex.h Fri Apr 03 13:46:16 2009 +0200
1.3 @@ -49,24 +49,28 @@
1.4 /// in LEMON for the minimum cost flow problem.
1.5 ///
1.6 /// \tparam GR The digraph type the algorithm runs on.
1.7 - /// \tparam V The value type used in the algorithm.
1.8 - /// By default it is \c int.
1.9 + /// \tparam F The value type used for flow amounts, capacity bounds
1.10 + /// and supply values in the algorithm. By default it is \c int.
1.11 + /// \tparam C The value type used for costs and potentials in the
1.12 + /// algorithm. By default it is the same as \c F.
1.13 ///
1.14 - /// \warning The value type must be a signed integer type.
1.15 + /// \warning Both value types must be signed integer types.
1.16 ///
1.17 /// \note %NetworkSimplex provides five different pivot rule
1.18 /// implementations. For more information see \ref PivotRule.
1.19 - template <typename GR, typename V = int>
1.20 + template <typename GR, typename F = int, typename C = F>
1.21 class NetworkSimplex
1.22 {
1.23 public:
1.24
1.25 - /// The value type of the algorithm
1.26 - typedef V Value;
1.27 + /// The flow type of the algorithm
1.28 + typedef F Flow;
1.29 + /// The cost type of the algorithm
1.30 + typedef C Cost;
1.31 /// The type of the flow map
1.32 - typedef typename GR::template ArcMap<Value> FlowMap;
1.33 + typedef typename GR::template ArcMap<Flow> FlowMap;
1.34 /// The type of the potential map
1.35 - typedef typename GR::template NodeMap<Value> PotentialMap;
1.36 + typedef typename GR::template NodeMap<Cost> PotentialMap;
1.37
1.38 public:
1.39
1.40 @@ -117,14 +121,16 @@
1.41
1.42 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.43
1.44 - typedef typename GR::template ArcMap<Value> ValueArcMap;
1.45 - typedef typename GR::template NodeMap<Value> ValueNodeMap;
1.46 + typedef typename GR::template ArcMap<Flow> FlowArcMap;
1.47 + typedef typename GR::template ArcMap<Cost> CostArcMap;
1.48 + typedef typename GR::template NodeMap<Flow> FlowNodeMap;
1.49
1.50 typedef std::vector<Arc> ArcVector;
1.51 typedef std::vector<Node> NodeVector;
1.52 typedef std::vector<int> IntVector;
1.53 typedef std::vector<bool> BoolVector;
1.54 - typedef std::vector<Value> ValueVector;
1.55 + typedef std::vector<Flow> FlowVector;
1.56 + typedef std::vector<Cost> CostVector;
1.57
1.58 // State constants for arcs
1.59 enum ArcStateEnum {
1.60 @@ -141,13 +147,13 @@
1.61 int _arc_num;
1.62
1.63 // Parameters of the problem
1.64 - ValueArcMap *_plower;
1.65 - ValueArcMap *_pupper;
1.66 - ValueArcMap *_pcost;
1.67 - ValueNodeMap *_psupply;
1.68 + FlowArcMap *_plower;
1.69 + FlowArcMap *_pupper;
1.70 + CostArcMap *_pcost;
1.71 + FlowNodeMap *_psupply;
1.72 bool _pstsup;
1.73 Node _psource, _ptarget;
1.74 - Value _pstflow;
1.75 + Flow _pstflow;
1.76
1.77 // Result maps
1.78 FlowMap *_flow_map;
1.79 @@ -162,11 +168,11 @@
1.80 IntVector _target;
1.81
1.82 // Node and arc data
1.83 - ValueVector _cap;
1.84 - ValueVector _cost;
1.85 - ValueVector _supply;
1.86 - ValueVector _flow;
1.87 - ValueVector _pi;
1.88 + FlowVector _cap;
1.89 + CostVector _cost;
1.90 + FlowVector _supply;
1.91 + FlowVector _flow;
1.92 + CostVector _pi;
1.93
1.94 // Data for storing the spanning tree structure
1.95 IntVector _parent;
1.96 @@ -184,7 +190,7 @@
1.97 int in_arc, join, u_in, v_in, u_out, v_out;
1.98 int first, second, right, last;
1.99 int stem, par_stem, new_stem;
1.100 - Value delta;
1.101 + Flow delta;
1.102
1.103 private:
1.104
1.105 @@ -196,9 +202,9 @@
1.106 // References to the NetworkSimplex class
1.107 const IntVector &_source;
1.108 const IntVector &_target;
1.109 - const ValueVector &_cost;
1.110 + const CostVector &_cost;
1.111 const IntVector &_state;
1.112 - const ValueVector &_pi;
1.113 + const CostVector &_pi;
1.114 int &_in_arc;
1.115 int _arc_num;
1.116
1.117 @@ -216,7 +222,7 @@
1.118
1.119 // Find next entering arc
1.120 bool findEnteringArc() {
1.121 - Value c;
1.122 + Cost c;
1.123 for (int e = _next_arc; e < _arc_num; ++e) {
1.124 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
1.125 if (c < 0) {
1.126 @@ -247,9 +253,9 @@
1.127 // References to the NetworkSimplex class
1.128 const IntVector &_source;
1.129 const IntVector &_target;
1.130 - const ValueVector &_cost;
1.131 + const CostVector &_cost;
1.132 const IntVector &_state;
1.133 - const ValueVector &_pi;
1.134 + const CostVector &_pi;
1.135 int &_in_arc;
1.136 int _arc_num;
1.137
1.138 @@ -264,7 +270,7 @@
1.139
1.140 // Find next entering arc
1.141 bool findEnteringArc() {
1.142 - Value c, min = 0;
1.143 + Cost c, min = 0;
1.144 for (int e = 0; e < _arc_num; ++e) {
1.145 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
1.146 if (c < min) {
1.147 @@ -286,9 +292,9 @@
1.148 // References to the NetworkSimplex class
1.149 const IntVector &_source;
1.150 const IntVector &_target;
1.151 - const ValueVector &_cost;
1.152 + const CostVector &_cost;
1.153 const IntVector &_state;
1.154 - const ValueVector &_pi;
1.155 + const CostVector &_pi;
1.156 int &_in_arc;
1.157 int _arc_num;
1.158
1.159 @@ -314,7 +320,7 @@
1.160
1.161 // Find next entering arc
1.162 bool findEnteringArc() {
1.163 - Value c, min = 0;
1.164 + Cost c, min = 0;
1.165 int cnt = _block_size;
1.166 int e, min_arc = _next_arc;
1.167 for (e = _next_arc; e < _arc_num; ++e) {
1.168 @@ -358,9 +364,9 @@
1.169 // References to the NetworkSimplex class
1.170 const IntVector &_source;
1.171 const IntVector &_target;
1.172 - const ValueVector &_cost;
1.173 + const CostVector &_cost;
1.174 const IntVector &_state;
1.175 - const ValueVector &_pi;
1.176 + const CostVector &_pi;
1.177 int &_in_arc;
1.178 int _arc_num;
1.179
1.180 @@ -394,7 +400,7 @@
1.181
1.182 /// Find next entering arc
1.183 bool findEnteringArc() {
1.184 - Value min, c;
1.185 + Cost min, c;
1.186 int e, min_arc = _next_arc;
1.187 if (_curr_length > 0 && _minor_count < _minor_limit) {
1.188 // Minor iteration: select the best eligible arc from the
1.189 @@ -463,9 +469,9 @@
1.190 // References to the NetworkSimplex class
1.191 const IntVector &_source;
1.192 const IntVector &_target;
1.193 - const ValueVector &_cost;
1.194 + const CostVector &_cost;
1.195 const IntVector &_state;
1.196 - const ValueVector &_pi;
1.197 + const CostVector &_pi;
1.198 int &_in_arc;
1.199 int _arc_num;
1.200
1.201 @@ -473,15 +479,15 @@
1.202 int _block_size, _head_length, _curr_length;
1.203 int _next_arc;
1.204 IntVector _candidates;
1.205 - ValueVector _cand_cost;
1.206 + CostVector _cand_cost;
1.207
1.208 // Functor class to compare arcs during sort of the candidate list
1.209 class SortFunc
1.210 {
1.211 private:
1.212 - const ValueVector &_map;
1.213 + const CostVector &_map;
1.214 public:
1.215 - SortFunc(const ValueVector &map) : _map(map) {}
1.216 + SortFunc(const CostVector &map) : _map(map) {}
1.217 bool operator()(int left, int right) {
1.218 return _map[left] > _map[right];
1.219 }
1.220 @@ -590,9 +596,12 @@
1.221 _local_flow(false), _local_potential(false),
1.222 _node_id(graph)
1.223 {
1.224 - LEMON_ASSERT(std::numeric_limits<Value>::is_integer &&
1.225 - std::numeric_limits<Value>::is_signed,
1.226 - "The value type of NetworkSimplex must be a signed integer");
1.227 + LEMON_ASSERT(std::numeric_limits<Flow>::is_integer &&
1.228 + std::numeric_limits<Flow>::is_signed,
1.229 + "The flow type of NetworkSimplex must be signed integer");
1.230 + LEMON_ASSERT(std::numeric_limits<Cost>::is_integer &&
1.231 + std::numeric_limits<Cost>::is_signed,
1.232 + "The cost type of NetworkSimplex must be signed integer");
1.233 }
1.234
1.235 /// Destructor.
1.236 @@ -609,14 +618,14 @@
1.237 /// on all arcs.
1.238 ///
1.239 /// \param map An arc map storing the lower bounds.
1.240 - /// Its \c Value type must be convertible to the \c Value type
1.241 + /// Its \c Value type must be convertible to the \c Flow type
1.242 /// of the algorithm.
1.243 ///
1.244 /// \return <tt>(*this)</tt>
1.245 template <typename LOWER>
1.246 NetworkSimplex& lowerMap(const LOWER& map) {
1.247 delete _plower;
1.248 - _plower = new ValueArcMap(_graph);
1.249 + _plower = new FlowArcMap(_graph);
1.250 for (ArcIt a(_graph); a != INVALID; ++a) {
1.251 (*_plower)[a] = map[a];
1.252 }
1.253 @@ -629,17 +638,17 @@
1.254 /// If none of the functions \ref upperMap(), \ref capacityMap()
1.255 /// and \ref boundMaps() is used before calling \ref run(),
1.256 /// the upper bounds (capacities) will be set to
1.257 - /// \c std::numeric_limits<Value>::max() on all arcs.
1.258 + /// \c std::numeric_limits<Flow>::max() on all arcs.
1.259 ///
1.260 /// \param map An arc map storing the upper bounds.
1.261 - /// Its \c Value type must be convertible to the \c Value type
1.262 + /// Its \c Value type must be convertible to the \c Flow type
1.263 /// of the algorithm.
1.264 ///
1.265 /// \return <tt>(*this)</tt>
1.266 template<typename UPPER>
1.267 NetworkSimplex& upperMap(const UPPER& map) {
1.268 delete _pupper;
1.269 - _pupper = new ValueArcMap(_graph);
1.270 + _pupper = new FlowArcMap(_graph);
1.271 for (ArcIt a(_graph); a != INVALID; ++a) {
1.272 (*_pupper)[a] = map[a];
1.273 }
1.274 @@ -666,13 +675,13 @@
1.275 /// If none of the functions \ref upperMap(), \ref capacityMap()
1.276 /// and \ref boundMaps() is used before calling \ref run(),
1.277 /// the upper bounds (capacities) will be set to
1.278 - /// \c std::numeric_limits<Value>::max() on all arcs.
1.279 + /// \c std::numeric_limits<Flow>::max() on all arcs.
1.280 ///
1.281 /// \param lower An arc map storing the lower bounds.
1.282 /// \param upper An arc map storing the upper bounds.
1.283 ///
1.284 /// The \c Value type of the maps must be convertible to the
1.285 - /// \c Value type of the algorithm.
1.286 + /// \c Flow type of the algorithm.
1.287 ///
1.288 /// \note This function is just a shortcut of calling \ref lowerMap()
1.289 /// and \ref upperMap() separately.
1.290 @@ -690,14 +699,14 @@
1.291 /// will be set to \c 1 on all arcs.
1.292 ///
1.293 /// \param map An arc map storing the costs.
1.294 - /// Its \c Value type must be convertible to the \c Value type
1.295 + /// Its \c Value type must be convertible to the \c Cost type
1.296 /// of the algorithm.
1.297 ///
1.298 /// \return <tt>(*this)</tt>
1.299 template<typename COST>
1.300 NetworkSimplex& costMap(const COST& map) {
1.301 delete _pcost;
1.302 - _pcost = new ValueArcMap(_graph);
1.303 + _pcost = new CostArcMap(_graph);
1.304 for (ArcIt a(_graph); a != INVALID; ++a) {
1.305 (*_pcost)[a] = map[a];
1.306 }
1.307 @@ -712,7 +721,7 @@
1.308 /// (It makes sense only if non-zero lower bounds are given.)
1.309 ///
1.310 /// \param map A node map storing the supply values.
1.311 - /// Its \c Value type must be convertible to the \c Value type
1.312 + /// Its \c Value type must be convertible to the \c Flow type
1.313 /// of the algorithm.
1.314 ///
1.315 /// \return <tt>(*this)</tt>
1.316 @@ -720,7 +729,7 @@
1.317 NetworkSimplex& supplyMap(const SUP& map) {
1.318 delete _psupply;
1.319 _pstsup = false;
1.320 - _psupply = new ValueNodeMap(_graph);
1.321 + _psupply = new FlowNodeMap(_graph);
1.322 for (NodeIt n(_graph); n != INVALID; ++n) {
1.323 (*_psupply)[n] = map[n];
1.324 }
1.325 @@ -741,7 +750,7 @@
1.326 /// (i.e. the supply of \c s and the demand of \c t).
1.327 ///
1.328 /// \return <tt>(*this)</tt>
1.329 - NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
1.330 + NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
1.331 delete _psupply;
1.332 _psupply = NULL;
1.333 _pstsup = true;
1.334 @@ -874,14 +883,14 @@
1.335 /// \brief Return the total cost of the found flow.
1.336 ///
1.337 /// This function returns the total cost of the found flow.
1.338 - /// The complexity of the function is \f$ O(e) \f$.
1.339 + /// The complexity of the function is O(e).
1.340 ///
1.341 /// \note The return type of the function can be specified as a
1.342 /// template parameter. For example,
1.343 /// \code
1.344 /// ns.totalCost<double>();
1.345 /// \endcode
1.346 - /// It is useful if the total cost cannot be stored in the \c Value
1.347 + /// It is useful if the total cost cannot be stored in the \c Cost
1.348 /// type of the algorithm, which is the default return type of the
1.349 /// function.
1.350 ///
1.351 @@ -900,8 +909,8 @@
1.352 }
1.353
1.354 #ifndef DOXYGEN
1.355 - Value totalCost() const {
1.356 - return totalCost<Value>();
1.357 + Cost totalCost() const {
1.358 + return totalCost<Cost>();
1.359 }
1.360 #endif
1.361
1.362 @@ -910,7 +919,7 @@
1.363 /// This function returns the flow on the given arc.
1.364 ///
1.365 /// \pre \ref run() must be called before using this function.
1.366 - Value flow(const Arc& a) const {
1.367 + Flow flow(const Arc& a) const {
1.368 return (*_flow_map)[a];
1.369 }
1.370
1.371 @@ -930,7 +939,7 @@
1.372 /// given node.
1.373 ///
1.374 /// \pre \ref run() must be called before using this function.
1.375 - Value potential(const Node& n) const {
1.376 + Cost potential(const Node& n) const {
1.377 return (*_potential_map)[n];
1.378 }
1.379
1.380 @@ -996,7 +1005,7 @@
1.381 _pstflow = 0;
1.382 }
1.383 if (_psupply) {
1.384 - Value sum = 0;
1.385 + Flow sum = 0;
1.386 int i = 0;
1.387 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
1.388 _node_id[n] = i;
1.389 @@ -1035,6 +1044,8 @@
1.390 }
1.391
1.392 // Initialize arc maps
1.393 + Flow max_cap = std::numeric_limits<Flow>::max();
1.394 + Cost max_cost = std::numeric_limits<Cost>::max() / 4;
1.395 if (_pupper && _pcost) {
1.396 for (int i = 0; i != _arc_num; ++i) {
1.397 Arc e = _arc_ref[i];
1.398 @@ -1057,9 +1068,8 @@
1.399 for (int i = 0; i != _arc_num; ++i)
1.400 _cap[i] = (*_pupper)[_arc_ref[i]];
1.401 } else {
1.402 - Value val = std::numeric_limits<Value>::max();
1.403 for (int i = 0; i != _arc_num; ++i)
1.404 - _cap[i] = val;
1.405 + _cap[i] = max_cap;
1.406 }
1.407 if (_pcost) {
1.408 for (int i = 0; i != _arc_num; ++i)
1.409 @@ -1073,7 +1083,7 @@
1.410 // Remove non-zero lower bounds
1.411 if (_plower) {
1.412 for (int i = 0; i != _arc_num; ++i) {
1.413 - Value c = (*_plower)[_arc_ref[i]];
1.414 + Flow c = (*_plower)[_arc_ref[i]];
1.415 if (c != 0) {
1.416 _cap[i] -= c;
1.417 _supply[_source[i]] -= c;
1.418 @@ -1083,8 +1093,6 @@
1.419 }
1.420
1.421 // Add artificial arcs and initialize the spanning tree data structure
1.422 - Value max_cap = std::numeric_limits<Value>::max();
1.423 - Value max_cost = std::numeric_limits<Value>::max() / 4;
1.424 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
1.425 _thread[u] = u + 1;
1.426 _rev_thread[u + 1] = u;
1.427 @@ -1137,7 +1145,7 @@
1.428 }
1.429 delta = _cap[in_arc];
1.430 int result = 0;
1.431 - Value d;
1.432 + Flow d;
1.433 int e;
1.434
1.435 // Search the cycle along the path form the first node to the root
1.436 @@ -1175,7 +1183,7 @@
1.437 void changeFlow(bool change) {
1.438 // Augment along the cycle
1.439 if (delta > 0) {
1.440 - Value val = _state[in_arc] * delta;
1.441 + Flow val = _state[in_arc] * delta;
1.442 _flow[in_arc] += val;
1.443 for (int u = _source[in_arc]; u != join; u = _parent[u]) {
1.444 _flow[_pred[u]] += _forward[u] ? -val : val;
1.445 @@ -1316,7 +1324,7 @@
1.446
1.447 // Update potentials
1.448 void updatePotential() {
1.449 - Value sigma = _forward[u_in] ?
1.450 + Cost sigma = _forward[u_in] ?
1.451 _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
1.452 _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
1.453 if (_succ_num[u_in] > _node_num / 2) {
2.1 --- a/test/min_cost_flow_test.cc Wed Mar 25 21:37:50 2009 +0100
2.2 +++ b/test/min_cost_flow_test.cc Fri Apr 03 13:46:16 2009 +0200
2.3 @@ -77,7 +77,7 @@
2.4
2.5
2.6 // Check the interface of an MCF algorithm
2.7 -template <typename GR, typename Value>
2.8 +template <typename GR, typename Flow, typename Cost>
2.9 class McfClassConcept
2.10 {
2.11 public:
2.12 @@ -116,18 +116,19 @@
2.13
2.14 typedef typename GR::Node Node;
2.15 typedef typename GR::Arc Arc;
2.16 - typedef concepts::ReadMap<Node, Value> NM;
2.17 - typedef concepts::ReadMap<Arc, Value> AM;
2.18 + typedef concepts::ReadMap<Node, Flow> NM;
2.19 + typedef concepts::ReadMap<Arc, Flow> FAM;
2.20 + typedef concepts::ReadMap<Arc, Cost> CAM;
2.21
2.22 const GR &g;
2.23 - const AM &lower;
2.24 - const AM &upper;
2.25 - const AM &cost;
2.26 + const FAM &lower;
2.27 + const FAM &upper;
2.28 + const CAM &cost;
2.29 const NM ⊃
2.30 const Node &n;
2.31 const Arc &a;
2.32 - const Value &k;
2.33 - Value v;
2.34 + const Flow &k;
2.35 + Flow v;
2.36 bool b;
2.37
2.38 typename MCF::FlowMap &flow;
2.39 @@ -206,15 +207,16 @@
2.40 {
2.41 // Check the interfaces
2.42 {
2.43 - typedef int Value;
2.44 + typedef int Flow;
2.45 + typedef int Cost;
2.46 // TODO: This typedef should be enabled if the standard maps are
2.47 // reference maps in the graph concepts (See #190).
2.48 /**/
2.49 //typedef concepts::Digraph GR;
2.50 typedef ListDigraph GR;
2.51 /**/
2.52 - checkConcept< McfClassConcept<GR, Value>,
2.53 - NetworkSimplex<GR, Value> >();
2.54 + checkConcept< McfClassConcept<GR, Flow, Cost>,
2.55 + NetworkSimplex<GR, Flow, Cost> >();
2.56 }
2.57
2.58 // Run various MCF tests