equal
deleted
inserted
replaced
5 #include <sage_graph.h> |
5 #include <sage_graph.h> |
6 #include <hugo/smart_graph.h> |
6 #include <hugo/smart_graph.h> |
7 #include <hugo/dimacs.h> |
7 #include <hugo/dimacs.h> |
8 #include <hugo/time_measure.h> |
8 #include <hugo/time_measure.h> |
9 //#include <graph_wrapper.h> |
9 //#include <graph_wrapper.h> |
10 #include <max_flow.h> |
10 #include <hugo/max_flow.h> |
|
11 #include <augmenting_flow.h> |
11 //#include <preflow_res.h> |
12 //#include <preflow_res.h> |
12 #include <hugo/for_each_macros.h> |
13 #include <for_each_macros.h> |
13 #include <graph_concept.h> |
14 #include <graph_concept.h> |
14 |
15 |
15 using namespace hugo; |
16 using namespace hugo; |
16 |
17 |
17 // Use a DIMACS max flow file as stdin. |
18 // Use a DIMACS max flow file as stdin. |
36 int main(int, char **) { |
37 int main(int, char **) { |
37 |
38 |
38 typedef SageGraph MutableGraph; |
39 typedef SageGraph MutableGraph; |
39 |
40 |
40 //typedef FullFeatureGraphConcept Graph; |
41 //typedef FullFeatureGraphConcept Graph; |
41 typedef SmartGraph Graph; |
42 //typedef SmartGraph Graph; |
42 // typedef SageGraph Graph; |
43 typedef SageGraph Graph; |
43 typedef Graph::Node Node; |
44 typedef Graph::Node Node; |
44 typedef Graph::EdgeIt EdgeIt; |
45 typedef Graph::EdgeIt EdgeIt; |
45 |
46 |
46 |
47 |
47 // Mize mize[10]; |
48 // Mize mize[10]; |
73 readDimacs(std::cin, g, cap, s, t); |
74 readDimacs(std::cin, g, cap, s, t); |
74 Timer ts; |
75 Timer ts; |
75 Graph::EdgeMap<int> flow(g); //0 flow |
76 Graph::EdgeMap<int> flow(g); //0 flow |
76 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
77 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
77 max_flow_test(g, s, t, cap, flow); |
78 max_flow_test(g, s, t, cap, flow); |
|
79 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
|
80 augmenting_flow_test(g, s, t, cap, flow); |
|
81 |
78 Graph::NodeMap<bool> cut(g); |
82 Graph::NodeMap<bool> cut(g); |
79 |
83 |
80 { |
84 { |
81 std::cout << "preflow ..." << std::endl; |
85 std::cout << "preflow ..." << std::endl; |
82 ts.reset(); |
86 ts.reset(); |
121 { |
125 { |
122 std::cout << "physical blocking flow augmentation ..." << std::endl; |
126 std::cout << "physical blocking flow augmentation ..." << std::endl; |
123 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
127 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
124 ts.reset(); |
128 ts.reset(); |
125 int i=0; |
129 int i=0; |
126 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
130 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
127 std::cout << "elapsed time: " << ts << std::endl; |
131 std::cout << "elapsed time: " << ts << std::endl; |
128 std::cout << "number of augmentation phases: " << i << std::endl; |
132 std::cout << "number of augmentation phases: " << i << std::endl; |
129 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
133 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
130 |
134 |
131 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
135 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
132 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
136 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
133 std::cout << "Slackness does not hold!" << std::endl; |
137 std::cout << "Slackness does not hold!" << std::endl; |
134 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
138 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
150 { |
154 { |
151 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
155 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
152 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
156 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
153 ts.reset(); |
157 ts.reset(); |
154 int i=0; |
158 int i=0; |
155 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } |
159 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
156 std::cout << "elapsed time: " << ts << std::endl; |
160 std::cout << "elapsed time: " << ts << std::endl; |
157 std::cout << "number of augmentation phases: " << i << std::endl; |
161 std::cout << "number of augmentation phases: " << i << std::endl; |
158 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
162 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
159 |
163 |
160 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
164 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
161 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
165 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
162 std::cout << "Slackness does not hold!" << std::endl; |
166 std::cout << "Slackness does not hold!" << std::endl; |
163 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
167 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
168 { |
172 { |
169 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
173 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
170 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
174 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
171 ts.reset(); |
175 ts.reset(); |
172 int i=0; |
176 int i=0; |
173 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
177 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
174 std::cout << "elapsed time: " << ts << std::endl; |
178 std::cout << "elapsed time: " << ts << std::endl; |
175 std::cout << "number of augmentation phases: " << i << std::endl; |
179 std::cout << "number of augmentation phases: " << i << std::endl; |
176 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
180 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
177 |
181 |
178 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
182 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
179 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
183 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
180 std::cout << "Slackness does not hold!" << std::endl; |
184 std::cout << "Slackness does not hold!" << std::endl; |
181 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
185 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
186 { |
190 { |
187 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
191 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
188 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
192 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
189 ts.reset(); |
193 ts.reset(); |
190 int i=0; |
194 int i=0; |
191 while (max_flow_test.augmentOnShortestPath2()) { ++i; } |
195 while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; } |
192 std::cout << "elapsed time: " << ts << std::endl; |
196 std::cout << "elapsed time: " << ts << std::endl; |
193 std::cout << "number of augmentation phases: " << i << std::endl; |
197 std::cout << "number of augmentation phases: " << i << std::endl; |
194 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
198 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
195 |
199 |
196 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
200 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
197 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
201 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
198 std::cout << "Slackness does not hold!" << std::endl; |
202 std::cout << "Slackness does not hold!" << std::endl; |
199 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
203 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |