26 #include <lemon/concepts/graph.h> |
26 #include <lemon/concepts/graph.h> |
27 #include <lemon/concepts/maps.h> |
27 #include <lemon/concepts/maps.h> |
28 |
28 |
29 using namespace lemon; |
29 using namespace lemon; |
30 |
30 |
31 void check_Preflow() |
31 void checkPreflow() |
32 { |
32 { |
33 typedef int VType; |
33 typedef int VType; |
34 typedef concepts::Graph Graph; |
34 typedef concepts::Graph Graph; |
35 |
35 |
36 typedef Graph::Node Node; |
36 typedef Graph::Node Node; |
37 typedef Graph::Edge Edge; |
37 typedef Graph::Edge Edge; |
38 typedef concepts::ReadMap<Edge,VType> CapMap; |
38 typedef concepts::ReadMap<Edge,VType> CapMap; |
39 typedef concepts::ReadWriteMap<Edge,VType> FlowMap; |
39 typedef concepts::ReadWriteMap<Edge,VType> FlowMap; |
40 typedef concepts::ReadWriteMap<Node,bool> CutMap; |
40 typedef concepts::WriteMap<Node,bool> CutMap; |
41 |
41 |
42 typedef Preflow<Graph, int, CapMap, FlowMap> PType; |
|
43 |
|
44 Graph g; |
42 Graph g; |
45 Node n; |
43 Node n; |
|
44 Edge e; |
46 CapMap cap; |
45 CapMap cap; |
47 FlowMap flow; |
46 FlowMap flow; |
48 CutMap cut; |
47 CutMap cut; |
49 |
48 |
50 PType preflow_test(g,n,n,cap,flow); |
49 Preflow<Graph, CapMap>::DefFlowMap<FlowMap>::Create preflow_test(g,cap,n,n); |
51 |
50 |
|
51 preflow_test.capacityMap(cap); |
|
52 flow = preflow_test.flowMap(); |
|
53 preflow_test.flowMap(flow); |
|
54 preflow_test.source(n); |
|
55 preflow_test.target(n); |
|
56 |
|
57 preflow_test.init(); |
|
58 preflow_test.flowInit(cap); |
|
59 preflow_test.startFirstPhase(); |
|
60 preflow_test.startSecondPhase(); |
52 preflow_test.run(); |
61 preflow_test.run(); |
|
62 preflow_test.runMinCut(); |
|
63 |
53 preflow_test.flowValue(); |
64 preflow_test.flowValue(); |
54 preflow_test.source(n); |
65 preflow_test.minCut(n); |
55 preflow_test.flowMap(flow); |
66 preflow_test.minCutMap(cut); |
56 |
67 preflow_test.flow(e); |
57 preflow_test.phase1(PType::NO_FLOW); |
68 |
58 preflow_test.minCut(cut); |
69 } |
59 |
70 |
60 preflow_test.phase2(); |
71 int cutValue (const SmartGraph& g, |
61 preflow_test.target(n); |
72 const SmartGraph::NodeMap<bool>& cut, |
62 preflow_test.capacityMap(cap); |
73 const SmartGraph::EdgeMap<int>& cap) { |
63 preflow_test.minMinCut(cut); |
|
64 preflow_test.maxMinCut(cut); |
|
65 } |
|
66 |
|
67 int cut_value ( SmartGraph& g, SmartGraph::NodeMap<bool>& cut, |
|
68 SmartGraph::EdgeMap<int>& cap) { |
|
69 |
74 |
70 int c=0; |
75 int c=0; |
71 for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) { |
76 for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) { |
72 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; |
77 if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; |
73 } |
78 } |
74 return c; |
79 return c; |
|
80 } |
|
81 |
|
82 bool checkFlow(const SmartGraph& g, |
|
83 const SmartGraph::EdgeMap<int>& flow, |
|
84 const SmartGraph::EdgeMap<int>& cap, |
|
85 SmartGraph::Node s, SmartGraph::Node t) { |
|
86 |
|
87 for (SmartGraph::EdgeIt e(g); e != INVALID; ++e) { |
|
88 if (flow[e] < 0 || flow[e] > cap[e]) return false; |
|
89 } |
|
90 |
|
91 for (SmartGraph::NodeIt n(g); n != INVALID; ++n) { |
|
92 if (n == s || n == t) continue; |
|
93 int sum = 0; |
|
94 for (SmartGraph::OutEdgeIt e(g, n); e != INVALID; ++e) { |
|
95 sum += flow[e]; |
|
96 } |
|
97 for (SmartGraph::InEdgeIt e(g, n); e != INVALID; ++e) { |
|
98 sum -= flow[e]; |
|
99 } |
|
100 if (sum != 0) return false; |
|
101 } |
|
102 return true; |
75 } |
103 } |
76 |
104 |
77 int main() { |
105 int main() { |
78 |
106 |
79 typedef SmartGraph Graph; |
107 typedef SmartGraph Graph; |
100 Graph g; |
128 Graph g; |
101 Node s, t; |
129 Node s, t; |
102 CapMap cap(g); |
130 CapMap cap(g); |
103 readDimacs(file, g, cap, s, t); |
131 readDimacs(file, g, cap, s, t); |
104 |
132 |
105 FlowMap flow(g,0); |
133 PType preflow_test(g, cap, s, t); |
106 |
134 preflow_test.run(); |
107 |
|
108 |
|
109 PType preflow_test(g, s, t, cap, flow); |
|
110 preflow_test.run(PType::ZERO_FLOW); |
|
111 |
135 |
112 CutMap min_cut(g,false); |
136 check(checkFlow(g, preflow_test.flowMap(), cap, s, t), |
113 preflow_test.minCut(min_cut); |
137 "The flow is not feasible."); |
114 int min_cut_value=cut_value(g,min_cut,cap); |
138 |
115 |
139 CutMap min_cut(g); |
116 CutMap min_min_cut(g,false); |
140 preflow_test.minCutMap(min_cut); |
117 preflow_test.minMinCut(min_min_cut); |
141 int min_cut_value=cutValue(g,min_cut,cap); |
118 int min_min_cut_value=cut_value(g,min_min_cut,cap); |
142 |
119 |
143 check(preflow_test.flowValue() == min_cut_value, |
120 CutMap max_min_cut(g,false); |
|
121 preflow_test.maxMinCut(max_min_cut); |
|
122 int max_min_cut_value=cut_value(g,max_min_cut,cap); |
|
123 |
|
124 check(preflow_test.flowValue() == min_cut_value && |
|
125 min_cut_value == min_min_cut_value && |
|
126 min_min_cut_value == max_min_cut_value, |
|
127 "The max flow value is not equal to the three min cut values."); |
144 "The max flow value is not equal to the three min cut values."); |
128 |
145 |
|
146 FlowMap flow(g); |
|
147 flow = preflow_test.flowMap(); |
|
148 |
129 int flow_value=preflow_test.flowValue(); |
149 int flow_value=preflow_test.flowValue(); |
130 |
150 |
131 |
|
132 |
|
133 for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; |
151 for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; |
134 preflow_test.capacityMap(cap); |
152 preflow_test.flowInit(flow); |
135 |
153 preflow_test.startFirstPhase(); |
136 preflow_test.phase1(PType::PRE_FLOW); |
154 |
137 |
155 CutMap min_cut1(g); |
138 CutMap min_cut1(g,false); |
156 preflow_test.minCutMap(min_cut1); |
139 preflow_test.minCut(min_cut1); |
157 min_cut_value=cutValue(g,min_cut1,cap); |
140 min_cut_value=cut_value(g,min_cut1,cap); |
|
141 |
158 |
142 check(preflow_test.flowValue() == min_cut_value && |
159 check(preflow_test.flowValue() == min_cut_value && |
143 min_cut_value == 2*flow_value, |
160 min_cut_value == 2*flow_value, |
144 "The max flow value or the min cut value is wrong."); |
161 "The max flow value or the min cut value is wrong."); |
145 |
162 |
146 preflow_test.phase2(); |
163 preflow_test.startSecondPhase(); |
147 |
164 |
148 CutMap min_cut2(g,false); |
165 check(checkFlow(g, preflow_test.flowMap(), cap, s, t), |
149 preflow_test.minCut(min_cut2); |
166 "The flow is not feasible."); |
150 min_cut_value=cut_value(g,min_cut2,cap); |
167 |
|
168 CutMap min_cut2(g); |
|
169 preflow_test.minCutMap(min_cut2); |
|
170 min_cut_value=cutValue(g,min_cut2,cap); |
151 |
171 |
152 CutMap min_min_cut2(g,false); |
|
153 preflow_test.minMinCut(min_min_cut2); |
|
154 min_min_cut_value=cut_value(g,min_min_cut2,cap); |
|
155 |
|
156 preflow_test.maxMinCut(max_min_cut); |
|
157 max_min_cut_value=cut_value(g,max_min_cut,cap); |
|
158 |
|
159 check(preflow_test.flowValue() == min_cut_value && |
172 check(preflow_test.flowValue() == min_cut_value && |
160 min_cut_value == min_min_cut_value && |
|
161 min_min_cut_value == max_min_cut_value && |
|
162 min_cut_value == 2*flow_value, |
173 min_cut_value == 2*flow_value, |
163 "The max flow value or the three min cut values were not doubled"); |
174 "The max flow value or the three min cut values were not doubled"); |
164 |
175 |
165 |
|
166 |
|
167 EdgeIt e(g); |
|
168 for( int i=1; i==10; ++i ) { |
|
169 flow.set(e,0); |
|
170 ++e; |
|
171 } |
|
172 |
176 |
173 preflow_test.flowMap(flow); |
177 preflow_test.flowMap(flow); |
174 |
178 |
175 NodeIt tmp1(g,s); |
179 NodeIt tmp1(g,s); |
176 ++tmp1; |
180 ++tmp1; |
183 preflow_test.source(s); |
187 preflow_test.source(s); |
184 preflow_test.target(t); |
188 preflow_test.target(t); |
185 |
189 |
186 preflow_test.run(); |
190 preflow_test.run(); |
187 |
191 |
188 CutMap min_cut3(g,false); |
192 CutMap min_cut3(g); |
189 preflow_test.minCut(min_cut3); |
193 preflow_test.minCutMap(min_cut3); |
190 min_cut_value=cut_value(g,min_cut3,cap); |
194 min_cut_value=cutValue(g,min_cut3,cap); |
191 |
195 |
192 CutMap min_min_cut3(g,false); |
196 |
193 preflow_test.minMinCut(min_min_cut3); |
197 check(preflow_test.flowValue() == min_cut_value, |
194 min_min_cut_value=cut_value(g,min_min_cut3,cap); |
|
195 |
|
196 preflow_test.maxMinCut(max_min_cut); |
|
197 max_min_cut_value=cut_value(g,max_min_cut,cap); |
|
198 |
|
199 check(preflow_test.flowValue() == min_cut_value && |
|
200 min_cut_value == min_min_cut_value && |
|
201 min_min_cut_value == max_min_cut_value, |
|
202 "The max flow value or the three min cut values are incorrect."); |
198 "The max flow value or the three min cut values are incorrect."); |
203 } |
199 |
|
200 return 0; |
|
201 } |