Changeset 206:47f62d789fe7 in lemon-0.x for src/work/marci

Timestamp:

03/19/04 10:09:20 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

Location:

src/work/marci

Files:

• dimacs.h (modified) (1 diff)
• edmonds_karp_demo.cc (modified) (2 diffs)

src/work/marci/dimacs.h

@@ -26 +26 @@
         getline(is, str);
         break;
-//       case 't': //type
-//      getline(is, str);
-//      break;
       case 'p': //problem definition
         is >> problem >> n >> m;

src/work/marci/edmonds_karp_demo.cc

@@ -35 +35 @@
   typedef ListGraph MutableGraph;
 
-//  typedef SmartGraph Graph;
-  typedef ListGraph Graph;
+  typedef SmartGraph Graph;
+  //typedef ListGraph Graph;
   typedef Graph::Node Node;
   typedef Graph::EdgeIt EdgeIt;
@@ -115 +115 @@
 
   {
+    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);
+    //max_flow_test.augmentWithBlockingFlow<Graph>();
+    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