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

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

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

    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     }

    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     }

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

    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     }

    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   }

    95   {

    96     typedef SmartGraph Graph;

    97     typedef Graph::Node Node;

    98     typedef Graph::EdgeIt EdgeIt;

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

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

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

   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     }

   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     }

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

   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     }

   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   }

   172   return 0;

   173 }

author	alpar
	Fri, 07 May 2004 06:57:50 +0000
changeset 567	efaa79ee8d14
parent 480	4fb0d1e166ea
child 577	e8703f0a6e2f
permissions	-rw-r--r--