src/work/marci/lg_vs_sg.cc
author marci
Fri, 14 May 2004 18:28:57 +0000
changeset 642 e812963087f0
parent 640 d426dca0aaf7
permissions -rw-r--r--
To avoid confusion my old ListGraph is can be used under name SageGraph, work/sage_graph.h contains it.
     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 <max_flow.h>
    11 #include <hugo/time_measure.h>
    12 #include <hugo/for_each_macros.h>
    13 
    14 using namespace hugo;
    15 
    16 // Use a DIMACS max flow file as stdin.
    17 // read_dimacs_demo dimacs_max_flow_file
    18 
    19 int main(int, char** argv) {
    20 
    21   std::string in=argv[1];
    22   typedef SageGraph MutableGraph;
    23 
    24   {
    25     typedef SageGraph Graph;
    26     typedef Graph::Node Node;
    27     typedef Graph::EdgeIt EdgeIt;
    28 
    29     Graph g;
    30     Node s, t;
    31     Graph::EdgeMap<int> cap(g);
    32     std::ifstream ins(in.c_str());
    33     //readDimacsMaxFlow(ins, g, s, t, cap);
    34     readDimacs(ins, g, cap, s, t);
    35 
    36     Timer ts;
    37     Graph::EdgeMap<int> flow(g); //0 flow
    38     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    39       max_flow_test(g, s, t, cap, flow/*, true*/);
    40 
    41     std::cout << "SageGraph ..." << std::endl;
    42 
    43     {
    44       std::cout << "preflow ..." << std::endl;
    45       ts.reset();
    46       max_flow_test.run();
    47       std::cout << "elapsed time: " << ts << std::endl;
    48       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    49     }
    50 
    51     {
    52       std::cout << "physical blocking flow augmentation ..." << std::endl;
    53       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    54       ts.reset();
    55       int i=0;
    56       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    57       std::cout << "elapsed time: " << ts << std::endl;
    58       std::cout << "number of augmentation phases: " << i << std::endl; 
    59       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    60     }
    61 
    62 //     {
    63 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    64 //       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    65 //       ts.reset();
    66 //       int i=0;
    67 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    68 //       std::cout << "elapsed time: " << ts << std::endl;
    69 //       std::cout << "number of augmentation phases: " << i << std::endl; 
    70 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    71 //     }
    72 
    73     {
    74       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    75       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    76       ts.reset();
    77       int i=0;
    78       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    79       std::cout << "elapsed time: " << ts << std::endl;
    80       std::cout << "number of augmentation phases: " << i << std::endl; 
    81       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    82     }
    83 
    84     {
    85       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    86       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    87       ts.reset();
    88       int i=0;
    89       while (max_flow_test.augmentOnShortestPath()) { ++i; }
    90       std::cout << "elapsed time: " << ts << std::endl;
    91       std::cout << "number of augmentation phases: " << i << std::endl; 
    92       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    93     }
    94   }
    95 
    96   {
    97     typedef SmartGraph Graph;
    98     typedef Graph::Node Node;
    99     typedef Graph::EdgeIt EdgeIt;
   100 
   101     Graph g;
   102     Node s, t;
   103     Graph::EdgeMap<int> cap(g);
   104     std::ifstream ins(in.c_str());
   105     //readDimacsMaxFlow(ins, g, s, t, cap);
   106     readDimacs(ins, g, cap, s, t);
   107 
   108     Timer ts;
   109     Graph::EdgeMap<int> flow(g); //0 flow
   110     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   111       max_flow_test(g, s, t, cap, flow/*, true*/);
   112     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   113     //  max_flow_test(g, s, t, cap, flow);
   114 
   115     std::cout << "SmartGraph ..." << std::endl;
   116 
   117     {
   118       std::cout << "preflow ..." << std::endl;
   119       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   120       ts.reset();
   121       max_flow_test.run();
   122       std::cout << "elapsed time: " << ts << std::endl;
   123       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   124     }
   125 
   126     {
   127       std::cout << "physical blocking flow augmentation ..." << std::endl;
   128       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   129       ts.reset();
   130       int i=0;
   131       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
   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 << "faster physical blocking flow augmentation ..." << std::endl;
   139 //       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   140 //       ts.reset();
   141 //       int i=0;
   142 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
   143 //       std::cout << "elapsed time: " << ts << std::endl;
   144 //       std::cout << "number of augmentation phases: " << i << std::endl; 
   145 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   146 //     }
   147 
   148     {
   149       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
   150       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   151       ts.reset();
   152       int i=0;
   153       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
   154       std::cout << "elapsed time: " << ts << std::endl;
   155       std::cout << "number of augmentation phases: " << i << std::endl; 
   156       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   157     }
   158 
   159     {
   160       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
   161       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   162       ts.reset();
   163       int i=0;
   164       while (max_flow_test.augmentOnShortestPath()) { ++i; }
   165       std::cout << "elapsed time: " << ts << std::endl;
   166       std::cout << "number of augmentation phases: " << i << std::endl; 
   167       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   168     }
   169   }
   170 
   171   {
   172     typedef ListGraph Graph;
   173     typedef Graph::Node Node;
   174     typedef Graph::EdgeIt EdgeIt;
   175 
   176     Graph g;
   177     Node s, t;
   178     Graph::EdgeMap<int> cap(g);
   179     std::ifstream ins(in.c_str());
   180     //readDimacsMaxFlow(ins, g, s, t, cap);
   181     readDimacs(ins, g, cap, s, t);
   182 
   183     Timer ts;
   184     Graph::EdgeMap<int> flow(g); //0 flow
   185     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   186       max_flow_test(g, s, t, cap, flow/*, true*/);
   187     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   188     //  max_flow_test(g, s, t, cap, flow);
   189 
   190     std::cout << "ListGraph ..." << std::endl;
   191 
   192     {
   193       std::cout << "preflow ..." << std::endl;
   194       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   195       ts.reset();
   196       max_flow_test.run();
   197       std::cout << "elapsed time: " << ts << std::endl;
   198       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   199     }
   200 
   201     {
   202       std::cout << "physical blocking flow augmentation ..." << std::endl;
   203       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   204       ts.reset();
   205       int i=0;
   206       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
   207       std::cout << "elapsed time: " << ts << std::endl;
   208       std::cout << "number of augmentation phases: " << i << std::endl; 
   209       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   210     }
   211 
   212 //     {
   213 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
   214 //       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   215 //       ts.reset();
   216 //       int i=0;
   217 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
   218 //       std::cout << "elapsed time: " << ts << std::endl;
   219 //       std::cout << "number of augmentation phases: " << i << std::endl; 
   220 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   221 //     }
   222 
   223     {
   224       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
   225       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   226       ts.reset();
   227       int i=0;
   228       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
   229       std::cout << "elapsed time: " << ts << std::endl;
   230       std::cout << "number of augmentation phases: " << i << std::endl; 
   231       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   232     }
   233 
   234     {
   235       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
   236       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   237       ts.reset();
   238       int i=0;
   239       while (max_flow_test.augmentOnShortestPath()) { ++i; }
   240       std::cout << "elapsed time: " << ts << std::endl;
   241       std::cout << "number of augmentation phases: " << i << std::endl; 
   242       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   243     }
   244   }
   245 
   246 
   247 
   248 
   249   return 0;
   250 }