src/work/marci/experiment/edmonds_karp_demo_1.cc
author deba
Mon, 04 Oct 2004 17:13:21 +0000
changeset 937 d4e911acef3d
parent 281 3fefabfd00b7
child 986 e997802b855c
permissions -rw-r--r--
Revert backport changes -r1230.
     1 // -*- c++ -*-
     2 #include <iostream>
     3 #include <fstream>
     4 
     5 #include <list_graph.h>
     6 //#include <smart_graph.h>
     7 #include <dimacs.h>
     8 #include <edmonds_karp_1.h>
     9 #include <time_measure.h>
    10 #include <graph_wrapper_1.h>
    11 
    12 class CM {
    13 public:
    14   template<typename T> int get(T) const {return 1;}
    15 };
    16 
    17 using namespace lemon;
    18 
    19 // Use a DIMACS max flow file as stdin.
    20 // read_dimacs_demo < dimacs_max_flow_file
    21 
    22 
    23 //   struct Ize {
    24 //   };
    25   
    26 //   struct Mize {
    27 //     Ize bumm;
    28 //   };
    29 
    30 //   template <typename B>
    31 //     class Huha {
    32 //     public:
    33 //       int u;
    34 //       B brr;
    35 //     };
    36 
    37 
    38 int main(int, char **) {
    39 
    40   typedef ListGraph MutableGraph;
    41 
    42   //typedef SmartGraph Graph;
    43   typedef ListGraph Graph;
    44   typedef Graph::Node Node;
    45   typedef Graph::EdgeIt EdgeIt;
    46 
    47 
    48 //   Mize mize[10];
    49 //   Mize bize[0];
    50 //   Mize zize;
    51 //   typedef Mize Tize[0];
    52 
    53 //   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
    54 //   std::cout << sizeof(bize) << std::endl;
    55 
    56 
    57 //   Huha<Tize> k;
    58 //   std::cout << sizeof(k) << std::endl;
    59 
    60 
    61 //   struct Bumm {
    62 //     //int a;
    63 //     bool b;
    64 //   };
    65 
    66 //   std::cout << sizeof(Bumm) << std::endl;
    67 
    68 
    69   Graph G;
    70   Node s, t;
    71   Graph::EdgeMap<int> cap(G);
    72   readDimacsMaxFlow(std::cin, G, s, t, cap);
    73 
    74 //   typedef TrivGraphWrapper<Graph> TGW;
    75 //   TGW gw(G);
    76 //   TGW::NodeIt sw;
    77 //   gw./*getF*/first(sw);
    78 //   std::cout << "p1:" << gw.nodeNum() << std::endl;
    79 //   gw.erase(sw);
    80 //   std::cout << "p2:" << gw.nodeNum() << std::endl;
    81 
    82 //   typedef const Graph cLG;
    83 //   typedef TrivGraphWrapper<const cLG> CTGW;
    84 //   CTGW cgw(G);
    85 //   CTGW::NodeIt csw;
    86 //   cgw./*getF*/first(csw);
    87 //   std::cout << "p1:" << cgw.nodeNum() << std::endl;
    88 //   //cgw.erase(csw);
    89 //   std::cout << "p2:" << cgw.nodeNum() << std::endl;
    90 
    91 
    92   {
    93     typedef TrivGraphWrapper<const Graph> GW;
    94     GW gw(G);
    95     std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
    96     GW::EdgeMap<int> flow(gw); //0 flow
    97 
    98     Timer ts;
    99     ts.reset();
   100 
   101     typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
   102     EMW cw(cap);
   103     MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
   104     int i=0;
   105     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 
   106 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
   107 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
   108 //     }
   109 //     std::cout<<std::endl;
   110       ++i; 
   111     }
   112 
   113 //   std::cout << "maximum flow: "<< std::endl;
   114 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
   115 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
   116 //   }
   117 //   std::cout<<std::endl;
   118     std::cout << "elapsed time: " << ts << std::endl;
   119     std::cout << "number of augmentation phases: " << i << std::endl; 
   120     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   121   }
   122 
   123   {
   124     typedef TrivGraphWrapper<const Graph> GW;
   125     GW gw(G);
   126     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
   127     GW::EdgeMap<int> flow(gw); //0 flow
   128 
   129     Timer ts;
   130     ts.reset();
   131 
   132     typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
   133     EMW cw(cap);
   134     MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
   135     int i=0;
   136     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
   137 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
   138 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
   139 //     }
   140 //     std::cout<<std::endl;
   141       ++i; 
   142     }
   143 
   144 //   std::cout << "maximum flow: "<< std::endl;
   145 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
   146 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
   147 //   }
   148 //   std::cout<<std::endl;
   149     std::cout << "elapsed time: " << ts << std::endl;
   150     std::cout << "number of augmentation phases: " << i << std::endl; 
   151     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   152   }
   153 
   154   {
   155     typedef TrivGraphWrapper<const Graph> GW;
   156     GW gw(G);
   157     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
   158     GW::EdgeMap<int> flow(gw); //0 flow
   159 
   160     Timer ts;
   161     ts.reset();
   162 
   163     typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
   164     EMW cw(cap);
   165     MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
   166     int i=0;
   167     while (max_flow_test.augmentOnBlockingFlow2()) { 
   168 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
   169 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
   170 //     }
   171 //     std::cout<<std::endl;
   172       ++i; 
   173     }
   174 
   175 //   std::cout << "maximum flow: "<< std::endl;
   176 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
   177 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
   178 //   }
   179 //   std::cout<<std::endl;
   180     std::cout << "elapsed time: " << ts << std::endl;
   181     std::cout << "number of augmentation phases: " << i << std::endl; 
   182     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   183   }
   184 
   185   {
   186     typedef TrivGraphWrapper<const Graph> GW;
   187     GW gw(G);
   188     std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
   189     GW::EdgeMap<int> flow(gw); //0 flow
   190 
   191     Timer ts;
   192     ts.reset();
   193 
   194     typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
   195     EMW cw(cap);
   196     MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw);
   197     int i=0;
   198     while (max_flow_test.augmentOnShortestPath()) { 
   199 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
   200 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
   201 //     }
   202 //     std::cout<<std::endl;
   203       ++i; 
   204     }
   205 
   206 //   std::cout << "maximum flow: "<< std::endl;
   207 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
   208 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
   209 //   }
   210 //   std::cout<<std::endl;
   211     std::cout << "elapsed time: " << ts << std::endl;
   212     std::cout << "number of augmentation phases: " << i << std::endl; 
   213     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   214   }
   215 
   216 
   217   return 0;
   218 }