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

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

     2 #include <iostream>

     3 #include <fstream>

     4 #include <string>

     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>

    14 using namespace hugo;

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

    17 // read_dimacs_demo dimacs_max_flow_file

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

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

    22   typedef SageGraph MutableGraph;

    24   {

    25     typedef SageGraph Graph;

    26     typedef Graph::Node Node;

    27     typedef Graph::EdgeIt EdgeIt;

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

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

    41     std::cout << "SageGraph ..." << std::endl;

    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     }

    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     }

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

    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     }

    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   }

    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 << "SmartGraph ..." << 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   }

   171   {

   172     typedef ListGraph Graph;

   173     typedef Graph::Node Node;

   174     typedef Graph::EdgeIt EdgeIt;

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

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

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

   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     }

   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     }

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

   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     }

   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   }

   249   return 0;

   250 }

author	alpar
	Thu, 22 Jul 2004 20:06:40 +0000
changeset 733	240003bddaff
parent 642	e812963087f0
child 762	511200bdb71f
permissions	-rw-r--r--