Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/gw_vs_not.cc
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
child 921 818510fa3d99
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed. 
     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 }
lemon-0.x