Changeset 266:4cec4981dfd1 in lemon-0.x for src/work/marci/edmonds_karp_demo.cc

Timestamp:

03/30/04 19:16:53 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

GraphWrappers?, MapWrappers?

File:

• src/work/marci/edmonds_karp_demo.cc (modified) (4 diffs)

src/work/marci/edmonds_karp_demo.cc

@@ -9 +9 @@
 #include <time_measure.h>
 #include <graph_wrapper.h>
+
+class CM {
+public:
+  template<typename T> int get(T) const {return 1;}
+};
 
 using namespace hugo;
@@ -87 +92 @@
   {
     //std::cout << "SmartGraph..." << std::endl;
+    typedef TrivGraphWrapper<const Graph> GW;
+    GW gw(G);
     std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
-    Graph::EdgeMap<int> flow(G); //0 flow
+    GW::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);
-    //max_flow_test.augmentWithBlockingFlow<Graph>();
+    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
+    EMW cw(cap);
+    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(G, s, t, flow, cw);
     int i=0;
     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 
@@ -114 +122 @@
   }
 
+//   {
+//     //std::cout << "SmartGraph..." << std::endl;
+//     std::cout << "edmonds karp demo (physical blocking flow 1 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.augmentOnBlockingFlow1<MutableGraph>()) { 
+// //     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;
+//   }
+
+//   {
+//     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;
+//   }
+
   {
-    //std::cout << "SmartGraph..." << std::endl;
-    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
-    Graph::EdgeMap<int> flow(G); //0 flow
+    typedef TrivGraphWrapper<const Graph> GW;
+    GW gw(G);
+    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
+    GW::EdgeMap<int> flow(gw); //0 flow
 
     Timer ts;
     ts.reset();
 
-    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
-    //max_flow_test.augmentWithBlockingFlow<Graph>();
+    //CM cm;
+    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.augmentOnBlockingFlow1<MutableGraph>()) { 
+    while (max_flow_test.augmentOnShortestPath()) { 
 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
@@ -143 +209 @@
   }
 
-  {
-    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);
-    //max_flow_test.augmentWithBlockingFlow<Graph>();
-    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;
-  }
-
-  {
-    std::cout << "edmonds karp demo (on-the-fly shortest path 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);
-    //max_flow_test.augmentWithBlockingFlow<Graph>();
-    int i=0;
-    while (max_flow_test.augmentOnShortestPath()) { 
-//     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;
-  }
-
 
   return 0;