Concept modification to resolve the item by its ID.
3 #include <smart_graph.h>
6 #include <time_measure.h>
10 int main(int, char **) {
12 typedef SmartGraph Graph;
14 typedef Graph::Node Node;
15 typedef Graph::EdgeIt EdgeIt;
19 Graph::EdgeMap<int> cap(G);
20 readDimacsMaxFlow(std::cin, G, s, t, cap);
25 "\n Testing preflow.h on a graph with " <<
26 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
30 Graph::EdgeMap<int> flow(G,0);
31 Preflow<Graph, int> preflow_test(G, s, t, cap, flow);
32 std::cout << "\nCalling run() (flow must be constant zero)..."<<std::endl;
35 std::cout << "Elapsed time: " << ts << std::endl;
37 Graph::NodeMap<bool> mincut(G);
38 preflow_test.minMinCut(mincut);
39 int min_min_cut_value=0;
40 Graph::NodeMap<bool> cut(G);
41 preflow_test.minCut(cut);
43 Graph::NodeMap<bool> maxcut(G);
44 preflow_test.maxMinCut(maxcut);
45 int max_min_cut_value=0;
47 for(G.first(e); G.valid(e); G.next(e)) {
49 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=c;
50 if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=c;
51 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=c;
54 std::cout << "\nChecking the result: " <<std::endl;
55 std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl;
56 std::cout << "Min cut value: "<< min_cut_value << std::endl;
57 std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
58 std::cout << "Max min cut value: "<< max_min_cut_value <<
61 if ( preflow_test.flowValue() == min_cut_value &&
62 min_cut_value == min_min_cut_value &&
63 min_min_cut_value == max_min_cut_value )
64 std::cout << "They are equal. " <<std::endl;
66 std::cout << "ERROR! They are not equal! " <<std::endl;
72 Preflow<Graph, int> preflow_test2(G, s, t, cap, flow);
73 std::cout << "\n\nCalling preflow(GEN_FLOW) with the given maximum flow..."<<std::endl;
75 preflow_test2.preflow(preflow_test2.GEN_FLOW);
76 std::cout << "Elapsed time: " << ts << std::endl;
78 Graph::NodeMap<bool> mincut2(G);
79 preflow_test.minMinCut(mincut2);
80 int min_min_cut2_value=0;
81 Graph::NodeMap<bool> cut2(G);
82 preflow_test.minCut(cut2);
84 Graph::NodeMap<bool> maxcut2(G);
85 preflow_test.maxMinCut(maxcut2);
86 int max_min_cut2_value=0;
87 for(G.first(e); G.valid(e); G.next(e)) {
89 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut2_value+=c;
90 if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut2_value+=c;
91 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut2_value+=c;
94 std::cout << "\nThe given flow value is "
95 << preflow_test2.flowValue();
97 if ( preflow_test2.flowValue() == min_cut2_value &&
98 min_cut2_value == min_min_cut2_value &&
99 min_min_cut2_value == max_min_cut2_value )
100 std::cout <<", which is equal to all three min cut values."
103 std::cout << "ERROR! It is not equal to all three min cut values! "
111 Graph::EdgeMap<int> flow3(G,0);
112 Preflow<Graph, int> preflow_test3(G, s, t, cap, flow3);
113 std::cout << "\n\nCalling preflowPhase0(PREFLOW) on the constant zero flow..."<<std::endl;
115 preflow_test3.preflowPhase0(preflow_test3.PREFLOW);
116 std::cout << "Elapsed time: " << ts << std::endl;
117 Graph::NodeMap<bool> actcut3(G);
118 std::cout << "\nCalling actMinCut()..."<<std::endl;
119 preflow_test3.actMinCut(actcut3);
120 std::cout << "Calling preflowPhase1() on the given flow..."<<std::endl;
122 preflow_test3.preflowPhase1();
123 std::cout << "Elapsed time: " << ts << std::endl;
125 int act_min_cut3_value=0;
127 Graph::NodeMap<bool> mincut3(G);
128 preflow_test.minMinCut(mincut3);
129 int min_min_cut3_value=0;
131 Graph::NodeMap<bool> cut3(G);
132 preflow_test.minCut(cut3);
133 int min_cut3_value=0;
135 Graph::NodeMap<bool> maxcut3(G);
136 preflow_test.maxMinCut(maxcut3);
137 int max_min_cut3_value=0;
139 for(G.first(e); G.valid(e); G.next(e)) {
141 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut3_value+=c;
142 if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut3_value+=c;
143 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut3_value+=c;
144 if (actcut3[G.source(e)] && !actcut3[G.target(e)]) act_min_cut3_value+=c;
147 std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<<
150 if ( preflow_test3.flowValue() == min_cut3_value &&
151 min_cut3_value == min_min_cut3_value &&
152 min_min_cut3_value == max_min_cut3_value &&
153 max_min_cut3_value == act_min_cut3_value ) {
155 ", which is equal to the given flow value and to all three min cut values after phase 1."
160 "ERROR! It is not equal to the given flow value and to all three min cut values after phase 1! "
169 Graph::EdgeMap<int> flow4(G,0);
170 Preflow<Graph, int> preflow_test4(G, s, t, cap, flow4);
172 "\n\nCalling preflow(PREFLOW) with the constant 0 flow, the result is f..."
174 preflow_test4.preflow(preflow_test4.PREFLOW);
176 std::cout << "Swapping the source and the target, "<<std::endl;
177 std::cout << "by calling resetSource(t) and resetTarget(s)..."
179 preflow_test4.resetSource(t);
180 preflow_test4.resetTarget(s);
183 "Calling preflow(PREFLOW) to find a maximum t-s flow starting with flow f..."
185 preflow_test4.preflow(preflow_test4.PREFLOW);
187 Graph::NodeMap<bool> mincut4(G);
188 preflow_test4.minMinCut(mincut4);
189 int min_min_cut4_value=0;
190 Graph::NodeMap<bool> cut4(G);
191 preflow_test4.minCut(cut4);
192 int min_cut4_value=0;
193 Graph::NodeMap<bool> maxcut4(G);
194 preflow_test4.maxMinCut(maxcut4);
195 int max_min_cut4_value=0;
196 for(G.first(e); G.valid(e); G.next(e)) {
198 if (mincut4[G.source(e)] && !mincut4[G.target(e)]) min_min_cut4_value+=c;
199 if (cut4[G.source(e)] && !cut4[G.target(e)]) min_cut4_value+=c;
200 if (maxcut4[G.source(e)] && !maxcut4[G.target(e)]) max_min_cut4_value+=c;
203 std::cout << "\nThe given flow value is "
204 << preflow_test4.flowValue();
206 if ( preflow_test4.flowValue() == min_cut4_value &&
207 min_cut4_value == min_min_cut4_value &&
208 min_min_cut4_value == max_min_cut4_value )
209 std::cout <<", which is equal to all three min cut values."
212 std::cout << "ERROR! It is not equal to all three min cut values! "
220 Graph::EdgeMap<int> flow5(G,0);
221 std::cout << "Resetting the stored flow to constant zero, by calling resetFlow..."
223 preflow_test4.resetFlow(flow5);
225 "Calling preflow(GEN_FLOW) to find a maximum t-s flow "<<std::endl;
227 "starting with this constant zero flow..." <<std::endl;
228 preflow_test4.preflow(preflow_test4.GEN_FLOW);
230 Graph::NodeMap<bool> mincut5(G);
231 preflow_test4.minMinCut(mincut5);
232 int min_min_cut5_value=0;
233 Graph::NodeMap<bool> cut5(G);
234 preflow_test4.minCut(cut5);
235 int min_cut5_value=0;
236 Graph::NodeMap<bool> maxcut5(G);
237 preflow_test4.maxMinCut(maxcut5);
238 int max_min_cut5_value=0;
239 for(G.first(e); G.valid(e); G.next(e)) {
241 if (mincut5[G.source(e)] && !mincut5[G.target(e)]) min_min_cut5_value+=c;
242 if (cut5[G.source(e)] && !cut5[G.target(e)]) min_cut5_value+=c;
243 if (maxcut5[G.source(e)] && !maxcut5[G.target(e)]) max_min_cut5_value+=c;
246 std::cout << "\nThe given flow value is "
247 << preflow_test4.flowValue();
249 if ( preflow_test4.flowValue() == min_cut5_value &&
250 min_cut5_value == min_min_cut5_value &&
251 min_min_cut5_value == max_min_cut5_value )
252 std::cout <<", which is equal to all three min cut values."
253 <<std::endl<<std::endl;
255 std::cout << "ERROR! It is not equal to all three min cut values! "
260 if (error) std::cout <<"\nThere was some error in the results!\n"<<std::endl;
261 else std::cout <<"\nThere was no error in the results.\n"<<std::endl;