lemon/preflow.h
changeset 1032 62ba43576f85
parent 877 141f9c0db4a3
parent 891 bb70ad62c95f
child 924 a80381c43760
equal deleted inserted replaced
22:bd1c171a341b 24:fd570853c214
   574     /// \pre One of the \ref init() functions must be called before
   574     /// \pre One of the \ref init() functions must be called before
   575     /// using this function.
   575     /// using this function.
   576     void startFirstPhase() {
   576     void startFirstPhase() {
   577       _phase = true;
   577       _phase = true;
   578 
   578 
   579       Node n = _level->highestActive();
   579       while (true) {
   580       int level = _level->highestActiveLevel();
       
   581       while (n != INVALID) {
       
   582         int num = _node_num;
   580         int num = _node_num;
   583 
   581 
   584         while (num > 0 && n != INVALID) {
   582         Node n = INVALID;
       
   583         int level = -1;
       
   584 
       
   585         while (num > 0) {
       
   586           n = _level->highestActive();
       
   587           if (n == INVALID) goto first_phase_done;
       
   588           level = _level->highestActiveLevel();
       
   589           --num;
       
   590           
   585           Value excess = (*_excess)[n];
   591           Value excess = (*_excess)[n];
   586           int new_level = _level->maxLevel();
   592           int new_level = _level->maxLevel();
   587 
   593 
   588           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   594           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   589             Value rem = (*_capacity)[e] - (*_flow)[e];
   595             Value rem = (*_capacity)[e] - (*_flow)[e];
   645               _level->liftToTop(level);
   651               _level->liftToTop(level);
   646             }
   652             }
   647           } else {
   653           } else {
   648             _level->deactivate(n);
   654             _level->deactivate(n);
   649           }
   655           }
   650 
   656         }
   651           n = _level->highestActive();
   657 
   652           level = _level->highestActiveLevel();
   658         num = _node_num * 20;
       
   659         while (num > 0) {
       
   660           while (level >= 0 && _level->activeFree(level)) {
       
   661             --level;
       
   662           }
       
   663           if (level == -1) {
       
   664             n = _level->highestActive();
       
   665             level = _level->highestActiveLevel();
       
   666             if (n == INVALID) goto first_phase_done;
       
   667           } else {
       
   668             n = _level->activeOn(level);
       
   669           }
   653           --num;
   670           --num;
   654         }
   671 
   655 
       
   656         num = _node_num * 20;
       
   657         while (num > 0 && n != INVALID) {
       
   658           Value excess = (*_excess)[n];
   672           Value excess = (*_excess)[n];
   659           int new_level = _level->maxLevel();
   673           int new_level = _level->maxLevel();
   660 
   674 
   661           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   675           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   662             Value rem = (*_capacity)[e] - (*_flow)[e];
   676             Value rem = (*_capacity)[e] - (*_flow)[e];
   718               _level->liftToTop(level);
   732               _level->liftToTop(level);
   719             }
   733             }
   720           } else {
   734           } else {
   721             _level->deactivate(n);
   735             _level->deactivate(n);
   722           }
   736           }
   723 
   737         }
   724           while (level >= 0 && _level->activeFree(level)) {
   738       }
   725             --level;
   739     first_phase_done:;
   726           }
       
   727           if (level == -1) {
       
   728             n = _level->highestActive();
       
   729             level = _level->highestActiveLevel();
       
   730           } else {
       
   731             n = _level->activeOn(level);
       
   732           }
       
   733           --num;
       
   734         }
       
   735       }
       
   736     }
   740     }
   737 
   741 
   738     /// \brief Starts the second phase of the preflow algorithm.
   742     /// \brief Starts the second phase of the preflow algorithm.
   739     ///
   743     ///
   740     /// The preflow algorithm consists of two phases, this method runs
   744     /// The preflow algorithm consists of two phases, this method runs