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
Show white space 2 line context
... ... 
@@ -560,8 +560,14 @@
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];


			




	...
	...
	
		
@@ -631,6 +637,2 @@


			




	631
	637
	
		
          }


			




	632
	
	
		

			




	633
	
	
		
          n = _level->highestActive();


			




	634
	
	
		
          level = _level->highestActiveLevel();


			




	635
	
	
		
          --num;


			




	636
	638
	
		
        }


			




	...
	...
	
		
@@ -638,3 +640,15 @@


			




	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];


			




	...
	...
	
		
@@ -704,15 +718,5 @@


			




	704
	718
	
		
          }


			




	705
	
	
		

			




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


			




	707
	
	
		
            --level;


			




	708
	719
	
		
          }


			




	709
	
	
		
          if (level == -1) {


			




	710
	
	
		
            n = _level->highestActive();


			




	711
	
	
		
            level = _level->highestActiveLevel();


			




	712
	
	
		
          } else {


			




	713
	
	
		
            n = _level->activeOn(level);


			




	714
	720
	
		
          }


			




	715
	
	
		
          --num;


			




	716
	
	
		
        }


			




	717
	
	
		
      }


			




	
	721
	
		
    first_phase_done:;


			




	718
	722
	
		
    }


			




        

    






    
    



    


    

     
    
0 comments (0 inline)