162 private: |
162 private: |
163 |
163 |
164 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
164 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
165 |
165 |
166 typedef std::vector<int> IntVector; |
166 typedef std::vector<int> IntVector; |
167 typedef std::vector<bool> BoolVector; |
167 typedef std::vector<char> CharVector; |
168 typedef std::vector<Value> ValueVector; |
168 typedef std::vector<Value> ValueVector; |
169 typedef std::vector<Cost> CostVector; |
169 typedef std::vector<Cost> CostVector; |
170 |
170 |
171 // State constants for arcs |
171 // State constants for arcs |
172 enum ArcStateEnum { |
172 enum ArcStateEnum { |
210 IntVector _thread; |
210 IntVector _thread; |
211 IntVector _rev_thread; |
211 IntVector _rev_thread; |
212 IntVector _succ_num; |
212 IntVector _succ_num; |
213 IntVector _last_succ; |
213 IntVector _last_succ; |
214 IntVector _dirty_revs; |
214 IntVector _dirty_revs; |
215 BoolVector _forward; |
215 CharVector _forward; |
216 IntVector _state; |
216 CharVector _state; |
217 int _root; |
217 int _root; |
218 |
218 |
219 // Temporary data used in the current pivot iteration |
219 // Temporary data used in the current pivot iteration |
220 int in_arc, join, u_in, v_in, u_out, v_out; |
220 int in_arc, join, u_in, v_in, u_out, v_out; |
221 int first, second, right, last; |
221 int first, second, right, last; |
222 int stem, par_stem, new_stem; |
222 int stem, par_stem, new_stem; |
223 Value delta; |
223 Value delta; |
|
224 |
|
225 const Value MAX; |
224 |
226 |
225 public: |
227 public: |
226 |
228 |
227 /// \brief Constant for infinite upper bounds (capacities). |
229 /// \brief Constant for infinite upper bounds (capacities). |
228 /// |
230 /// |
240 |
242 |
241 // References to the NetworkSimplex class |
243 // References to the NetworkSimplex class |
242 const IntVector &_source; |
244 const IntVector &_source; |
243 const IntVector &_target; |
245 const IntVector &_target; |
244 const CostVector &_cost; |
246 const CostVector &_cost; |
245 const IntVector &_state; |
247 const CharVector &_state; |
246 const CostVector &_pi; |
248 const CostVector &_pi; |
247 int &_in_arc; |
249 int &_in_arc; |
248 int _search_arc_num; |
250 int _search_arc_num; |
249 |
251 |
250 // Pivot rule data |
252 // Pivot rule data |
292 |
294 |
293 // References to the NetworkSimplex class |
295 // References to the NetworkSimplex class |
294 const IntVector &_source; |
296 const IntVector &_source; |
295 const IntVector &_target; |
297 const IntVector &_target; |
296 const CostVector &_cost; |
298 const CostVector &_cost; |
297 const IntVector &_state; |
299 const CharVector &_state; |
298 const CostVector &_pi; |
300 const CostVector &_pi; |
299 int &_in_arc; |
301 int &_in_arc; |
300 int _search_arc_num; |
302 int _search_arc_num; |
301 |
303 |
302 public: |
304 public: |
331 |
333 |
332 // References to the NetworkSimplex class |
334 // References to the NetworkSimplex class |
333 const IntVector &_source; |
335 const IntVector &_source; |
334 const IntVector &_target; |
336 const IntVector &_target; |
335 const CostVector &_cost; |
337 const CostVector &_cost; |
336 const IntVector &_state; |
338 const CharVector &_state; |
337 const CostVector &_pi; |
339 const CostVector &_pi; |
338 int &_in_arc; |
340 int &_in_arc; |
339 int _search_arc_num; |
341 int _search_arc_num; |
340 |
342 |
341 // Pivot rule data |
343 // Pivot rule data |
404 |
406 |
405 // References to the NetworkSimplex class |
407 // References to the NetworkSimplex class |
406 const IntVector &_source; |
408 const IntVector &_source; |
407 const IntVector &_target; |
409 const IntVector &_target; |
408 const CostVector &_cost; |
410 const CostVector &_cost; |
409 const IntVector &_state; |
411 const CharVector &_state; |
410 const CostVector &_pi; |
412 const CostVector &_pi; |
411 int &_in_arc; |
413 int &_in_arc; |
412 int _search_arc_num; |
414 int _search_arc_num; |
413 |
415 |
414 // Pivot rule data |
416 // Pivot rule data |
507 |
509 |
508 // References to the NetworkSimplex class |
510 // References to the NetworkSimplex class |
509 const IntVector &_source; |
511 const IntVector &_source; |
510 const IntVector &_target; |
512 const IntVector &_target; |
511 const CostVector &_cost; |
513 const CostVector &_cost; |
512 const IntVector &_state; |
514 const CharVector &_state; |
513 const CostVector &_pi; |
515 const CostVector &_pi; |
514 int &_in_arc; |
516 int &_in_arc; |
515 int _search_arc_num; |
517 int _search_arc_num; |
516 |
518 |
517 // Pivot rule data |
519 // Pivot rule data |
629 /// mixed order in the internal data structure. |
631 /// mixed order in the internal data structure. |
630 /// In special cases, it could lead to better overall performance, |
632 /// In special cases, it could lead to better overall performance, |
631 /// but it is usually slower. Therefore it is disabled by default. |
633 /// but it is usually slower. Therefore it is disabled by default. |
632 NetworkSimplex(const GR& graph, bool arc_mixing = false) : |
634 NetworkSimplex(const GR& graph, bool arc_mixing = false) : |
633 _graph(graph), _node_id(graph), _arc_id(graph), |
635 _graph(graph), _node_id(graph), _arc_id(graph), |
|
636 MAX(std::numeric_limits<Value>::max()), |
634 INF(std::numeric_limits<Value>::has_infinity ? |
637 INF(std::numeric_limits<Value>::has_infinity ? |
635 std::numeric_limits<Value>::infinity() : |
638 std::numeric_limits<Value>::infinity() : MAX) |
636 std::numeric_limits<Value>::max()) |
|
637 { |
639 { |
638 // Check the value types |
640 // Check the value types |
639 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
641 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
640 "The flow type of NetworkSimplex must be signed"); |
642 "The flow type of NetworkSimplex must be signed"); |
641 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
643 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
1018 // Remove non-zero lower bounds |
1020 // Remove non-zero lower bounds |
1019 if (_have_lower) { |
1021 if (_have_lower) { |
1020 for (int i = 0; i != _arc_num; ++i) { |
1022 for (int i = 0; i != _arc_num; ++i) { |
1021 Value c = _lower[i]; |
1023 Value c = _lower[i]; |
1022 if (c >= 0) { |
1024 if (c >= 0) { |
1023 _cap[i] = _upper[i] < INF ? _upper[i] - c : INF; |
1025 _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF; |
1024 } else { |
1026 } else { |
1025 _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF; |
1027 _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF; |
1026 } |
1028 } |
1027 _supply[_source[i]] -= c; |
1029 _supply[_source[i]] -= c; |
1028 _supply[_target[i]] += c; |
1030 _supply[_target[i]] += c; |
1029 } |
1031 } |
1030 } else { |
1032 } else { |
1212 |
1214 |
1213 // Search the cycle along the path form the first node to the root |
1215 // Search the cycle along the path form the first node to the root |
1214 for (int u = first; u != join; u = _parent[u]) { |
1216 for (int u = first; u != join; u = _parent[u]) { |
1215 e = _pred[u]; |
1217 e = _pred[u]; |
1216 d = _forward[u] ? |
1218 d = _forward[u] ? |
1217 _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]); |
1219 _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]); |
1218 if (d < delta) { |
1220 if (d < delta) { |
1219 delta = d; |
1221 delta = d; |
1220 u_out = u; |
1222 u_out = u; |
1221 result = 1; |
1223 result = 1; |
1222 } |
1224 } |
1223 } |
1225 } |
1224 // Search the cycle along the path form the second node to the root |
1226 // Search the cycle along the path form the second node to the root |
1225 for (int u = second; u != join; u = _parent[u]) { |
1227 for (int u = second; u != join; u = _parent[u]) { |
1226 e = _pred[u]; |
1228 e = _pred[u]; |
1227 d = _forward[u] ? |
1229 d = _forward[u] ? |
1228 (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e]; |
1230 (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e]; |
1229 if (d <= delta) { |
1231 if (d <= delta) { |
1230 delta = d; |
1232 delta = d; |
1231 u_out = u; |
1233 u_out = u; |
1232 result = 2; |
1234 result = 2; |
1233 } |
1235 } |
1422 |
1424 |
1423 // Execute the Network Simplex algorithm |
1425 // Execute the Network Simplex algorithm |
1424 while (pivot.findEnteringArc()) { |
1426 while (pivot.findEnteringArc()) { |
1425 findJoinNode(); |
1427 findJoinNode(); |
1426 bool change = findLeavingArc(); |
1428 bool change = findLeavingArc(); |
1427 if (delta >= INF) return UNBOUNDED; |
1429 if (delta >= MAX) return UNBOUNDED; |
1428 changeFlow(change); |
1430 changeFlow(change); |
1429 if (change) { |
1431 if (change) { |
1430 updateTreeStructure(); |
1432 updateTreeStructure(); |
1431 updatePotential(); |
1433 updatePotential(); |
1432 } |
1434 } |