Changeset 174:44700ed9ffaa in lemon-0.x for src/work/marci/edmonds_karp_demo.cc

Timestamp:

03/12/04 10:19:54 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

towards on ListGraph?, SmartGraph? compatibility

File:

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

src/work/marci/edmonds_karp_demo.cc

@@ +1 @@
+// -*- c++ -*-
 #include <iostream>
 #include <fstream>
 
-#include <list_graph.hh>
-#include <dimacs.hh>
-#include <edmonds_karp.hh>
+#include <list_graph.h>
+#include <smart_graph.h>
+#include <dimacs.h>
+#include <edmonds_karp.h>
 #include <time_measure.h>
 #include <graph_wrapper.h>
@@ -13 +15 @@
 // read_dimacs_demo < dimacs_max_flow_file
 
-/*
-  struct Ize {
-  };
+
+//   struct Ize {
+//   };
   
-  struct Mize {
-    Ize bumm;
-  };
+//   struct Mize {
+//     Ize bumm;
+//   };
 
-  template <typename B>
-    class Huha {
-    public:
-      int u;
-      B brr;
-    };
-*/
+//   template <typename B>
+//     class Huha {
+//     public:
+//       int u;
+//       B brr;
+//     };
+
 
 int main(int, char **) {
-  typedef ListGraph::NodeIt NodeIt;
-  typedef ListGraph::EachEdgeIt EachEdgeIt;
 
-/*
-  Mize mize[10];
-  Mize bize[0];
-  Mize zize;
-  typedef Mize Tize[0];
+  typedef ListGraph MutableGraph;
 
-  std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
-  std::cout << sizeof(bize) << std::endl;
+  typedef SmartGraph Graph;
+  typedef Graph::Node Node;
+  typedef Graph::EdgeIt EdgeIt;
 
 
-  Huha<Tize> k;
-  std::cout << sizeof(k) << std::endl;
+//   Mize mize[10];
+//   Mize bize[0];
+//   Mize zize;
+//   typedef Mize Tize[0];
+
+//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
+//   std::cout << sizeof(bize) << std::endl;
 
 
-  struct Bumm {
-    //int a;
-    bool b;
-  };
+//   Huha<Tize> k;
+//   std::cout << sizeof(k) << std::endl;
 
-  std::cout << sizeof(Bumm) << std::endl;
-*/
 
-  ListGraph G;
-  NodeIt s, t;
-  ListGraph::EdgeMap<int> cap(G);
+//   struct Bumm {
+//     //int a;
+//     bool b;
+//   };
+
+//   std::cout << sizeof(Bumm) << std::endl;
+
+
+  Graph G;
+  Node s, t;
+  Graph::EdgeMap<int> cap(G);
   readDimacsMaxFlow(std::cin, G, s, t, cap);
-/*
-  typedef TrivGraphWrapper<ListGraph> TGW;
-  TGW gw(G);
-  TGW::EachNodeIt sw;
-  gw.getFirst(sw);
-  std::cout << "p1:" << gw.nodeNum() << std::endl;
-  gw.erase(sw);
-  std::cout << "p2:" << gw.nodeNum() << std::endl;
 
-  typedef const ListGraph cLG;
-  typedef TrivGraphWrapper<const cLG> CTGW;
-  CTGW cgw(G);
-  CTGW::EachNodeIt csw;
-  cgw.getFirst(csw);
-  std::cout << "p1:" << cgw.nodeNum() << std::endl;
-  //cgw.erase(csw);
-  std::cout << "p2:" << cgw.nodeNum() << std::endl;
-*/
+//   typedef TrivGraphWrapper<Graph> TGW;
+//   TGW gw(G);
+//   TGW::NodeIt sw;
+//   gw./*getF*/first(sw);
+//   std::cout << "p1:" << gw.nodeNum() << std::endl;
+//   gw.erase(sw);
+//   std::cout << "p2:" << gw.nodeNum() << std::endl;
+
+//   typedef const Graph cLG;
+//   typedef TrivGraphWrapper<const cLG> CTGW;
+//   CTGW cgw(G);
+//   CTGW::NodeIt csw;
+//   cgw./*getF*/first(csw);
+//   std::cout << "p1:" << cgw.nodeNum() << std::endl;
+//   //cgw.erase(csw);
+//   std::cout << "p2:" << cgw.nodeNum() << std::endl;
+
 
   {
-  std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
-  ListGraph::EdgeMap<int> flow(G); //0 flow
+    std::cout << "SmartGraph..." << std::endl;
+    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
+    Graph::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.augmentOnBlockingFlow<ListGraph>()) { 
-//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+    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.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; 
-  }
-  //double post_time=currTime();
+      ++i; 
+    }
 
-  //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 << "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 (blocking flow augmentation)..." << std::endl;
-  ListGraph::EdgeMap<int> flow(G); //0 flow
+    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
+    Graph::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) { 
+    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; 
-  }
-  //double post_time=currTime();
+      ++i; 
+    }
 
-  //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 << "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 (shortest path augmentation)..." << std::endl;
-  ListGraph::EdgeMap<int> flow(G); //0 flow
+    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
+    Graph::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.augmentOnShortestPath()) { 
-//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+    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; 
+      ++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;
   }
-  //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;
-  }
 
   return 0;