Changeset 269:07af3069c0b8 in lemon-0.x for src/work/marci

Timestamp:

03/31/04 17:50:21 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

Working on-the-fly with wrappers

Location:

src/work/marci

Files:

• edmonds_karp_demo.cc (modified) (4 diffs)
• graph_wrapper.h (modified) (10 diffs)

src/work/marci/edmonds_karp_demo.cc

@@ -91 +91 @@
 
   {
-    //std::cout << "SmartGraph..." << std::endl;
     typedef TrivGraphWrapper<const Graph> GW;
     GW gw(G);
@@ -123 +122 @@
 
   {
-    //std::cout << "SmartGraph..." << std::endl;
     typedef TrivGraphWrapper<const Graph> GW;
     GW gw(G);
@@ -154 +152 @@
   }
 
-//   {
-//     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
-//     Graph::EdgeMap<int> flow(G); //0 flow
-
-//     Timer ts;
-//     ts.reset();
-
-//     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
-//     int i=0;
-//     while (max_flow_test.augmentOnBlockingFlow2()) { 
-// //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
-// //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-// //     }
-// //     std::cout<<std::endl;
-//       ++i; 
-//     }
-
-// //   std::cout << "maximum flow: "<< std::endl;
-// //   for(EdgeIt e=G.first<EdgeIt>(); 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;
-//   }
+  {
+    typedef TrivGraphWrapper<const Graph> GW;
+    GW gw(G);
+    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
+    GW::EdgeMap<int> flow(G); //0 flow
+
+    Timer ts;
+    ts.reset();
+
+    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
+    EMW cw(cap);
+    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
+    int i=0;
+    while (max_flow_test.augmentOnBlockingFlow2()) { 
+//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//     }
+//     std::cout<<std::endl;
+      ++i; 
+    }
+
+//   std::cout << "maximum flow: "<< std::endl;
+//   for(EdgeIt e=G.first<EdgeIt>(); 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;
+  }
 
   {
@@ -190 +192 @@
     ts.reset();
 
-    //CM cm;
     typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
     EMW cw(cap);

src/work/marci/graph_wrapper.h

@@ -1000 +1000 @@
       OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 
         resG.gw.first(out, v);
-        while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
+        while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
         if (!resG.gw.valid(out)) {
           out_or_in=0;
           resG.gw.first(in, v);
-          while( resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
+          while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
         }
       }
@@ -1012 +1012 @@
 //        Node v=/*resG->*/G->aNode(out);
 //        ++out;
-//        while( out.valid() && !(Edge::free()>0) ) { ++out; }
+//        while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
 //        if (!out.valid()) {
 //          out_or_in=0;
 //          G->first(in, v); 
-//          while( in.valid() && !(Edge::free()>0) ) { ++in; }
+//          while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
 //        }
 //      } else {
 //        ++in;
-//        while( in.valid() && !(Edge::free()>0) ) { ++in; } 
+//        while( in.valid() && !(Edge::resCap()>0) ) { ++in; } 
 //      }
 //      return *this; 
@@ -1038 +1038 @@
       EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() { 
         resG.gw.first(v);
-        if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);
-        while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
+        if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
+        while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
         while (resG.gw.valid(v) && !resG.gw.valid(out)) { 
           resG.gw.next(v); 
           if (resG.gw.valid(v)) resG.gw.first(out, v); 
-          while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
+          while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
         }
         if (!resG.gw.valid(out)) {
           out_or_in=0;
           resG.gw.first(v);
-          if (resG.gw.valid(v)) resG.gw.first(in, v); else in=/*OldInEdgeIt*/(INVALID);
-          while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
+          if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
+          while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
           while (resG.gw.valid(v) && !resG.gw.valid(in)) { 
             resG.gw.next(v); 
             if (resG.gw.valid(v)) resG.gw.first(in, v); 
-            while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
+            while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
           }
         }
@@ -1060 +1060 @@
 //      if (out_or_in) {
 //        ++out;
-//        while (out.valid() && !(Edge::free()>0) ) { ++out; }
+//        while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
 //        while (v.valid() && !out.valid()) { 
 //          ++v; 
 //          if (v.valid()) G->first(out, v); 
-//          while (out.valid() && !(Edge::free()>0) ) { ++out; }
+//          while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
 //        }
 //        if (!out.valid()) {
@@ -1070 +1070 @@
 //          G->first(v);
 //          if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
-//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
+//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
 //          while (v.valid() && !in.valid()) { 
 //            ++v; 
 //            if (v.valid()) G->first(in, v); 
-//            while (in.valid() && !(Edge::free()>0) ) { ++in; }
+//            while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
 //          }  
 //        }
 //      } else {
 //        ++in;
-//        while (in.valid() && !(Edge::free()>0) ) { ++in; }
+//        while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
 //        while (v.valid() && !in.valid()) { 
 //          ++v; 
 //          if (v.valid()) G->first(in, v); 
-//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
+//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
 //        }
 //      }
@@ -1106 +1106 @@
         Node v=gw.aNode(e.out);
         gw.next(e.out);
-        while( gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
+        while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
         if (!gw.valid(e.out)) {
           e.out_or_in=0;
           gw.first(e.in, v); 
-          while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
+          while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
         }
       } else {
         gw.next(e.in);
-        while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); } 
+        while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } 
       }
       return e;
