Changeset 85:15362fafaf1a in lemon-0.x for src/work/jacint/preflow_push_hl.h

Timestamp:

02/17/04 12:16:39 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@112

Message:

* empty log message *

File:

• src/work/jacint/preflow_push_hl.h (modified) (7 diffs)

src/work/jacint/preflow_push_hl.h

@@ -26 +26 @@
 #define PREFLOW_PUSH_HL_H
 
-#include <algorithm>
+//#include <algorithm>
 #include <vector>
 #include <stack>
 
-#include <list_graph.hh>
 #include <reverse_bfs.h>
 
@@ -68 +67 @@
       typename Graph::NodeMap<int> level(G);      
       typename Graph::NodeMap<T> excess(G); 
-      std::cout <<"excess s:"<<excess.get(s);      //delme
-            
+
       int n=G.nodeNum(); 
       int b=n-2; 
@@ -77 +75 @@
       */
 
+      std::vector<int> numb(n);     //The number of nodes on level i < n.
       std::vector<std::stack<NodeIt> > stack(2*n-1);    
       //Stack of the active nodes in level i.
@@ -86 +85 @@
       for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) 
         {
-          level.set(v, bfs.dist(v)); 
+          int dist=bfs.dist(v);
+          level.set(v, dist);
+          ++numb[dist];
         }
 
@@ -97 +98 @@
           if ( capacity.get(e) > 0 ) {
             NodeIt w=G.head(e);
-            if ( excess.get(w) == 0 && w!=t && w!=s ) stack[level.get(w)].push(w); 
-            flow.set(e, capacity.get(e)); 
-            excess.set(w, excess.get(w)+capacity.get(e));
+            if ( w!=s ) {         
+              if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 
+              flow.set(e, capacity.get(e)); 
+              excess.set(w, excess.get(w)+capacity.get(e));
+            }
           }
         }
@@ -113 +116 @@
       */
         
-      /*While there exists active node.*/
+      /*While there exists an active node.*/
       while (b) { 
 
-        /*We decrease the bound if there is no active Node of level b.*/
+        /*We decrease the bound if there is no active node of level b.*/
         if (stack[b].empty()) {
           --b;
@@ -133 +136 @@
               NodeIt v=G.head(e);               /*e is the edge wv.*/
 
-              if( level.get(w) > level.get(v)+1 ) { std::cout<<"HIBA1!";} //delme     
-
               if( level.get(w) == level.get(v)+1 ) {      
                 /*Push is allowed now*/
 
-                if (capacity.get(e)-flow.get(e) > excess.get(w)) {       
+                if ( excess.get(v)==0 && v != s && v !=t ) stack[level.get(v)].push(v); 
+                /*v becomes active.*/
+
+                if ( capacity.get(e)-flow.get(e) > excess.get(w) ) {       
                   /*A nonsaturating push.*/
                   
-                  if (excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v); 
-                  /*v becomes active.*/
-
                   flow.set(e, flow.get(e)+excess.get(w));
                   excess.set(v, excess.get(v)+excess.get(w));
                   excess.set(w,0);
-                  //std::cout << w << " " << v <<" elore elen nonsat pump "  << std::endl;
                   break; 
+
                 } else { 
                   /*A saturating push.*/
-
-                  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v); 
-                  /*v becomes active.*/
 
                   excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
                   excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
                   flow.set(e, capacity.get(e));
-                  //std::cout << w<<" " <<v<<" elore elen sat pump "   << std::endl;
-                  if (excess.get(w)==0) break;
-                  /*If w is not active any more, then we go on to the next Node.*/
+                  if ( excess.get(w)==0 ) break;
+                  /*If w is not active any more, then we go on to the next node.*/
                   
-                  //std::cout<<++i;
+                }
+              } else {
+                newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
+              }
+            
+            } //if the out edge wv is in the res graph 
+         
+          } //for out edges wv 
+          
+
+          if ( excess.get(w) > 0 ) {    
+            
+            for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
+              NodeIt v=G.tail(e);  /*e is the edge vw.*/
+
+              if( flow.get(e) > 0 ) {             
+                /*e is an edge of the residual graph */
+
+                if( level.get(w)==level.get(v)+1 ) {  
+                  /*Push is allowed now*/
+                
+                  if ( excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v); 
+                  /*v becomes active.*/
+
+                  if ( flow.get(e) > excess.get(w) ) { 
+                    /*A nonsaturating push.*/
                   
-                } // if (capacity.get(e)-flow.get(e) > excess.get(w))
-              } // if(level.get(w)==level.get(v)+1)
-            
-              else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
-            
-            } //if (flow.get(e)<capacity.get(e))
-         
-          } //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e) 
+                    flow.set(e, flow.get(e)-excess.get(w));
+                    excess.set(v, excess.get(v)+excess.get(w));
+                    excess.set(w,0);
+                    break; 
+                  } else {                                               
+                    /*A saturating push.*/
+                    
+                    excess.set(v, excess.get(v)+flow.get(e));
+                    excess.set(w, excess.get(w)-flow.get(e));
+                    flow.set(e,0);
+                    if ( excess.get(w)==0 ) break;
+                  }  
+                } else {
+                  newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
+                }
+                
+              } //if in edge vw is in the res graph 
+
+            } //for in edges vw
+
+          } // if w still has excess after the out edge for cycle
+
+
+          /*
+            Relabel
+          */
           
