lemon/preflow.h
changeset 594 d657c71db7db
parent 559 c5fd2d996909
child 611 85cb3aa71cce
equal deleted inserted replaced
8:8d3d731b597a 9:9477044392ce
   402     void init() {
   402     void init() {
   403       createStructures();
   403       createStructures();
   404 
   404 
   405       _phase = true;
   405       _phase = true;
   406       for (NodeIt n(_graph); n != INVALID; ++n) {
   406       for (NodeIt n(_graph); n != INVALID; ++n) {
   407         _excess->set(n, 0);
   407         (*_excess)[n] = 0;
   408       }
   408       }
   409 
   409 
   410       for (ArcIt e(_graph); e != INVALID; ++e) {
   410       for (ArcIt e(_graph); e != INVALID; ++e) {
   411         _flow->set(e, 0);
   411         _flow->set(e, 0);
   412       }
   412       }
   415 
   415 
   416       _level->initStart();
   416       _level->initStart();
   417       _level->initAddItem(_target);
   417       _level->initAddItem(_target);
   418 
   418 
   419       std::vector<Node> queue;
   419       std::vector<Node> queue;
   420       reached.set(_source, true);
   420       reached[_source] = true;
   421 
   421 
   422       queue.push_back(_target);
   422       queue.push_back(_target);
   423       reached.set(_target, true);
   423       reached[_target] = true;
   424       while (!queue.empty()) {
   424       while (!queue.empty()) {
   425         _level->initNewLevel();
   425         _level->initNewLevel();
   426         std::vector<Node> nqueue;
   426         std::vector<Node> nqueue;
   427         for (int i = 0; i < int(queue.size()); ++i) {
   427         for (int i = 0; i < int(queue.size()); ++i) {
   428           Node n = queue[i];
   428           Node n = queue[i];
   429           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   429           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   430             Node u = _graph.source(e);
   430             Node u = _graph.source(e);
   431             if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
   431             if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
   432               reached.set(u, true);
   432               reached[u] = true;
   433               _level->initAddItem(u);
   433               _level->initAddItem(u);
   434               nqueue.push_back(u);
   434               nqueue.push_back(u);
   435             }
   435             }
   436           }
   436           }
   437         }
   437         }
   442       for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
   442       for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
   443         if (_tolerance.positive((*_capacity)[e])) {
   443         if (_tolerance.positive((*_capacity)[e])) {
   444           Node u = _graph.target(e);
   444           Node u = _graph.target(e);
   445           if ((*_level)[u] == _level->maxLevel()) continue;
   445           if ((*_level)[u] == _level->maxLevel()) continue;
   446           _flow->set(e, (*_capacity)[e]);
   446           _flow->set(e, (*_capacity)[e]);
   447           _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
   447           (*_excess)[u] += (*_capacity)[e];
   448           if (u != _target && !_level->active(u)) {
   448           if (u != _target && !_level->active(u)) {
   449             _level->activate(u);
   449             _level->activate(u);
   450           }
   450           }
   451         }
   451         }
   452       }
   452       }
   476         }
   476         }
   477         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   477         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   478           excess -= (*_flow)[e];
   478           excess -= (*_flow)[e];
   479         }
   479         }
   480         if (excess < 0 && n != _source) return false;
   480         if (excess < 0 && n != _source) return false;
   481         _excess->set(n, excess);
   481         (*_excess)[n] = excess;
   482       }
   482       }
   483 
   483 
   484       typename Digraph::template NodeMap<bool> reached(_graph, false);
   484       typename Digraph::template NodeMap<bool> reached(_graph, false);
   485 
   485 
   486       _level->initStart();
   486       _level->initStart();
   487       _level->initAddItem(_target);
   487       _level->initAddItem(_target);
   488 
   488 
   489       std::vector<Node> queue;
   489       std::vector<Node> queue;
   490       reached.set(_source, true);
   490       reached[_source] = true;
   491 
   491 
   492       queue.push_back(_target);
   492       queue.push_back(_target);
   493       reached.set(_target, true);
   493       reached[_target] = true;
   494       while (!queue.empty()) {
   494       while (!queue.empty()) {
   495         _level->initNewLevel();
   495         _level->initNewLevel();
   496         std::vector<Node> nqueue;
   496         std::vector<Node> nqueue;
   497         for (int i = 0; i < int(queue.size()); ++i) {
   497         for (int i = 0; i < int(queue.size()); ++i) {
   498           Node n = queue[i];
   498           Node n = queue[i];
   499           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   499           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   500             Node u = _graph.source(e);
   500             Node u = _graph.source(e);
   501             if (!reached[u] &&
   501             if (!reached[u] &&
   502                 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
   502                 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
   503               reached.set(u, true);
   503               reached[u] = true;
   504               _level->initAddItem(u);
   504               _level->initAddItem(u);
   505               nqueue.push_back(u);
   505               nqueue.push_back(u);
   506             }
   506             }
   507           }
   507           }
   508           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   508           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   509             Node v = _graph.target(e);
   509             Node v = _graph.target(e);
   510             if (!reached[v] && _tolerance.positive((*_flow)[e])) {
   510             if (!reached[v] && _tolerance.positive((*_flow)[e])) {
   511               reached.set(v, true);
   511               reached[v] = true;
   512               _level->initAddItem(v);
   512               _level->initAddItem(v);
   513               nqueue.push_back(v);
   513               nqueue.push_back(v);
   514             }
   514             }
   515           }
   515           }
   516         }
   516         }
   522         Value rem = (*_capacity)[e] - (*_flow)[e];
   522         Value rem = (*_capacity)[e] - (*_flow)[e];
   523         if (_tolerance.positive(rem)) {
   523         if (_tolerance.positive(rem)) {
   524           Node u = _graph.target(e);
   524           Node u = _graph.target(e);
   525           if ((*_level)[u] == _level->maxLevel()) continue;
   525           if ((*_level)[u] == _level->maxLevel()) continue;
   526           _flow->set(e, (*_capacity)[e]);
   526           _flow->set(e, (*_capacity)[e]);
   527           _excess->set(u, (*_excess)[u] + rem);
   527           (*_excess)[u] += rem;
   528           if (u != _target && !_level->active(u)) {
   528           if (u != _target && !_level->active(u)) {
   529             _level->activate(u);
   529             _level->activate(u);
   530           }
   530           }
   531         }
   531         }
   532       }
   532       }
   534         Value rem = (*_flow)[e];
   534         Value rem = (*_flow)[e];
   535         if (_tolerance.positive(rem)) {
   535         if (_tolerance.positive(rem)) {
   536           Node v = _graph.source(e);
   536           Node v = _graph.source(e);
   537           if ((*_level)[v] == _level->maxLevel()) continue;
   537           if ((*_level)[v] == _level->maxLevel()) continue;
   538           _flow->set(e, 0);
   538           _flow->set(e, 0);
   539           _excess->set(v, (*_excess)[v] + rem);
   539           (*_excess)[v] += rem;
   540           if (v != _target && !_level->active(v)) {
   540           if (v != _target && !_level->active(v)) {
   541             _level->activate(v);
   541             _level->activate(v);
   542           }
   542           }
   543         }
   543         }
   544       }
   544       }
   575               if (!_level->active(v) && v != _target) {
   575               if (!_level->active(v) && v != _target) {
   576                 _level->activate(v);
   576                 _level->activate(v);
   577               }
   577               }
   578               if (!_tolerance.less(rem, excess)) {
   578               if (!_tolerance.less(rem, excess)) {
   579                 _flow->set(e, (*_flow)[e] + excess);
   579                 _flow->set(e, (*_flow)[e] + excess);
   580                 _excess->set(v, (*_excess)[v] + excess);
   580                 (*_excess)[v] += excess;
   581                 excess = 0;
   581                 excess = 0;
   582                 goto no_more_push_1;
   582                 goto no_more_push_1;
   583               } else {
   583               } else {
   584                 excess -= rem;
   584                 excess -= rem;
   585                 _excess->set(v, (*_excess)[v] + rem);
   585                 (*_excess)[v] += rem;
   586                 _flow->set(e, (*_capacity)[e]);
   586                 _flow->set(e, (*_capacity)[e]);
   587               }
   587               }
   588             } else if (new_level > (*_level)[v]) {
   588             } else if (new_level > (*_level)[v]) {
   589               new_level = (*_level)[v];
   589               new_level = (*_level)[v];
   590             }
   590             }
   598               if (!_level->active(v) && v != _target) {
   598               if (!_level->active(v) && v != _target) {
   599                 _level->activate(v);
   599                 _level->activate(v);
   600               }
   600               }
   601               if (!_tolerance.less(rem, excess)) {
   601               if (!_tolerance.less(rem, excess)) {
   602                 _flow->set(e, (*_flow)[e] - excess);
   602                 _flow->set(e, (*_flow)[e] - excess);
   603                 _excess->set(v, (*_excess)[v] + excess);
   603                 (*_excess)[v] += excess;
   604                 excess = 0;
   604                 excess = 0;
   605                 goto no_more_push_1;
   605                 goto no_more_push_1;
   606               } else {
   606               } else {
   607                 excess -= rem;
   607                 excess -= rem;
   608                 _excess->set(v, (*_excess)[v] + rem);
   608                 (*_excess)[v] += rem;
   609                 _flow->set(e, 0);
   609                 _flow->set(e, 0);
   610               }
   610               }
   611             } else if (new_level > (*_level)[v]) {
   611             } else if (new_level > (*_level)[v]) {
   612               new_level = (*_level)[v];
   612               new_level = (*_level)[v];
   613             }
   613             }
   614           }
   614           }
   615 
   615 
   616         no_more_push_1:
   616         no_more_push_1:
   617 
   617 
   618           _excess->set(n, excess);
   618           (*_excess)[n] = excess;
   619 
   619 
   620           if (excess != 0) {
   620           if (excess != 0) {
   621             if (new_level + 1 < _level->maxLevel()) {
   621             if (new_level + 1 < _level->maxLevel()) {
   622               _level->liftHighestActive(new_level + 1);
   622               _level->liftHighestActive(new_level + 1);
   623             } else {
   623             } else {
   648               if (!_level->active(v) && v != _target) {
   648               if (!_level->active(v) && v != _target) {
   649                 _level->activate(v);
   649                 _level->activate(v);
   650               }
   650               }
   651               if (!_tolerance.less(rem, excess)) {
   651               if (!_tolerance.less(rem, excess)) {
   652                 _flow->set(e, (*_flow)[e] + excess);
   652                 _flow->set(e, (*_flow)[e] + excess);
   653                 _excess->set(v, (*_excess)[v] + excess);
   653                 (*_excess)[v] += excess;
   654                 excess = 0;
   654                 excess = 0;
   655                 goto no_more_push_2;
   655                 goto no_more_push_2;
   656               } else {
   656               } else {
   657                 excess -= rem;
   657                 excess -= rem;
   658                 _excess->set(v, (*_excess)[v] + rem);
   658                 (*_excess)[v] += rem;
   659                 _flow->set(e, (*_capacity)[e]);
   659                 _flow->set(e, (*_capacity)[e]);
   660               }
   660               }
   661             } else if (new_level > (*_level)[v]) {
   661             } else if (new_level > (*_level)[v]) {
   662               new_level = (*_level)[v];
   662               new_level = (*_level)[v];
   663             }
   663             }
   671               if (!_level->active(v) && v != _target) {
   671               if (!_level->active(v) && v != _target) {
   672                 _level->activate(v);
   672                 _level->activate(v);
   673               }
   673               }
   674               if (!_tolerance.less(rem, excess)) {
   674               if (!_tolerance.less(rem, excess)) {
   675                 _flow->set(e, (*_flow)[e] - excess);
   675                 _flow->set(e, (*_flow)[e] - excess);
   676                 _excess->set(v, (*_excess)[v] + excess);
   676                 (*_excess)[v] += excess;
   677                 excess = 0;
   677                 excess = 0;
   678                 goto no_more_push_2;
   678                 goto no_more_push_2;
   679               } else {
   679               } else {
   680                 excess -= rem;
   680                 excess -= rem;
   681                 _excess->set(v, (*_excess)[v] + rem);
   681                 (*_excess)[v] += rem;
   682                 _flow->set(e, 0);
   682                 _flow->set(e, 0);
   683               }
   683               }
   684             } else if (new_level > (*_level)[v]) {
   684             } else if (new_level > (*_level)[v]) {
   685               new_level = (*_level)[v];
   685               new_level = (*_level)[v];
   686             }
   686             }
   687           }
   687           }
   688 
   688 
   689         no_more_push_2:
   689         no_more_push_2:
   690 
   690 
   691           _excess->set(n, excess);
   691           (*_excess)[n] = excess;
   692 
   692 
   693           if (excess != 0) {
   693           if (excess != 0) {
   694             if (new_level + 1 < _level->maxLevel()) {
   694             if (new_level + 1 < _level->maxLevel()) {
   695               _level->liftActiveOn(level, new_level + 1);
   695               _level->liftActiveOn(level, new_level + 1);
   696             } else {
   696             } else {
   729     void startSecondPhase() {
   729     void startSecondPhase() {
   730       _phase = false;
   730       _phase = false;
   731 
   731 
   732       typename Digraph::template NodeMap<bool> reached(_graph);
   732       typename Digraph::template NodeMap<bool> reached(_graph);
   733       for (NodeIt n(_graph); n != INVALID; ++n) {
   733       for (NodeIt n(_graph); n != INVALID; ++n) {
   734         reached.set(n, (*_level)[n] < _level->maxLevel());
   734         reached[n] = (*_level)[n] < _level->maxLevel();
   735       }
   735       }
   736 
   736 
   737       _level->initStart();
   737       _level->initStart();
   738       _level->initAddItem(_source);
   738       _level->initAddItem(_source);
   739 
   739 
   740       std::vector<Node> queue;
   740       std::vector<Node> queue;
   741       queue.push_back(_source);
   741       queue.push_back(_source);
   742       reached.set(_source, true);
   742       reached[_source] = true;
   743 
   743 
   744       while (!queue.empty()) {
   744       while (!queue.empty()) {
   745         _level->initNewLevel();
   745         _level->initNewLevel();
   746         std::vector<Node> nqueue;
   746         std::vector<Node> nqueue;
   747         for (int i = 0; i < int(queue.size()); ++i) {
   747         for (int i = 0; i < int(queue.size()); ++i) {
   748           Node n = queue[i];
   748           Node n = queue[i];
   749           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   749           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   750             Node v = _graph.target(e);
   750             Node v = _graph.target(e);
   751             if (!reached[v] && _tolerance.positive((*_flow)[e])) {
   751             if (!reached[v] && _tolerance.positive((*_flow)[e])) {
   752               reached.set(v, true);
   752               reached[v] = true;
   753               _level->initAddItem(v);
   753               _level->initAddItem(v);
   754               nqueue.push_back(v);
   754               nqueue.push_back(v);
   755             }
   755             }
   756           }
   756           }
   757           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   757           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   758             Node u = _graph.source(e);
   758             Node u = _graph.source(e);
   759             if (!reached[u] &&
   759             if (!reached[u] &&
   760                 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
   760                 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
   761               reached.set(u, true);
   761               reached[u] = true;
   762               _level->initAddItem(u);
   762               _level->initAddItem(u);
   763               nqueue.push_back(u);
   763               nqueue.push_back(u);
   764             }
   764             }
   765           }
   765           }
   766         }
   766         }
   790             if (!_level->active(v) && v != _source) {
   790             if (!_level->active(v) && v != _source) {
   791               _level->activate(v);
   791               _level->activate(v);
   792             }
   792             }
   793             if (!_tolerance.less(rem, excess)) {
   793             if (!_tolerance.less(rem, excess)) {
   794               _flow->set(e, (*_flow)[e] + excess);
   794               _flow->set(e, (*_flow)[e] + excess);
   795               _excess->set(v, (*_excess)[v] + excess);
   795               (*_excess)[v] += excess;
   796               excess = 0;
   796               excess = 0;
   797               goto no_more_push;
   797               goto no_more_push;
   798             } else {
   798             } else {
   799               excess -= rem;
   799               excess -= rem;
   800               _excess->set(v, (*_excess)[v] + rem);
   800               (*_excess)[v] += rem;
   801               _flow->set(e, (*_capacity)[e]);
   801               _flow->set(e, (*_capacity)[e]);
   802             }
   802             }
   803           } else if (new_level > (*_level)[v]) {
   803           } else if (new_level > (*_level)[v]) {
   804             new_level = (*_level)[v];
   804             new_level = (*_level)[v];
   805           }
   805           }
   813             if (!_level->active(v) && v != _source) {
   813             if (!_level->active(v) && v != _source) {
   814               _level->activate(v);
   814               _level->activate(v);
   815             }
   815             }
   816             if (!_tolerance.less(rem, excess)) {
   816             if (!_tolerance.less(rem, excess)) {
   817               _flow->set(e, (*_flow)[e] - excess);
   817               _flow->set(e, (*_flow)[e] - excess);
   818               _excess->set(v, (*_excess)[v] + excess);
   818               (*_excess)[v] += excess;
   819               excess = 0;
   819               excess = 0;
   820               goto no_more_push;
   820               goto no_more_push;
   821             } else {
   821             } else {
   822               excess -= rem;
   822               excess -= rem;
   823               _excess->set(v, (*_excess)[v] + rem);
   823               (*_excess)[v] += rem;
   824               _flow->set(e, 0);
   824               _flow->set(e, 0);
   825             }
   825             }
   826           } else if (new_level > (*_level)[v]) {
   826           } else if (new_level > (*_level)[v]) {
   827             new_level = (*_level)[v];
   827             new_level = (*_level)[v];
   828           }
   828           }
   829         }
   829         }
   830 
   830 
   831       no_more_push:
   831       no_more_push:
   832 
   832 
   833         _excess->set(n, excess);
   833         (*_excess)[n] = excess;
   834 
   834 
   835         if (excess != 0) {
   835         if (excess != 0) {
   836           if (new_level + 1 < _level->maxLevel()) {
   836           if (new_level + 1 < _level->maxLevel()) {
   837             _level->liftHighestActive(new_level + 1);
   837             _level->liftHighestActive(new_level + 1);
   838           } else {
   838           } else {