51 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
51 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
52 } |
52 } |
53 |
53 |
54 { |
54 { |
55 std::cout << "physical blocking flow augmentation ..." << std::endl; |
55 std::cout << "physical blocking flow augmentation ..." << std::endl; |
56 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
56 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
57 ts.reset(); |
57 ts.reset(); |
58 int i=0; |
58 int i=0; |
59 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
59 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
60 std::cout << "elapsed time: " << ts << std::endl; |
60 std::cout << "elapsed time: " << ts << std::endl; |
61 std::cout << "number of augmentation phases: " << i << std::endl; |
61 std::cout << "number of augmentation phases: " << i << std::endl; |
73 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
73 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
74 // } |
74 // } |
75 |
75 |
76 { |
76 { |
77 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
77 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
78 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
78 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
79 ts.reset(); |
79 ts.reset(); |
80 int i=0; |
80 int i=0; |
81 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
81 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
82 std::cout << "elapsed time: " << ts << std::endl; |
82 std::cout << "elapsed time: " << ts << std::endl; |
83 std::cout << "number of augmentation phases: " << i << std::endl; |
83 std::cout << "number of augmentation phases: " << i << std::endl; |
84 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
84 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
85 } |
85 } |
86 |
86 |
87 { |
87 { |
88 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
88 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
89 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
89 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
90 ts.reset(); |
90 ts.reset(); |
91 int i=0; |
91 int i=0; |
92 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
92 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
93 std::cout << "elapsed time: " << ts << std::endl; |
93 std::cout << "elapsed time: " << ts << std::endl; |
94 std::cout << "number of augmentation phases: " << i << std::endl; |
94 std::cout << "number of augmentation phases: " << i << std::endl; |
119 |
119 |
120 std::cout << "SmartGraph ..." << std::endl; |
120 std::cout << "SmartGraph ..." << std::endl; |
121 |
121 |
122 { |
122 { |
123 std::cout << "preflow ..." << std::endl; |
123 std::cout << "preflow ..." << std::endl; |
124 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
124 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
125 ts.reset(); |
125 ts.reset(); |
126 max_flow_test.run(); |
126 max_flow_test.run(); |
127 std::cout << "elapsed time: " << ts << std::endl; |
127 std::cout << "elapsed time: " << ts << std::endl; |
128 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
128 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
129 } |
129 } |
130 |
130 |
131 { |
131 { |
132 std::cout << "physical blocking flow augmentation ..." << std::endl; |
132 std::cout << "physical blocking flow augmentation ..." << std::endl; |
133 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
133 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
134 ts.reset(); |
134 ts.reset(); |
135 int i=0; |
135 int i=0; |
136 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
136 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
137 std::cout << "elapsed time: " << ts << std::endl; |
137 std::cout << "elapsed time: " << ts << std::endl; |
138 std::cout << "number of augmentation phases: " << i << std::endl; |
138 std::cout << "number of augmentation phases: " << i << std::endl; |
150 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
150 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
151 // } |
151 // } |
152 |
152 |
153 { |
153 { |
154 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
154 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
155 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
155 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
156 ts.reset(); |
156 ts.reset(); |
157 int i=0; |
157 int i=0; |
158 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
158 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
159 std::cout << "elapsed time: " << ts << std::endl; |
159 std::cout << "elapsed time: " << ts << std::endl; |
160 std::cout << "number of augmentation phases: " << i << std::endl; |
160 std::cout << "number of augmentation phases: " << i << std::endl; |
161 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
161 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
162 } |
162 } |
163 |
163 |
164 { |
164 { |
165 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
165 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
166 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
166 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
167 ts.reset(); |
167 ts.reset(); |
168 int i=0; |
168 int i=0; |
169 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
169 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
170 std::cout << "elapsed time: " << ts << std::endl; |
170 std::cout << "elapsed time: " << ts << std::endl; |
171 std::cout << "number of augmentation phases: " << i << std::endl; |
171 std::cout << "number of augmentation phases: " << i << std::endl; |
196 |
196 |
197 std::cout << "ListGraph ..." << std::endl; |
197 std::cout << "ListGraph ..." << std::endl; |
198 |
198 |
199 { |
199 { |
200 std::cout << "preflow ..." << std::endl; |
200 std::cout << "preflow ..." << std::endl; |
201 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
201 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
202 ts.reset(); |
202 ts.reset(); |
203 max_flow_test.run(); |
203 max_flow_test.run(); |
204 std::cout << "elapsed time: " << ts << std::endl; |
204 std::cout << "elapsed time: " << ts << std::endl; |
205 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
205 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
206 } |
206 } |
207 |
207 |
208 { |
208 { |
209 std::cout << "physical blocking flow augmentation ..." << std::endl; |
209 std::cout << "physical blocking flow augmentation ..." << std::endl; |
210 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
210 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
211 ts.reset(); |
211 ts.reset(); |
212 int i=0; |
212 int i=0; |
213 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
213 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
214 std::cout << "elapsed time: " << ts << std::endl; |
214 std::cout << "elapsed time: " << ts << std::endl; |
215 std::cout << "number of augmentation phases: " << i << std::endl; |
215 std::cout << "number of augmentation phases: " << i << std::endl; |
227 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
227 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
228 // } |
228 // } |
229 |
229 |
230 { |
230 { |
231 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
231 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
232 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
232 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
233 ts.reset(); |
233 ts.reset(); |
234 int i=0; |
234 int i=0; |
235 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
235 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
236 std::cout << "elapsed time: " << ts << std::endl; |
236 std::cout << "elapsed time: " << ts << std::endl; |
237 std::cout << "number of augmentation phases: " << i << std::endl; |
237 std::cout << "number of augmentation phases: " << i << std::endl; |
238 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
238 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
239 } |
239 } |
240 |
240 |
241 { |
241 { |
242 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
242 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
243 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
243 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
244 ts.reset(); |
244 ts.reset(); |
245 int i=0; |
245 int i=0; |
246 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
246 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
247 std::cout << "elapsed time: " << ts << std::endl; |
247 std::cout << "elapsed time: " << ts << std::endl; |
248 std::cout << "number of augmentation phases: " << i << std::endl; |
248 std::cout << "number of augmentation phases: " << i << std::endl; |