5 |
5 |
6 #include <sage_graph.h> |
6 #include <sage_graph.h> |
7 #include <hugo/list_graph.h> |
7 #include <hugo/list_graph.h> |
8 #include <hugo/smart_graph.h> |
8 #include <hugo/smart_graph.h> |
9 #include <hugo/dimacs.h> |
9 #include <hugo/dimacs.h> |
10 #include <max_flow.h> |
10 #include <hugo/max_flow.h> |
|
11 #include <augmenting_flow.h> |
11 #include <hugo/time_measure.h> |
12 #include <hugo/time_measure.h> |
12 #include <hugo/for_each_macros.h> |
13 #include <for_each_macros.h> |
13 |
14 |
14 using namespace hugo; |
15 using namespace hugo; |
15 |
16 |
16 // Use a DIMACS max flow file as stdin. |
17 // Use a DIMACS max flow file as stdin. |
17 // read_dimacs_demo dimacs_max_flow_file |
18 // read_dimacs_demo dimacs_max_flow_file |
35 |
36 |
36 Timer ts; |
37 Timer ts; |
37 Graph::EdgeMap<int> flow(g); //0 flow |
38 Graph::EdgeMap<int> flow(g); //0 flow |
38 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
39 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
39 max_flow_test(g, s, t, cap, flow/*, true*/); |
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*/); |
40 |
43 |
41 std::cout << "SageGraph ..." << std::endl; |
44 std::cout << "SageGraph ..." << std::endl; |
42 |
45 |
43 { |
46 { |
44 std::cout << "preflow ..." << std::endl; |
47 std::cout << "preflow ..." << std::endl; |
51 { |
54 { |
52 std::cout << "physical blocking flow augmentation ..." << std::endl; |
55 std::cout << "physical blocking flow augmentation ..." << std::endl; |
53 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
56 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
54 ts.reset(); |
57 ts.reset(); |
55 int i=0; |
58 int i=0; |
56 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
59 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
57 std::cout << "elapsed time: " << ts << std::endl; |
60 std::cout << "elapsed time: " << ts << std::endl; |
58 std::cout << "number of augmentation phases: " << i << std::endl; |
61 std::cout << "number of augmentation phases: " << i << std::endl; |
59 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
62 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
60 } |
63 } |
61 |
64 |
62 // { |
65 // { |
63 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
66 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
64 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
67 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
73 { |
76 { |
74 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
77 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
75 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
78 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
76 ts.reset(); |
79 ts.reset(); |
77 int i=0; |
80 int i=0; |
78 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } |
81 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
79 std::cout << "elapsed time: " << ts << std::endl; |
82 std::cout << "elapsed time: " << ts << std::endl; |
80 std::cout << "number of augmentation phases: " << i << std::endl; |
83 std::cout << "number of augmentation phases: " << i << std::endl; |
81 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
84 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
82 } |
85 } |
83 |
86 |
84 { |
87 { |
85 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
88 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
86 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
89 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
87 ts.reset(); |
90 ts.reset(); |
88 int i=0; |
91 int i=0; |
89 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
92 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
90 std::cout << "elapsed time: " << ts << std::endl; |
93 std::cout << "elapsed time: " << ts << std::endl; |
91 std::cout << "number of augmentation phases: " << i << std::endl; |
94 std::cout << "number of augmentation phases: " << i << std::endl; |
92 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
95 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
93 } |
96 } |
94 } |
97 } |
95 |
98 |
96 { |
99 { |
97 typedef SmartGraph Graph; |
100 typedef SmartGraph Graph; |
107 |
110 |
108 Timer ts; |
111 Timer ts; |
109 Graph::EdgeMap<int> flow(g); //0 flow |
112 Graph::EdgeMap<int> flow(g); //0 flow |
110 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
113 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
111 max_flow_test(g, s, t, cap, flow/*, true*/); |
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*/); |
112 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
117 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
113 // max_flow_test(g, s, t, cap, flow); |
118 // max_flow_test(g, s, t, cap, flow); |
114 |
119 |
115 std::cout << "SmartGraph ..." << std::endl; |
120 std::cout << "SmartGraph ..." << std::endl; |
116 |
121 |
126 { |
131 { |
127 std::cout << "physical blocking flow augmentation ..." << std::endl; |
132 std::cout << "physical blocking flow augmentation ..." << std::endl; |
128 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
133 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
129 ts.reset(); |
134 ts.reset(); |
130 int i=0; |
135 int i=0; |
131 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
136 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
132 std::cout << "elapsed time: " << ts << std::endl; |
137 std::cout << "elapsed time: " << ts << std::endl; |
133 std::cout << "number of augmentation phases: " << i << std::endl; |
138 std::cout << "number of augmentation phases: " << i << std::endl; |
134 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
139 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
135 } |
140 } |
136 |
141 |
137 // { |
142 // { |
138 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
143 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
139 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
144 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
148 { |
153 { |
149 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
154 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
150 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
155 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
151 ts.reset(); |
156 ts.reset(); |
152 int i=0; |
157 int i=0; |
153 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } |
158 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
154 std::cout << "elapsed time: " << ts << std::endl; |
159 std::cout << "elapsed time: " << ts << std::endl; |
155 std::cout << "number of augmentation phases: " << i << std::endl; |
160 std::cout << "number of augmentation phases: " << i << std::endl; |
156 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
161 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
157 } |
162 } |
158 |
163 |
159 { |
164 { |
160 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
165 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
161 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
166 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
162 ts.reset(); |
167 ts.reset(); |
163 int i=0; |
168 int i=0; |
164 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
169 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
165 std::cout << "elapsed time: " << ts << std::endl; |
170 std::cout << "elapsed time: " << ts << std::endl; |
166 std::cout << "number of augmentation phases: " << i << std::endl; |
171 std::cout << "number of augmentation phases: " << i << std::endl; |
167 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
172 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
168 } |
173 } |
169 } |
174 } |
170 |
175 |
171 { |
176 { |
172 typedef ListGraph Graph; |
177 typedef ListGraph Graph; |
182 |
187 |
183 Timer ts; |
188 Timer ts; |
184 Graph::EdgeMap<int> flow(g); //0 flow |
189 Graph::EdgeMap<int> flow(g); //0 flow |
185 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
190 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
186 max_flow_test(g, s, t, cap, flow/*, true*/); |
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*/); |
187 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
194 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
188 // max_flow_test(g, s, t, cap, flow); |
195 // max_flow_test(g, s, t, cap, flow); |
189 |
196 |
190 std::cout << "ListGraph ..." << std::endl; |
197 std::cout << "ListGraph ..." << std::endl; |
191 |
198 |
201 { |
208 { |
202 std::cout << "physical blocking flow augmentation ..." << std::endl; |
209 std::cout << "physical blocking flow augmentation ..." << std::endl; |
203 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
210 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
204 ts.reset(); |
211 ts.reset(); |
205 int i=0; |
212 int i=0; |
206 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
213 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
207 std::cout << "elapsed time: " << ts << std::endl; |
214 std::cout << "elapsed time: " << ts << std::endl; |
208 std::cout << "number of augmentation phases: " << i << std::endl; |
215 std::cout << "number of augmentation phases: " << i << std::endl; |
209 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
216 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
210 } |
217 } |
211 |
218 |
212 // { |
219 // { |
213 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
220 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
214 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
221 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
223 { |
230 { |
224 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
231 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
225 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
232 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
226 ts.reset(); |
233 ts.reset(); |
227 int i=0; |
234 int i=0; |
228 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } |
235 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
229 std::cout << "elapsed time: " << ts << std::endl; |
236 std::cout << "elapsed time: " << ts << std::endl; |
230 std::cout << "number of augmentation phases: " << i << std::endl; |
237 std::cout << "number of augmentation phases: " << i << std::endl; |
231 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
238 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
232 } |
239 } |
233 |
240 |
234 { |
241 { |
235 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
242 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
236 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
243 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
237 ts.reset(); |
244 ts.reset(); |
238 int i=0; |
245 int i=0; |
239 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
246 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
240 std::cout << "elapsed time: " << ts << std::endl; |
247 std::cout << "elapsed time: " << ts << std::endl; |
241 std::cout << "number of augmentation phases: " << i << std::endl; |
248 std::cout << "number of augmentation phases: " << i << std::endl; |
242 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
249 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
243 } |
250 } |
244 } |
251 } |
245 |
|
246 |
|
247 |
|
248 |
252 |
249 return 0; |
253 return 0; |
250 } |
254 } |