Changeset 311:6635b11938fe in lemon-0.x for src/work/marci/edmonds_karp_demo.cc

Timestamp:

04/06/04 14:00:34 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

gw

File:

• src/work/marci/edmonds_karp_demo.cc (modified) (5 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;}
-};
+#include <preflow.h>
 
 using namespace hugo;
@@ -89 +85 @@
 //   std::cout << "p2:" << cgw.nodeNum() << std::endl;
 
-
-  {
-    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
+  {
+    std::cout << "preflow ..." << std::endl;
+    Graph::EdgeMap<int> flow(G); //0 flow
+
+    Timer ts;
+    ts.reset();
+
+    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
+      max_flow_test(G, s, t, cap, flow);
+    max_flow_test.run();
+//    int i=0;
+//    while (max_flow_test.augmentOnBlockingFlow<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 << "physical blocking flow augmentation ..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
 
@@ -119 +143 @@
 
   {
-    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
+    std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
 
@@ -147 +171 @@
 
   {
-    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
+    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
 
@@ -175 +199 @@
 
   {
-    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
+    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow