Changeset 101:d2ac583ed195 in lemon-0.x for src

Timestamp:

02/18/04 22:50:45 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

another heuristic

Location:

src/work/jacint

Files:

• preflow_hl2.h (modified) (3 diffs)
• preflow_hl3.h (added)
• preflow_push_hl.h (modified) (3 diffs)

src/work/jacint/preflow_hl2.h

@@ -81 +81 @@
       TMap excess(G); 
       
-      std::vector<int> numb(n+1);    
+      std::vector<int> numb(n);    
       /*
         The number of nodes on level i < n. It is
@@ -119 +119 @@
       for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
         {
-          if ( capacity.get(e) == 0 ) continue; 
+          T c=capacity.get(e);
+          if ( c == 0 ) continue;
           NodeIt w=G.head(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));
-          } 
+            flow.set(e, c); 
+            excess.set(w, excess.get(w)+c);
+          }
         }
 
@@ -156 +157 @@
           int lev=level.get(w);
           int exc=excess.get(w);
-          int newlevel=2*n-2;      //In newlevel we bound the next level of w.
+          int newlevel=2*n;      //In newlevel we bound the next level of w.
           
           //  if ( level.get(w) < n ) { //Nem tudom ez mukodik-e

src/work/jacint/preflow_push_hl.h

@@ -1 +1 @@
 // -*- C++ -*-
+
+//kerdesek: nem tudom lehet-e a 
+//kieleket csak a legf n szintu pontokra nezni.
+
 /*
 preflow_push_hl.h
@@ -117 +121 @@
       for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
         {
-          if ( capacity.get(e) == 0 ) continue;
+          T c=capacity.get(e);
+          if ( c == 0 ) continue;
           NodeIt w=G.head(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));
+            flow.set(e, c); 
+            excess.set(w, excess.get(w)+c);
           }
         }
@@ -145 +150 @@
         int lev=level.get(w);
         int exc=excess.get(w);
-        int newlevel=2*n-2;      //In newlevel we bound the next level of w.
-        
+        int newlevel=2*n;      //In newlevel we bound the next level of w.
+        //vagy MAXINT   
+
         //  if ( level.get(w) < n ) { //Nem tudom ez mukodik-e
           for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {