Changeset 84:56e879edcca6 in lemon-0.x for src/work/jacint

Timestamp:

02/17/04 10:34:55 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

after debugging

File:

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

src/work/jacint/preflow_push_hl.h

@@ -66 +66 @@
     void run() {
  
-      int i=0;//DELME
-
       typename Graph::NodeMap<int> level(G);      
-      typename Graph::NodeMap<T> excess(G);      
+      typename Graph::NodeMap<T> excess(G); 
+      std::cout <<"excess s:"<<excess.get(s);      //delme
             
-      int n=G.nodeNum();    
+      int n=G.nodeNum(); 
       int b=n-2; 
       /*
@@ -90 +89 @@
         }
 
-      std::cout << "the level of t is " << bfs.dist(t);//delme
-
       level.set(s,n);
 
@@ -100 +97 @@
           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)); 
-            stack[level.get(w)].push(w); 
             excess.set(w, excess.get(w)+capacity.get(e));
           }
         }
 
-
       /* 
          End of preprocessing 
@@ -114 +110 @@
 
       /*
-        Push/relabel on the highest level active Nodes.
+        Push/relabel on the highest level active nodes.
       */
         
-      /*While there exists active Node.*/
+      /*While there exists active node.*/
       while (b) { 
 
@@ -125 +121 @@
         } else {
 
-          NodeIt w=stack[b].top();    //w is the highest label active Node.
-          stack[b].pop();                    //We delete w from the stack.
+          NodeIt w=stack[b].top();        //w is a highest label active node.
+          stack[b].pop();           
         
-          int newlevel=2*n-2;                   //In newlevel we maintain the next level of w.
+          int newlevel=2*n-2;             //In newlevel we bound the next level of w.
         
           for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
-            NodeIt v=G.head(e);
-            /*e is the Edge wv.*/
-
-            if (flow.get(e)<capacity.get(e)) {              
-              /*e is an Edge of the residual graph */
-
-              if(level.get(w)==level.get(v)+1) {      
+            
+            if ( flow.get(e) < capacity.get(e) ) {              
+              /*e is an edge of the residual graph */
+
+              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*/
 
@@ -143 +141 @@
                   /*A nonsaturating push.*/
                   
-                  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
+                  if (excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v); 
                   /*v becomes active.*/
 
-                  //std::cout<<++i;
-                  
                   flow.set(e, flow.get(e)+excess.get(w));
                   excess.set(v, excess.get(v)+excess.get(w));
@@ -156 +152 @@
                   /*A saturating push.*/
 
-                  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
+                  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v); 
                   /*v becomes active.*/
 
@@ -194 +190 @@
                   /*A nonsaturating push.*/
                   
-                  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
+                  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v); 
                   /*v becomes active.*/
 
@@ -205 +201 @@
                   /*A saturating push.*/
                   
-                  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
+                  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v); 
                   /*v becomes active.*/