Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/lg_vs_sg.cc
author marci
Fri, 12 Mar 2004 09:19:54 +0000
changeset 174 44700ed9ffaa
child 334 63703ea7d02f
permissions -rw-r--r--
towards on ListGraph, SmartGraph compatibility 
     1 // -*- c++ -*-

     2 #include <iostream>

     3 #include <fstream>

     4 #include <string>

     5 

     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>

    12 

    13 using namespace hugo;

    14 

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

    16 // read_dimacs_demo dimacs_max_flow_file

    17 

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

    19 

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

    21   typedef ListGraph MutableGraph;

    22 

    23   {

    24     typedef ListGraph Graph;

    25     typedef Graph::Node Node;

    26     typedef Graph::EdgeIt EdgeIt;

    27 

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

    33 

    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

    38 

    39       Timer ts;

    40       ts.reset();

    41 

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

    45 

    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     }

    50 

    51     {

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

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

    54 

    55       Timer ts;

    56       ts.reset();

    57 

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

    61 

    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     }

    66 

    67     {

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

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

    70 

    71       Timer ts;

    72       ts.reset();

    73 

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

    77 

    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   }

    83 

    84 

    85   {

    86     typedef SmartGraph Graph;

    87     typedef Graph::Node Node;

    88     typedef Graph::EdgeIt EdgeIt;

    89 

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

    95 

    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

   100 

   101       Timer ts;

   102       ts.reset();

   103 

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

   107 

   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     }

   112 

   113     {

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

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

   116 

   117       Timer ts;

   118       ts.reset();

   119 

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

   123 

   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     }

   128 

   129     {

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

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

   132 

   133       Timer ts;

   134       ts.reset();

   135 

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

   139 

   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   }

   145 

   146   return 0;

   147 }
lemon-0.x