223 |
223 |
224 for (ArcIt a(_graph); a != INVALID; ++a) { |
224 for (ArcIt a(_graph); a != INVALID; ++a) { |
225 _flow->set(a, 0); |
225 _flow->set(a, 0); |
226 } |
226 } |
227 |
227 |
228 int bucket_num = 1; |
228 int bucket_num = 0; |
|
229 std::vector<Node> queue(_node_num); |
|
230 int qfirst = 0, qlast = 0, qsep = 0; |
229 |
231 |
230 { |
232 { |
231 typename Digraph::template NodeMap<bool> reached(_graph, false); |
233 typename Digraph::template NodeMap<bool> reached(_graph, false); |
232 |
234 |
233 reached.set(_source, true); |
235 reached.set(_source, true); |
234 |
|
235 bool first_set = true; |
236 bool first_set = true; |
236 |
237 |
237 for (NodeIt t(_graph); t != INVALID; ++t) { |
238 for (NodeIt t(_graph); t != INVALID; ++t) { |
238 if (reached[t]) continue; |
239 if (reached[t]) continue; |
239 _sets.push_front(std::list<int>()); |
240 _sets.push_front(std::list<int>()); |
240 _sets.front().push_front(bucket_num); |
241 |
241 _dormant[bucket_num] = !first_set; |
242 queue[qlast++] = t; |
242 |
|
243 _bucket->set(t, bucket_num); |
|
244 _first[bucket_num] = _last[bucket_num] = t; |
|
245 _next->set(t, INVALID); |
|
246 _prev->set(t, INVALID); |
|
247 |
|
248 ++bucket_num; |
|
249 |
|
250 std::vector<Node> queue; |
|
251 queue.push_back(t); |
|
252 reached.set(t, true); |
243 reached.set(t, true); |
253 |
244 |
254 while (!queue.empty()) { |
245 while (qfirst != qlast) { |
255 _sets.front().push_front(bucket_num); |
246 if (qsep == qfirst) { |
256 _dormant[bucket_num] = !first_set; |
247 ++bucket_num; |
257 _first[bucket_num] = _last[bucket_num] = INVALID; |
248 _sets.front().push_front(bucket_num); |
258 |
249 _dormant[bucket_num] = !first_set; |
259 std::vector<Node> nqueue; |
250 _first[bucket_num] = _last[bucket_num] = INVALID; |
260 for (int i = 0; i < int(queue.size()); ++i) { |
251 qsep = qlast; |
261 Node n = queue[i]; |
252 } |
262 for (InArcIt a(_graph, n); a != INVALID; ++a) { |
253 |
263 Node u = _graph.source(a); |
254 Node n = queue[qfirst++]; |
264 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
255 addItem(n, bucket_num); |
265 reached.set(u, true); |
256 |
266 addItem(u, bucket_num); |
257 for (InArcIt a(_graph, n); a != INVALID; ++a) { |
267 nqueue.push_back(u); |
258 Node u = _graph.source(a); |
268 } |
259 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
269 } |
260 reached.set(u, true); |
270 } |
261 queue[qlast++] = u; |
271 queue.swap(nqueue); |
262 } |
272 ++bucket_num; |
263 } |
273 } |
264 } |
274 _sets.front().pop_front(); |
|
275 --bucket_num; |
|
276 first_set = false; |
265 first_set = false; |
277 } |
266 } |
278 |
267 |
|
268 ++bucket_num; |
279 _bucket->set(_source, 0); |
269 _bucket->set(_source, 0); |
280 _dormant[0] = true; |
270 _dormant[0] = true; |
281 } |
271 } |
282 _source_set->set(_source, true); |
272 _source_set->set(_source, true); |
283 |
273 |
544 bool first_set = true; |
536 bool first_set = true; |
545 |
537 |
546 for (NodeIt t(_graph); t != INVALID; ++t) { |
538 for (NodeIt t(_graph); t != INVALID; ++t) { |
547 if (reached[t]) continue; |
539 if (reached[t]) continue; |
548 _sets.push_front(std::list<int>()); |
540 _sets.push_front(std::list<int>()); |
549 _sets.front().push_front(bucket_num); |
541 |
550 _dormant[bucket_num] = !first_set; |
542 queue[qlast++] = t; |
551 |
|
552 _bucket->set(t, bucket_num); |
|
553 _first[bucket_num] = _last[bucket_num] = t; |
|
554 _next->set(t, INVALID); |
|
555 _prev->set(t, INVALID); |
|
556 |
|
557 ++bucket_num; |
|
558 |
|
559 std::vector<Node> queue; |
|
560 queue.push_back(t); |
|
561 reached.set(t, true); |
543 reached.set(t, true); |
562 |
544 |
563 while (!queue.empty()) { |
545 while (qfirst != qlast) { |
564 _sets.front().push_front(bucket_num); |
546 if (qsep == qfirst) { |
565 _dormant[bucket_num] = !first_set; |
547 ++bucket_num; |
566 _first[bucket_num] = _last[bucket_num] = INVALID; |
548 _sets.front().push_front(bucket_num); |
567 |
549 _dormant[bucket_num] = !first_set; |
568 std::vector<Node> nqueue; |
550 _first[bucket_num] = _last[bucket_num] = INVALID; |
569 for (int i = 0; i < int(queue.size()); ++i) { |
551 qsep = qlast; |
570 Node n = queue[i]; |
552 } |
571 for (OutArcIt a(_graph, n); a != INVALID; ++a) { |
553 |
572 Node u = _graph.target(a); |
554 Node n = queue[qfirst++]; |
573 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
555 addItem(n, bucket_num); |
574 reached.set(u, true); |
556 |
575 addItem(u, bucket_num); |
557 for (OutArcIt a(_graph, n); a != INVALID; ++a) { |
576 nqueue.push_back(u); |
558 Node u = _graph.target(a); |
577 } |
559 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
578 } |
560 reached.set(u, true); |
579 } |
561 queue[qlast++] = u; |
580 queue.swap(nqueue); |
562 } |
581 ++bucket_num; |
563 } |
582 } |
564 } |
583 _sets.front().pop_front(); |
|
584 --bucket_num; |
|
585 first_set = false; |
565 first_set = false; |
586 } |
566 } |
587 |
567 |
|
568 ++bucket_num; |
588 _bucket->set(_source, 0); |
569 _bucket->set(_source, 0); |
589 _dormant[0] = true; |
570 _dormant[0] = true; |
590 } |
571 } |
591 _source_set->set(_source, true); |
572 _source_set->set(_source, true); |
592 |
573 |