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 <hugo/max_flow.h>

    11 #include <augmenting_flow.h>

    12 #include <hugo/time_measure.h>

    13 #include <for_each_macros.h>

    15 using namespace hugo;

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

    18 // read_dimacs_demo dimacs_max_flow_file

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

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

    23   typedef SageGraph MutableGraph;

    25   {

    26     typedef SageGraph Graph;

    27     typedef Graph::Node Node;

    28     typedef Graph::EdgeIt EdgeIt;

    30     Graph g;

    31     Node s, t;

    32     Graph::EdgeMap<int> cap(g);

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

    34     //readDimacsMaxFlow(ins, g, s, t, cap);

    35     readDimacs(ins, g, cap, s, t);

    37     Timer ts;

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

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

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

    41     AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >

    42       augmenting_flow_test(g, s, t, cap, flow/*, true*/);

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

    46     {

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

    48       ts.reset();

    49       max_flow_test.run();

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

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

    52     }

    54     {

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

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

    57       ts.reset();

    58       int i=0;

    59       while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

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

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

    62       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

    63     }

    65 //     {

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

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

    68 //       ts.reset();

    69 //       int i=0;

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

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

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

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

    74 //     }

    76     {

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

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

    79       ts.reset();

    80       int i=0;

    81       while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }

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

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

    84       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

    85     }

    87     {

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

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

    90       ts.reset();

    91       int i=0;

    92       while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }

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

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

    95       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

    96     }

    97   }

    99   {

   100     typedef SmartGraph Graph;

   101     typedef Graph::Node Node;

   102     typedef Graph::EdgeIt EdgeIt;

   104     Graph g;

   105     Node s, t;

   106     Graph::EdgeMap<int> cap(g);

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

   108     //readDimacsMaxFlow(ins, g, s, t, cap);

   109     readDimacs(ins, g, cap, s, t);

   111     Timer ts;

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

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

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

   115     AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >

   116       augmenting_flow_test(g, s, t, cap, flow/*, true*/);

   117     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >

   118     //  max_flow_test(g, s, t, cap, flow);

   120     std::cout << "SmartGraph ..." << std::endl;

   122     {

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

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

   125       ts.reset();

   126       max_flow_test.run();

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

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

   129     }

   131     {

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

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

   134       ts.reset();

   135       int i=0;

   136       while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

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

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

   139       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   140     }

   142 //     {

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

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

   145 //       ts.reset();

   146 //       int i=0;

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

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

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

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

   151 //     }

   153     {

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

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

   156       ts.reset();

   157       int i=0;

   158       while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }

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

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

   161       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   162     }

   164     {

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

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

   167       ts.reset();

   168       int i=0;

   169       while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }

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

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

   172       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   173     }

   174   }

   176   {

   177     typedef ListGraph Graph;

   178     typedef Graph::Node Node;

   179     typedef Graph::EdgeIt EdgeIt;

   181     Graph g;

   182     Node s, t;

   183     Graph::EdgeMap<int> cap(g);

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

   185     //readDimacsMaxFlow(ins, g, s, t, cap);

   186     readDimacs(ins, g, cap, s, t);

   188     Timer ts;

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

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

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

   192     AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >

   193       augmenting_flow_test(g, s, t, cap, flow/*, true*/);

   194     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >

   195     //  max_flow_test(g, s, t, cap, flow);

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

   199     {

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

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

   202       ts.reset();

   203       max_flow_test.run();

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

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

   206     }

   208     {

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

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

   211       ts.reset();

   212       int i=0;

   213       while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

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

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

   216       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   217     }

   219 //     {

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

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

   222 //       ts.reset();

   223 //       int i=0;

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

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

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

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

   228 //     }

   230     {

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

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

   233       ts.reset();

   234       int i=0;

   235       while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }

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

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

   238       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   239     }

   241     {

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

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

   244       ts.reset();

   245       int i=0;

   246       while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }

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

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

   249       std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   250     }

   251   }

   253   return 0;

   254 }

author	marci
	Tue, 31 Aug 2004 11:26:59 +0000
changeset 775	e46a1f0623a0
parent 643	f8053cb51047
child 777	a82713ed19f3
permissions	-rw-r--r--