27 #include <lemon/iterable_maps.h> |
29 #include <lemon/iterable_maps.h> |
28 |
30 |
29 |
31 |
30 /// \file |
32 /// \file |
31 /// \ingroup flowalgs |
33 /// \ingroup flowalgs |
32 /// Implementation of the Hao-Orlin algorithms class for testing network |
34 /// \brief Implementation of the Hao-Orlin algorithm. |
|
35 /// |
|
36 /// Implementation of the HaoOrlin algorithms class for testing network |
33 /// reliability. |
37 /// reliability. |
34 |
38 |
35 namespace lemon { |
39 namespace lemon { |
36 |
40 |
37 /// \addtogroup flowalgs |
41 /// \ingroup flowalgs |
38 /// @{ |
42 /// |
39 |
43 /// \brief %Hao-Orlin algorithm for calculate minimum cut in directed graphs. |
40 /// %Hao-Orlin algorithm for calculate minimum cut in directed graphs. |
|
41 /// |
44 /// |
42 /// Hao-Orlin calculates the minimum cut in directed graphs. It |
45 /// Hao-Orlin calculates the minimum cut in directed graphs. It |
43 /// separates the nodes of the graph into two disjoint sets and the |
46 /// separates the nodes of the graph into two disjoint sets, |
44 /// summary of the edge capacities go from the first set to the |
47 /// \f$ V_{out} \f$ and \f$ V_{in} \f$. This separation is the minimum |
45 /// second set is the minimum. The algorithm is a modified |
48 /// cut if the summary of the edge capacities which source is in |
46 /// push-relabel preflow algorithm and it calculates the minimum cat |
49 /// \f$ V_{out} \f$ and the target is in \f$ V_{in} \f$ is the |
47 /// in \f$ O(n^3) \f$ time. The purpose of such algorithm is testing |
50 /// minimum. The algorithm is a modified push-relabel preflow |
48 /// network reliability. For sparse undirected graph you can use the |
51 /// algorithm and it calculates the minimum cut in \f$ O(n^3) \f$ |
49 /// algorithm of Nagamochi and Ibraki which solves the undirected |
52 /// time. The purpose of such algorithm is testing network |
50 /// problem in \f$ O(n^3) \f$ time. |
53 /// reliability. For sparse undirected graph you can use the |
|
54 /// algorithm of Nagamochi and Ibaraki which solves the undirected |
|
55 /// problem in \f$ O(ne + n^2 \log(n)) \f$ time and it is implemented in the |
|
56 /// MinCut algorithm class. |
|
57 /// |
|
58 /// \param _Graph is the graph type of the algorithm. |
|
59 /// \param _CapacityMap is an edge map of capacities which should |
|
60 /// be any numreric type. The default type is _Graph::EdgeMap<int>. |
|
61 /// \param _Tolerance is the handler of the inexact computation. The |
|
62 /// default type for it is Tolerance<typename CapacityMap::Value>. |
51 /// |
63 /// |
52 /// \author Attila Bernath and Balazs Dezso |
64 /// \author Attila Bernath and Balazs Dezso |
|
65 #ifdef DOXYGEN |
|
66 template <typename _Graph, typename _CapacityMap, typename _Tolerance> |
|
67 #else |
53 template <typename _Graph, |
68 template <typename _Graph, |
54 typename _CapacityMap = typename _Graph::template EdgeMap<int>, |
69 typename _CapacityMap = typename _Graph::template EdgeMap<int>, |
55 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > |
70 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > |
|
71 #endif |
56 class HaoOrlin { |
72 class HaoOrlin { |
57 protected: |
73 protected: |
58 |
74 |
59 typedef _Graph Graph; |
75 typedef _Graph Graph; |
60 typedef _CapacityMap CapacityMap; |
76 typedef _CapacityMap CapacityMap; |
68 typedef typename Graph::EdgeIt EdgeIt; |
84 typedef typename Graph::EdgeIt EdgeIt; |
69 typedef typename Graph::OutEdgeIt OutEdgeIt; |
85 typedef typename Graph::OutEdgeIt OutEdgeIt; |
70 typedef typename Graph::InEdgeIt InEdgeIt; |
86 typedef typename Graph::InEdgeIt InEdgeIt; |
71 |
87 |
72 const Graph* _graph; |
88 const Graph* _graph; |
|
89 |
73 const CapacityMap* _capacity; |
90 const CapacityMap* _capacity; |
74 |
91 |
75 typedef typename Graph::template EdgeMap<Value> FlowMap; |
92 typedef typename Graph::template EdgeMap<Value> FlowMap; |
76 |
93 |
77 FlowMap* _preflow; |
94 FlowMap* _preflow; |
78 |
95 |
79 Node _source, _target; |
96 Node _source, _target; |
80 int _node_num; |
97 int _node_num; |
81 |
98 |
82 typedef ResGraphAdaptor<const Graph, Value, CapacityMap, |
99 typedef ResGraphAdaptor<const Graph, Value, CapacityMap, |
83 FlowMap, Tolerance> ResGraph; |
100 FlowMap, Tolerance> OutResGraph; |
84 typedef typename ResGraph::Node ResNode; |
101 typedef typename OutResGraph::Edge OutResEdge; |
85 typedef typename ResGraph::NodeIt ResNodeIt; |
102 |
86 typedef typename ResGraph::EdgeIt ResEdgeIt; |
103 OutResGraph* _out_res_graph; |
87 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt; |
104 |
88 typedef typename ResGraph::Edge ResEdge; |
105 typedef typename Graph::template NodeMap<OutResEdge> OutCurrentEdgeMap; |
89 typedef typename ResGraph::InEdgeIt ResInEdgeIt; |
106 OutCurrentEdgeMap* _out_current_edge; |
90 |
107 |
91 ResGraph* _res_graph; |
108 typedef RevGraphAdaptor<const Graph> RevGraph; |
92 |
109 RevGraph* _rev_graph; |
93 typedef typename Graph::template NodeMap<ResEdge> CurrentArcMap; |
110 |
94 CurrentArcMap* _current_arc; |
111 typedef ResGraphAdaptor<const RevGraph, Value, CapacityMap, |
|
112 FlowMap, Tolerance> InResGraph; |
|
113 typedef typename InResGraph::Edge InResEdge; |
|
114 |
|
115 InResGraph* _in_res_graph; |
|
116 |
|
117 typedef typename Graph::template NodeMap<InResEdge> InCurrentEdgeMap; |
|
118 InCurrentEdgeMap* _in_current_edge; |
95 |
119 |
96 |
120 |
97 typedef IterableBoolMap<Graph, Node> WakeMap; |
121 typedef IterableBoolMap<Graph, Node> WakeMap; |
98 WakeMap* _wake; |
122 WakeMap* _wake; |
99 |
123 |
122 |
146 |
123 Tolerance _tolerance; |
147 Tolerance _tolerance; |
124 |
148 |
125 public: |
149 public: |
126 |
150 |
|
151 /// \brief Constructor |
|
152 /// |
|
153 /// Constructor of the algorithm class. |
127 HaoOrlin(const Graph& graph, const CapacityMap& capacity, |
154 HaoOrlin(const Graph& graph, const CapacityMap& capacity, |
128 const Tolerance& tolerance = Tolerance()) : |
155 const Tolerance& tolerance = Tolerance()) : |
129 _graph(&graph), _capacity(&capacity), |
156 _graph(&graph), _capacity(&capacity), |
130 _preflow(0), _source(), _target(), _res_graph(0), _current_arc(0), |
157 _preflow(0), _source(), _target(), |
|
158 _out_res_graph(0), _out_current_edge(0), |
|
159 _rev_graph(0), _in_res_graph(0), _in_current_edge(0), |
131 _wake(0),_dist(0), _excess(0), _source_set(0), |
160 _wake(0),_dist(0), _excess(0), _source_set(0), |
132 _highest_active(), _active_nodes(), _dormant_max(), _dormant(), |
161 _highest_active(), _active_nodes(), _dormant_max(), _dormant(), |
133 _min_cut(), _min_cut_map(0), _tolerance(tolerance) {} |
162 _min_cut(), _min_cut_map(0), _tolerance(tolerance) {} |
134 |
163 |
135 ~HaoOrlin() { |
164 ~HaoOrlin() { |
136 if (_res_graph) { |
|
137 delete _res_graph; |
|
138 } |
|
139 if (_min_cut_map) { |
165 if (_min_cut_map) { |
140 delete _min_cut_map; |
166 delete _min_cut_map; |
141 } |
167 } |
142 if (_current_arc) { |
168 if (_in_current_edge) { |
143 delete _current_arc; |
169 delete _in_current_edge; |
|
170 } |
|
171 if (_in_res_graph) { |
|
172 delete _in_res_graph; |
|
173 } |
|
174 if (_rev_graph) { |
|
175 delete _rev_graph; |
|
176 } |
|
177 if (_out_current_edge) { |
|
178 delete _out_current_edge; |
|
179 } |
|
180 if (_out_res_graph) { |
|
181 delete _out_res_graph; |
144 } |
182 } |
145 if (_source_set) { |
183 if (_source_set) { |
146 delete _source_set; |
184 delete _source_set; |
147 } |
185 } |
148 if (_excess) { |
186 if (_excess) { |
159 } |
197 } |
160 } |
198 } |
161 |
199 |
162 private: |
200 private: |
163 |
201 |
164 void relabel(Node i) { |
202 template <typename ResGraph, typename EdgeMap> |
165 int k = (*_dist)[i]; |
203 void findMinCut(const Node& target, bool out, |
|
204 ResGraph& res_graph, EdgeMap& current_edge) { |
|
205 typedef typename ResGraph::Edge ResEdge; |
|
206 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt; |
|
207 |
|
208 for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) { |
|
209 (*_preflow)[it] = 0; |
|
210 } |
|
211 for (NodeIt it(*_graph); it != INVALID; ++it) { |
|
212 (*_wake)[it] = true; |
|
213 (*_dist)[it] = 1; |
|
214 (*_excess)[it] = 0; |
|
215 (*_source_set)[it] = false; |
|
216 |
|
217 res_graph.firstOut(current_edge[it], it); |
|
218 } |
|
219 |
|
220 _target = target; |
|
221 (*_dist)[target] = 0; |
|
222 |
|
223 for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) { |
|
224 Value delta = res_graph.rescap(it); |
|
225 if (!_tolerance.positive(delta)) continue; |
|
226 |
|
227 (*_excess)[res_graph.source(it)] -= delta; |
|
228 res_graph.augment(it, delta); |
|
229 Node a = res_graph.target(it); |
|
230 if (!_tolerance.positive((*_excess)[a]) && |
|
231 (*_wake)[a] && a != _target) { |
|
232 _active_nodes[(*_dist)[a]].push_front(a); |
|
233 if (_highest_active < (*_dist)[a]) { |
|
234 _highest_active = (*_dist)[a]; |
|
235 } |
|
236 } |
|
237 (*_excess)[a] += delta; |
|
238 } |
|
239 |
|
240 _dormant[0].push_front(_source); |
|
241 (*_source_set)[_source] = true; |
|
242 _dormant_max = 0; |
|
243 (*_wake)[_source] = false; |
|
244 |
|
245 _level_size[0] = 1; |
|
246 _level_size[1] = _node_num - 1; |
|
247 |
|
248 do { |
|
249 Node n; |
|
250 while ((n = findActiveNode()) != INVALID) { |
|
251 ResEdge e; |
|
252 while (_tolerance.positive((*_excess)[n]) && |
|
253 (e = findAdmissibleEdge(n, res_graph, current_edge)) |
|
254 != INVALID){ |
|
255 Value delta; |
|
256 if ((*_excess)[n] < res_graph.rescap(e)) { |
|
257 delta = (*_excess)[n]; |
|
258 } else { |
|
259 delta = res_graph.rescap(e); |
|
260 res_graph.nextOut(current_edge[n]); |
|
261 } |
|
262 if (!_tolerance.positive(delta)) continue; |
|
263 res_graph.augment(e, delta); |
|
264 (*_excess)[res_graph.source(e)] -= delta; |
|
265 Node a = res_graph.target(e); |
|
266 if (!_tolerance.positive((*_excess)[a]) && a != _target) { |
|
267 _active_nodes[(*_dist)[a]].push_front(a); |
|
268 } |
|
269 (*_excess)[a] += delta; |
|
270 } |
|
271 if (_tolerance.positive((*_excess)[n])) { |
|
272 relabel(n, res_graph, current_edge); |
|
273 } |
|
274 } |
|
275 |
|
276 Value current_value = cutValue(out); |
|
277 if (_min_cut > current_value){ |
|
278 if (out) { |
|
279 for (NodeIt it(*_graph); it != INVALID; ++it) { |
|
280 _min_cut_map->set(it, !(*_wake)[it]); |
|
281 } |
|
282 } else { |
|
283 for (NodeIt it(*_graph); it != INVALID; ++it) { |
|
284 _min_cut_map->set(it, (*_wake)[it]); |
|
285 } |
|
286 } |
|
287 |
|
288 _min_cut = current_value; |
|
289 } |
|
290 |
|
291 } while (selectNewSink(res_graph)); |
|
292 } |
|
293 |
|
294 template <typename ResGraph, typename EdgeMap> |
|
295 void relabel(const Node& n, ResGraph& res_graph, EdgeMap& current_edge) { |
|
296 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt; |
|
297 |
|
298 int k = (*_dist)[n]; |
166 if (_level_size[k] == 1) { |
299 if (_level_size[k] == 1) { |
167 ++_dormant_max; |
300 ++_dormant_max; |
168 for (NodeIt it(*_graph); it != INVALID; ++it) { |
301 for (NodeIt it(*_graph); it != INVALID; ++it) { |
169 if ((*_wake)[it] && (*_dist)[it] >= k) { |
302 if ((*_wake)[it] && (*_dist)[it] >= k) { |
170 (*_wake)[it] = false; |
303 (*_wake)[it] = false; |
171 _dormant[_dormant_max].push_front(it); |
304 _dormant[_dormant_max].push_front(it); |
172 --_level_size[(*_dist)[it]]; |
305 --_level_size[(*_dist)[it]]; |
173 } |
306 } |
174 } |
307 } |
175 --_highest_active; |
308 --_highest_active; |
176 } else { |
309 } else { |
177 ResOutEdgeIt e(*_res_graph, i); |
310 int new_dist = _node_num; |
178 while (e != INVALID && !(*_wake)[_res_graph->target(e)]) { |
311 for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) { |
179 ++e; |
312 Node t = res_graph.target(e); |
|
313 if ((*_wake)[t] && new_dist > (*_dist)[t]) { |
|
314 new_dist = (*_dist)[t]; |
|
315 } |
|
316 } |
|
317 if (new_dist == _node_num) { |
|
318 ++_dormant_max; |
|
319 (*_wake)[n] = false; |
|
320 _dormant[_dormant_max].push_front(n); |
|
321 --_level_size[(*_dist)[n]]; |
|
322 } else { |
|
323 --_level_size[(*_dist)[n]]; |
|
324 (*_dist)[n] = new_dist + 1; |
|
325 _highest_active = (*_dist)[n]; |
|
326 _active_nodes[_highest_active].push_front(n); |
|
327 ++_level_size[(*_dist)[n]]; |
|
328 res_graph.firstOut(current_edge[n], n); |
180 } |
329 } |
181 |
330 } |
182 if (e == INVALID){ |
331 } |
183 ++_dormant_max; |
332 |
184 (*_wake)[i] = false; |
333 template <typename ResGraph> |
185 _dormant[_dormant_max].push_front(i); |
334 bool selectNewSink(ResGraph& res_graph) { |
186 --_level_size[(*_dist)[i]]; |
335 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt; |
187 } else{ |
336 |
188 Node j = _res_graph->target(e); |
|
189 int new_dist = (*_dist)[j]; |
|
190 ++e; |
|
191 while (e != INVALID){ |
|
192 Node j = _res_graph->target(e); |
|
193 if ((*_wake)[j] && new_dist > (*_dist)[j]) { |
|
194 new_dist = (*_dist)[j]; |
|
195 } |
|
196 ++e; |
|
197 } |
|
198 --_level_size[(*_dist)[i]]; |
|
199 (*_dist)[i] = new_dist + 1; |
|
200 _highest_active = (*_dist)[i]; |
|
201 _active_nodes[_highest_active].push_front(i); |
|
202 ++_level_size[(*_dist)[i]]; |
|
203 _res_graph->firstOut((*_current_arc)[i], i); |
|
204 } |
|
205 } |
|
206 } |
|
207 |
|
208 bool selectNewSink(){ |
|
209 Node old_target = _target; |
337 Node old_target = _target; |
210 (*_wake)[_target] = false; |
338 (*_wake)[_target] = false; |
211 --_level_size[(*_dist)[_target]]; |
339 --_level_size[(*_dist)[_target]]; |
212 _dormant[0].push_front(_target); |
340 _dormant[0].push_front(_target); |
213 (*_source_set)[_target] = true; |
341 (*_source_set)[_target] = true; |
269 } else { |
409 } else { |
270 return INVALID; |
410 return INVALID; |
271 } |
411 } |
272 } |
412 } |
273 |
413 |
274 ResEdge findAdmissibleEdge(const Node& n){ |
414 template <typename ResGraph, typename EdgeMap> |
275 ResEdge e = (*_current_arc)[n]; |
415 typename ResGraph::Edge findAdmissibleEdge(const Node& n, |
|
416 ResGraph& res_graph, |
|
417 EdgeMap& current_edge) { |
|
418 typedef typename ResGraph::Edge ResEdge; |
|
419 ResEdge e = current_edge[n]; |
276 while (e != INVALID && |
420 while (e != INVALID && |
277 ((*_dist)[n] <= (*_dist)[_res_graph->target(e)] || |
421 ((*_dist)[n] <= (*_dist)[res_graph.target(e)] || |
278 !(*_wake)[_res_graph->target(e)])) { |
422 !(*_wake)[res_graph.target(e)])) { |
279 _res_graph->nextOut(e); |
423 res_graph.nextOut(e); |
280 } |
424 } |
281 if (e != INVALID) { |
425 if (e != INVALID) { |
282 (*_current_arc)[n] = e; |
426 current_edge[n] = e; |
283 return e; |
427 return e; |
284 } else { |
428 } else { |
285 return INVALID; |
429 return INVALID; |
286 } |
430 } |
287 } |
431 } |
288 |
432 |
289 void push(ResEdge& e,const Value& delta){ |
433 Value cutValue(bool out) { |
290 _res_graph->augment(e, delta); |
|
291 if (!_tolerance.positive(delta)) return; |
|
292 |
|
293 (*_excess)[_res_graph->source(e)] -= delta; |
|
294 Node a = _res_graph->target(e); |
|
295 if (!_tolerance.positive((*_excess)[a]) && (*_wake)[a] && a != _target) { |
|
296 _active_nodes[(*_dist)[a]].push_front(a); |
|
297 if (_highest_active < (*_dist)[a]) { |
|
298 _highest_active = (*_dist)[a]; |
|
299 } |
|
300 } |
|
301 (*_excess)[a] += delta; |
|
302 } |
|
303 |
|
304 Value cutValue() { |
|
305 Value value = 0; |
434 Value value = 0; |
306 for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) { |
435 if (out) { |
307 for (InEdgeIt e(*_graph, it); e != INVALID; ++e) { |
436 for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) { |
308 if (!(*_wake)[_graph->source(e)]){ |
437 for (InEdgeIt e(*_graph, it); e != INVALID; ++e) { |
309 value += (*_capacity)[e]; |
438 if (!(*_wake)[_graph->source(e)]){ |
310 } |
439 value += (*_capacity)[e]; |
311 } |
440 } |
|
441 } |
|
442 } |
|
443 } else { |
|
444 for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) { |
|
445 for (OutEdgeIt e(*_graph, it); e != INVALID; ++e) { |
|
446 if (!(*_wake)[_graph->target(e)]){ |
|
447 value += (*_capacity)[e]; |
|
448 } |
|
449 } |
|
450 } |
312 } |
451 } |
313 return value; |
452 return value; |
314 } |
453 } |
|
454 |
315 |
455 |
316 public: |
456 public: |
317 |
457 |
|
458 /// \name Execution control |
|
459 /// The simplest way to execute the algorithm is to use |
|
460 /// one of the member functions called \c run(...). |
|
461 /// \n |
|
462 /// If you need more control on the execution, |
|
463 /// first you must call \ref init(), then the \ref calculateIn() or |
|
464 /// \ref calculateIn() functions. |
|
465 |
|
466 /// @{ |
|
467 |
318 /// \brief Initializes the internal data structures. |
468 /// \brief Initializes the internal data structures. |
319 /// |
469 /// |
320 /// Initializes the internal data structures. It creates |
470 /// Initializes the internal data structures. It creates |
321 /// the maps, residual graph adaptor and some bucket structures |
471 /// the maps, residual graph adaptors and some bucket structures |
322 /// for the algorithm. |
472 /// for the algorithm. |
323 void init() { |
473 void init() { |
324 init(NodeIt(*_graph)); |
474 init(NodeIt(*_graph)); |
325 } |
475 } |
326 |
476 |
351 _excess = new ExcessMap(*_graph); |
501 _excess = new ExcessMap(*_graph); |
352 } |
502 } |
353 if (!_source_set) { |
503 if (!_source_set) { |
354 _source_set = new SourceSetMap(*_graph); |
504 _source_set = new SourceSetMap(*_graph); |
355 } |
505 } |
356 if (!_current_arc) { |
506 if (!_out_res_graph) { |
357 _current_arc = new CurrentArcMap(*_graph); |
507 _out_res_graph = new OutResGraph(*_graph, *_capacity, *_preflow); |
|
508 } |
|
509 if (!_out_current_edge) { |
|
510 _out_current_edge = new OutCurrentEdgeMap(*_graph); |
|
511 } |
|
512 if (!_rev_graph) { |
|
513 _rev_graph = new RevGraph(*_graph); |
|
514 } |
|
515 if (!_in_res_graph) { |
|
516 _in_res_graph = new InResGraph(*_rev_graph, *_capacity, *_preflow); |
|
517 } |
|
518 if (!_in_current_edge) { |
|
519 _in_current_edge = new InCurrentEdgeMap(*_graph); |
358 } |
520 } |
359 if (!_min_cut_map) { |
521 if (!_min_cut_map) { |
360 _min_cut_map = new MinCutMap(*_graph); |
522 _min_cut_map = new MinCutMap(*_graph); |
361 } |
523 } |
362 if (!_res_graph) { |
|
363 _res_graph = new ResGraph(*_graph, *_capacity, *_preflow); |
|
364 } |
|
365 |
524 |
366 _min_cut = std::numeric_limits<Value>::max(); |
525 _min_cut = std::numeric_limits<Value>::max(); |
367 } |
526 } |
368 |
527 |
369 |
528 |
370 /// \brief Calculates the minimum cut with the \c source node |
529 /// \brief Calculates the minimum cut with the \c source node |
371 /// in the first partition. |
530 /// in the \f$ V_{out} \f$. |
372 /// |
531 /// |
373 /// Calculates the minimum cut with the \c source node |
532 /// Calculates the minimum cut with the \c source node |
374 /// in the first partition. |
533 /// in the \f$ V_{out} \f$. |
375 void calculateOut() { |
534 void calculateOut() { |
376 for (NodeIt it(*_graph); it != INVALID; ++it) { |
535 for (NodeIt it(*_graph); it != INVALID; ++it) { |
377 if (it != _source) { |
536 if (it != _source) { |
378 calculateOut(it); |
537 calculateOut(it); |
379 return; |
538 return; |
380 } |
539 } |
381 } |
540 } |
382 } |
541 } |
383 |
542 |
384 /// \brief Calculates the minimum cut with the \c source node |
543 /// \brief Calculates the minimum cut with the \c source node |
385 /// in the first partition. |
544 /// in the \f$ V_{out} \f$. |
386 /// |
545 /// |
387 /// Calculates the minimum cut with the \c source node |
546 /// Calculates the minimum cut with the \c source node |
388 /// in the first partition. The \c target is the initial target |
547 /// in the \f$ V_{out} \f$. The \c target is the initial target |
389 /// for the push-relabel algorithm. |
548 /// for the push-relabel algorithm. |
390 void calculateOut(const Node& target) { |
549 void calculateOut(const Node& target) { |
391 for (NodeIt it(*_graph); it != INVALID; ++it) { |
550 findMinCut(target, true, *_out_res_graph, *_out_current_edge); |
392 (*_wake)[it] = true; |
551 } |
393 (*_dist)[it] = 1; |
552 |
394 (*_excess)[it] = 0; |
553 /// \brief Calculates the minimum cut with the \c source node |
395 (*_source_set)[it] = false; |
554 /// in the \f$ V_{in} \f$. |
396 |
555 /// |
397 _res_graph->firstOut((*_current_arc)[it], it); |
556 /// Calculates the minimum cut with the \c source node |
398 } |
557 /// in the \f$ V_{in} \f$. |
399 |
|
400 _target = target; |
|
401 (*_dist)[target] = 0; |
|
402 |
|
403 for (ResOutEdgeIt it(*_res_graph, _source); it != INVALID; ++it) { |
|
404 push(it, _res_graph->rescap(it)); |
|
405 } |
|
406 |
|
407 _dormant[0].push_front(_source); |
|
408 (*_source_set)[_source] = true; |
|
409 _dormant_max = 0; |
|
410 (*_wake)[_source]=false; |
|
411 |
|
412 _level_size[0] = 1; |
|
413 _level_size[1] = _node_num - 1; |
|
414 |
|
415 do { |
|
416 Node n; |
|
417 while ((n = findActiveNode()) != INVALID) { |
|
418 ResEdge e; |
|
419 while (_tolerance.positive((*_excess)[n]) && |
|
420 (e = findAdmissibleEdge(n)) != INVALID){ |
|
421 Value delta; |
|
422 if ((*_excess)[n] < _res_graph->rescap(e)) { |
|
423 delta = (*_excess)[n]; |
|
424 } else { |
|
425 delta = _res_graph->rescap(e); |
|
426 _res_graph->nextOut((*_current_arc)[n]); |
|
427 } |
|
428 if (!_tolerance.positive(delta)) continue; |
|
429 _res_graph->augment(e, delta); |
|
430 (*_excess)[_res_graph->source(e)] -= delta; |
|
431 Node a = _res_graph->target(e); |
|
432 if (!_tolerance.positive((*_excess)[a]) && a != _target) { |
|
433 _active_nodes[(*_dist)[a]].push_front(a); |
|
434 } |
|
435 (*_excess)[a] += delta; |
|
436 } |
|
437 if (_tolerance.positive((*_excess)[n])) { |
|
438 relabel(n); |
|
439 } |
|
440 } |
|
441 |
|
442 Value current_value = cutValue(); |
|
443 if (_min_cut > current_value){ |
|
444 for (NodeIt it(*_graph); it != INVALID; ++it) { |
|
445 _min_cut_map->set(it, !(*_wake)[it]); |
|
446 } |
|
447 |
|
448 _min_cut = current_value; |
|
449 } |
|
450 |
|
451 } while (selectNewSink()); |
|
452 } |
|
453 |
|
454 void calculateIn() { |
558 void calculateIn() { |
455 for (NodeIt it(*_graph); it != INVALID; ++it) { |
559 for (NodeIt it(*_graph); it != INVALID; ++it) { |
456 if (it != _source) { |
560 if (it != _source) { |
457 calculateIn(it); |
561 calculateIn(it); |
458 return; |
562 return; |
459 } |
563 } |
460 } |
564 } |
461 } |
565 } |
462 |
566 |
|
567 /// \brief Calculates the minimum cut with the \c source node |
|
568 /// in the \f$ V_{in} \f$. |
|
569 /// |
|
570 /// Calculates the minimum cut with the \c source node |
|
571 /// in the \f$ V_{in} \f$. The \c target is the initial target |
|
572 /// for the push-relabel algorithm. |
|
573 void calculateIn(const Node& target) { |
|
574 findMinCut(target, false, *_in_res_graph, *_in_current_edge); |
|
575 } |
|
576 |
|
577 /// \brief Runs the algorithm. |
|
578 /// |
|
579 /// Runs the algorithm. It finds a proper \c source and \c target |
|
580 /// and then calls the \ref init(), \ref calculateOut() and \ref |
|
581 /// calculateIn(). |
463 void run() { |
582 void run() { |
464 init(); |
583 init(); |
465 for (NodeIt it(*_graph); it != INVALID; ++it) { |
584 for (NodeIt it(*_graph); it != INVALID; ++it) { |
466 if (it != _source) { |
585 if (it != _source) { |
467 startOut(it); |
586 calculateOut(it); |
468 // startIn(it); |
587 calculateIn(it); |
469 return; |
588 return; |
470 } |
589 } |
471 } |
590 } |
472 } |
591 } |
473 |
592 |
|
593 /// \brief Runs the algorithm. |
|
594 /// |
|
595 /// Runs the algorithm. It finds a proper \c target and then calls |
|
596 /// the \ref init(), \ref calculateOut() and \ref calculateIn(). |
474 void run(const Node& s) { |
597 void run(const Node& s) { |
475 init(s); |
598 init(s); |
476 for (NodeIt it(*_graph); it != INVALID; ++it) { |
599 for (NodeIt it(*_graph); it != INVALID; ++it) { |
477 if (it != _source) { |
600 if (it != _source) { |
478 startOut(it); |
601 calculateOut(it); |
479 // startIn(it); |
602 calculateIn(it); |
480 return; |
603 return; |
481 } |
604 } |
482 } |
605 } |
483 } |
606 } |
484 |
607 |
|
608 /// \brief Runs the algorithm. |
|
609 /// |
|
610 /// Runs the algorithm. It just calls the \ref init() and then |
|
611 /// \ref calculateOut() and \ref calculateIn(). |
485 void run(const Node& s, const Node& t) { |
612 void run(const Node& s, const Node& t) { |
486 init(s); |
613 init(s); |
487 startOut(t); |
614 calculateOut(t); |
488 startIn(t); |
615 calculateIn(t); |
489 } |
616 } |
490 |
617 |
491 /// \brief Returns the value of the minimum value cut with node \c |
618 /// @} |
492 /// source on the source side. |
619 |
|
620 /// \name Query Functions The result of the %HaoOrlin algorithm |
|
621 /// can be obtained using these functions. |
|
622 /// \n |
|
623 /// Before the use of these functions, either \ref run(), \ref |
|
624 /// calculateOut() or \ref calculateIn() must be called. |
|
625 |
|
626 /// @{ |
|
627 |
|
628 /// \brief Returns the value of the minimum value cut. |
493 /// |
629 /// |
494 /// Returns the value of the minimum value cut with node \c source |
630 /// Returns the value of the minimum value cut. |
495 /// on the source side. This function can be called after running |
|
496 /// \ref findMinCut. |
|
497 Value minCut() const { |
631 Value minCut() const { |
498 return _min_cut; |
632 return _min_cut; |
499 } |
633 } |
500 |
634 |
501 |
635 |
502 /// \brief Returns a minimum value cut. |
636 /// \brief Returns a minimum value cut. |
503 /// |
637 /// |
504 /// Sets \c nodeMap to the characteristic vector of a minimum |
638 /// Sets \c nodeMap to the characteristic vector of a minimum |
505 /// value cut with node \c source on the source side. This |
639 /// value cut. The nodes in \f$ V_{out} \f$ will be set true and |
506 /// function can be called after running \ref findMinCut. |
640 /// the nodes in \f$ V_{in} \f$ will be set false. |
507 /// \pre nodeMap should be a bool-valued node-map. |
641 /// \pre nodeMap should be a bool-valued node-map. |
508 template <typename NodeMap> |
642 template <typename NodeMap> |
509 Value minCut(NodeMap& nodeMap) const { |
643 Value minCut(NodeMap& nodeMap) const { |
510 for (NodeIt it(*_graph); it != INVALID; ++it) { |
644 for (NodeIt it(*_graph); it != INVALID; ++it) { |
511 nodeMap.set(it, (*_min_cut_map)[it]); |
645 nodeMap.set(it, (*_min_cut_map)[it]); |
512 } |
646 } |
513 return minCut(); |
647 return minCut(); |
514 } |
648 } |
|
649 |
|
650 /// @} |
515 |
651 |
516 }; //class HaoOrlin |
652 }; //class HaoOrlin |
517 |
653 |
518 |
654 |
519 } //namespace lemon |
655 } //namespace lemon |