Changeset 745:d976ba609099 in lemon-0.x

Timestamp:

07/29/04 19:18:49 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

jacint javitgatott.

File:

• src/hugo/max_flow.h (modified) (19 diffs)

src/hugo/max_flow.h

@@ -141 +141 @@
     ///
     MaxFlow(const Graph& _G, Node _s, Node _t,
-                   const CapMap& _capacity, FlowMap& _flow) :
+            const CapMap& _capacity, FlowMap& _flow) :
       g(&_G), s(_s), t(_t), capacity(&_capacity),
       flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0), 
@@ -218 +218 @@
       VecFirst first(n, INVALID);
       NNMap next(*g, INVALID); //maybe INVALID is not needed
-      //    VecStack active(n);
 
       NNMap left(*g, INVALID);
@@ -255 +254 @@
                 first[lev]=v;
               }
-            //    active[lev].push(v);
           }
           break;
@@ -281 +279 @@
       }
 
-      preflowPreproc(fe, next, first,/*active*/ level_list, left, right);
+      preflowPreproc(fe, next, first, level_list, left, right);
       //End of preprocessing
 
@@ -294 +292 @@
         }
 
-        if ( !g->valid(first[b])/*active[b].empty()*/ ) --b;
+        if ( !g->valid(first[b]) ) --b;
         else {
           end=false;
           Node w=first[b];
           first[b]=next[w];
-          /*    Node w=active[b].top();
-                active[b].pop();*/
-          int newlevel=push(w,/*active*/next, first);
-          if ( excess[w] > 0 ) relabel(w, newlevel, /*active*/next, first, level_list,
+          int newlevel=push(w, next, first);
+          if ( excess[w] > 0 ) relabel(w, newlevel, next, first, level_list,
                                        left, right, b, k, what_heur);
 
@@ -341 +337 @@
       VecFirst first(n, INVALID);
       NNMap next(*g, INVALID); //maybe INVALID is not needed
-      //    VecStack active(n);
       level.set(s,0);
       std::queue<Node> bfs_queue;
@@ -362 +357 @@
               next.set(u,first[l]);
               first[l]=u;
-              //active[l].push(u);
             }
           }
@@ -377 +371 @@
               next.set(u,first[l]);
               first[l]=u;
-              //active[l].push(u);
             }
           }
@@ -388 +381 @@
         if ( b == 0 ) break;
 
-        if ( !g->valid(first[b])/*active[b].empty()*/ ) --b;
+        if ( !g->valid(first[b]) ) --b;
         else {
 
           Node w=first[b];
           first[b]=next[w];
-          /*    Node w=active[b].top();
-                active[b].pop();*/
           int newlevel=push(w,next, first/*active*/);
 
@@ -402 +393 @@
             next.set(w,first[newlevel]);
             first[newlevel]=w;
-            //active[newlevel].push(w);
             b=newlevel;
           }
@@ -421 +411 @@
       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
-
+      return a;
       //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
+    }
+    Num flowValue2() const {
+      return excess[t];
+//       Num a=0;
+//       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
+//       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
+//       return a;
+//       //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan  
+      
     }
 
@@ -452 +451 @@
       case AFTER_PRE_FLOW_PHASE_2:
       case AFTER_NOTHING:
+      case AFTER_AUGMENTING:
+      case AFTER_FAST_AUGMENTING:
         minMinCut(M);
         break;
@@ -592 +593 @@
             next.set(v,first[level[v]]);
             first[level[v]]=v;
-            //      int lev_v=level[v];
-            //active[lev_v].push(v);
           }
 
@@ -627 +626 @@
               next.set(v,first[level[v]]);
               first[level[v]]=v;
-              //int lev_v=level[v];
-              //active[lev_v].push(v);
             }
 
@@ -701 +698 @@
                     next.set(w,first[level[w]]);
                     first[level[w]]=w;
-                    //active[level[w]].push(w);
                   }
                 flow->set(e, c);
@@ -766 +762 @@
                     next.set(w,first[level[w]]);
                     first[level[w]]=w;
-                    //active[level[w]].push(w);
                   }   
                 flow->set(e, (*capacity)[e]);
@@ -783 +778 @@
                     next.set(w,first[level[w]]);
                     first[level[w]]=w;
-                    //active[level[w]].push(w);
                   }   
                 excess.set(w, excess[w]+(*flow)[f]);
@@ -835 +829 @@
           level_list[i]=INVALID;
           if ( !what_heur ) first[i]=INVALID;
-          /*{
-            while ( !active[i].empty() ) {
-            active[i].pop();    //FIXME: ezt szebben kene
-            }
-            }*/
         }
 
@@ -854 +843 @@
           next.set(w,first[newlevel]);
           first[newlevel]=w;
-          //      active[newlevel].push(w);
           if ( what_heur ) b=newlevel;
           if ( k < newlevel ) ++k;      //now k=newlevel