Changeset 374:0fc9cd9b854a in lemon-0.x for src

Timestamp:

04/22/04 17:56:05 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

 

Location:

src/work/jacint

Files:

• preflow.cc (modified) (1 diff)
• preflowproba.h (modified) (3 diffs)

src/work/jacint/preflow.cc

@@ -25 +25 @@
   
   Graph::EdgeMap<int> flow(G);
-  Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1);
+  Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1,1);
   ts.reset();
   max_flow_test.run();
+  std::cout << "elapsed time with res: " << ts << std::endl;
+  
+  std::cout << "preflow demo ..." << std::endl;
+  
+  Graph::EdgeMap<int> flow2(G);
+  Preflow<Graph, int> max_flow_test2(G, s, t, cap, flow, 1,0);
+  ts.reset();
+  max_flow_test2.run();
   std::cout << "elapsed time: " << ts << std::endl;
   

src/work/jacint/preflowproba.h

@@ -71 +71 @@
     T value;
     bool constzero;
+    bool res;
 
     typedef ResGraphWrapper<const Graph, T, CapMap, FlowMap> ResGW;
@@ -79 +80 @@
   public:
     Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, 
-            FlowMap& _flow, bool _constzero ) :
-      G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {}
+            FlowMap& _flow, bool _constzero, bool _res ) :
+      G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero), res(_res) {}
     
     
@@ -303 +304 @@
               int l=level[v]+1;
               
-              /*              ResInEdgeIt e;
-              for(res_graph.first(e,s); res_graph.valid(e); 
-                  res_graph.next(e)) {
-                Node u=res_graph.tail(e);
-                if ( level[u] >= n ) { 
-                  bfs_queue.push(u);
-                  level.set(u, l);
-                  if ( excess[u] > 0 ) {
-                    next.set(u,active[l]);
-                    active[l]=u;
+              if (res){ 
+                ResInEdgeIt e;
+                for(res_graph.first(e,v); res_graph.valid(e); 
+                    res_graph.next(e)) {
+                  Node u=res_graph.tail(e);
+                  if ( level[u] >= n ) { 
+                    bfs_queue.push(u);
+                    level.set(u, l);
+                    if ( excess[u] > 0 ) {
+                      next.set(u,active[l]);
+                      active[l]=u;
+                    }
                   }
                 }
-                }*/
-                    InEdgeIt e;
-              for(G.first(e,v); G.valid(e); G.next(e)) {
-                if ( capacity[e] == flow[e] ) continue;
-                Node u=G.tail(e);
-                if ( level[u] >= n ) { 
-                  bfs_queue.push(u);
-                  level.set(u, l);
-                  if ( excess[u] > 0 ) {
-                    next.set(u,active[l]);
-                    active[l]=u;
+              } else {
+                InEdgeIt e;
+                for(G.first(e,v); G.valid(e); G.next(e)) {
+                  if ( capacity[e] == flow[e] ) continue;
+                  Node u=G.tail(e);
+                  if ( level[u] >= n ) { 
+                    bfs_queue.push(u);
+                    level.set(u, l);
+                    if ( excess[u] > 0 ) {
+                      next.set(u,active[l]);
+                      active[l]=u;
+                    }
+                  }
+                }
+                
+                OutEdgeIt f;
+                for(G.first(f,v); G.valid(f); G.next(f)) {
+                  if ( 0 == flow[f] ) continue;
+                  Node u=G.head(f);
+                  if ( level[u] >= n ) { 
+                    bfs_queue.push(u);
+                    level.set(u, l);
+                    if ( excess[u] > 0 ) {
+                      next.set(u,active[l]);
+                      active[l]=u;
+                    }
                   }
                 }
               }
-            
-              OutEdgeIt f;
-              for(G.first(f,v); G.valid(f); G.next(f)) {
-                if ( 0 == flow[f] ) continue;
-                Node u=G.head(f);
-                if ( level[u] >= n ) { 
-                  bfs_queue.push(u);
-                  level.set(u, l);
-                  if ( excess[u] > 0 ) {
-                    next.set(u,active[l]);
-                    active[l]=u;
-                  }
-                }
-                }
             }
             b=n-2;