Changeset 191:efea403c9595 in lemon-0.x

Timestamp:

03/17/04 14:33:13 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

File:

• src/work/edmonds_karp.h (modified) (16 diffs)

src/work/edmonds_karp.h

@@ -267 +267 @@
     typedef typename AugGraph::Edge AugEdge;
 
-    //AugGraph res_graph;    
-    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
-    //typename AugGraph::NodeMap<AugEdge> pred; 
-    //typename AugGraph::NodeMap<Number> free;
   public:
     MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 
-      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,  
-      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 
-      { }
+      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
     bool augmentOnShortestPath() {
       AugGraph res_graph(*G, *flow, *capacity);
@@ -291 +285 @@
       //searching for augmenting path
       while ( !res_bfs.finished() ) { 
-        AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
+        AugOutEdgeIt e=res_bfs;
         if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
           Node v=res_graph.tail(e);
@@ -313 +307 @@
           AugEdge e=pred.get(n);
           res_graph.augment(e, augment_value); 
-          //e.augment(augment_value); 
           n=res_graph.tail(e);
         }
@@ -321 +314 @@
     }
 
-    template<typename MutableGraph> bool augmentOnBlockingFlow() {
-      
-//       std::cout << "number of nodes: " << G->nodeNum() << std::endl;
-//       typename Graph::NodeIt n; 
-//       G->first(n);
-//       for( ; G->valid(n); G->next(n)) {
-//      std::cout << G->id(n) << std::endl;
-//       }
-//       std::cout << "meg elek 1";
-
-//       for(typename Graph::NodeIt n=G->template first<typename Graph::NodeIt>(); G->valid(n); G->next(n)) {
-//      std::cout << G->id(n) << std::endl;
-//       }
-//       std::cout << "meg elek 2";
-      
+    template<typename MutableGraph> bool augmentOnBlockingFlow() {      
       bool _augment=false;
 
@@ -346 +325 @@
       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
       while ( !bfs.finished() ) { 
-        AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
+        AugOutEdgeIt e=bfs;
         if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
           dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
@@ -353 +332 @@
         ++bfs;
       } //computing distances from s in the residual graph
-
-//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
-//      std::cout << res_graph.id(n) << std::endl;
-//       }
-//       std::cout << "meg elek";
 
       MutableGraph F;
@@ -384 +358 @@
       }
 
-//       for(typename MutableGraph::NodeIt n=F.template first<typename MutableGraph::NodeIt>(); F.valid(n); F.next(n)) {
-//      std::cout << F.id(n) << std::endl;
-//       }
-
       bool __augment=true;
 
@@ -406 +376 @@
           if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
             if (dfs.isBNodeNewlyReached()) {
-//            std::cout << "OutEdgeIt: " << dfs; 
-//            std::cout << " aNode: " << F.aNode(dfs); 
-//            std::cout << " bNode: " << F.bNode(dfs) << " ";
-          
               typename MutableGraph::Node v=F.aNode(dfs);
               typename MutableGraph::Node w=F.bNode(dfs);
@@ -419 +385 @@
               }
               if (w==tF) { 
-                //std::cout << "AUGMENTATION"<<std::endl;
                 __augment=true; 
                 _augment=true;
@@ -437 +402 @@
             typename MutableGraph::Edge e=pred.get(n);
             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) 
@@ -460 +424 @@
       EAugGraph res_graph(*G, *flow, *capacity);
 
-      //std::cout << "meg jo1" << std::endl;
-
       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
       BfsIterator4< 
@@ -468 +430 @@
         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() ) {
         typename 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::NodeIt EAugNodeIt;
-//       for(EAugNodeIt n=res_graph.template first<EAugNodeIt>(); 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;
@@ -520 +463 @@
           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::Node v=res_graph.aNode(dfs);
@@ -529 +468 @@
 
               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))));
+                free.set(w, std::min(free.get(v), res_graph.free(dfs)));
               } else {
-                free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); 
+                free.set(w, res_graph.free(dfs)); 
               }
               
               if (w==t) { 
-//              std::cout << "t is reached, AUGMENTATION"<<std::endl;
                 __augment=true; 
                 _augment=true;
@@ -544 +480 @@
               }
             } 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);
             }
@@ -559 +489 @@
           typename EAugGraph::Node n=t;
           Number augment_value=free.get(t);
-//        std::cout << "av:" << augment_value << std::endl;
           while (res_graph.valid(pred.get(n))) { 
             EAugEdge 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)