lemon-0.x: src/work/marci/lg_vs

     1 // -*- c++ -*-

     2 #include <iostream>

     3 #include <fstream>

     4 #include <string>

     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>

    13 using namespace hugo;

    15 // Use a DIMACS max flow file as stdin.

    16 // read_dimacs_demo dimacs_max_flow_file

    18 int main(int, char** argv) {

    20   std::string in=argv[1];

    21   typedef ListGraph MutableGraph;

    23   {

    24     typedef ListGraph Graph;

    25     typedef Graph::Node Node;

    26     typedef Graph::EdgeIt EdgeIt;

    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     readDimacs(ins, g, cap, s, t);

    35     Timer ts;

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

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

    38       max_flow_test(g, s, t, cap, flow/*, true*/);

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

    42     {

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

    44       ts.reset();

    45       max_flow_test.run();

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

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

    48     }

    50     {

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

    52       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

    53       ts.reset();

    54       int i=0;

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

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

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

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

    59     }

    61 //     {

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

    63 //       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

    64 //       ts.reset();

    65 //       int i=0;

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

    67 //       std::cout << "elapsed time: " << ts << std::endl;

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

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

    70 //     }

    72     {

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

    74       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

    75       ts.reset();

    76       int i=0;

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

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

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

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

    81     }

    83     {

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

    85       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

    86       ts.reset();

    87       int i=0;

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

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

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

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

    92     }

    93   }

    96   {

    97     typedef SmartGraph Graph;

    98     typedef Graph::Node Node;

    99     typedef Graph::EdgeIt EdgeIt;

   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);

   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);

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

   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     }

   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     }

   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 //     }

   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     }

   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   }

   174   return 0;

   175 }

author	marci
	Mon, 10 May 2004 08:25:10 +0000
changeset 593	b83b36ee7f10
parent 555	995bc1f1a3ce
child 640	d426dca0aaf7
permissions	-rw-r--r--