COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/preflow.cc @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 15 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 8.3 KB
Line 
1#include <iostream>
2
3#include <smart_graph.h>
4#include <dimacs.h>
5#include <preflow.h>
6#include <time_measure.h>
7
8using namespace lemon;
9
10int main(int, char **) {
11 
12  typedef SmartGraph Graph;
13 
14  typedef Graph::Node Node;
15  typedef Graph::EdgeIt EdgeIt;
16
17  Graph G;
18  Node s, t;
19  Graph::EdgeMap<int> cap(G);
20  readDimacsMaxFlow(std::cin, G, s, t, cap);
21  Timer ts;
22  bool error=false;
23 
24  std::cout <<
25    "\n  Testing preflow.h on a graph with " <<
26    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
27           << std::endl;
28
29
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;
33  ts.reset();
34  preflow_test.run();
35  std::cout << "Elapsed time: " << ts << std::endl;
36
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);
42  int min_cut_value=0;
43  Graph::NodeMap<bool> maxcut(G);
44  preflow_test.maxMinCut(maxcut);
45  int max_min_cut_value=0;
46  EdgeIt e;
47  for(G.first(e); G.valid(e); G.next(e)) {
48    int c=cap[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;
52  }
53
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 <<
59    std::endl;
60
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; 
65  else {
66    std::cout << "ERROR! They are not equal! " <<std::endl; 
67    error=true;
68  }
69
70
71
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;
74  ts.reset();
75  preflow_test2.preflow(preflow_test2.GEN_FLOW);
76  std::cout << "Elapsed time: " << ts << std::endl;
77
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);
83  int min_cut2_value=0;
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)) {
88    int c=cap[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;
92  }
93
94  std::cout << "\nThe given flow value is "
95            << preflow_test2.flowValue();
96
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."
101              <<std::endl; 
102  else {
103    std::cout << "ERROR! It is not equal to all three min cut values! "
104              <<std::endl; 
105    error=true;
106  }
107 
108
109
110
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;
114  ts.reset();
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;
121  ts.reset();
122  preflow_test3.preflowPhase1();
123  std::cout << "Elapsed time: " << ts << std::endl;
124 
125  int act_min_cut3_value=0;
126 
127  Graph::NodeMap<bool> mincut3(G);
128  preflow_test.minMinCut(mincut3);
129  int min_min_cut3_value=0;
130 
131  Graph::NodeMap<bool> cut3(G);
132  preflow_test.minCut(cut3);
133  int min_cut3_value=0;
134 
135  Graph::NodeMap<bool> maxcut3(G);
136  preflow_test.maxMinCut(maxcut3);
137  int max_min_cut3_value=0;
138 
139  for(G.first(e); G.valid(e); G.next(e)) {
140    int c=cap[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;
145  }
146
147 std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<<
148   act_min_cut3_value;
149
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 ) {
154    std::cout <<
155      ", which is equal to the given flow value and to all three min cut values after phase 1."
156              <<std::endl; 
157  }
158  else {
159    std::cout <<
160      "ERROR! It is not equal to the given flow value and to all three min cut values after phase 1! "
161              <<std::endl; 
162    error=true;
163  }
164 
165
166
167
168
169  Graph::EdgeMap<int> flow4(G,0);
170  Preflow<Graph, int> preflow_test4(G, s, t, cap, flow4);
171  std::cout <<
172    "\n\nCalling preflow(PREFLOW) with the constant 0 flow, the result is f..."
173            <<std::endl;
174  preflow_test4.preflow(preflow_test4.PREFLOW);
175
176  std::cout << "Swapping the source and the target, "<<std::endl;
177  std::cout << "by calling resetSource(t) and resetTarget(s)..."
178            <<std::endl;
179  preflow_test4.resetSource(t);
180  preflow_test4.resetTarget(s);
181
182  std::cout <<
183    "Calling preflow(PREFLOW) to find a maximum t-s flow starting with flow f..."
184            <<std::endl;
185  preflow_test4.preflow(preflow_test4.PREFLOW);
186
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)) {
197    int c=cap[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;
201  }
202
203  std::cout << "\nThe given flow value is "
204            << preflow_test4.flowValue();
205 
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."
210              <<std::endl; 
211  else {
212    std::cout << "ERROR! It is not equal to all three min cut values! "
213              <<std::endl; 
214    error=true;
215  }
216
217
218
219
220  Graph::EdgeMap<int> flow5(G,0);
221  std::cout << "Resetting the stored flow to constant zero, by calling resetFlow..."
222            <<std::endl;
223  preflow_test4.resetFlow(flow5);
224  std::cout <<
225    "Calling preflow(GEN_FLOW) to find a maximum t-s flow "<<std::endl;
226  std::cout <<
227    "starting with this constant zero flow..." <<std::endl;
228  preflow_test4.preflow(preflow_test4.GEN_FLOW);
229
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)) {
240    int c=cap[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;
244  }
245
246  std::cout << "\nThe given flow value is "
247            << preflow_test4.flowValue();
248 
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; 
254  else {
255    std::cout << "ERROR! It is not equal to all three min cut values! "
256              <<std::endl; 
257    error=true;
258  }
259 
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;
262
263  return 0;
264}
Note: See TracBrowser for help on using the repository browser.