src/work/marci/lg_vs_sg.cc
author marci
Thu, 06 May 2004 16:54:54 +0000
changeset 555 995bc1f1a3ce
parent 480 4fb0d1e166ea
child 577 e8703f0a6e2f
permissions -rw-r--r--
#include <hugo/ > modifications
     1 // -*- c++ -*-
     2 #include <iostream>
     3 #include <fstream>
     4 #include <string>
     5 
     6 #include <list_graph.h>
     7 #include <hugo/smart_graph.h>
     8 #include <hugo/dimacs.h>
     9 #include <max_flow.h>
    10 #include <hugo/time_measure.h>
    11 #include <for_each_macros.h>
    12 
    13 using namespace hugo;
    14 
    15 // Use a DIMACS max flow file as stdin.
    16 // read_dimacs_demo dimacs_max_flow_file
    17 
    18 int main(int, char** argv) {
    19 
    20   std::string in=argv[1];
    21   typedef ListGraph MutableGraph;
    22 
    23   {
    24     typedef ListGraph Graph;
    25     typedef Graph::Node Node;
    26     typedef Graph::EdgeIt EdgeIt;
    27 
    28     Graph G;
    29     Node s, t;
    30     Graph::EdgeMap<int> cap(G);
    31     std::ifstream ins(in.c_str());
    32     readDimacsMaxFlow(ins, G, s, t, cap);
    33 
    34     Timer ts;
    35     Graph::EdgeMap<int> flow(G); //0 flow
    36     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    37       max_flow_test(G, s, t, cap, flow/*, true*/);
    38 
    39     std::cout << "ListGraph ..." << std::endl;
    40 
    41     {
    42       std::cout << "preflow ..." << std::endl;
    43       ts.reset();
    44       max_flow_test.run();
    45       std::cout << "elapsed time: " << ts << std::endl;
    46       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    47     }
    48 
    49     {
    50       std::cout << "physical blocking flow augmentation ..." << std::endl;
    51       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    52       ts.reset();
    53       int i=0;
    54       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    55       std::cout << "elapsed time: " << ts << std::endl;
    56       std::cout << "number of augmentation phases: " << i << std::endl; 
    57       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    58     }
    59 
    60 //     {
    61 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    62 //       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    63 //       ts.reset();
    64 //       int i=0;
    65 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    66 //       std::cout << "elapsed time: " << ts << std::endl;
    67 //       std::cout << "number of augmentation phases: " << i << std::endl; 
    68 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    69 //     }
    70 
    71     {
    72       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    73       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    74       ts.reset();
    75       int i=0;
    76       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    77       std::cout << "elapsed time: " << ts << std::endl;
    78       std::cout << "number of augmentation phases: " << i << std::endl; 
    79       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    80     }
    81 
    82     {
    83       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    84       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    85       ts.reset();
    86       int i=0;
    87       while (max_flow_test.augmentOnShortestPath()) { ++i; }
    88       std::cout << "elapsed time: " << ts << std::endl;
    89       std::cout << "number of augmentation phases: " << i << std::endl; 
    90       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    91     }
    92   }
    93 
    94 
    95   {
    96     typedef SmartGraph Graph;
    97     typedef Graph::Node Node;
    98     typedef Graph::EdgeIt EdgeIt;
    99 
   100     Graph G;
   101     Node s, t;
   102     Graph::EdgeMap<int> cap(G);
   103     std::ifstream ins(in.c_str());
   104     readDimacsMaxFlow(ins, G, s, t, cap);
   105 
   106     Timer ts;
   107     Graph::EdgeMap<int> flow(G); //0 flow
   108     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   109       max_flow_test(G, s, t, cap, flow/*, true*/);
   110     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   111     //  max_flow_test(G, s, t, cap, flow);
   112 
   113     std::cout << "SmatrGraph ..." << std::endl;
   114 
   115     {
   116       std::cout << "preflow ..." << std::endl;
   117       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   118       ts.reset();
   119       max_flow_test.run();
   120       std::cout << "elapsed time: " << ts << std::endl;
   121       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   122     }
   123 
   124     {
   125       std::cout << "physical blocking flow augmentation ..." << std::endl;
   126       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   127       ts.reset();
   128       int i=0;
   129       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
   130       std::cout << "elapsed time: " << ts << std::endl;
   131       std::cout << "number of augmentation phases: " << i << std::endl; 
   132       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   133     }
   134 
   135 //     {
   136 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
   137 //       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   138 //       ts.reset();
   139 //       int i=0;
   140 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
   141 //       std::cout << "elapsed time: " << ts << std::endl;
   142 //       std::cout << "number of augmentation phases: " << i << std::endl; 
   143 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   144 //     }
   145 
   146     {
   147       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
   148       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   149       ts.reset();
   150       int i=0;
   151       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
   152       std::cout << "elapsed time: " << ts << std::endl;
   153       std::cout << "number of augmentation phases: " << i << std::endl; 
   154       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   155     }
   156 
   157     {
   158       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
   159       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   160       ts.reset();
   161       int i=0;
   162       while (max_flow_test.augmentOnShortestPath()) { ++i; }
   163       std::cout << "elapsed time: " << ts << std::endl;
   164       std::cout << "number of augmentation phases: " << i << std::endl; 
   165       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   166     }
   167   }
   168 
   169 
   170 
   171 
   172   return 0;
   173 }