lemon/hao_orlin.h
changeset 589 630c4898c548
parent 559 c5fd2d996909
child 596 293551ad254f
equal deleted inserted replaced
4:6b37b4153c1b 5:c848d2888106
   159     }
   159     }
   160 
   160 
   161   private:
   161   private:
   162 
   162 
   163     void activate(const Node& i) {
   163     void activate(const Node& i) {
   164       _active->set(i, true);
   164       (*_active)[i] = true;
   165 
   165 
   166       int bucket = (*_bucket)[i];
   166       int bucket = (*_bucket)[i];
   167 
   167 
   168       if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return;
   168       if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return;
   169       //unlace
   169       //unlace
   170       _next->set((*_prev)[i], (*_next)[i]);
   170       (*_next)[(*_prev)[i]] = (*_next)[i];
   171       if ((*_next)[i] != INVALID) {
   171       if ((*_next)[i] != INVALID) {
   172         _prev->set((*_next)[i], (*_prev)[i]);
   172         (*_prev)[(*_next)[i]] = (*_prev)[i];
   173       } else {
   173       } else {
   174         _last[bucket] = (*_prev)[i];
   174         _last[bucket] = (*_prev)[i];
   175       }
   175       }
   176       //lace
   176       //lace
   177       _next->set(i, _first[bucket]);
   177       (*_next)[i] = _first[bucket];
   178       _prev->set(_first[bucket], i);
   178       (*_prev)[_first[bucket]] = i;
   179       _prev->set(i, INVALID);
   179       (*_prev)[i] = INVALID;
   180       _first[bucket] = i;
   180       _first[bucket] = i;
   181     }
   181     }
   182 
   182 
   183     void deactivate(const Node& i) {
   183     void deactivate(const Node& i) {
   184       _active->set(i, false);
   184       (*_active)[i] = false;
   185       int bucket = (*_bucket)[i];
   185       int bucket = (*_bucket)[i];
   186 
   186 
   187       if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return;
   187       if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return;
   188 
   188 
   189       //unlace
   189       //unlace
   190       _prev->set((*_next)[i], (*_prev)[i]);
   190       (*_prev)[(*_next)[i]] = (*_prev)[i];
   191       if ((*_prev)[i] != INVALID) {
   191       if ((*_prev)[i] != INVALID) {
   192         _next->set((*_prev)[i], (*_next)[i]);
   192         (*_next)[(*_prev)[i]] = (*_next)[i];
   193       } else {
   193       } else {
   194         _first[bucket] = (*_next)[i];
   194         _first[bucket] = (*_next)[i];
   195       }
   195       }
   196       //lace
   196       //lace
   197       _prev->set(i, _last[bucket]);
   197       (*_prev)[i] = _last[bucket];
   198       _next->set(_last[bucket], i);
   198       (*_next)[_last[bucket]] = i;
   199       _next->set(i, INVALID);
   199       (*_next)[i] = INVALID;
   200       _last[bucket] = i;
   200       _last[bucket] = i;
   201     }
   201     }
   202 
   202 
   203     void addItem(const Node& i, int bucket) {
   203     void addItem(const Node& i, int bucket) {
   204       (*_bucket)[i] = bucket;
   204       (*_bucket)[i] = bucket;
   205       if (_last[bucket] != INVALID) {
   205       if (_last[bucket] != INVALID) {
   206         _prev->set(i, _last[bucket]);
   206         (*_prev)[i] = _last[bucket];
   207         _next->set(_last[bucket], i);
   207         (*_next)[_last[bucket]] = i;
   208         _next->set(i, INVALID);
   208         (*_next)[i] = INVALID;
   209         _last[bucket] = i;
   209         _last[bucket] = i;
   210       } else {
   210       } else {
   211         _prev->set(i, INVALID);
   211         (*_prev)[i] = INVALID;
   212         _first[bucket] = i;
   212         _first[bucket] = i;
   213         _next->set(i, INVALID);
   213         (*_next)[i] = INVALID;
   214         _last[bucket] = i;
   214         _last[bucket] = i;
   215       }
   215       }
   216     }
   216     }
   217 
   217 
   218     void findMinCutOut() {
   218     void findMinCutOut() {
   219 
   219 
   220       for (NodeIt n(_graph); n != INVALID; ++n) {
   220       for (NodeIt n(_graph); n != INVALID; ++n) {
   221         _excess->set(n, 0);
   221         (*_excess)[n] = 0;
   222       }
   222       }
   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)[a] = 0;
   226       }
   226       }
   227 
   227 
   228       int bucket_num = 0;
   228       int bucket_num = 0;
   229       std::vector<Node> queue(_node_num);
   229       std::vector<Node> queue(_node_num);
   230       int qfirst = 0, qlast = 0, qsep = 0;
   230       int qfirst = 0, qlast = 0, qsep = 0;
   231 
   231 
   232       {
   232       {
   233         typename Digraph::template NodeMap<bool> reached(_graph, false);
   233         typename Digraph::template NodeMap<bool> reached(_graph, false);
   234 
   234 
   235         reached.set(_source, true);
   235         reached[_source] = true;
   236         bool first_set = true;
   236         bool first_set = true;
   237 
   237 
   238         for (NodeIt t(_graph); t != INVALID; ++t) {
   238         for (NodeIt t(_graph); t != INVALID; ++t) {
   239           if (reached[t]) continue;
   239           if (reached[t]) continue;
   240           _sets.push_front(std::list<int>());
   240           _sets.push_front(std::list<int>());
   241 
   241 
   242           queue[qlast++] = t;
   242           queue[qlast++] = t;
   243           reached.set(t, true);
   243           reached[t] = true;
   244 
   244 
   245           while (qfirst != qlast) {
   245           while (qfirst != qlast) {
   246             if (qsep == qfirst) {
   246             if (qsep == qfirst) {
   247               ++bucket_num;
   247               ++bucket_num;
   248               _sets.front().push_front(bucket_num);
   248               _sets.front().push_front(bucket_num);
   255             addItem(n, bucket_num);
   255             addItem(n, bucket_num);
   256 
   256 
   257             for (InArcIt a(_graph, n); a != INVALID; ++a) {
   257             for (InArcIt a(_graph, n); a != INVALID; ++a) {
   258               Node u = _graph.source(a);
   258               Node u = _graph.source(a);
   259               if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
   259               if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
   260                 reached.set(u, true);
   260                 reached[u] = true;
   261                 queue[qlast++] = u;
   261                 queue[qlast++] = u;
   262               }
   262               }
   263             }
   263             }
   264           }
   264           }
   265           first_set = false;
   265           first_set = false;
   266         }
   266         }
   267 
   267 
   268         ++bucket_num;
   268         ++bucket_num;
   269         _bucket->set(_source, 0);
   269         (*_bucket)[_source] = 0;
   270         _dormant[0] = true;
   270         _dormant[0] = true;
   271       }
   271       }
   272       _source_set->set(_source, true);
   272       (*_source_set)[_source] = true;
   273 
   273 
   274       Node target = _last[_sets.back().back()];
   274       Node target = _last[_sets.back().back()];
   275       {
   275       {
   276         for (OutArcIt a(_graph, _source); a != INVALID; ++a) {
   276         for (OutArcIt a(_graph, _source); a != INVALID; ++a) {
   277           if (_tolerance.positive((*_capacity)[a])) {
   277           if (_tolerance.positive((*_capacity)[a])) {
   278             Node u = _graph.target(a);
   278             Node u = _graph.target(a);
   279             _flow->set(a, (*_capacity)[a]);
   279             (*_flow)[a] = (*_capacity)[a];
   280             _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
   280             (*_excess)[u] += (*_capacity)[a];
   281             if (!(*_active)[u] && u != _source) {
   281             if (!(*_active)[u] && u != _source) {
   282               activate(u);
   282               activate(u);
   283             }
   283             }
   284           }
   284           }
   285         }
   285         }
   316             if ((*_bucket)[v] == under_bucket) {
   316             if ((*_bucket)[v] == under_bucket) {
   317               if (!(*_active)[v] && v != target) {
   317               if (!(*_active)[v] && v != target) {
   318                 activate(v);
   318                 activate(v);
   319               }
   319               }
   320               if (!_tolerance.less(rem, excess)) {
   320               if (!_tolerance.less(rem, excess)) {
   321                 _flow->set(a, (*_flow)[a] + excess);
   321                 (*_flow)[a] += excess;
   322                 _excess->set(v, (*_excess)[v] + excess);
   322                 (*_excess)[v] += excess;
   323                 excess = 0;
   323                 excess = 0;
   324                 goto no_more_push;
   324                 goto no_more_push;
   325               } else {
   325               } else {
   326                 excess -= rem;
   326                 excess -= rem;
   327                 _excess->set(v, (*_excess)[v] + rem);
   327                 (*_excess)[v] += rem;
   328                 _flow->set(a, (*_capacity)[a]);
   328                 (*_flow)[a] = (*_capacity)[a];
   329               }
   329               }
   330             } else if (next_bucket > (*_bucket)[v]) {
   330             } else if (next_bucket > (*_bucket)[v]) {
   331               next_bucket = (*_bucket)[v];
   331               next_bucket = (*_bucket)[v];
   332             }
   332             }
   333           }
   333           }
   340             if ((*_bucket)[v] == under_bucket) {
   340             if ((*_bucket)[v] == under_bucket) {
   341               if (!(*_active)[v] && v != target) {
   341               if (!(*_active)[v] && v != target) {
   342                 activate(v);
   342                 activate(v);
   343               }
   343               }
   344               if (!_tolerance.less(rem, excess)) {
   344               if (!_tolerance.less(rem, excess)) {
   345                 _flow->set(a, (*_flow)[a] - excess);
   345                 (*_flow)[a] -= excess;
   346                 _excess->set(v, (*_excess)[v] + excess);
   346                 (*_excess)[v] += excess;
   347                 excess = 0;
   347                 excess = 0;
   348                 goto no_more_push;
   348                 goto no_more_push;
   349               } else {
   349               } else {
   350                 excess -= rem;
   350                 excess -= rem;
   351                 _excess->set(v, (*_excess)[v] + rem);
   351                 (*_excess)[v] += rem;
   352                 _flow->set(a, 0);
   352                 (*_flow)[a] = 0;
   353               }
   353               }
   354             } else if (next_bucket > (*_bucket)[v]) {
   354             } else if (next_bucket > (*_bucket)[v]) {
   355               next_bucket = (*_bucket)[v];
   355               next_bucket = (*_bucket)[v];
   356             }
   356             }
   357           }
   357           }
   358 
   358 
   359         no_more_push:
   359         no_more_push:
   360 
   360 
   361           _excess->set(n, excess);
   361           (*_excess)[n] = excess;
   362 
   362 
   363           if (excess != 0) {
   363           if (excess != 0) {
   364             if ((*_next)[n] == INVALID) {
   364             if ((*_next)[n] == INVALID) {
   365               typename std::list<std::list<int> >::iterator new_set =
   365               typename std::list<std::list<int> >::iterator new_set =
   366                 _sets.insert(--_sets.end(), std::list<int>());
   366                 _sets.insert(--_sets.end(), std::list<int>());
   374                      !(*_active)[_first[*_highest]]) {
   374                      !(*_active)[_first[*_highest]]) {
   375                 ++_highest;
   375                 ++_highest;
   376               }
   376               }
   377             } else if (next_bucket == _node_num) {
   377             } else if (next_bucket == _node_num) {
   378               _first[(*_bucket)[n]] = (*_next)[n];
   378               _first[(*_bucket)[n]] = (*_next)[n];
   379               _prev->set((*_next)[n], INVALID);
   379               (*_prev)[(*_next)[n]] = INVALID;
   380 
   380 
   381               std::list<std::list<int> >::iterator new_set =
   381               std::list<std::list<int> >::iterator new_set =
   382                 _sets.insert(--_sets.end(), std::list<int>());
   382                 _sets.insert(--_sets.end(), std::list<int>());
   383 
   383 
   384               new_set->push_front(bucket_num);
   384               new_set->push_front(bucket_num);
   385               _bucket->set(n, bucket_num);
   385               (*_bucket)[n] = bucket_num;
   386               _first[bucket_num] = _last[bucket_num] = n;
   386               _first[bucket_num] = _last[bucket_num] = n;
   387               _next->set(n, INVALID);
   387               (*_next)[n] = INVALID;
   388               _prev->set(n, INVALID);
   388               (*_prev)[n] = INVALID;
   389               _dormant[bucket_num] = true;
   389               _dormant[bucket_num] = true;
   390               ++bucket_num;
   390               ++bucket_num;
   391 
   391 
   392               while (_highest != _sets.back().end() &&
   392               while (_highest != _sets.back().end() &&
   393                      !(*_active)[_first[*_highest]]) {
   393                      !(*_active)[_first[*_highest]]) {
   394                 ++_highest;
   394                 ++_highest;
   395               }
   395               }
   396             } else {
   396             } else {
   397               _first[*_highest] = (*_next)[n];
   397               _first[*_highest] = (*_next)[n];
   398               _prev->set((*_next)[n], INVALID);
   398               (*_prev)[(*_next)[n]] = INVALID;
   399 
   399 
   400               while (next_bucket != *_highest) {
   400               while (next_bucket != *_highest) {
   401                 --_highest;
   401                 --_highest;
   402               }
   402               }
   403 
   403 
   407                 _first[bucket_num] = _last[bucket_num] = INVALID;
   407                 _first[bucket_num] = _last[bucket_num] = INVALID;
   408                 ++bucket_num;
   408                 ++bucket_num;
   409               }
   409               }
   410               --_highest;
   410               --_highest;
   411 
   411 
   412               _bucket->set(n, *_highest);
   412               (*_bucket)[n] = *_highest;
   413               _next->set(n, _first[*_highest]);
   413               (*_next)[n] = _first[*_highest];
   414               if (_first[*_highest] != INVALID) {
   414               if (_first[*_highest] != INVALID) {
   415                 _prev->set(_first[*_highest], n);
   415                 (*_prev)[_first[*_highest]] = n;
   416               } else {
   416               } else {
   417                 _last[*_highest] = n;
   417                 _last[*_highest] = n;
   418               }
   418               }
   419               _first[*_highest] = n;
   419               _first[*_highest] = n;
   420             }
   420             }
   432         }
   432         }
   433 
   433 
   434         if ((*_excess)[target] < _min_cut) {
   434         if ((*_excess)[target] < _min_cut) {
   435           _min_cut = (*_excess)[target];
   435           _min_cut = (*_excess)[target];
   436           for (NodeIt i(_graph); i != INVALID; ++i) {
   436           for (NodeIt i(_graph); i != INVALID; ++i) {
   437             _min_cut_map->set(i, true);
   437             (*_min_cut_map)[i] = true;
   438           }
   438           }
   439           for (std::list<int>::iterator it = _sets.back().begin();
   439           for (std::list<int>::iterator it = _sets.back().begin();
   440                it != _sets.back().end(); ++it) {
   440                it != _sets.back().end(); ++it) {
   441             Node n = _first[*it];
   441             Node n = _first[*it];
   442             while (n != INVALID) {
   442             while (n != INVALID) {
   443               _min_cut_map->set(n, false);
   443               (*_min_cut_map)[n] = false;
   444               n = (*_next)[n];
   444               n = (*_next)[n];
   445             }
   445             }
   446           }
   446           }
   447         }
   447         }
   448 
   448 
   451           if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
   451           if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
   452             if ((*_next)[target] == INVALID) {
   452             if ((*_next)[target] == INVALID) {
   453               _last[(*_bucket)[target]] = (*_prev)[target];
   453               _last[(*_bucket)[target]] = (*_prev)[target];
   454               new_target = (*_prev)[target];
   454               new_target = (*_prev)[target];
   455             } else {
   455             } else {
   456               _prev->set((*_next)[target], (*_prev)[target]);
   456               (*_prev)[(*_next)[target]] = (*_prev)[target];
   457               new_target = (*_next)[target];
   457               new_target = (*_next)[target];
   458             }
   458             }
   459             if ((*_prev)[target] == INVALID) {
   459             if ((*_prev)[target] == INVALID) {
   460               _first[(*_bucket)[target]] = (*_next)[target];
   460               _first[(*_bucket)[target]] = (*_next)[target];
   461             } else {
   461             } else {
   462               _next->set((*_prev)[target], (*_next)[target]);
   462               (*_next)[(*_prev)[target]] = (*_next)[target];
   463             }
   463             }
   464           } else {
   464           } else {
   465             _sets.back().pop_back();
   465             _sets.back().pop_back();
   466             if (_sets.back().empty()) {
   466             if (_sets.back().empty()) {
   467               _sets.pop_back();
   467               _sets.pop_back();
   473               }
   473               }
   474             }
   474             }
   475             new_target = _last[_sets.back().back()];
   475             new_target = _last[_sets.back().back()];
   476           }
   476           }
   477 
   477 
   478           _bucket->set(target, 0);
   478           (*_bucket)[target] = 0;
   479 
   479 
   480           _source_set->set(target, true);
   480           (*_source_set)[target] = true;
   481           for (OutArcIt a(_graph, target); a != INVALID; ++a) {
   481           for (OutArcIt a(_graph, target); a != INVALID; ++a) {
   482             Value rem = (*_capacity)[a] - (*_flow)[a];
   482             Value rem = (*_capacity)[a] - (*_flow)[a];
   483             if (!_tolerance.positive(rem)) continue;
   483             if (!_tolerance.positive(rem)) continue;
   484             Node v = _graph.target(a);
   484             Node v = _graph.target(a);
   485             if (!(*_active)[v] && !(*_source_set)[v]) {
   485             if (!(*_active)[v] && !(*_source_set)[v]) {
   486               activate(v);
   486               activate(v);
   487             }
   487             }
   488             _excess->set(v, (*_excess)[v] + rem);
   488             (*_excess)[v] += rem;
   489             _flow->set(a, (*_capacity)[a]);
   489             (*_flow)[a] = (*_capacity)[a];
   490           }
   490           }
   491 
   491 
   492           for (InArcIt a(_graph, target); a != INVALID; ++a) {
   492           for (InArcIt a(_graph, target); a != INVALID; ++a) {
   493             Value rem = (*_flow)[a];
   493             Value rem = (*_flow)[a];
   494             if (!_tolerance.positive(rem)) continue;
   494             if (!_tolerance.positive(rem)) continue;
   495             Node v = _graph.source(a);
   495             Node v = _graph.source(a);
   496             if (!(*_active)[v] && !(*_source_set)[v]) {
   496             if (!(*_active)[v] && !(*_source_set)[v]) {
   497               activate(v);
   497               activate(v);
   498             }
   498             }
   499             _excess->set(v, (*_excess)[v] + rem);
   499             (*_excess)[v] += rem;
   500             _flow->set(a, 0);
   500             (*_flow)[a] = 0;
   501           }
   501           }
   502 
   502 
   503           target = new_target;
   503           target = new_target;
   504           if ((*_active)[target]) {
   504           if ((*_active)[target]) {
   505             deactivate(target);
   505             deactivate(target);
   515     }
   515     }
   516 
   516 
   517     void findMinCutIn() {
   517     void findMinCutIn() {
   518 
   518 
   519       for (NodeIt n(_graph); n != INVALID; ++n) {
   519       for (NodeIt n(_graph); n != INVALID; ++n) {
   520         _excess->set(n, 0);
   520         (*_excess)[n] = 0;
   521       }
   521       }
   522 
   522 
   523       for (ArcIt a(_graph); a != INVALID; ++a) {
   523       for (ArcIt a(_graph); a != INVALID; ++a) {
   524         _flow->set(a, 0);
   524         (*_flow)[a] = 0;
   525       }
   525       }
   526 
   526 
   527       int bucket_num = 0;
   527       int bucket_num = 0;
   528       std::vector<Node> queue(_node_num);
   528       std::vector<Node> queue(_node_num);
   529       int qfirst = 0, qlast = 0, qsep = 0;
   529       int qfirst = 0, qlast = 0, qsep = 0;
   530 
   530 
   531       {
   531       {
   532         typename Digraph::template NodeMap<bool> reached(_graph, false);
   532         typename Digraph::template NodeMap<bool> reached(_graph, false);
   533 
   533 
   534         reached.set(_source, true);
   534         reached[_source] = true;
   535 
   535 
   536         bool first_set = true;
   536         bool first_set = true;
   537 
   537 
   538         for (NodeIt t(_graph); t != INVALID; ++t) {
   538         for (NodeIt t(_graph); t != INVALID; ++t) {
   539           if (reached[t]) continue;
   539           if (reached[t]) continue;
   540           _sets.push_front(std::list<int>());
   540           _sets.push_front(std::list<int>());
   541 
   541 
   542           queue[qlast++] = t;
   542           queue[qlast++] = t;
   543           reached.set(t, true);
   543           reached[t] = true;
   544 
   544 
   545           while (qfirst != qlast) {
   545           while (qfirst != qlast) {
   546             if (qsep == qfirst) {
   546             if (qsep == qfirst) {
   547               ++bucket_num;
   547               ++bucket_num;
   548               _sets.front().push_front(bucket_num);
   548               _sets.front().push_front(bucket_num);
   555             addItem(n, bucket_num);
   555             addItem(n, bucket_num);
   556 
   556 
   557             for (OutArcIt a(_graph, n); a != INVALID; ++a) {
   557             for (OutArcIt a(_graph, n); a != INVALID; ++a) {
   558               Node u = _graph.target(a);
   558               Node u = _graph.target(a);
   559               if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
   559               if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
   560                 reached.set(u, true);
   560                 reached[u] = true;
   561                 queue[qlast++] = u;
   561                 queue[qlast++] = u;
   562               }
   562               }
   563             }
   563             }
   564           }
   564           }
   565           first_set = false;
   565           first_set = false;
   566         }
   566         }
   567 
   567 
   568         ++bucket_num;
   568         ++bucket_num;
   569         _bucket->set(_source, 0);
   569         (*_bucket)[_source] = 0;
   570         _dormant[0] = true;
   570         _dormant[0] = true;
   571       }
   571       }
   572       _source_set->set(_source, true);
   572       (*_source_set)[_source] = true;
   573 
   573 
   574       Node target = _last[_sets.back().back()];
   574       Node target = _last[_sets.back().back()];
   575       {
   575       {
   576         for (InArcIt a(_graph, _source); a != INVALID; ++a) {
   576         for (InArcIt a(_graph, _source); a != INVALID; ++a) {
   577           if (_tolerance.positive((*_capacity)[a])) {
   577           if (_tolerance.positive((*_capacity)[a])) {
   578             Node u = _graph.source(a);
   578             Node u = _graph.source(a);
   579             _flow->set(a, (*_capacity)[a]);
   579             (*_flow)[a] = (*_capacity)[a];
   580             _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
   580             (*_excess)[u] += (*_capacity)[a];
   581             if (!(*_active)[u] && u != _source) {
   581             if (!(*_active)[u] && u != _source) {
   582               activate(u);
   582               activate(u);
   583             }
   583             }
   584           }
   584           }
   585         }
   585         }
   616             if ((*_bucket)[v] == under_bucket) {
   616             if ((*_bucket)[v] == under_bucket) {
   617               if (!(*_active)[v] && v != target) {
   617               if (!(*_active)[v] && v != target) {
   618                 activate(v);
   618                 activate(v);
   619               }
   619               }
   620               if (!_tolerance.less(rem, excess)) {
   620               if (!_tolerance.less(rem, excess)) {
   621                 _flow->set(a, (*_flow)[a] + excess);
   621                 (*_flow)[a] += excess;
   622                 _excess->set(v, (*_excess)[v] + excess);
   622                 (*_excess)[v] += excess;
   623                 excess = 0;
   623                 excess = 0;
   624                 goto no_more_push;
   624                 goto no_more_push;
   625               } else {
   625               } else {
   626                 excess -= rem;
   626                 excess -= rem;
   627                 _excess->set(v, (*_excess)[v] + rem);
   627                 (*_excess)[v] += rem;
   628                 _flow->set(a, (*_capacity)[a]);
   628                 (*_flow)[a] = (*_capacity)[a];
   629               }
   629               }
   630             } else if (next_bucket > (*_bucket)[v]) {
   630             } else if (next_bucket > (*_bucket)[v]) {
   631               next_bucket = (*_bucket)[v];
   631               next_bucket = (*_bucket)[v];
   632             }
   632             }
   633           }
   633           }
   640             if ((*_bucket)[v] == under_bucket) {
   640             if ((*_bucket)[v] == under_bucket) {
   641               if (!(*_active)[v] && v != target) {
   641               if (!(*_active)[v] && v != target) {
   642                 activate(v);
   642                 activate(v);
   643               }
   643               }
   644               if (!_tolerance.less(rem, excess)) {
   644               if (!_tolerance.less(rem, excess)) {
   645                 _flow->set(a, (*_flow)[a] - excess);
   645                 (*_flow)[a] -= excess;
   646                 _excess->set(v, (*_excess)[v] + excess);
   646                 (*_excess)[v] += excess;
   647                 excess = 0;
   647                 excess = 0;
   648                 goto no_more_push;
   648                 goto no_more_push;
   649               } else {
   649               } else {
   650                 excess -= rem;
   650                 excess -= rem;
   651                 _excess->set(v, (*_excess)[v] + rem);
   651                 (*_excess)[v] += rem;
   652                 _flow->set(a, 0);
   652                 (*_flow)[a] = 0;
   653               }
   653               }
   654             } else if (next_bucket > (*_bucket)[v]) {
   654             } else if (next_bucket > (*_bucket)[v]) {
   655               next_bucket = (*_bucket)[v];
   655               next_bucket = (*_bucket)[v];
   656             }
   656             }
   657           }
   657           }
   658 
   658 
   659         no_more_push:
   659         no_more_push:
   660 
   660 
   661           _excess->set(n, excess);
   661           (*_excess)[n] = excess;
   662 
   662 
   663           if (excess != 0) {
   663           if (excess != 0) {
   664             if ((*_next)[n] == INVALID) {
   664             if ((*_next)[n] == INVALID) {
   665               typename std::list<std::list<int> >::iterator new_set =
   665               typename std::list<std::list<int> >::iterator new_set =
   666                 _sets.insert(--_sets.end(), std::list<int>());
   666                 _sets.insert(--_sets.end(), std::list<int>());
   674                      !(*_active)[_first[*_highest]]) {
   674                      !(*_active)[_first[*_highest]]) {
   675                 ++_highest;
   675                 ++_highest;
   676               }
   676               }
   677             } else if (next_bucket == _node_num) {
   677             } else if (next_bucket == _node_num) {
   678               _first[(*_bucket)[n]] = (*_next)[n];
   678               _first[(*_bucket)[n]] = (*_next)[n];
   679               _prev->set((*_next)[n], INVALID);
   679               (*_prev)[(*_next)[n]] = INVALID;
   680 
   680 
   681               std::list<std::list<int> >::iterator new_set =
   681               std::list<std::list<int> >::iterator new_set =
   682                 _sets.insert(--_sets.end(), std::list<int>());
   682                 _sets.insert(--_sets.end(), std::list<int>());
   683 
   683 
   684               new_set->push_front(bucket_num);
   684               new_set->push_front(bucket_num);
   685               _bucket->set(n, bucket_num);
   685               (*_bucket)[n] = bucket_num;
   686               _first[bucket_num] = _last[bucket_num] = n;
   686               _first[bucket_num] = _last[bucket_num] = n;
   687               _next->set(n, INVALID);
   687               (*_next)[n] = INVALID;
   688               _prev->set(n, INVALID);
   688               (*_prev)[n] = INVALID;
   689               _dormant[bucket_num] = true;
   689               _dormant[bucket_num] = true;
   690               ++bucket_num;
   690               ++bucket_num;
   691 
   691 
   692               while (_highest != _sets.back().end() &&
   692               while (_highest != _sets.back().end() &&
   693                      !(*_active)[_first[*_highest]]) {
   693                      !(*_active)[_first[*_highest]]) {
   694                 ++_highest;
   694                 ++_highest;
   695               }
   695               }
   696             } else {
   696             } else {
   697               _first[*_highest] = (*_next)[n];
   697               _first[*_highest] = (*_next)[n];
   698               _prev->set((*_next)[n], INVALID);
   698               (*_prev)[(*_next)[n]] = INVALID;
   699 
   699 
   700               while (next_bucket != *_highest) {
   700               while (next_bucket != *_highest) {
   701                 --_highest;
   701                 --_highest;
   702               }
   702               }
   703               if (_highest == _sets.back().begin()) {
   703               if (_highest == _sets.back().begin()) {
   706                 _first[bucket_num] = _last[bucket_num] = INVALID;
   706                 _first[bucket_num] = _last[bucket_num] = INVALID;
   707                 ++bucket_num;
   707                 ++bucket_num;
   708               }
   708               }
   709               --_highest;
   709               --_highest;
   710 
   710 
   711               _bucket->set(n, *_highest);
   711               (*_bucket)[n] = *_highest;
   712               _next->set(n, _first[*_highest]);
   712               (*_next)[n] = _first[*_highest];
   713               if (_first[*_highest] != INVALID) {
   713               if (_first[*_highest] != INVALID) {
   714                 _prev->set(_first[*_highest], n);
   714                 (*_prev)[_first[*_highest]] = n;
   715               } else {
   715               } else {
   716                 _last[*_highest] = n;
   716                 _last[*_highest] = n;
   717               }
   717               }
   718               _first[*_highest] = n;
   718               _first[*_highest] = n;
   719             }
   719             }
   731         }
   731         }
   732 
   732 
   733         if ((*_excess)[target] < _min_cut) {
   733         if ((*_excess)[target] < _min_cut) {
   734           _min_cut = (*_excess)[target];
   734           _min_cut = (*_excess)[target];
   735           for (NodeIt i(_graph); i != INVALID; ++i) {
   735           for (NodeIt i(_graph); i != INVALID; ++i) {
   736             _min_cut_map->set(i, false);
   736             (*_min_cut_map)[i] = false;
   737           }
   737           }
   738           for (std::list<int>::iterator it = _sets.back().begin();
   738           for (std::list<int>::iterator it = _sets.back().begin();
   739                it != _sets.back().end(); ++it) {
   739                it != _sets.back().end(); ++it) {
   740             Node n = _first[*it];
   740             Node n = _first[*it];
   741             while (n != INVALID) {
   741             while (n != INVALID) {
   742               _min_cut_map->set(n, true);
   742               (*_min_cut_map)[n] = true;
   743               n = (*_next)[n];
   743               n = (*_next)[n];
   744             }
   744             }
   745           }
   745           }
   746         }
   746         }
   747 
   747 
   750           if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
   750           if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
   751             if ((*_next)[target] == INVALID) {
   751             if ((*_next)[target] == INVALID) {
   752               _last[(*_bucket)[target]] = (*_prev)[target];
   752               _last[(*_bucket)[target]] = (*_prev)[target];
   753               new_target = (*_prev)[target];
   753               new_target = (*_prev)[target];
   754             } else {
   754             } else {
   755               _prev->set((*_next)[target], (*_prev)[target]);
   755               (*_prev)[(*_next)[target]] = (*_prev)[target];
   756               new_target = (*_next)[target];
   756               new_target = (*_next)[target];
   757             }
   757             }
   758             if ((*_prev)[target] == INVALID) {
   758             if ((*_prev)[target] == INVALID) {
   759               _first[(*_bucket)[target]] = (*_next)[target];
   759               _first[(*_bucket)[target]] = (*_next)[target];
   760             } else {
   760             } else {
   761               _next->set((*_prev)[target], (*_next)[target]);
   761               (*_next)[(*_prev)[target]] = (*_next)[target];
   762             }
   762             }
   763           } else {
   763           } else {
   764             _sets.back().pop_back();
   764             _sets.back().pop_back();
   765             if (_sets.back().empty()) {
   765             if (_sets.back().empty()) {
   766               _sets.pop_back();
   766               _sets.pop_back();
   772               }
   772               }
   773             }
   773             }
   774             new_target = _last[_sets.back().back()];
   774             new_target = _last[_sets.back().back()];
   775           }
   775           }
   776 
   776 
   777           _bucket->set(target, 0);
   777           (*_bucket)[target] = 0;
   778 
   778 
   779           _source_set->set(target, true);
   779           (*_source_set)[target] = true;
   780           for (InArcIt a(_graph, target); a != INVALID; ++a) {
   780           for (InArcIt a(_graph, target); a != INVALID; ++a) {
   781             Value rem = (*_capacity)[a] - (*_flow)[a];
   781             Value rem = (*_capacity)[a] - (*_flow)[a];
   782             if (!_tolerance.positive(rem)) continue;
   782             if (!_tolerance.positive(rem)) continue;
   783             Node v = _graph.source(a);
   783             Node v = _graph.source(a);
   784             if (!(*_active)[v] && !(*_source_set)[v]) {
   784             if (!(*_active)[v] && !(*_source_set)[v]) {
   785               activate(v);
   785               activate(v);
   786             }
   786             }
   787             _excess->set(v, (*_excess)[v] + rem);
   787             (*_excess)[v] += rem;
   788             _flow->set(a, (*_capacity)[a]);
   788             (*_flow)[a] = (*_capacity)[a];
   789           }
   789           }
   790 
   790 
   791           for (OutArcIt a(_graph, target); a != INVALID; ++a) {
   791           for (OutArcIt a(_graph, target); a != INVALID; ++a) {
   792             Value rem = (*_flow)[a];
   792             Value rem = (*_flow)[a];
   793             if (!_tolerance.positive(rem)) continue;
   793             if (!_tolerance.positive(rem)) continue;
   794             Node v = _graph.target(a);
   794             Node v = _graph.target(a);
   795             if (!(*_active)[v] && !(*_source_set)[v]) {
   795             if (!(*_active)[v] && !(*_source_set)[v]) {
   796               activate(v);
   796               activate(v);
   797             }
   797             }
   798             _excess->set(v, (*_excess)[v] + rem);
   798             (*_excess)[v] += rem;
   799             _flow->set(a, 0);
   799             (*_flow)[a] = 0;
   800           }
   800           }
   801 
   801 
   802           target = new_target;
   802           target = new_target;
   803           if ((*_active)[target]) {
   803           if ((*_active)[target]) {
   804             deactivate(target);
   804             deactivate(target);