0
2
0
... | ... |
@@ -480,113 +480,111 @@ |
480 | 480 |
if (excess < 0 && n != _source) return false; |
481 | 481 |
(*_excess)[n] = excess; |
482 | 482 |
} |
483 | 483 |
|
484 | 484 |
typename Digraph::template NodeMap<bool> reached(_graph, false); |
485 | 485 |
|
486 | 486 |
_level->initStart(); |
487 | 487 |
_level->initAddItem(_target); |
488 | 488 |
|
489 | 489 |
std::vector<Node> queue; |
490 | 490 |
reached[_source] = true; |
491 | 491 |
|
492 | 492 |
queue.push_back(_target); |
493 | 493 |
reached[_target] = true; |
494 | 494 |
while (!queue.empty()) { |
495 | 495 |
_level->initNewLevel(); |
496 | 496 |
std::vector<Node> nqueue; |
497 | 497 |
for (int i = 0; i < int(queue.size()); ++i) { |
498 | 498 |
Node n = queue[i]; |
499 | 499 |
for (InArcIt e(_graph, n); e != INVALID; ++e) { |
500 | 500 |
Node u = _graph.source(e); |
501 | 501 |
if (!reached[u] && |
502 | 502 |
_tolerance.positive((*_capacity)[e] - (*_flow)[e])) { |
503 | 503 |
reached[u] = true; |
504 | 504 |
_level->initAddItem(u); |
505 | 505 |
nqueue.push_back(u); |
506 | 506 |
} |
507 | 507 |
} |
508 | 508 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
509 | 509 |
Node v = _graph.target(e); |
510 | 510 |
if (!reached[v] && _tolerance.positive((*_flow)[e])) { |
511 | 511 |
reached[v] = true; |
512 | 512 |
_level->initAddItem(v); |
513 | 513 |
nqueue.push_back(v); |
514 | 514 |
} |
515 | 515 |
} |
516 | 516 |
} |
517 | 517 |
queue.swap(nqueue); |
518 | 518 |
} |
519 | 519 |
_level->initFinish(); |
520 | 520 |
|
521 | 521 |
for (OutArcIt e(_graph, _source); e != INVALID; ++e) { |
522 | 522 |
Value rem = (*_capacity)[e] - (*_flow)[e]; |
523 | 523 |
if (_tolerance.positive(rem)) { |
524 | 524 |
Node u = _graph.target(e); |
525 | 525 |
if ((*_level)[u] == _level->maxLevel()) continue; |
526 | 526 |
_flow->set(e, (*_capacity)[e]); |
527 | 527 |
(*_excess)[u] += rem; |
528 |
if (u != _target && !_level->active(u)) { |
|
529 |
_level->activate(u); |
|
530 |
} |
|
531 | 528 |
} |
532 | 529 |
} |
533 | 530 |
for (InArcIt e(_graph, _source); e != INVALID; ++e) { |
534 | 531 |
Value rem = (*_flow)[e]; |
535 | 532 |
if (_tolerance.positive(rem)) { |
536 | 533 |
Node v = _graph.source(e); |
537 | 534 |
if ((*_level)[v] == _level->maxLevel()) continue; |
538 | 535 |
_flow->set(e, 0); |
539 | 536 |
(*_excess)[v] += rem; |
540 |
if (v != _target && !_level->active(v)) { |
|
541 |
_level->activate(v); |
|
542 | 537 |
} |
543 | 538 |
} |
544 |
|
|
539 |
for (NodeIt n(_graph); n != INVALID; ++n) |
|
540 |
if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n])) |
|
541 |
_level->activate(n); |
|
542 |
|
|
545 | 543 |
return true; |
546 | 544 |
} |
547 | 545 |
|
548 | 546 |
/// \brief Starts the first phase of the preflow algorithm. |
549 | 547 |
/// |
550 | 548 |
/// The preflow algorithm consists of two phases, this method runs |
551 | 549 |
/// the first phase. After the first phase the maximum flow value |
552 | 550 |
/// and a minimum value cut can already be computed, although a |
553 | 551 |
/// maximum flow is not yet obtained. So after calling this method |
554 | 552 |
/// \ref flowValue() returns the value of a maximum flow and \ref |
555 | 553 |
/// minCut() returns a minimum cut. |
556 | 554 |
/// \pre One of the \ref init() functions must be called before |
557 | 555 |
/// using this function. |
558 | 556 |
void startFirstPhase() { |
559 | 557 |
_phase = true; |
560 | 558 |
|
561 | 559 |
while (true) { |
562 | 560 |
int num = _node_num; |
563 | 561 |
|
564 | 562 |
Node n = INVALID; |
565 | 563 |
int level = -1; |
566 | 564 |
|
567 | 565 |
while (num > 0) { |
568 | 566 |
n = _level->highestActive(); |
569 | 567 |
if (n == INVALID) goto first_phase_done; |
570 | 568 |
level = _level->highestActiveLevel(); |
571 | 569 |
--num; |
572 | 570 |
|
573 | 571 |
Value excess = (*_excess)[n]; |
574 | 572 |
int new_level = _level->maxLevel(); |
575 | 573 |
|
576 | 574 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
577 | 575 |
Value rem = (*_capacity)[e] - (*_flow)[e]; |
578 | 576 |
if (!_tolerance.positive(rem)) continue; |
579 | 577 |
Node v = _graph.target(e); |
580 | 578 |
if ((*_level)[v] < level) { |
581 | 579 |
if (!_level->active(v) && v != _target) { |
582 | 580 |
_level->activate(v); |
583 | 581 |
} |
584 | 582 |
if (!_tolerance.less(rem, excess)) { |
585 | 583 |
_flow->set(e, (*_flow)[e] + excess); |
586 | 584 |
(*_excess)[v] += excess; |
587 | 585 |
excess = 0; |
588 | 586 |
goto no_more_push_1; |
589 | 587 |
} else { |
590 | 588 |
excess -= rem; |
591 | 589 |
(*_excess)[v] += rem; |
592 | 590 |
_flow->set(e, (*_capacity)[e]); |
... | ... |
@@ -106,140 +106,166 @@ |
106 | 106 |
preflow_test.startFirstPhase(); |
107 | 107 |
preflow_test.startSecondPhase(); |
108 | 108 |
preflow_test.run(); |
109 | 109 |
preflow_test.runMinCut(); |
110 | 110 |
|
111 | 111 |
v = const_preflow_test.flowValue(); |
112 | 112 |
v = const_preflow_test.flow(e); |
113 | 113 |
const FlowMap& fm = const_preflow_test.flowMap(); |
114 | 114 |
b = const_preflow_test.minCut(n); |
115 | 115 |
const_preflow_test.minCutMap(cut); |
116 | 116 |
|
117 | 117 |
ignore_unused_variable_warning(fm); |
118 | 118 |
} |
119 | 119 |
|
120 | 120 |
int cutValue (const SmartDigraph& g, |
121 | 121 |
const SmartDigraph::NodeMap<bool>& cut, |
122 | 122 |
const SmartDigraph::ArcMap<int>& cap) { |
123 | 123 |
|
124 | 124 |
int c=0; |
125 | 125 |
for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { |
126 | 126 |
if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; |
127 | 127 |
} |
128 | 128 |
return c; |
129 | 129 |
} |
130 | 130 |
|
131 | 131 |
bool checkFlow(const SmartDigraph& g, |
132 | 132 |
const SmartDigraph::ArcMap<int>& flow, |
133 | 133 |
const SmartDigraph::ArcMap<int>& cap, |
134 | 134 |
SmartDigraph::Node s, SmartDigraph::Node t) { |
135 | 135 |
|
136 | 136 |
for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { |
137 | 137 |
if (flow[e] < 0 || flow[e] > cap[e]) return false; |
138 | 138 |
} |
139 | 139 |
|
140 | 140 |
for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { |
141 | 141 |
if (n == s || n == t) continue; |
142 | 142 |
int sum = 0; |
143 | 143 |
for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { |
144 | 144 |
sum += flow[e]; |
145 | 145 |
} |
146 | 146 |
for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { |
147 | 147 |
sum -= flow[e]; |
148 | 148 |
} |
149 | 149 |
if (sum != 0) return false; |
150 | 150 |
} |
151 | 151 |
return true; |
152 | 152 |
} |
153 | 153 |
|
154 |
void initFlowTest() |
|
155 |
{ |
|
156 |
DIGRAPH_TYPEDEFS(SmartDigraph); |
|
157 |
|
|
158 |
SmartDigraph g; |
|
159 |
SmartDigraph::ArcMap<int> cap(g),iflow(g); |
|
160 |
Node s=g.addNode(); Node t=g.addNode(); |
|
161 |
Node n1=g.addNode(); Node n2=g.addNode(); |
|
162 |
Arc a; |
|
163 |
a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; |
|
164 |
a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; |
|
165 |
a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; |
|
166 |
|
|
167 |
Preflow<SmartDigraph> pre(g,cap,s,t); |
|
168 |
pre.init(iflow); |
|
169 |
pre.startFirstPhase(); |
|
170 |
check(pre.flowValue() == 10, "The incorrect max flow value."); |
|
171 |
check(pre.minCut(s), "Wrong min cut (Node s)."); |
|
172 |
check(pre.minCut(n1), "Wrong min cut (Node n1)."); |
|
173 |
check(!pre.minCut(n2), "Wrong min cut (Node n2)."); |
|
174 |
check(!pre.minCut(t), "Wrong min cut (Node t)."); |
|
175 |
} |
|
176 |
|
|
177 |
|
|
154 | 178 |
int main() { |
155 | 179 |
|
156 | 180 |
typedef SmartDigraph Digraph; |
157 | 181 |
|
158 | 182 |
typedef Digraph::Node Node; |
159 | 183 |
typedef Digraph::NodeIt NodeIt; |
160 | 184 |
typedef Digraph::ArcIt ArcIt; |
161 | 185 |
typedef Digraph::ArcMap<int> CapMap; |
162 | 186 |
typedef Digraph::ArcMap<int> FlowMap; |
163 | 187 |
typedef Digraph::NodeMap<bool> CutMap; |
164 | 188 |
|
165 | 189 |
typedef Preflow<Digraph, CapMap> PType; |
166 | 190 |
|
167 | 191 |
Digraph g; |
168 | 192 |
Node s, t; |
169 | 193 |
CapMap cap(g); |
170 | 194 |
std::istringstream input(test_lgf); |
171 | 195 |
DigraphReader<Digraph>(g,input). |
172 | 196 |
arcMap("capacity", cap). |
173 | 197 |
node("source",s). |
174 | 198 |
node("target",t). |
175 | 199 |
run(); |
176 | 200 |
|
177 | 201 |
PType preflow_test(g, cap, s, t); |
178 | 202 |
preflow_test.run(); |
179 | 203 |
|
180 | 204 |
check(checkFlow(g, preflow_test.flowMap(), cap, s, t), |
181 | 205 |
"The flow is not feasible."); |
182 | 206 |
|
183 | 207 |
CutMap min_cut(g); |
184 | 208 |
preflow_test.minCutMap(min_cut); |
185 | 209 |
int min_cut_value=cutValue(g,min_cut,cap); |
186 | 210 |
|
187 | 211 |
check(preflow_test.flowValue() == min_cut_value, |
188 | 212 |
"The max flow value is not equal to the three min cut values."); |
189 | 213 |
|
190 | 214 |
FlowMap flow(g); |
191 | 215 |
for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e]; |
192 | 216 |
|
193 | 217 |
int flow_value=preflow_test.flowValue(); |
194 | 218 |
|
195 | 219 |
for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; |
196 | 220 |
preflow_test.init(flow); |
197 | 221 |
preflow_test.startFirstPhase(); |
198 | 222 |
|
199 | 223 |
CutMap min_cut1(g); |
200 | 224 |
preflow_test.minCutMap(min_cut1); |
201 | 225 |
min_cut_value=cutValue(g,min_cut1,cap); |
202 | 226 |
|
203 | 227 |
check(preflow_test.flowValue() == min_cut_value && |
204 | 228 |
min_cut_value == 2*flow_value, |
205 | 229 |
"The max flow value or the min cut value is wrong."); |
206 | 230 |
|
207 | 231 |
preflow_test.startSecondPhase(); |
208 | 232 |
|
209 | 233 |
check(checkFlow(g, preflow_test.flowMap(), cap, s, t), |
210 | 234 |
"The flow is not feasible."); |
211 | 235 |
|
212 | 236 |
CutMap min_cut2(g); |
213 | 237 |
preflow_test.minCutMap(min_cut2); |
214 | 238 |
min_cut_value=cutValue(g,min_cut2,cap); |
215 | 239 |
|
216 | 240 |
check(preflow_test.flowValue() == min_cut_value && |
217 | 241 |
min_cut_value == 2*flow_value, |
218 | 242 |
"The max flow value or the three min cut values were not doubled"); |
219 | 243 |
|
220 | 244 |
|
221 | 245 |
preflow_test.flowMap(flow); |
222 | 246 |
|
223 | 247 |
NodeIt tmp1(g,s); |
224 | 248 |
++tmp1; |
225 | 249 |
if ( tmp1 != INVALID ) s=tmp1; |
226 | 250 |
|
227 | 251 |
NodeIt tmp2(g,t); |
228 | 252 |
++tmp2; |
229 | 253 |
if ( tmp2 != INVALID ) t=tmp2; |
230 | 254 |
|
231 | 255 |
preflow_test.source(s); |
232 | 256 |
preflow_test.target(t); |
233 | 257 |
|
234 | 258 |
preflow_test.run(); |
235 | 259 |
|
236 | 260 |
CutMap min_cut3(g); |
237 | 261 |
preflow_test.minCutMap(min_cut3); |
238 | 262 |
min_cut_value=cutValue(g,min_cut3,cap); |
239 | 263 |
|
240 | 264 |
|
241 | 265 |
check(preflow_test.flowValue() == min_cut_value, |
242 | 266 |
"The max flow value or the three min cut values are incorrect."); |
243 | 267 |
|
268 |
initFlowTest(); |
|
269 |
|
|
244 | 270 |
return 0; |
245 | 271 |
} |
0 comments (0 inline)