COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/preflow.cc @ 469:5f6ea657b75d

Last change on this file since 469:5f6ea657b75d was 451:6b36be4cffa4, checked in by jacint, 21 years ago

Changes in the interface and new test program added.

File size: 7.4 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 hugo;
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 
23  std::cout <<
24    "\n  Testing preflow.h on a graph with " <<
25    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
26           << std::endl;
27
28
29  Graph::EdgeMap<int> flow(G,0);
30  Preflow<Graph, int> preflow_test(G, s, t, cap, flow);
31  std::cout << "\nCalling run() (flow must be constant zero)..."<<std::endl;
32  ts.reset();
33  preflow_test.run();
34  std::cout << "Elapsed time: " << ts << std::endl;
35
36  Graph::NodeMap<bool> mincut(G);
37  preflow_test.minMinCut(mincut);
38  int min_min_cut_value=0;
39  Graph::NodeMap<bool> cut(G);
40  preflow_test.minCut(cut);
41  int min_cut_value=0;
42  Graph::NodeMap<bool> maxcut(G);
43  preflow_test.maxMinCut(maxcut);
44  int max_min_cut_value=0;
45  EdgeIt e;
46  for(G.first(e); G.valid(e); G.next(e)) {
47    int c=cap[e];
48    if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=c;
49    if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=c;
50    if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) max_min_cut_value+=c;
51  }
52
53  std::cout << "\nChecking the result: " <<std::endl; 
54  std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl;
55  std::cout << "Min cut value: "<< min_cut_value << std::endl;
56  std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
57  std::cout << "Max min cut value: "<< max_min_cut_value <<
58    std::endl;
59
60  if ( preflow_test.flowValue() == min_cut_value &&
61       min_cut_value == min_min_cut_value &&
62       min_min_cut_value == max_min_cut_value )
63    std::cout << "They are equal. " <<std::endl; 
64
65
66
67
68
69  Preflow<Graph, int> preflow_test2(G, s, t, cap, flow);
70  std::cout << "\n\nCalling preflow(GEN_FLOW) with the given maximum flow..."<<std::endl;
71  ts.reset();
72  preflow_test2.preflow(preflow_test2.GEN_FLOW);
73  std::cout << "Elapsed time: " << ts << std::endl;
74
75  Graph::NodeMap<bool> mincut2(G);
76  preflow_test.minMinCut(mincut2);
77  int min_min_cut2_value=0;
78  Graph::NodeMap<bool> cut2(G);
79  preflow_test.minCut(cut2);
80  int min_cut2_value=0;
81  Graph::NodeMap<bool> maxcut2(G);
82  preflow_test.maxMinCut(maxcut2);
83  int max_min_cut2_value=0;
84  for(G.first(e); G.valid(e); G.next(e)) {
85    int c=cap[e];
86    if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut2_value+=c;
87    if (cut2[G.tail(e)] && !cut2[G.head(e)]) min_cut2_value+=c;
88    if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) max_min_cut2_value+=c;
89  }
90
91  std::cout << "\nThe given flow value is "
92            << preflow_test2.flowValue();
93
94  if ( preflow_test2.flowValue() == min_cut2_value &&
95       min_cut2_value == min_min_cut2_value &&
96       min_min_cut2_value == max_min_cut2_value )
97    std::cout <<", which is equal to all three min cut values."
98              <<std::endl; 
99
100
101
102
103
104  Graph::EdgeMap<int> flow3(G,0);
105  Preflow<Graph, int> preflow_test3(G, s, t, cap, flow3);
106  std::cout << "\n\nCalling preflowPhase0(PREFLOW) on the constant zero flow..."<<std::endl;
107  ts.reset();
108  preflow_test3.preflowPhase0(preflow_test3.PREFLOW);
109  std::cout << "Elapsed time: " << ts << std::endl;
110  Graph::NodeMap<bool> actcut3(G);
111  std::cout << "\nCalling actMinCut()..."<<std::endl;
112  preflow_test3.actMinCut(actcut3);
113  std::cout << "Calling preflowPhase1() on the given flow..."<<std::endl;
114  ts.reset();
115  preflow_test3.preflowPhase1();
116  std::cout << "Elapsed time: " << ts << std::endl;
117 
118  int act_min_cut3_value=0;
119 
120  Graph::NodeMap<bool> mincut3(G);
121  preflow_test.minMinCut(mincut3);
122  int min_min_cut3_value=0;
123 
124  Graph::NodeMap<bool> cut3(G);
125  preflow_test.minCut(cut3);
126  int min_cut3_value=0;
127 
128  Graph::NodeMap<bool> maxcut3(G);
129  preflow_test.maxMinCut(maxcut3);
130  int max_min_cut3_value=0;
131 
132  for(G.first(e); G.valid(e); G.next(e)) {
133    int c=cap[e];
134    if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut3_value+=c;
135    if (cut3[G.tail(e)] && !cut3[G.head(e)]) min_cut3_value+=c;
136    if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) max_min_cut3_value+=c;
137    if (actcut3[G.tail(e)] && !actcut3[G.head(e)]) act_min_cut3_value+=c;
138  }
139
140 std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<<
141   act_min_cut3_value;
142
143  if ( preflow_test3.flowValue() == min_cut3_value &&
144       min_cut3_value == min_min_cut3_value &&
145       min_min_cut3_value == max_min_cut3_value &&
146       max_min_cut3_value == act_min_cut3_value ) {
147    std::cout <<
148      ", which is equal to the given flow value and to all three min cut values after phase 1."
149              <<std::endl; 
150  }
151
152
153
154
155
156  Graph::EdgeMap<int> flow4(G,0);
157  Preflow<Graph, int> preflow_test4(G, s, t, cap, flow4);
158  std::cout <<
159    "\n\nCalling preflow(PREFLOW) with the constant 0 flow, the result is f..."
160            <<std::endl;
161  preflow_test4.preflow(preflow_test4.PREFLOW);
162
163  std::cout << "Swapping the source and the target, "<<std::endl;
164  std::cout << "by calling resetSource(t) and resetTarget(s)..."
165            <<std::endl;
166  preflow_test4.resetSource(t);
167  preflow_test4.resetTarget(s);
168
169  std::cout <<
170    "Calling preflow(PREFLOW) to find a maximum t-s flow starting with flow f..."
171            <<std::endl;
172  preflow_test4.preflow(preflow_test4.PREFLOW);
173
174  Graph::NodeMap<bool> mincut4(G);
175  preflow_test4.minMinCut(mincut4);
176  int min_min_cut4_value=0;
177  Graph::NodeMap<bool> cut4(G);
178  preflow_test4.minCut(cut4);
179  int min_cut4_value=0;
180  Graph::NodeMap<bool> maxcut4(G);
181  preflow_test4.maxMinCut(maxcut4);
182  int max_min_cut4_value=0;
183  for(G.first(e); G.valid(e); G.next(e)) {
184    int c=cap[e];
185    if (mincut4[G.tail(e)] && !mincut4[G.head(e)]) min_min_cut4_value+=c;
186    if (cut4[G.tail(e)] && !cut4[G.head(e)]) min_cut4_value+=c;
187    if (maxcut4[G.tail(e)] && !maxcut4[G.head(e)]) max_min_cut4_value+=c;
188  }
189
190  std::cout << "\nThe given flow value is "
191            << preflow_test4.flowValue();
192 
193  if ( preflow_test4.flowValue() == min_cut4_value &&
194       min_cut4_value == min_min_cut4_value &&
195       min_min_cut4_value == max_min_cut4_value )
196    std::cout <<", which is equal to all three min cut values."
197              <<std::endl; 
198
199
200
201
202  Graph::EdgeMap<int> flow5(G,0);
203  std::cout << "Resetting the stored flow to constant zero, by calling resetFlow..."
204            <<std::endl;
205  preflow_test4.resetFlow(flow5);
206  std::cout <<
207    "Calling preflow(GEN_FLOW) to find a maximum t-s flow "<<std::endl;
208  std::cout <<
209    "starting with this constant zero flow..." <<std::endl;
210  preflow_test4.preflow(preflow_test4.GEN_FLOW);
211
212  Graph::NodeMap<bool> mincut5(G);
213  preflow_test4.minMinCut(mincut5);
214  int min_min_cut5_value=0;
215  Graph::NodeMap<bool> cut5(G);
216  preflow_test4.minCut(cut5);
217  int min_cut5_value=0;
218  Graph::NodeMap<bool> maxcut5(G);
219  preflow_test4.maxMinCut(maxcut5);
220  int max_min_cut5_value=0;
221  for(G.first(e); G.valid(e); G.next(e)) {
222    int c=cap[e];
223    if (mincut5[G.tail(e)] && !mincut5[G.head(e)]) min_min_cut5_value+=c;
224    if (cut5[G.tail(e)] && !cut5[G.head(e)]) min_cut5_value+=c;
225    if (maxcut5[G.tail(e)] && !maxcut5[G.head(e)]) max_min_cut5_value+=c;
226  }
227
228  std::cout << "\nThe given flow value is "
229            << preflow_test4.flowValue();
230 
231  if ( preflow_test4.flowValue() == min_cut5_value &&
232       min_cut5_value == min_min_cut5_value &&
233       min_min_cut5_value == max_min_cut5_value )
234    std::cout <<", which is equal to all three min cut values."
235              <<std::endl<<std::endl; 
236
237
238  return 0;
239}
Note: See TracBrowser for help on using the repository browser.