1 /* -*- C++ -*- |
|
2 * src/test/preflow_test.cc - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #include <fstream> |
|
18 #include <string> |
|
19 |
|
20 #include "test_tools.h" |
|
21 #include <lemon/smart_graph.h> |
|
22 #include <lemon/dimacs.h> |
|
23 #include <lemon/preflow.h> |
|
24 #include <lemon/concept/graph.h> |
|
25 #include <lemon/concept/maps.h> |
|
26 |
|
27 using namespace lemon; |
|
28 |
|
29 void check_Preflow() |
|
30 { |
|
31 typedef int VType; |
|
32 typedef concept::StaticGraph Graph; |
|
33 |
|
34 typedef Graph::Node Node; |
|
35 typedef Graph::Edge Edge; |
|
36 typedef concept::ReadMap<Edge,VType> CapMap; |
|
37 typedef concept::ReadWriteMap<Edge,VType> FlowMap; |
|
38 typedef concept::ReadWriteMap<Node,bool> CutMap; |
|
39 |
|
40 typedef Preflow<Graph, int, CapMap, FlowMap> PType; |
|
41 |
|
42 Graph g; |
|
43 Node n; |
|
44 CapMap cap; |
|
45 FlowMap flow; |
|
46 CutMap cut; |
|
47 |
|
48 PType preflow_test(g,n,n,cap,flow); |
|
49 |
|
50 preflow_test.run(); |
|
51 preflow_test.flowValue(); |
|
52 preflow_test.source(n); |
|
53 preflow_test.flowMap(flow); |
|
54 |
|
55 preflow_test.phase1(PType::NO_FLOW); |
|
56 preflow_test.minCut(cut); |
|
57 |
|
58 preflow_test.phase2(); |
|
59 preflow_test.target(n); |
|
60 preflow_test.capacityMap(cap); |
|
61 preflow_test.minMinCut(cut); |
|
62 preflow_test.maxMinCut(cut); |
|
63 } |
|
64 |
|
65 int cut_value ( SmartGraph& g, SmartGraph::NodeMap<bool>& cut, |
|
66 SmartGraph::EdgeMap<int>& cap) { |
|
67 |
|
68 int c=0; |
|
69 for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) { |
|
70 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; |
|
71 } |
|
72 return c; |
|
73 } |
|
74 |
|
75 int main() { |
|
76 |
|
77 typedef SmartGraph Graph; |
|
78 |
|
79 typedef Graph::Node Node; |
|
80 typedef Graph::NodeIt NodeIt; |
|
81 typedef Graph::EdgeIt EdgeIt; |
|
82 typedef Graph::EdgeMap<int> CapMap; |
|
83 typedef Graph::EdgeMap<int> FlowMap; |
|
84 typedef Graph::NodeMap<bool> CutMap; |
|
85 |
|
86 typedef Preflow<Graph, int> PType; |
|
87 |
|
88 std::string f_name; |
|
89 if( getenv("srcdir") ) |
|
90 f_name = std::string(getenv("srcdir")); |
|
91 else f_name = "."; |
|
92 f_name += "/preflow_graph.dim"; |
|
93 |
|
94 std::ifstream file(f_name.c_str()); |
|
95 |
|
96 check(file, "Input file '" << f_name << "' not found."); |
|
97 |
|
98 Graph g; |
|
99 Node s, t; |
|
100 CapMap cap(g); |
|
101 readDimacs(file, g, cap, s, t); |
|
102 |
|
103 FlowMap flow(g,0); |
|
104 |
|
105 |
|
106 |
|
107 PType preflow_test(g, s, t, cap, flow); |
|
108 preflow_test.run(PType::ZERO_FLOW); |
|
109 |
|
110 CutMap min_cut(g,false); |
|
111 preflow_test.minCut(min_cut); |
|
112 int min_cut_value=cut_value(g,min_cut,cap); |
|
113 |
|
114 CutMap min_min_cut(g,false); |
|
115 preflow_test.minMinCut(min_min_cut); |
|
116 int min_min_cut_value=cut_value(g,min_min_cut,cap); |
|
117 |
|
118 CutMap max_min_cut(g,false); |
|
119 preflow_test.maxMinCut(max_min_cut); |
|
120 int max_min_cut_value=cut_value(g,max_min_cut,cap); |
|
121 |
|
122 check(preflow_test.flowValue() == min_cut_value && |
|
123 min_cut_value == min_min_cut_value && |
|
124 min_min_cut_value == max_min_cut_value, |
|
125 "The max flow value is not equal to the three min cut values."); |
|
126 |
|
127 int flow_value=preflow_test.flowValue(); |
|
128 |
|
129 |
|
130 |
|
131 for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; |
|
132 preflow_test.capacityMap(cap); |
|
133 |
|
134 preflow_test.phase1(PType::PRE_FLOW); |
|
135 |
|
136 CutMap min_cut1(g,false); |
|
137 preflow_test.minCut(min_cut1); |
|
138 min_cut_value=cut_value(g,min_cut1,cap); |
|
139 |
|
140 check(preflow_test.flowValue() == min_cut_value && |
|
141 min_cut_value == 2*flow_value, |
|
142 "The max flow value or the min cut value is wrong."); |
|
143 |
|
144 preflow_test.phase2(); |
|
145 |
|
146 CutMap min_cut2(g,false); |
|
147 preflow_test.minCut(min_cut2); |
|
148 min_cut_value=cut_value(g,min_cut2,cap); |
|
149 |
|
150 CutMap min_min_cut2(g,false); |
|
151 preflow_test.minMinCut(min_min_cut2); |
|
152 min_min_cut_value=cut_value(g,min_min_cut2,cap); |
|
153 |
|
154 preflow_test.maxMinCut(max_min_cut); |
|
155 max_min_cut_value=cut_value(g,max_min_cut,cap); |
|
156 |
|
157 check(preflow_test.flowValue() == min_cut_value && |
|
158 min_cut_value == min_min_cut_value && |
|
159 min_min_cut_value == max_min_cut_value && |
|
160 min_cut_value == 2*flow_value, |
|
161 "The max flow value or the three min cut values were not doubled"); |
|
162 |
|
163 |
|
164 |
|
165 EdgeIt e(g); |
|
166 for( int i=1; i==10; ++i ) { |
|
167 flow.set(e,0); |
|
168 ++e; |
|
169 } |
|
170 |
|
171 preflow_test.flowMap(flow); |
|
172 |
|
173 NodeIt tmp1(g,s); |
|
174 ++tmp1; |
|
175 if ( tmp1 != INVALID ) s=tmp1; |
|
176 |
|
177 NodeIt tmp2(g,t); |
|
178 ++tmp2; |
|
179 if ( tmp2 != INVALID ) t=tmp2; |
|
180 |
|
181 preflow_test.source(s); |
|
182 preflow_test.target(t); |
|
183 |
|
184 preflow_test.run(); |
|
185 |
|
186 CutMap min_cut3(g,false); |
|
187 preflow_test.minCut(min_cut3); |
|
188 min_cut_value=cut_value(g,min_cut3,cap); |
|
189 |
|
190 CutMap min_min_cut3(g,false); |
|
191 preflow_test.minMinCut(min_min_cut3); |
|
192 min_min_cut_value=cut_value(g,min_min_cut3,cap); |
|
193 |
|
194 preflow_test.maxMinCut(max_min_cut); |
|
195 max_min_cut_value=cut_value(g,max_min_cut,cap); |
|
196 |
|
197 check(preflow_test.flowValue() == min_cut_value && |
|
198 min_cut_value == min_min_cut_value && |
|
199 min_min_cut_value == max_min_cut_value, |
|
200 "The max flow value or the three min cut values are incorrect."); |
|
201 } |
|