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.cc
author beckerjc
Sat, 17 Apr 2004 19:19:57 +0000
changeset 349 42c660f58702
parent 174 44700ed9ffaa
child 379 a5bff2813c4d
permissions -rw-r--r--
Kruskal lenyegeben kesz.
Kell meg dokumentalni, meg meg egy par jol hasznalhato wrapper fv.
Es valamit meg kene csinalni azzal, hogy nem const ref. a kimeno boolmap,
viszont sokszor "on-the-fly" akarjuk megkonstrualni (es ilyenkor persze a
const-os mapet is lehet set-elni...) 
     1 // -*- c++ -*-

     2 #include <iostream>

     3 #include <fstream>

     4 #include <string>

     5 

     6 #include <list_graph.h>

     7 #include <smart_graph.h>

     8 #include <dimacs.h>

     9 #include <edmonds_karp.h>

    10 #include <preflow.h>

    11 #include <time_measure.h>

    12 #include <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 ListGraph MutableGraph;

    23 

    24   {

    25     typedef ListGraph 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 

    35     Timer ts;

    36     Graph::EdgeMap<int> flow(G); //0 flow

    37     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

    38       pre_flow_test(G, s, t, cap, flow);

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

    40       max_flow_test(G, s, t, cap, flow);

    41 

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

    43 

    44     {

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

    46       ts.reset();

    47       pre_flow_test.run();

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

    49       std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;

    50     }

    51 

    52     {

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

    54       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);

    55       ts.reset();

    56       int i=0;

    57       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

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

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

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

    61     }

    62 

    63     {

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

    65       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);

    66       ts.reset();

    67       int i=0;

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

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

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

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

    72     }

    73 

    74     {

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

    76       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);

    77       ts.reset();

    78       int i=0;

    79       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }

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

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

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

    83     }

    84 

    85     {

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

    87       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);

    88       ts.reset();

    89       int i=0;

    90       while (max_flow_test.augmentOnShortestPath()) { ++i; }

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

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

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

    94     }

    95   }

    96 

    97 

    98   {

    99     typedef SmartGraph Graph;

   100     typedef Graph::Node Node;

   101     typedef Graph::EdgeIt EdgeIt;

   102 

   103     Graph G;

   104     Node s, t;

   105     Graph::EdgeMap<int> cap(G);

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

   107     readDimacsMaxFlow(ins, G, s, t, cap);

   108 

   109     Timer ts;

   110     Graph::EdgeMap<int> flow(G); //0 flow

   111     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 

   112       pre_flow_test(G, s, t, cap, flow);

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

   114       max_flow_test(G, s, t, cap, flow);

   115 

   116     std::cout << "SmatrGraph ..." << std::endl;

   117 

   118     {

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

   120       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);

   121       ts.reset();

   122       pre_flow_test.run();

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

   124       std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;

   125     }

   126 

   127     {

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

   129       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);

   130       ts.reset();

   131       int i=0;

   132       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

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

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

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

   136     }

   137 

   138     {

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

   140       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);

   141       ts.reset();

   142       int i=0;

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

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

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

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

   147     }

   148 

   149     {

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

   151       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);

   152       ts.reset();

   153       int i=0;

   154       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }

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

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

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

   158     }

   159 

   160     {

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

   162       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);

   163       ts.reset();

   164       int i=0;

   165       while (max_flow_test.augmentOnShortestPath()) { ++i; }

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

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

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

   169     }

   170   }

   171 

   172 

   173 

   174 

   175   return 0;

   176 }
lemon-0.x