src/work/marci/gw_vs_not.cc
author athos
Tue, 11 May 2004 16:38:17 +0000
changeset 611 83530dad618a
child 921 818510fa3d99
permissions -rw-r--r--
Some modifications and another testfile.
     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.h>
     9 #include <time_measure.h>
    10 #include <graph_wrapper.h>
    11 
    12 using namespace hugo;
    13 
    14 // Use a DIMACS max flow file as stdin.
    15 // read_dimacs_demo < dimacs_max_flow_file
    16 
    17 int main(int, char **) {
    18 
    19   typedef ListGraph MutableGraph;
    20   //typedef SmartGraph Graph;
    21   typedef ListGraph Graph;
    22   typedef Graph::Node Node;
    23   typedef Graph::EdgeIt EdgeIt;
    24 
    25   Graph G;
    26   Node s, t;
    27   Graph::EdgeMap<int> cap(G);
    28   readDimacsMaxFlow(std::cin, G, s, t, cap);
    29 
    30   {
    31     typedef TrivGraphWrapper<const Graph> GW;
    32     GW gw(G);
    33     typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
    34     EMW cw(cap);
    35     Timer ts;
    36     GW::EdgeMap<int> flow(gw); 
    37     MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
    38     int i;
    39 
    40     {
    41       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
    42       for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
    43       ts.reset();
    44 
    45       i=0;
    46       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    47 
    48       std::cout << "elapsed time: " << ts << std::endl;
    49       std::cout << "number of augmentation phases: " << i << std::endl; 
    50       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    51     }
    52 
    53     {
    54       std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
    55       for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
    56       ts.reset();
    57 
    58       i=0;
    59       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    60 
    61       std::cout << "elapsed time: " << ts << std::endl;
    62       std::cout << "number of augmentation phases: " << i << std::endl; 
    63       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    64     }
    65 
    66     {
    67       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    68       for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
    69       ts.reset();
    70 
    71       i=0;
    72       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    73 
    74       std::cout << "elapsed time: " << ts << std::endl;
    75       std::cout << "number of augmentation phases: " << i << std::endl; 
    76       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    77     }
    78 
    79     {
    80       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
    81       for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
    82       ts.reset();
    83 
    84       i=0;
    85       while (max_flow_test.augmentOnShortestPath()) { ++i; }
    86 
    87       std::cout << "elapsed time: " << ts << std::endl;
    88       std::cout << "number of augmentation phases: " << i << std::endl; 
    89       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    90     }
    91   }
    92 
    93 
    94 
    95 
    96   {
    97     typedef TrivGraphWrapper<const Graph> GW1;
    98     GW1 gw1(G);
    99     typedef TrivGraphWrapper<const GW1> GW2;
   100     GW2 gw2(gw1);
   101     typedef TrivGraphWrapper<const GW2> GW3;
   102     GW3 gw3(gw2);
   103     typedef TrivGraphWrapper<const GW3> GW4;
   104     GW4 gw4(gw3);
   105     typedef TrivGraphWrapper<const GW4> GW5;
   106     GW5 gw5(gw4);
   107     typedef TrivGraphWrapper<const GW5> GW6;
   108     GW6 gw6(gw5);
   109     typedef TrivGraphWrapper<const GW6> GW7;
   110     GW7 gw7(gw6);
   111     typedef TrivGraphWrapper<const GW7> GW8;
   112     GW8 gw8(gw7);
   113     typedef TrivGraphWrapper<const GW8> GW9;
   114     GW9 gw9(gw8);
   115     typedef TrivGraphWrapper<const GW9> GW;
   116     GW gw(gw9);
   117     typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
   118     EMW cw(cap);
   119     Timer ts;
   120     GW::EdgeMap<int> flow(gw); 
   121     MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
   122     int i;
   123 
   124     {
   125       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
   126       for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
   127       ts.reset();
   128 
   129       i=0;
   130       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
   131 
   132       std::cout << "elapsed time: " << ts << std::endl;
   133       std::cout << "number of augmentation phases: " << i << std::endl; 
   134       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   135     }
   136 
   137     {
   138       std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
   139       for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
   140       ts.reset();
   141 
   142       i=0;
   143       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
   144 
   145       std::cout << "elapsed time: " << ts << std::endl;
   146       std::cout << "number of augmentation phases: " << i << std::endl; 
   147       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   148     }
   149 
   150     {
   151       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
   152       for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
   153       ts.reset();
   154 
   155       i=0;
   156       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
   157 
   158       std::cout << "elapsed time: " << ts << std::endl;
   159       std::cout << "number of augmentation phases: " << i << std::endl; 
   160       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   161     }
   162 
   163     {
   164       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
   165       for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
   166       ts.reset();
   167 
   168       i=0;
   169       while (max_flow_test.augmentOnShortestPath()) { ++i; }
   170 
   171       std::cout << "elapsed time: " << ts << std::endl;
   172       std::cout << "number of augmentation phases: " << i << std::endl; 
   173       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   174     }
   175   }
   176 
   177 
   178   return 0;
   179 }