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

    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 ListGraph MutableGraph;

    24   {

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

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

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

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

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

    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     }

    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     }

    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     }

    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     }

    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   }

    98   {

    99     typedef SmartGraph Graph;

   100     typedef Graph::Node Node;

   101     typedef Graph::EdgeIt EdgeIt;

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

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

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

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

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

   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     }

   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     }

   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     }

   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     }

   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   }

   175   return 0;

   176 }

author	alpar
	Mon, 26 Apr 2004 17:39:38 +0000
changeset 428	3544872b38c2
parent 334	63703ea7d02f
child 465	d72e56f1730d
permissions	-rw-r--r--