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 marci
Tue, 14 Sep 2004 10:09:24 +0000
changeset 849 cc3867a7d380
parent 762 511200bdb71f
child 921 818510fa3d99
permissions -rw-r--r--
(none) 
     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