Changeset 168:27fbd1559fb7 in lemon-0.x

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

Location:

src/work

Files:

• bfs_iterator.hh (modified) (2 diffs)
• edmonds_karp.hh (modified) (7 diffs)
• marci/edmonds_karp_demo.cc (modified) (2 diffs)
• marci/graph_wrapper.h (modified) (19 diffs)
• marci/makefile (modified) (1 diff)
• marci_graph_demo.cc (modified) (1 diff)

src/work/bfs_iterator.hh

@@ -563 +563 @@
     ~BfsIterator4() { if (own_reached_map) delete &reached; }
     void pushAndSetReached(NodeIt s) { 
+      //std::cout << "mimi" << &reached << std::endl;
       reached.set(s, true);
+      //std::cout << "mumus" << std::endl;
       if (bfs_queue.empty()) {
+        //std::cout << "bibi1" << std::endl;
         bfs_queue.push(s);
+        //std::cout << "zizi" << std::endl;
         G.getFirst(actual_edge, s);
+        //std::cout << "kiki" << std::endl;
         if (G.valid(actual_edge)/*.valid()*/) { 
           NodeIt w=G.bNode(actual_edge);
@@ -578 +583 @@
         } 
       } else {
+        //std::cout << "bibi2" << std::endl;
         bfs_queue.push(s);
       }

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);
           }
         }

src/work/marci/edmonds_karp_demo.cc

@@ -88 +88 @@
   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
   int i=0;
-  while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; }
+  while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { 
+//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//     }
+//     std::cout<<std::endl;
+    ++i; 
+  }
+  //double post_time=currTime();
+
+  //std::cout << "maximum flow: "<< std::endl;
+  //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 
+  //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+  //}
+  //std::cout<<std::endl;
+  std::cout << "elapsed time: " << ts << std::endl;
+  std::cout << "number of augmentation phases: " << i << std::endl; 
+  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  }
+
+  {
+  std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
+  ListGraph::EdgeMap<int> flow(G); //0 flow
+
+  Timer ts;
+  ts.reset();
+  //double pre_time=currTime();
+  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
+  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
+  int i=0;
+  while (max_flow_test.augmentOnBlockingFlow2()) { 
+//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//     }
+//     std::cout<<std::endl;
+    ++i; 
+  }
   //double post_time=currTime();
 
@@ -111 +146 @@
   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
   int i=0;
-  while (max_flow_test.augmentOnShortestPath()) { ++i; }
+  while (max_flow_test.augmentOnShortestPath()) { 
+//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//     }
+//     std::cout<<std::endl;
+    ++i; 
+  }
   //double post_time=currTime();
 

src/work/marci/graph_wrapper.h

@@ -20 +20 @@
     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     typedef typename Graph::EachEdgeIt EachEdgeIt;
+
+    //TrivGraphWrapper() : graph(0) { }
+    TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
+
+    void setGraph(Graph& _graph) { graph = &_graph; }
+    Graph& getGraph() const { return (*graph); }
     
     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
@@ -67 +73 @@
         Graph::NodeMap<T>(_G.getGraph(), a) { }
     };
+
     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
     public:
@@ -74 +81 @@
         Graph::EdgeMap<T>(_G.getGraph(), a) { }
     };
-    
-    void setGraph(Graph& _graph) { graph = &_graph; }
-    Graph& getGraph() const { return (*graph); }
-  
-    //TrivGraphWrapper() : graph(0) { }
-    TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
   };
 
@@ -98 +99 @@
     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     typedef typename Graph::EachEdgeIt EachEdgeIt;
+
+    //RevGraphWrapper() : graph(0) { }
+    RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
+
+    void setGraph(Graph& _graph) { graph = &_graph; }
+    Graph& getGraph() const { return (*graph); }
     
     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
@@ -145 +152 @@
         Graph::NodeMap<T>(_G.getGraph(), a) { }
     };
+
     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
     public:
@@ -152 +160 @@
         Graph::EdgeMap<T>(_G.getGraph(), a) { }
     };
-
-    void setGraph(Graph& _graph) { graph = &_graph; }
-    Graph& getGraph() const { return (*graph); }
-
-    //RevGraphWrapper() : graph(0) { }
-    RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
   };
 
@@ -183 +185 @@
     //public:
 
