src/work/marci/lg_vs_sg_vs_sg.cc
author marci
Tue, 31 Aug 2004 17:54:22 +0000
changeset 777 a82713ed19f3
parent 762 511200bdb71f
child 921 818510fa3d99
permissions -rw-r--r--
graph_wrapper.h is ready for hugo 0.2
     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 }