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 <time_measure.h>

    11 #include <graph_wrapper.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     {

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

    36       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;

    37       Graph::EdgeMap<int> flow(G); //0 flow

    39       Timer ts;

    40       ts.reset();

    42       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);

    43       int i=0;

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

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

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

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

    49     }

    51     {

    52       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;

    53       Graph::EdgeMap<int> flow(G); //0 flow

    55       Timer ts;

    56       ts.reset();

    58       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);

    59       int i=0;

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

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

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

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

    65     }

    67     {

    68       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;

    69       Graph::EdgeMap<int> flow(G); //0 flow

    71       Timer ts;

    72       ts.reset();

    74       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);

    75       int i=0;

    76       while (max_flow_test.augmentOnShortestPath()) { ++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     }

    82   }

    85   {

    86     typedef SmartGraph Graph;

    87     typedef Graph::Node Node;

    88     typedef Graph::EdgeIt EdgeIt;

    90     Graph G;

    91     Node s, t;

    92     Graph::EdgeMap<int> cap(G);

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

    94     readDimacsMaxFlow(ins, G, s, t, cap);

    96     {

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

    98       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;

    99       Graph::EdgeMap<int> flow(G); //0 flow

   101       Timer ts;

   102       ts.reset();

   104       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);

   105       int i=0;

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

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

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

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

   111     }

   113     {

   114       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;

   115       Graph::EdgeMap<int> flow(G); //0 flow

   117       Timer ts;

   118       ts.reset();

   120       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);

   121       int i=0;

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

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

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

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

   127     }

   129     {

   130       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;

   131       Graph::EdgeMap<int> flow(G); //0 flow

   133       Timer ts;

   134       ts.reset();

   136       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);

   137       int i=0;

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

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

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

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

   143     }

   144   }

   146   return 0;

   147 }

author	athos
	Fri, 02 Apr 2004 15:59:17 +0000
changeset 277	044f5898b769
child 334	63703ea7d02f
permissions	-rw-r--r--