+    //UndirGraphWrapper() : graph(0) { }
+    UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
+
+    void setGraph(Graph& _graph) { graph = &_graph; }
+    Graph& getGraph() const { return (*graph); }
+  
     class EdgeIt {
       friend class UndirGraphWrapper<Graph>;
@@ -197 +205 @@
     class OutEdgeIt : public EdgeIt {
       friend class UndirGraphWrapper<Graph>;
-      //bool out_or_in; //true iff out
-      //GraphOutEdgeIt out;
-      //GraphInEdgeIt in;
     public:
       OutEdgeIt() : EdgeIt() { }
@@ -288 +293 @@
         Graph::NodeMap<T>(_G.getGraph(), a) { }
     };
+
     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
     public:
@@ -295 +301 @@
         Graph::EdgeMap<T>(_G.getGraph(), a) { }
     };
-    
-    void setGraph(Graph& _graph) { graph = &_graph; }
-    Graph& getGraph() const { return (*graph); }
-  
-    //TrivGraphWrapper() : graph(0) { }
-    UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
   };
 
@@ -387 +387 @@
     const CapacityMap* capacity;
   public:
+
     ResGraphWrapper(const Graph& _G, FlowMap& _flow, 
              const CapacityMap& _capacity) : 
@@ -392 +393 @@
 //     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : 
 //       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
-    void setGraph(Graph& _graph) { graph = &_graph; }
-    Graph& getGraph() const { return (*graph); }
+
+    void setGraph(const Graph& _graph) { graph = &_graph; }
+    const Graph& getGraph() const { return (*G); }
+
     class EdgeIt; 
     class OutEdgeIt; 
@@ -402 +405 @@
       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     protected:
-      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
-      const Graph* G;
-      FlowMap* flow;
-      const CapacityMap* capacity;
-      //OldSymEdgeIt sym;
+      bool out_or_in; //true, iff out
       OldOutEdgeIt out;
       OldInEdgeIt in;
-      bool out_or_in; //true, iff out
     public:
       EdgeIt() : out_or_in(true) { } 
-      EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : 
-        G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
-      //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
-      Number free() const { 
-        if (out_or_in) { 
-          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); 
-        } else { 
-          return (/*resG->*/flow->get(in)); 
+//       bool valid() const { 
+//      return out_or_in && out.valid() || in.valid(); }
+    };
+
+
+    class OutEdgeIt : public EdgeIt {
+      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
+    public:
+      OutEdgeIt() { }
+      //FIXME
+      OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }
+    private:
+      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() { 
+        resG.G->getFirst(out, v);
+        while( out.valid() && !(resG.free(out)>0) ) { ++out; }
+        if (!out.valid()) {
+          out_or_in=0;
+          resG.G->getFirst(in, v);
+          while( in.valid() && !(resG.free(in)>0) ) { ++in; }
         }
       }
-      bool valid() const { 
-        return out_or_in && out.valid() || in.valid(); }
-      void augment(Number a) const {
-        if (out_or_in) { 
-          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
-        } else { 
-          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
-        }
-      }
-      void print() { 
-        if (out_or_in) {
-          std::cout << "out "; 
-          if (out.valid()) 
-            std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out)); 
-          else 
-            std::cout << "invalid"; 
-        }
-        else {
-          std::cout << "in "; 
-          if (in.valid()) 
-            std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in)); 
-          else 
-            std::cout << "invalid"; 
-        }
-        std::cout << std::endl;
-      }
-    };
-
-    Number free(OldOutEdgeIt out) const { 
-      return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); 
-    }
-    Number free(OldInEdgeIt in) const { 
-      return (/*resG->*/flow->get(in)); 
-    }
-
-    class OutEdgeIt : public EdgeIt {
-      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
-    public:
-      OutEdgeIt() { }
-    private:
-      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 
-        //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
-        G->getFirst(out, v);
-        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
-        if (!out.valid()) {
-          out_or_in=0;
-          //in=/*resG->*/G->template first<OldInEdgeIt>(v);
-          G->getFirst(in, v);
-          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-        }
-      }
-    public:
-      OutEdgeIt& operator++() { 
-        if (out_or_in) {
-          NodeIt v=/*resG->*/G->aNode(out);
-          ++out;
-          while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
-          if (!out.valid()) {
-            out_or_in=0;
-            G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
-            while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-          }
-        } else {
-          ++in;
-          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 
-        }
-        return *this; 
-      }
+//     public:
+//       OutEdgeIt& operator++() { 
+//      if (out_or_in) {
+//        NodeIt v=/*resG->*/G->aNode(out);
+//        ++out;
+//        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+//        if (!out.valid()) {
+//          out_or_in=0;
+//          G->getFirst(in, v); 
+//          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+//        }
+//      } else {
+//        ++in;
+//        while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 
+//      }
+//      return *this; 
+//       }
     };
 