-
-
-          for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
-            NodeIt v=G.tail(e);
-            /*e is the Edge vw.*/
-
-            if (excess.get(w)==0) break;
-            /*It may happen, that w became inactive in the first for cycle.*/           
-            if(flow.get(e)>0) {             
-              /*e is an Edge of the residual graph */
-
-              if(level.get(w)==level.get(v)+1) {  
-                /*Push is allowed now*/
+          if ( excess.get(w) > 0 ) {
+            
+            int oldlevel=level.get(w);      
+            level.set(w,++newlevel);
+
+            if ( oldlevel < n ) {
+              --numb[oldlevel];
+
+              if ( !numb[oldlevel] ) {  //If the level of w gets empty. 
                 
-                if (flow.get(e) > excess.get(w)) { 
-                  /*A nonsaturating push.*/
-                  
-                  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v); 
-                  /*v becomes active.*/
-
-                  flow.set(e, flow.get(e)-excess.get(w));
-                  excess.set(v, excess.get(v)+excess.get(w));
-                  excess.set(w,0);
-                  //std::cout << v << " " << w << " vissza elen nonsat pump "     << std::endl;
-                  break; 
-                } else {                                               
-                  /*A saturating push.*/
-                  
-                  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v); 
-                  /*v becomes active.*/
-                  
-                  excess.set(v, excess.get(v)+flow.get(e));
-                  excess.set(w, excess.get(w)-flow.get(e));
-                  flow.set(e,0);
-                  //std::cout << v <<" " << w << " vissza elen sat pump "     << std::endl;
-                  if (excess.get(w)==0) { break;}
-                } //if (flow.get(e) > excess.get(v)) 
-              } //if(level.get(w)==level.get(v)+1)
-              
-              else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
-              
-
-            } //if (flow.get(e)>0)
-
-          } //for
-
-
-          if (excess.get(w)>0) {
-            level.set(w,++newlevel);
+                for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
+                  if (level.get(v) > oldlevel && level.get(v) < n ) level.set(v,n);  
+                }
+                for (int i=oldlevel+1 ; i!=n ; ++i) numb[i]=0; 
+                if ( newlevel < n ) newlevel=n; 
+              } else { 
+                if ( newlevel < n ) ++numb[newlevel]; 
+              }
+            } else { 
+            if ( newlevel < n ) ++numb[newlevel];
+            }
+            
             stack[newlevel].push(w);
             b=newlevel;
-            //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl; 
+
           }
 
-
-        } //else
-       
-      } //while(b)
+        } // if stack[b] is nonempty
+
+      } // while(b)
+
 
       value = excess.get(t);
       /*Max flow value.*/
-
-