Changeset 168:27fbd1559fb7 in lemon-0.x for src/work/marci/edmonds_karp_demo.cc

Timestamp:

03/11/04 15:15:07 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

graph wrapper improvements, blocking flow on fly

File:

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

src/work/marci/edmonds_karp_demo.cc

@@ -88 +88 @@
   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
   int i=0;
-  while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; }
+  while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { 
+//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//     }
+//     std::cout<<std::endl;
+    ++i; 
+  }
+  //double post_time=currTime();
+
+  //std::cout << "maximum flow: "<< std::endl;
+  //for(EachEdgeIt e=G.first<EachEdgeIt>(); 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 (blocking flow augmentation)..." << std::endl;
+  ListGraph::EdgeMap<int> flow(G); //0 flow
+
+  Timer ts;
+  ts.reset();
+  //double pre_time=currTime();
+  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
+  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
+  int i=0;
+  while (max_flow_test.augmentOnBlockingFlow2()) { 
+//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//     }
+//     std::cout<<std::endl;
+    ++i; 
+  }
   //double post_time=currTime();
 
@@ -111 +146 @@
   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
   int i=0;
-  while (max_flow_test.augmentOnShortestPath()) { ++i; }
+  while (max_flow_test.augmentOnShortestPath()) { 
+//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//     }
+//     std::cout<<std::endl;
+    ++i; 
+  }
   //double post_time=currTime();