@@ -498 +456 @@
       EachEdgeIt() { }
       //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
-      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 
-        out_or_in=true;
-        G->getFirst(v);
-        if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
-        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+      EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() { 
+        resG.G->getFirst(v);
+        if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();
+        while (out.valid() && !(resG.free(out)>0) ) { ++out; }
         while (v.valid() && !out.valid()) { 
           ++v; 
-          if (v.valid()) G->getFirst(out, v); 
-          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+          if (v.valid()) resG.G->getFirst(out, v); 
+          while (out.valid() && !(resG.free(out)>0) ) { ++out; }
         }
         if (!out.valid()) {
           out_or_in=0;
-          G->getFirst(v);
-          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
-          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+          resG.G->getFirst(v);
+          if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();
+          while (in.valid() && !(resG.free(in)>0) ) { ++in; }
           while (v.valid() && !in.valid()) { 
             ++v; 
-            if (v.valid()) G->getFirst(in, v); 
-            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+            if (v.valid()) resG.G->getFirst(in, v); 
+            while (in.valid() && !(resG.free(in)>0) ) { ++in; }
           }
         }
       }
-      EachEdgeIt& operator++() { 
-        if (out_or_in) {
-          ++out;
-          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
-          while (v.valid() && !out.valid()) { 
-            ++v; 
-            if (v.valid()) G->getFirst(out, v); 
-            while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
-          }
-          if (!out.valid()) {
-            out_or_in=0;
-            G->getFirst(v);
-            if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
-            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-            while (v.valid() && !in.valid()) { 
-              ++v; 
-              if (v.valid()) G->getFirst(in, v); 
-              while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-            }  
-          }
-        } else {
-          ++in;
-          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-          while (v.valid() && !in.valid()) { 
-            ++v; 
-            if (v.valid()) G->getFirst(in, v); 
-            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-          }
-        }
-        return *this;
-      }
-    };
-
-    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
-    void getFirst(OutEdgeIt& e, NodeIt v) const { 
-      e=OutEdgeIt(*G, v, *flow, *capacity); 
-    }
-    void getFirst(EachEdgeIt& e) const { 
-      e=EachEdgeIt(*G, *flow, *capacity); 
+//       EachEdgeIt& operator++() { 
+//      if (out_or_in) {
+//        ++out;
+//        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+//        while (v.valid() && !out.valid()) { 
+//          ++v; 
+//          if (v.valid()) G->getFirst(out, v); 
+//          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+//        }
+//        if (!out.valid()) {
+//          out_or_in=0;
+//          G->getFirst(v);
+//          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
+//          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+//          while (v.valid() && !in.valid()) { 
+//            ++v; 
+//            if (v.valid()) G->getFirst(in, v); 
+//            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+//          }  
+//        }
+//      } else {
+//        ++in;
+//        while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+//        while (v.valid() && !in.valid()) { 
+//          ++v; 
+//          if (v.valid()) G->getFirst(in, v); 
+//          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+//        }
+//      }
+//      return *this;
+//       }
+    };
+
+    EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }
+    OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const { 
+      e=OutEdgeIt(*this, v); 
+    }
+    EachEdgeIt& getFirst(EachEdgeIt& e) const { 
+      e=EachEdgeIt(*this); 
     }
    
@@ -567 +524 @@
         NodeIt v=G->aNode(e.out);
         ++(e.out);
-        while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
+        while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
         if (!G->valid(e.out)) {
           e.out_or_in=0;
-          G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
-          while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+          G->getFirst(e.in, v); 
+          while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
         }
       } else {
         ++(e.in);
-        while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); } 
+        while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } 
       }
       return e;
