Changeset 168:27fbd1559fb7 in lemon-0.x for src/work/edmonds_karp.hh

Timestamp:

03/11/04 15:15:07 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

graph wrapper improvements, blocking flow on fly

File:

• src/work/edmonds_karp.hh (modified) (7 diffs)

src/work/edmonds_karp.hh

@@ -280 +280 @@
       
       typedef typename AugGraph::NodeMap<bool> ReachedMap;
-      BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
+      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
       res_bfs.pushAndSetReached(s);
         
@@ -297 +297 @@
           pred.set(w, e);
           if (res_graph.valid(pred.get(v))) {
-            free.set(w, std::min(free.get(v), e.free()));
+            free.set(w, std::min(free.get(v), res_graph.free(e)));
           } else {
-            free.set(w, e.free()); 
+            free.set(w, res_graph.free(e)); 
           }
           if (res_graph.head(e)==t) { _augment=true; break; }
@@ -312 +312 @@
         while (res_graph.valid(pred.get(n))) { 
           AugEdgeIt e=pred.get(n);
-          e.augment(augment_value); 
+          res_graph.augment(e, augment_value); 
+          //e.augment(augment_value); 
           n=res_graph.tail(e);
         }
@@ -359 +360 @@
           original_edge.set(f, e);
           residual_capacity.update();
-          residual_capacity.set(f, e.free());
+          residual_capacity.set(f, res_graph.free(e));
         } 
       }
@@ -377 +378 @@
           ++dfs;
           if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
-            //std::cout << "OutEdgeIt: " << dfs; 
-            //std::cout << " aNode: " << F.aNode(dfs); 
-            //std::cout << " bNode: " << F.bNode(dfs) << " ";
+            if (dfs.isBNodeNewlyReached()) {
+//            std::cout << "OutEdgeIt: " << dfs; 
+//            std::cout << " aNode: " << F.aNode(dfs); 
+//            std::cout << " bNode: " << F.bNode(dfs) << " ";
           
-            typename MutableGraph::NodeIt v=F.aNode(dfs);
-            typename MutableGraph::NodeIt w=F.bNode(dfs);
-            pred.set(w, dfs);
-            if (F.valid(pred.get(v))) {
-              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+              typename MutableGraph::NodeIt v=F.aNode(dfs);
+              typename MutableGraph::NodeIt w=F.bNode(dfs);
+              pred.set(w, dfs);
+              if (F.valid(pred.get(v))) {
+                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+              } else {
+                free.set(w, residual_capacity.get(dfs)); 
+              }
+              if (w==tF) { 
+                //std::cout << "AUGMENTATION"<<std::endl;
+                __augment=true; 
+                _augment=true;
+                break; 
+              }
+              
             } else {
-              free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/); 
-            }
-            if (w==tF) { 
-              //std::cout << "AUGMENTATION"<<std::endl;
-              __augment=true; 
-              _augment=true;
-              break; 
-            }
-          } else { 
-            //std::cout << "OutEdgeIt: " << "invalid"; 
-            //std::cout << " aNode: " << dfs.aNode(); 
-            //std::cout << " bNode: " << "invalid" << " ";
-          }
-          if (dfs.isBNodeNewlyReached()) { 
-            //std::cout << "bNodeIsNewlyReached ";
-          } else { 
-            //std::cout << "bNodeIsNotNewlyReached ";
-            if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
-              //std::cout << "DELETE ";
               F.erase(typename MutableGraph::OutEdgeIt(dfs));
             }
           } 
-          //if (dfs.isANodeExamined()) { 
-            //std::cout << "aNodeIsExamined ";
-            //} else { 
-            //std::cout << "aNodeIsNotExamined ";
-            //} 
-          //std::cout<<std::endl;
         }
 
@@ -422 +409 @@
           while (F.valid(pred.get(n))) { 
             typename MutableGraph::EdgeIt e=pred.get(n);
-            original_edge.get(e).augment(augment_value); 
+            res_graph.augment(original_edge.get(e), augment_value); 
+            //original_edge.get(e).augment(augment_value); 
             n=F.tail(e);
             if (residual_capacity.get(e)==augment_value) 
@@ -428 +416 @@
             else 
               residual_capacity.set(e, residual_capacity.get(e)-augment_value);
+          }
+        }
+        
+      }
+            
+      return _augment;
+    }
+    bool augmentOnBlockingFlow2() {
+      bool _augment=false;
+
+      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
+      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
+      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
+      typedef typename EAugGraph::EdgeIt EAugEdgeIt;
+
+      EAugGraph res_graph(*G, *flow, *capacity);
+
+      //std::cout << "meg jo1" << std::endl;
+
+      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
+      BfsIterator4< 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
+      
+      //std::cout << "meg jo2" << std::endl;
+
+      bfs.pushAndSetReached(s);
+      //std::cout << "meg jo2.5" << std::endl;
+
+      //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
+      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
+        NodeMap<int>& dist=res_graph.dist;
+      //std::cout << "meg jo2.6" << std::endl;
+
+      while ( !bfs.finished() ) {
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
+//      EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
+        //if (res_graph.valid(e)) {
+        //    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
+        //}
+        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
+          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+        }
+        
+        ++bfs;  
+      } //computing distances from s in the residual graph
+
+
+      //std::cout << "meg jo3" << std::endl;
+
+//       typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
+//       for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
+//      std::cout << "dist: " << dist.get(n) << std::endl;
+//       }
+
+      bool __augment=true;
+
+      while (__augment) {
+//      std::cout << "new iteration"<< std::endl;
+
+        __augment=false;
+        //computing blocking flow with dfs
+        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
+        DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 
+          dfs(res_graph);
+        typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
+        typename EAugGraph::NodeMap<Number> free(res_graph);
+
+        dfs.pushAndSetReached(s);
+        while (!dfs.finished()) {
+          ++dfs;
+          if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
+            if (dfs.isBNodeNewlyReached()) {
+//            std::cout << "OutEdgeIt: " << dfs; 
+//            std::cout << " aNode: " << res_graph.aNode(dfs); 
+//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
+//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
+          
+              typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
+              typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
+
+              pred.set(w, EAugOutEdgeIt(dfs));
+
+              //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
+              if (res_graph.valid(pred.get(v))) {
+                free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
+              } else {
+                free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); 
+              }
+              
+              if (w==t) { 
+//              std::cout << "t is reached, AUGMENTATION"<<std::endl;
+                __augment=true; 
+                _augment=true;
+                break; 
+              }
+            } else {
+//            std::cout << "<<DELETE ";
+//            std::cout << " aNode: " << res_graph.aNode(dfs); 
+//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
+//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
+//            std::cout << "DELETE>> ";
+
+              res_graph.erase(dfs);
+            }
+          } 
+
+        }
+
+        if (__augment) {
+          typename EAugGraph::NodeIt n=t;
+          Number augment_value=free.get(t);
+//        std::cout << "av:" << augment_value << std::endl;
+          while (res_graph.valid(pred.get(n))) { 
+            EAugEdgeIt e=pred.get(n);
+            res_graph.augment(e, augment_value);
+            //e.augment(augment_value); 
+            n=res_graph.tail(e);
+            if (res_graph.free(e)==0)
+              res_graph.erase(e);
           }
         }