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/lg_vs_sg_vs_sg.cc
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
parent 762 511200bdb71f
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 #include <string>

     5 

     6 #include <sage_graph.h>

     7 #include <hugo/list_graph.h>

     8 #include <hugo/smart_graph.h>

     9 #include <hugo/dimacs.h>

    10 #include <hugo/max_flow.h>

    11 #include <augmenting_flow.h>

    12 #include <hugo/time_measure.h>

    13 #include <for_each_macros.h>

    14 

    15 using namespace hugo;

    16 

    17 // Use a DIMACS max flow file as stdin.

    18 // read_dimacs_demo dimacs_max_flow_file

    19 

    20 int main(int, char** argv) {

    21 

    22   std::string in=argv[1];

    23   typedef SageGraph MutableGraph;

    24 

    25   {

    26     typedef SageGraph Graph;

    27     typedef Graph::Node Node;

    28     typedef Graph::EdgeIt EdgeIt;

    29 

    30     Graph g;

    31     Node s, t;

    32     Graph::EdgeMap<int> cap(g);

    33     std::ifstream ins(in.c_str());

    34     //readDimacsMaxFlow(ins, g, s, t, cap);

    35     readDimacs(ins, g, cap, s, t);

    36 

    37     Timer ts;

    38     Graph::EdgeMap<int> flow(g); //0 flow

    39     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

    40       max_flow_test(g, s, t, cap, flow/*, true*/);

    41     AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

    42       augmenting_flow_test(g, s, t, cap, flow/*, true*/);

    43 

    44     std::cout << "SageGraph ..." << std::endl;

    45 

    46     {

    47       std::cout << "preflow ..." << std::endl;

    48       ts.reset();

    49       max_flow_test.run();

    50       std::cout << "elapsed time: " << ts << std::endl;

    51       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

    52     }

    53 

    54     {

    55       std::cout << "physical blocking flow augmentation ..." << std::endl;

    56       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

    57       ts.reset();

    58       int i=0;

    59       while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

    60       std::cout << "elapsed time: " << ts << std::endl;

    61       std::cout << "number of augmentation phases: " << i << std::endl; 

    62       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

    63     }

    64 

    65 //     {

    66 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;

    67 //       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

    68 //       ts.reset();

    69 //       int i=0;

    70 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }

    71 //       std::cout << "elapsed time: " << ts << std::endl;

    72 //       std::cout << "number of augmentation phases: " << i << std::endl; 

    73 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

    74 //     }

    75 

    76     {

    77       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;

    78       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

    79       ts.reset();

    80       int i=0;

    81       while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }

    82       std::cout << "elapsed time: " << ts << std::endl;

    83       std::cout << "number of augmentation phases: " << i << std::endl; 

    84       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

    85     }

    86 

    87     {

    88       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;

    89       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

    90       ts.reset();

    91       int i=0;

    92       while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }

    93       std::cout << "elapsed time: " << ts << std::endl;

    94       std::cout << "number of augmentation phases: " << i << std::endl; 

    95       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

    96     }

    97   }

    98 

    99   {

   100     typedef SmartGraph Graph;

   101     typedef Graph::Node Node;

   102     typedef Graph::EdgeIt EdgeIt;

   103 

   104     Graph g;

   105     Node s, t;

   106     Graph::EdgeMap<int> cap(g);

   107     std::ifstream ins(in.c_str());

   108     //readDimacsMaxFlow(ins, g, s, t, cap);

   109     readDimacs(ins, g, cap, s, t);

   110 

   111     Timer ts;

   112     Graph::EdgeMap<int> flow(g); //0 flow

   113     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

   114       max_flow_test(g, s, t, cap, flow/*, true*/);

   115     AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

   116       augmenting_flow_test(g, s, t, cap, flow/*, true*/);

   117     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

   118     //  max_flow_test(g, s, t, cap, flow);

   119 

   120     std::cout << "SmartGraph ..." << std::endl;

   121 

   122     {

   123       std::cout << "preflow ..." << std::endl;

   124       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

   125       ts.reset();

   126       max_flow_test.run();

   127       std::cout << "elapsed time: " << ts << std::endl;

   128       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

   129     }

   130 

   131     {

   132       std::cout << "physical blocking flow augmentation ..." << std::endl;

   133       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

   134       ts.reset();

   135       int i=0;

   136       while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

   137       std::cout << "elapsed time: " << ts << std::endl;

   138       std::cout << "number of augmentation phases: " << i << std::endl; 

   139       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   140     }

   141 

   142 //     {

   143 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;

   144 //       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

   145 //       ts.reset();

   146 //       int i=0;

   147 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }

   148 //       std::cout << "elapsed time: " << ts << std::endl;

   149 //       std::cout << "number of augmentation phases: " << i << std::endl; 

   150 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

   151 //     }

   152 

   153     {

   154       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;

   155       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

   156       ts.reset();

   157       int i=0;

   158       while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }

   159       std::cout << "elapsed time: " << ts << std::endl;

   160       std::cout << "number of augmentation phases: " << i << std::endl; 

   161       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   162     }

   163 

   164     {

   165       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;

   166       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

   167       ts.reset();

   168       int i=0;

   169       while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }

   170       std::cout << "elapsed time: " << ts << std::endl;

   171       std::cout << "number of augmentation phases: " << i << std::endl; 

   172       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   173     }

   174   }

   175 

   176   {

   177     typedef ListGraph Graph;

   178     typedef Graph::Node Node;

   179     typedef Graph::EdgeIt EdgeIt;

   180 

   181     Graph g;

   182     Node s, t;

   183     Graph::EdgeMap<int> cap(g);

   184     std::ifstream ins(in.c_str());

   185     //readDimacsMaxFlow(ins, g, s, t, cap);

   186     readDimacs(ins, g, cap, s, t);

   187 

   188     Timer ts;

   189     Graph::EdgeMap<int> flow(g); //0 flow

   190     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

   191       max_flow_test(g, s, t, cap, flow/*, true*/);

   192     AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

   193       augmenting_flow_test(g, s, t, cap, flow/*, true*/);

   194     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

   195     //  max_flow_test(g, s, t, cap, flow);

   196 

   197     std::cout << "ListGraph ..." << std::endl;

   198 

   199     {

   200       std::cout << "preflow ..." << std::endl;

   201       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

   202       ts.reset();

   203       max_flow_test.run();

   204       std::cout << "elapsed time: " << ts << std::endl;

   205       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

   206     }

   207 

   208     {

   209       std::cout << "physical blocking flow augmentation ..." << std::endl;

   210       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

   211       ts.reset();

   212       int i=0;

   213       while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

   214       std::cout << "elapsed time: " << ts << std::endl;

   215       std::cout << "number of augmentation phases: " << i << std::endl; 

   216       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   217     }

   218 

   219 //     {

   220 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;

   221 //       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

   222 //       ts.reset();

   223 //       int i=0;

   224 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }

   225 //       std::cout << "elapsed time: " << ts << std::endl;

   226 //       std::cout << "number of augmentation phases: " << i << std::endl; 

   227 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

   228 //     }

   229 

   230     {

   231       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;

   232       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

   233       ts.reset();

   234       int i=0;

   235       while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }

   236       std::cout << "elapsed time: " << ts << std::endl;

   237       std::cout << "number of augmentation phases: " << i << std::endl; 

   238       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   239     }

   240 

   241     {

   242       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;

   243       for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);

   244       ts.reset();

   245       int i=0;

   246       while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }

   247       std::cout << "elapsed time: " << ts << std::endl;

   248       std::cout << "number of augmentation phases: " << i << std::endl; 

   249       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   250     }

   251   }

   252 

   253   return 0;

   254 }
lemon-0.x