@@ -583 +540 @@
       if (e.out_or_in) {
         ++(e.out);
-        while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
+        while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
           while (G->valid(e.v) && !G->valid(e.out)) { 
             ++(e.v); 
             if (G->valid(e.v)) G->getFirst(e.out, e.v); 
-            while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
+            while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
           }
           if (!G->valid(e.out)) {
@@ -593 +550 @@
             G->getFirst(e.v);
             if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
-            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+            while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
             while (G->valid(e.v) && !G->valid(e.in)) { 
               ++(e.v); 
               if (G->valid(e.v)) G->getFirst(e.in, e.v); 
-              while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+              while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
             }  
           }
         } else {
           ++(e.in);
-          while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+          while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
           while (G->valid(e.v) && !G->valid(e.in)) { 
             ++(e.v); 
             if (G->valid(e.v)) G->getFirst(e.in, e.v); 
-            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+            while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
           }
         }
@@ -642 +599 @@
     bool valid(EdgeIt e) const { 
       return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
+
+    void augment(const EdgeIt& e, Number a) const {
+      if (e.out_or_in)  
+        flow->set(e.out, flow->get(e.out)+a);
+      else  
+        flow->set(e.in, flow->get(e.in)-a);
+    }
+
+    Number free(const EdgeIt& e) const { 
+      if (e.out_or_in) 
+        return (capacity->get(e.out)-flow->get(e.out)); 
+      else 
+        return (flow->get(e.in)); 
+    }
+
+    Number free(OldOutEdgeIt out) const { 
+      return (capacity->get(out)-flow->get(out)); 
+    }
+    
+    Number free(OldInEdgeIt in) const { 
+      return (flow->get(in)); 
+    }
 
     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
@@ -680 +659 @@
       }
     };
