COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/gw_vs_not.cc @ 495:6114a8ab5d27

Last change on this file since 495:6114a8ab5d27 was 270:e4811faaaa75, checked in by marci, 20 years ago

Ment-e a dereferalasok sporolasaval elobbre a vilag?

File size: 5.5 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <list_graph.h>
6#include <smart_graph.h>
7#include <dimacs.h>
8#include <edmonds_karp.h>
9#include <time_measure.h>
10#include <graph_wrapper.h>
11
12using namespace hugo;
13
14// Use a DIMACS max flow file as stdin.
15// read_dimacs_demo < dimacs_max_flow_file
16
17int main(int, char **) {
18
19  typedef ListGraph MutableGraph;
20  //typedef SmartGraph Graph;
21  typedef ListGraph Graph;
22  typedef Graph::Node Node;
23  typedef Graph::EdgeIt EdgeIt;
24
25  Graph G;
26  Node s, t;
27  Graph::EdgeMap<int> cap(G);
28  readDimacsMaxFlow(std::cin, G, s, t, cap);
29
30  {
31    typedef TrivGraphWrapper<const Graph> GW;
32    GW gw(G);
33    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
34    EMW cw(cap);
35    Timer ts;
36    GW::EdgeMap<int> flow(gw);
37    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
38    int i;
39
40    {
41      std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
42      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
43      ts.reset();
44
45      i=0;
46      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
47
48      std::cout << "elapsed time: " << ts << std::endl;
49      std::cout << "number of augmentation phases: " << i << std::endl;
50      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
51    }
52
53    {
54      std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
55      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
56      ts.reset();
57
58      i=0;
59      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
60
61      std::cout << "elapsed time: " << ts << std::endl;
62      std::cout << "number of augmentation phases: " << i << std::endl;
63      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
64    }
65
66    {
67      std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
68      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
69      ts.reset();
70
71      i=0;
72      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
73
74      std::cout << "elapsed time: " << ts << std::endl;
75      std::cout << "number of augmentation phases: " << i << std::endl;
76      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
77    }
78
79    {
80      std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
81      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
82      ts.reset();
83
84      i=0;
85      while (max_flow_test.augmentOnShortestPath()) { ++i; }
86
87      std::cout << "elapsed time: " << ts << std::endl;
88      std::cout << "number of augmentation phases: " << i << std::endl;
89      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
90    }
91  }
92
93
94
95
96  {
97    typedef TrivGraphWrapper<const Graph> GW1;
98    GW1 gw1(G);
99    typedef TrivGraphWrapper<const GW1> GW2;
100    GW2 gw2(gw1);
101    typedef TrivGraphWrapper<const GW2> GW3;
102    GW3 gw3(gw2);
103    typedef TrivGraphWrapper<const GW3> GW4;
104    GW4 gw4(gw3);
105    typedef TrivGraphWrapper<const GW4> GW5;
106    GW5 gw5(gw4);
107    typedef TrivGraphWrapper<const GW5> GW6;
108    GW6 gw6(gw5);
109    typedef TrivGraphWrapper<const GW6> GW7;
110    GW7 gw7(gw6);
111    typedef TrivGraphWrapper<const GW7> GW8;
112    GW8 gw8(gw7);
113    typedef TrivGraphWrapper<const GW8> GW9;
114    GW9 gw9(gw8);
115    typedef TrivGraphWrapper<const GW9> GW;
116    GW gw(gw9);
117    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
118    EMW cw(cap);
119    Timer ts;
120    GW::EdgeMap<int> flow(gw);
121    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
122    int i;
123
124    {
125      std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
126      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
127      ts.reset();
128
129      i=0;
130      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
131
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    }
136
137    {
138      std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
139      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
140      ts.reset();
141
142      i=0;
143      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
144
145      std::cout << "elapsed time: " << ts << std::endl;
146      std::cout << "number of augmentation phases: " << i << std::endl;
147      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
148    }
149
150    {
151      std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
152      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
153      ts.reset();
154
155      i=0;
156      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
157
158      std::cout << "elapsed time: " << ts << std::endl;
159      std::cout << "number of augmentation phases: " << i << std::endl;
160      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
161    }
162
163    {
164      std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
165      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
166      ts.reset();
167
168      i=0;
169      while (max_flow_test.augmentOnShortestPath()) { ++i; }
170
171      std::cout << "elapsed time: " << ts << std::endl;
172      std::cout << "number of augmentation phases: " << i << std::endl;
173      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
174    }
175  }
176
177
178  return 0;
179}
Note: See TracBrowser for help on using the repository browser.