@@ -1122 +1122 @@
       if (e.out_or_in) {
         gw.next(e.out);
-        while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
+        while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
           while (gw.valid(e.v) && !gw.valid(e.out)) { 
             gw.next(e.v); 
             if (gw.valid(e.v)) gw.first(e.out, e.v); 
-            while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
+            while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
           }
           if (!gw.valid(e.out)) {
             e.out_or_in=0;
             gw.first(e.v);
-            if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=/*OldInEdgeIt*/(INVALID);
-            while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
+            if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
+            while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
             while (gw.valid(e.v) && !gw.valid(e.in)) { 
               gw.next(e.v); 
               if (gw.valid(e.v)) gw.first(e.in, e.v); 
-              while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
+              while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
             }  
           }
         } else {
           gw.next(e.in);
-          while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
+          while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
           while (gw.valid(e.v) && !gw.valid(e.in)) { 
             gw.next(e.v); 
             if (gw.valid(e.v)) gw.first(e.in, e.v); 
-            while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
+            while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
           }
         }
@@ -1194 +1194 @@
     }
 
-    Number free(const Edge& e) const { 
+    Number resCap(const Edge& e) const { 
       if (e.out_or_in) 
         return (capacity->get(e.out)-flow->get(e.out)); 
@@ -1201 +1201 @@
     }
 
-    Number free(OldOutEdgeIt out) const { 
+    Number resCap(OldOutEdgeIt out) const { 
       return (capacity->get(out)-flow->get(out)); 
     }
     
-    Number free(OldInEdgeIt in) const { 
+    Number resCap(OldInEdgeIt in) const { 
       return (flow->get(in)); 
     }
@@ -1246 +1246 @@
       }
     };
+  };
+
+  //Subgraph on the same node-set and partial edge-set
+  template<typename GraphWrapper, typename FirstOutEdgesMap>
+  class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
+  protected:
+    FirstOutEdgesMap* first_out_edges;
+  public:
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
+
+    ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) : 
+      GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }  
+
+    template<typename I> I& first(I& i) const { 
+      gw.first(i); 
+      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+      return i;
+    }
+    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
+      e=first_out_edges->get(n);
+      return e;
+    }
+    template<typename I, typename P> I& first(I& i, const P& p) const { 
+      gw.first(i, p); 
+      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+      return i;
+    }
+    
+    //template<typename I> I getNext(const I& i) const { 
+    //  return gw.getNext(i); 
+    //}
+    template<typename I> I& next(I &i) const { 
+      gw.next(i); 
+      //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+      return i;
+    }
+    
+    template< typename It > It first() const { 
+      It e; this->first(e); return e; }
+    
+    template< typename It > It first(const Node& v) const { 
+      It e; this->first(e, v); return e; }
+
+    void erase(const OutEdgeIt& e) const {
+      OutEdgeIt f=e;
+      this->next(f);
+      first_out_edges->set(this->tail(e), f);
+    }
   };