Changeset 268:f4eb1ae59b50 in lemon-0.x for src/work/marci

Timestamp:

03/30/04 19:47:51 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

blocking flows

File:

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

src/work/marci/edmonds_karp_demo.cc

@@ -122 +122 @@
   }
 
+  {
+    //std::cout << "SmartGraph..." << std::endl;
+    typedef TrivGraphWrapper<const Graph> GW;
+    GW gw(G);
+    std::cout << "edmonds karp demo (physical blocking flow 1 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.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 << "SmartGraph..." << std::endl;
-//     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
+//     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
 //     Graph::EdgeMap<int> flow(G); //0 flow
 
@@ -132 +163 @@
 //     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>()) { 
+//     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)<<") ";
@@ -150 +181 @@
 //   }
 
-//   {
-//     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;