+  };
+
+  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+  class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
+  protected:
+    ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
+    //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
+  public:
+    ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow, 
+                           const CapacityMap& _capacity) : 
+      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), 
+      first_out_edges(*this) /*, dist(*this)*/ { 
+      for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {
+        OutEdgeIt e;
+        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
+        first_out_edges.set(n, e);
+      }
+    }
+
+    //void setGraph(Graph& _graph) { graph = &_graph; }
+    //Graph& getGraph() const { return (*graph); }
+  
+    //TrivGraphWrapper() : graph(0) { }
+    //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
+
+    //typedef Graph BaseGraph;
+
+    //typedef typename Graph::NodeIt NodeIt;
+    //typedef typename Graph::EachNodeIt EachNodeIt;
+
+    //typedef typename Graph::EdgeIt EdgeIt;
+    //typedef typename Graph::OutEdgeIt OutEdgeIt;
+    //typedef typename Graph::InEdgeIt InEdgeIt;
+    //typedef typename Graph::SymEdgeIt SymEdgeIt;
+    //typedef typename Graph::EachEdgeIt EachEdgeIt;
+
+    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
+    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
+
+    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
+    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
+    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
+    //typedef typename Graph::SymEdgeIt SymEdgeIt;
+    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
+
+    EachNodeIt& getFirst(EachNodeIt& n) const { 
+      return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
+    }
+
+    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { 
+      e=first_out_edges.get(n);
+      return e;
+    }
+    
+    //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }
+    //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
+    //  return getFirst(i, p); }
+    
+    //template<typename I> I getNext(const I& i) const { 
+    //  return graph->getNext(i); }
+    //template<typename I> I& next(I &i) const { return graph->next(i); }    
+
+    template< typename It > It first() const { 
+      It e; getFirst(e); return e; }
+
+    template< typename It > It first(const NodeIt& v) const { 
+      It e; getFirst(e, v); return e; }
+
+    //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
+    //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
+
+    //template<typename I> bool valid(const I& i) const 
+    //  { return graph->valid(i); }
+  
+    //int nodeNum() const { return graph->nodeNum(); }
+    //int edgeNum() const { return graph->edgeNum(); }
+  
+    //template<typename I> NodeIt aNode(const I& e) const { 
+    //  return graph->aNode(e); }
+    //template<typename I> NodeIt bNode(const I& e) const { 
+    //  return graph->bNode(e); }
+  
+    //NodeIt addNode() const { return graph->addNode(); }
+    //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
+    //  return graph->addEdge(tail, head); }
+  
+    //void erase(const OutEdgeIt& e) {
+    //  first_out_edge(this->tail(e))=e;
+    //}
+    void erase(const EdgeIt& e) {
+      OutEdgeIt f(e);
+      next(f);
+      first_out_edges.set(this->tail(e), f);
+    }
+    //template<typename I> void erase(const I& i) const { graph->erase(i); }
+  
+    //void clear() const { graph->clear(); }
+    
+    template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> { 
+    public:
+      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : 
+        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
+      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : 
+        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
+    };
+
+    template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> { 
+    public:
+      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : 
+        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
+      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : 
+        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
+    };
+  };
+
+  template<typename GraphWrapper> 
+  class FilterGraphWrapper {
+  };
+
+  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+  class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
+
+    //Graph* graph;
+  
+  public:
+    //typedef Graph BaseGraph;
+
+    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
+    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
+
+    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
+    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
+    //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
+    //typedef typename Graph::SymEdgeIt SymEdgeIt;
+    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
+
+    //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
+    
+  public:
+    FilterGraphWrapper(const Graph& _G, FlowMap& _flow, 
+                           const CapacityMap& _capacity) : 
+      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) { 
+    }
+
+    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
+      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
+      while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
+      return e;
+    }
+
+    EachNodeIt& next(EachNodeIt& e) const {
+      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
+    }
+
+    OutEdgeIt& next(OutEdgeIt& e) const {
+      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
+      while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
+      return e;
+    }
+
+    EachNodeIt& getFirst(EachNodeIt& n) const {
+      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
+    }
+
+    void erase(const EdgeIt& e) {
+      OutEdgeIt f(e);
+      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
+      while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f)))) 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
+      first_out_edges.set(this->tail(e), f);
+    }
+
+    //TrivGraphWrapper() : graph(0) { }
+    //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
+
+    //void setGraph(Graph& _graph) { graph = &_graph; }
+    //Graph& getGraph() const { return (*graph); }
+    
+    //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
+    //template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
+    //  return graph->getFirst(i, p); }
+    
+    //template<typename I> I getNext(const I& i) const { 
+    //  return graph->getNext(i); }
+    //template<typename I> I& next(I &i) const { return graph->next(i); }    
+
+    template< typename It > It first() const { 
+      It e; getFirst(e); return e; }
+
+    template< typename It > It first(const NodeIt& v) const { 
+      It e; getFirst(e, v); return e; }
+
+    //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
+    //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
+
+    //template<typename I> bool valid(const I& i) const 
+    //  { return graph->valid(i); }
+  
+    //template<typename I> void setInvalid(const I &i);
+    //{ return graph->setInvalid(i); }
+
+    //int nodeNum() const { return graph->nodeNum(); }
+    //int edgeNum() const { return graph->edgeNum(); }
+  
+    //template<typename I> NodeIt aNode(const I& e) const { 
+    //  return graph->aNode(e); }
+    //template<typename I> NodeIt bNode(const I& e) const { 
+    //  return graph->bNode(e); }
+  
+    //NodeIt addNode() const { return graph->addNode(); }
+    //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
+    //  return graph->addEdge(tail, head); }
+  
+    //template<typename I> void erase(const I& i) const { graph->erase(i); }
+  
+    //void clear() const { graph->clear(); }
+    
+    template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> { 
+    public:
+      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) : 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
+      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) : 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
+    };
+
+    template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> { 
+    public:
+      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) : 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
+      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) : 
+        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
+    };
+
+  public:
+    ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
 
   };

src/work/marci/makefile

@@ -17 +17 @@
 
 edmonds_karp_demo: 
-        $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
-        $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo.cc
+        $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
+        $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo_prof.cc
 
 edmonds_karp_demo_alpar: 

src/work/marci_graph_demo.cc

@@ -237 +237 @@
     }
     std::cout<<std::endl;*/
-    max_flow_test.run();
+    //max_flow_test.run();
     
-    std::cout << "maximum flow: "<< std::endl;
-    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
-      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
-    }
-    std::cout<<std::endl;
+    //std::cout << "maximum flow: "<< std::endl;
+    while (max_flow_test.augmentOnShortestPath()) {
+      for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
+        std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
+      }
+      std::cout<<std::endl;
+    }
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   }