Changeset - r891:bb70ad62c95f
« 888:520514
923:30d5f9 »
892:a22b3f »
gravatar
deba@inf.elte.hu
deba@inf.elte.hu
Fix critical bug in preflow (#372) The wrong transition between the bound decrease and highest active heuristics caused the bug. The last node chosen in bound decrease mode is used in the first iteration in highest active mode.
0 1 0
default
1 file changed with 24 insertions and 20 deletions:
lemon/preflow.h
24
20
↑ Collapse diff ↑
lemon/preflow.h
Ignore white space 6 line context
... ... 
@@ -558,12 +558,18 @@
558 558 
    void startFirstPhase() {
559 559 
      _phase = true;
560 560 

			




	561
	
	
		
      Node n = _level->highestActive();


			




	562
	
	
		
      int level = _level->highestActiveLevel();


			




	563
	
	
		
      while (n != INVALID) {


			




	
	561
	
		
      while (true) {


			




	564
	562
	
		
        int num = _node_num;


			




	565
	563
	
		

			




	566
	
	
		
        while (num > 0 && n != INVALID) {


			




	
	564
	
		
        Node n = INVALID;


			




	
	565
	
		
        int level = -1;


			




	
	566
	
		

			




	
	567
	
		
        while (num > 0) {


			




	
	568
	
		
          n = _level->highestActive();


			




	
	569
	
		
          if (n == INVALID) goto first_phase_done;


			




	
	570
	
		
          level = _level->highestActiveLevel();


			




	
	571
	
		
          --num;


			




	
	572
	
		
          


			




	567
	573
	
		
          Value excess = (*_excess)[n];


			




	568
	574
	
		
          int new_level = _level->maxLevel();


			




	569
	575
	
		

			




	...
	...
	
		
@@ -629,14 +635,22 @@


			




	629
	635
	
		
          } else {


			




	630
	636
	
		
            _level->deactivate(n);


			




	631
	637
	
		
          }


			




	632
	
	
		

			




	633
	
	
		
          n = _level->highestActive();


			




	634
	
	
		
          level = _level->highestActiveLevel();


			




	635
	
	
		
          --num;


			




	636
	638
	
		
        }


			




	637
	639
	
		

			




	638
	640
	
		
        num = _node_num * 20;


			




	639
	
	
		
        while (num > 0 && n != INVALID) {


			




	
	641
	
		
        while (num > 0) {


			




	
	642
	
		
          while (level >= 0 && _level->activeFree(level)) {


			




	
	643
	
		
            --level;


			




	
	644
	
		
          }


			




	
	645
	
		
          if (level == -1) {


			




	
	646
	
		
            n = _level->highestActive();


			




	
	647
	
		
            level = _level->highestActiveLevel();


			




	
	648
	
		
            if (n == INVALID) goto first_phase_done;


			




	
	649
	
		
          } else {


			




	
	650
	
		
            n = _level->activeOn(level);


			




	
	651
	
		
          }


			




	
	652
	
		
          --num;


			




	
	653
	
		

			




	640
	654
	
		
          Value excess = (*_excess)[n];


			




	641
	655
	
		
          int new_level = _level->maxLevel();


			




	642
	656
	
		

			




	...
	...
	
		
@@ -702,19 +716,9 @@


			




	702
	716
	
		
          } else {


			




	703
	717
	
		
            _level->deactivate(n);


			




	704
	718
	
		
          }


			




	705
	
	
		

			




	706
	
	
		
          while (level >= 0 && _level->activeFree(level)) {


			




	707
	
	
		
            --level;


			




	708
	
	
		
          }


			




	709
	
	
		
          if (level == -1) {


			




	710
	
	
		
            n = _level->highestActive();


			




	711
	
	
		
            level = _level->highestActiveLevel();


			




	712
	
	
		
          } else {


			




	713
	
	
		
            n = _level->activeOn(level);


			




	714
	
	
		
          }


			




	715
	
	
		
          --num;


			




	716
	719
	
		
        }


			




	717
	720
	
		
      }


			




	
	721
	
		
    first_phase_done:;


			




	718
	722
	
		
    }


			




	719
	723
	
		

			




	720
	724
	
		
    /// \brief Starts the second phase of the preflow algorithm.


			




        

    






    
    



    


    

     
    
0 comments (0 inline)