17 */ |
17 */ |
18 |
18 |
19 #ifndef LEMON_CIRCULATION_H |
19 #ifndef LEMON_CIRCULATION_H |
20 #define LEMON_CIRCULATION_H |
20 #define LEMON_CIRCULATION_H |
21 |
21 |
22 #include <iostream> |
|
23 #include <queue> |
|
24 #include <lemon/tolerance.h> |
22 #include <lemon/tolerance.h> |
25 #include <lemon/elevator.h> |
23 #include <lemon/elevator.h> |
26 |
24 |
27 ///\ingroup max_flow |
25 ///\ingroup max_flow |
28 ///\file |
26 ///\file |
29 ///\brief Push-prelabel algorithm for finding a feasible circulation. |
27 ///\brief Push-relabel algorithm for finding a feasible circulation. |
30 /// |
28 /// |
31 namespace lemon { |
29 namespace lemon { |
32 |
30 |
33 /// \brief Default traits class of Circulation class. |
31 /// \brief Default traits class of Circulation class. |
34 /// |
32 /// |
35 /// Default traits class of Circulation class. |
33 /// Default traits class of Circulation class. |
36 /// \param _Graph Digraph type. |
34 /// \tparam _Diraph Digraph type. |
37 /// \param _CapacityMap Type of capacity map. |
35 /// \tparam _LCapMap Lower bound capacity map type. |
38 template <typename _Graph, typename _LCapMap, |
36 /// \tparam _UCapMap Upper bound capacity map type. |
|
37 /// \tparam _DeltaMap Delta map type. |
|
38 template <typename _Diraph, typename _LCapMap, |
39 typename _UCapMap, typename _DeltaMap> |
39 typename _UCapMap, typename _DeltaMap> |
40 struct CirculationDefaultTraits { |
40 struct CirculationDefaultTraits { |
41 |
41 |
42 /// \brief The digraph type the algorithm runs on. |
42 /// \brief The type of the digraph the algorithm runs on. |
43 typedef _Graph Digraph; |
43 typedef _Diraph Digraph; |
44 |
44 |
45 /// \brief The type of the map that stores the circulation lower |
45 /// \brief The type of the map that stores the circulation lower |
46 /// bound. |
46 /// bound. |
47 /// |
47 /// |
48 /// The type of the map that stores the circulation lower bound. |
48 /// The type of the map that stores the circulation lower bound. |
54 /// |
54 /// |
55 /// The type of the map that stores the circulation upper bound. |
55 /// The type of the map that stores the circulation upper bound. |
56 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
56 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
57 typedef _UCapMap UCapMap; |
57 typedef _UCapMap UCapMap; |
58 |
58 |
59 /// \brief The type of the map that stores the upper bound of |
59 /// \brief The type of the map that stores the lower bound for |
60 /// node excess. |
60 /// the supply of the nodes. |
61 /// |
61 /// |
62 /// The type of the map that stores the lower bound of node |
62 /// The type of the map that stores the lower bound for the supply |
63 /// excess. It must meet the \ref concepts::ReadMap "ReadMap" |
63 /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap" |
64 /// concept. |
64 /// concept. |
65 typedef _DeltaMap DeltaMap; |
65 typedef _DeltaMap DeltaMap; |
66 |
66 |
67 /// \brief The type of the length of the arcs. |
67 /// \brief The type of the flow values. |
68 typedef typename DeltaMap::Value Value; |
68 typedef typename DeltaMap::Value Value; |
69 |
69 |
70 /// \brief The map type that stores the flow values. |
70 /// \brief The type of the map that stores the flow values. |
71 /// |
71 /// |
72 /// The map type that stores the flow values. |
72 /// The type of the map that stores the flow values. |
73 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
73 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
74 typedef typename Digraph::template ArcMap<Value> FlowMap; |
74 typedef typename Digraph::template ArcMap<Value> FlowMap; |
75 |
75 |
76 /// \brief Instantiates a FlowMap. |
76 /// \brief Instantiates a FlowMap. |
77 /// |
77 /// |
80 /// the flow map. |
80 /// the flow map. |
81 static FlowMap* createFlowMap(const Digraph& digraph) { |
81 static FlowMap* createFlowMap(const Digraph& digraph) { |
82 return new FlowMap(digraph); |
82 return new FlowMap(digraph); |
83 } |
83 } |
84 |
84 |
85 /// \brief The eleavator type used by Circulation algorithm. |
85 /// \brief The elevator type used by the algorithm. |
86 /// |
86 /// |
87 /// The elevator type used by Circulation algorithm. |
87 /// The elevator type used by the algorithm. |
88 /// |
88 /// |
89 /// \sa Elevator |
89 /// \sa Elevator |
90 /// \sa LinkedElevator |
90 /// \sa LinkedElevator |
91 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; |
91 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; |
92 |
92 |
93 /// \brief Instantiates an Elevator. |
93 /// \brief Instantiates an Elevator. |
94 /// |
94 /// |
95 /// This function instantiates a \ref Elevator. |
95 /// This function instantiates an \ref Elevator. |
96 /// \param digraph The digraph, to which we would like to define |
96 /// \param digraph The digraph, to which we would like to define |
97 /// the elevator. |
97 /// the elevator. |
98 /// \param max_level The maximum level of the elevator. |
98 /// \param max_level The maximum level of the elevator. |
99 static Elevator* createElevator(const Digraph& digraph, int max_level) { |
99 static Elevator* createElevator(const Digraph& digraph, int max_level) { |
100 return new Elevator(digraph, max_level); |
100 return new Elevator(digraph, max_level); |
105 /// The tolerance used by the algorithm to handle inexact computation. |
105 /// The tolerance used by the algorithm to handle inexact computation. |
106 typedef lemon::Tolerance<Value> Tolerance; |
106 typedef lemon::Tolerance<Value> Tolerance; |
107 |
107 |
108 }; |
108 }; |
109 |
109 |
110 ///Push-relabel algorithm for the Network Circulation Problem. |
|
111 |
|
112 /** |
110 /** |
|
111 \brief Push-relabel algorithm for the network circulation problem. |
|
112 |
113 \ingroup max_flow |
113 \ingroup max_flow |
114 This class implements a push-relabel algorithm |
114 This class implements a push-relabel algorithm for the network |
115 or the Network Circulation Problem. |
115 circulation problem. |
|
116 It is to find a feasible circulation when lower and upper bounds |
|
117 are given for the flow values on the arcs and lower bounds |
|
118 are given for the supply values of the nodes. |
|
119 |
116 The exact formulation of this problem is the following. |
120 The exact formulation of this problem is the following. |
117 \f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq |
121 Let \f$G=(V,A)\f$ be a digraph, |
118 -delta(v)\quad \forall v\in V \f] |
122 \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$, |
119 \f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f] |
123 \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation |
|
124 \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that |
|
125 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) |
|
126 \geq delta(v) \quad \forall v\in V, \f] |
|
127 \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f] |
|
128 \note \f$delta(v)\f$ specifies a lower bound for the supply of node |
|
129 \f$v\f$. It can be either positive or negative, however note that |
|
130 \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to |
|
131 have a feasible solution. |
|
132 |
|
133 \note A special case of this problem is when |
|
134 \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$ |
|
135 will be \e equal \e to \f$delta(v)\f$, if a circulation can be found. |
|
136 Thus a feasible solution for the |
|
137 \ref min_cost_flow "minimum cost flow" problem can be calculated |
|
138 in this way. |
|
139 |
|
140 \tparam _Digraph The type of the digraph the algorithm runs on. |
|
141 \tparam _LCapMap The type of the lower bound capacity map. The default |
|
142 map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>". |
|
143 \tparam _UCapMap The type of the upper bound capacity map. The default |
|
144 map type is \c _LCapMap. |
|
145 \tparam _DeltaMap The type of the map that stores the lower bound |
|
146 for the supply of the nodes. The default map type is |
|
147 \c _Digraph::ArcMap<_UCapMap::Value>. |
120 */ |
148 */ |
121 template<class _Graph, |
149 #ifdef DOXYGEN |
122 class _LCapMap=typename _Graph::template ArcMap<int>, |
150 template< typename _Digraph, |
123 class _UCapMap=_LCapMap, |
151 typename _LCapMap, |
124 class _DeltaMap=typename _Graph::template NodeMap< |
152 typename _UCapMap, |
125 typename _UCapMap::Value>, |
153 typename _DeltaMap, |
126 class _Traits=CirculationDefaultTraits<_Graph, _LCapMap, |
154 typename _Traits > |
127 _UCapMap, _DeltaMap> > |
155 #else |
|
156 template< typename _Digraph, |
|
157 typename _LCapMap = typename _Digraph::template ArcMap<int>, |
|
158 typename _UCapMap = _LCapMap, |
|
159 typename _DeltaMap = typename _Digraph:: |
|
160 template NodeMap<typename _UCapMap::Value>, |
|
161 typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap, |
|
162 _UCapMap, _DeltaMap> > |
|
163 #endif |
128 class Circulation { |
164 class Circulation { |
129 |
165 public: |
|
166 |
|
167 ///The \ref CirculationDefaultTraits "traits class" of the algorithm. |
130 typedef _Traits Traits; |
168 typedef _Traits Traits; |
|
169 ///The type of the digraph the algorithm runs on. |
131 typedef typename Traits::Digraph Digraph; |
170 typedef typename Traits::Digraph Digraph; |
|
171 ///The type of the flow values. |
|
172 typedef typename Traits::Value Value; |
|
173 |
|
174 /// The type of the lower bound capacity map. |
|
175 typedef typename Traits::LCapMap LCapMap; |
|
176 /// The type of the upper bound capacity map. |
|
177 typedef typename Traits::UCapMap UCapMap; |
|
178 /// \brief The type of the map that stores the lower bound for |
|
179 /// the supply of the nodes. |
|
180 typedef typename Traits::DeltaMap DeltaMap; |
|
181 ///The type of the flow map. |
|
182 typedef typename Traits::FlowMap FlowMap; |
|
183 |
|
184 ///The type of the elevator. |
|
185 typedef typename Traits::Elevator Elevator; |
|
186 ///The type of the tolerance. |
|
187 typedef typename Traits::Tolerance Tolerance; |
|
188 |
|
189 private: |
|
190 |
132 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
191 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
133 |
|
134 typedef typename Traits::Value Value; |
|
135 |
|
136 typedef typename Traits::LCapMap LCapMap; |
|
137 typedef typename Traits::UCapMap UCapMap; |
|
138 typedef typename Traits::DeltaMap DeltaMap; |
|
139 typedef typename Traits::FlowMap FlowMap; |
|
140 typedef typename Traits::Elevator Elevator; |
|
141 typedef typename Traits::Tolerance Tolerance; |
|
142 |
|
143 typedef typename Digraph::template NodeMap<Value> ExcessMap; |
|
144 |
192 |
145 const Digraph &_g; |
193 const Digraph &_g; |
146 int _node_num; |
194 int _node_num; |
147 |
195 |
148 const LCapMap *_lo; |
196 const LCapMap *_lo; |
201 |
250 |
202 /// \brief \ref named-templ-param "Named parameter" for setting |
251 /// \brief \ref named-templ-param "Named parameter" for setting |
203 /// Elevator type |
252 /// Elevator type |
204 /// |
253 /// |
205 /// \ref named-templ-param "Named parameter" for setting Elevator |
254 /// \ref named-templ-param "Named parameter" for setting Elevator |
206 /// type |
255 /// type. If this named parameter is used, then an external |
|
256 /// elevator object must be passed to the algorithm using the |
|
257 /// \ref elevator(Elevator&) "elevator()" function before calling |
|
258 /// \ref run() or \ref init(). |
|
259 /// \sa SetStandardElevator |
207 template <typename _Elevator> |
260 template <typename _Elevator> |
208 struct SetElevator |
261 struct SetElevator |
209 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, |
262 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, |
210 SetElevatorTraits<_Elevator> > { |
263 SetElevatorTraits<_Elevator> > { |
211 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, |
264 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, |
219 return new Elevator(digraph, max_level); |
272 return new Elevator(digraph, max_level); |
220 } |
273 } |
221 }; |
274 }; |
222 |
275 |
223 /// \brief \ref named-templ-param "Named parameter" for setting |
276 /// \brief \ref named-templ-param "Named parameter" for setting |
224 /// Elevator type |
277 /// Elevator type with automatic allocation |
225 /// |
278 /// |
226 /// \ref named-templ-param "Named parameter" for setting Elevator |
279 /// \ref named-templ-param "Named parameter" for setting Elevator |
227 /// type. The Elevator should be standard constructor interface, ie. |
280 /// type with automatic allocation. |
228 /// the digraph and the maximum level should be passed to it. |
281 /// The Elevator should have standard constructor interface to be |
|
282 /// able to automatically created by the algorithm (i.e. the |
|
283 /// digraph and the maximum level should be passed to it). |
|
284 /// However an external elevator object could also be passed to the |
|
285 /// algorithm with the \ref elevator(Elevator&) "elevator()" function |
|
286 /// before calling \ref run() or \ref init(). |
|
287 /// \sa SetElevator |
229 template <typename _Elevator> |
288 template <typename _Elevator> |
230 struct SetStandardElevator |
289 struct SetStandardElevator |
231 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, |
290 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, |
232 SetStandardElevatorTraits<_Elevator> > { |
291 SetStandardElevatorTraits<_Elevator> > { |
233 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, |
292 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, |
246 |
305 |
247 /// The constructor of the class. |
306 /// The constructor of the class. |
248 /// \param g The digraph the algorithm runs on. |
307 /// \param g The digraph the algorithm runs on. |
249 /// \param lo The lower bound capacity of the arcs. |
308 /// \param lo The lower bound capacity of the arcs. |
250 /// \param up The upper bound capacity of the arcs. |
309 /// \param up The upper bound capacity of the arcs. |
251 /// \param delta The lower bound on node excess. |
310 /// \param delta The lower bound for the supply of the nodes. |
252 Circulation(const Digraph &g,const LCapMap &lo, |
311 Circulation(const Digraph &g,const LCapMap &lo, |
253 const UCapMap &up,const DeltaMap &delta) |
312 const UCapMap &up,const DeltaMap &delta) |
254 : _g(g), _node_num(), |
313 : _g(g), _node_num(), |
255 _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false), |
314 _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false), |
256 _level(0), _local_level(false), _excess(0), _el() {} |
315 _level(0), _local_level(false), _excess(0), _el() {} |
257 |
316 |
258 /// Destrcutor. |
317 /// Destructor. |
259 ~Circulation() { |
318 ~Circulation() { |
260 destroyStructures(); |
319 destroyStructures(); |
261 } |
320 } |
|
321 |
262 |
322 |
263 private: |
323 private: |
264 |
324 |
265 void createStructures() { |
325 void createStructures() { |
266 _node_num = _el = countNodes(_g); |
326 _node_num = _el = countNodes(_g); |
293 public: |
353 public: |
294 |
354 |
295 /// Sets the lower bound capacity map. |
355 /// Sets the lower bound capacity map. |
296 |
356 |
297 /// Sets the lower bound capacity map. |
357 /// Sets the lower bound capacity map. |
298 /// \return \c (*this) |
358 /// \return <tt>(*this)</tt> |
299 Circulation& lowerCapMap(const LCapMap& map) { |
359 Circulation& lowerCapMap(const LCapMap& map) { |
300 _lo = ↦ |
360 _lo = ↦ |
301 return *this; |
361 return *this; |
302 } |
362 } |
303 |
363 |
304 /// Sets the upper bound capacity map. |
364 /// Sets the upper bound capacity map. |
305 |
365 |
306 /// Sets the upper bound capacity map. |
366 /// Sets the upper bound capacity map. |
307 /// \return \c (*this) |
367 /// \return <tt>(*this)</tt> |
308 Circulation& upperCapMap(const LCapMap& map) { |
368 Circulation& upperCapMap(const LCapMap& map) { |
309 _up = ↦ |
369 _up = ↦ |
310 return *this; |
370 return *this; |
311 } |
371 } |
312 |
372 |
313 /// Sets the lower bound map on excess. |
373 /// Sets the lower bound map for the supply of the nodes. |
314 |
374 |
315 /// Sets the lower bound map on excess. |
375 /// Sets the lower bound map for the supply of the nodes. |
316 /// \return \c (*this) |
376 /// \return <tt>(*this)</tt> |
317 Circulation& deltaMap(const DeltaMap& map) { |
377 Circulation& deltaMap(const DeltaMap& map) { |
318 _delta = ↦ |
378 _delta = ↦ |
319 return *this; |
379 return *this; |
320 } |
380 } |
321 |
381 |
|
382 /// \brief Sets the flow map. |
|
383 /// |
322 /// Sets the flow map. |
384 /// Sets the flow map. |
323 |
385 /// If you don't use this function before calling \ref run() or |
324 /// Sets the flow map. |
386 /// \ref init(), an instance will be allocated automatically. |
325 /// \return \c (*this) |
387 /// The destructor deallocates this automatically allocated map, |
|
388 /// of course. |
|
389 /// \return <tt>(*this)</tt> |
326 Circulation& flowMap(FlowMap& map) { |
390 Circulation& flowMap(FlowMap& map) { |
327 if (_local_flow) { |
391 if (_local_flow) { |
328 delete _flow; |
392 delete _flow; |
329 _local_flow = false; |
393 _local_flow = false; |
330 } |
394 } |
331 _flow = ↦ |
395 _flow = ↦ |
332 return *this; |
396 return *this; |
333 } |
397 } |
334 |
398 |
335 /// Returns the flow map. |
399 /// \brief Sets the elevator used by algorithm. |
336 |
400 /// |
337 /// \return The flow map. |
401 /// Sets the elevator used by algorithm. |
338 /// |
402 /// If you don't use this function before calling \ref run() or |
339 const FlowMap& flowMap() { |
403 /// \ref init(), an instance will be allocated automatically. |
340 return *_flow; |
404 /// The destructor deallocates this automatically allocated elevator, |
341 } |
405 /// of course. |
342 |
406 /// \return <tt>(*this)</tt> |
343 /// Sets the elevator. |
|
344 |
|
345 /// Sets the elevator. |
|
346 /// \return \c (*this) |
|
347 Circulation& elevator(Elevator& elevator) { |
407 Circulation& elevator(Elevator& elevator) { |
348 if (_local_level) { |
408 if (_local_level) { |
349 delete _level; |
409 delete _level; |
350 _local_level = false; |
410 _local_level = false; |
351 } |
411 } |
352 _level = &elevator; |
412 _level = &elevator; |
353 return *this; |
413 return *this; |
354 } |
414 } |
355 |
415 |
356 /// Returns the elevator. |
416 /// \brief Returns a const reference to the elevator. |
357 |
417 /// |
358 /// \return The elevator. |
418 /// Returns a const reference to the elevator. |
359 /// |
419 /// |
|
420 /// \pre Either \ref run() or \ref init() must be called before |
|
421 /// using this function. |
360 const Elevator& elevator() { |
422 const Elevator& elevator() { |
361 return *_level; |
423 return *_level; |
362 } |
424 } |
363 |
425 |
|
426 /// \brief Sets the tolerance used by algorithm. |
|
427 /// |
364 /// Sets the tolerance used by algorithm. |
428 /// Sets the tolerance used by algorithm. |
365 |
|
366 /// Sets the tolerance used by algorithm. |
|
367 /// |
|
368 Circulation& tolerance(const Tolerance& tolerance) const { |
429 Circulation& tolerance(const Tolerance& tolerance) const { |
369 _tol = tolerance; |
430 _tol = tolerance; |
370 return *this; |
431 return *this; |
371 } |
432 } |
372 |
433 |
373 /// Returns the tolerance used by algorithm. |
434 /// \brief Returns a const reference to the tolerance. |
374 |
435 /// |
375 /// Returns the tolerance used by algorithm. |
436 /// Returns a const reference to the tolerance. |
376 /// |
|
377 const Tolerance& tolerance() const { |
437 const Tolerance& tolerance() const { |
378 return tolerance; |
438 return tolerance; |
379 } |
439 } |
380 |
440 |
381 /// \name Execution control |
441 /// \name Execution Control |
382 /// The simplest way to execute the algorithm is to use one of the |
442 /// The simplest way to execute the algorithm is to call \ref run().\n |
383 /// member functions called \c run(). |
443 /// If you need more control on the initial solution or the execution, |
384 /// \n |
444 /// first you have to call one of the \ref init() functions, then |
385 /// If you need more control on initial solution or execution then |
445 /// the \ref start() function. |
386 /// you have to call one \ref init() function and then the start() |
|
387 /// function. |
|
388 |
446 |
389 ///@{ |
447 ///@{ |
390 |
448 |
391 /// Initializes the internal data structures. |
449 /// Initializes the internal data structures. |
392 |
450 |
393 /// Initializes the internal data structures. This function sets |
451 /// Initializes the internal data structures and sets all flow values |
394 /// all flow values to the lower bound. |
452 /// to the lower bound. |
395 /// \return This function returns false if the initialization |
|
396 /// process found a barrier. |
|
397 void init() |
453 void init() |
398 { |
454 { |
399 createStructures(); |
455 createStructures(); |
400 |
456 |
401 for(NodeIt n(_g);n!=INVALID;++n) { |
457 for(NodeIt n(_g);n!=INVALID;++n) { |
541 ; |
599 ; |
542 } |
600 } |
543 return true; |
601 return true; |
544 } |
602 } |
545 |
603 |
546 /// Runs the circulation algorithm. |
604 /// Runs the algorithm. |
547 |
605 |
548 /// Runs the circulation algorithm. |
606 /// This function runs the algorithm. |
549 /// \note fc.run() is just a shortcut of the following code. |
607 /// |
|
608 /// \return \c true if a feasible circulation is found. |
|
609 /// |
|
610 /// \note Apart from the return value, c.run() is just a shortcut of |
|
611 /// the following code. |
550 /// \code |
612 /// \code |
551 /// fc.greedyInit(); |
613 /// c.greedyInit(); |
552 /// return fc.start(); |
614 /// c.start(); |
553 /// \endcode |
615 /// \endcode |
554 bool run() { |
616 bool run() { |
555 greedyInit(); |
617 greedyInit(); |
556 return start(); |
618 return start(); |
557 } |
619 } |
558 |
620 |
559 /// @} |
621 /// @} |
560 |
622 |
561 /// \name Query Functions |
623 /// \name Query Functions |
562 /// The result of the %Circulation algorithm can be obtained using |
624 /// The results of the circulation algorithm can be obtained using |
563 /// these functions. |
625 /// these functions.\n |
564 /// \n |
626 /// Either \ref run() or \ref start() should be called before |
565 /// Before the use of these functions, |
627 /// using them. |
566 /// either run() or start() must be called. |
|
567 |
628 |
568 ///@{ |
629 ///@{ |
569 |
630 |
|
631 /// \brief Returns the flow on the given arc. |
|
632 /// |
|
633 /// Returns the flow on the given arc. |
|
634 /// |
|
635 /// \pre Either \ref run() or \ref init() must be called before |
|
636 /// using this function. |
|
637 Value flow(const Arc& arc) const { |
|
638 return (*_flow)[arc]; |
|
639 } |
|
640 |
|
641 /// \brief Returns a const reference to the flow map. |
|
642 /// |
|
643 /// Returns a const reference to the arc map storing the found flow. |
|
644 /// |
|
645 /// \pre Either \ref run() or \ref init() must be called before |
|
646 /// using this function. |
|
647 const FlowMap& flowMap() { |
|
648 return *_flow; |
|
649 } |
|
650 |
570 /** |
651 /** |
571 \brief Returns a barrier |
652 \brief Returns \c true if the given node is in a barrier. |
572 |
653 |
573 Barrier is a set \e B of nodes for which |
654 Barrier is a set \e B of nodes for which |
574 \f[ \sum_{v\in B}-delta(v)< |
655 |
575 \sum_{e\in\rho(B)}lo(e)-\sum_{e\in\delta(B)}up(e) \f] |
656 \f[ \sum_{a\in\delta_{out}(B)} upper(a) - |
576 holds. The existence of a set with this property prooves that a feasible |
657 \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f] |
577 flow cannot exists. |
658 |
|
659 holds. The existence of a set with this property prooves that a |
|
660 feasible circualtion cannot exist. |
|
661 |
|
662 This function returns \c true if the given node is in the found |
|
663 barrier. If a feasible circulation is found, the function |
|
664 gives back \c false for every node. |
|
665 |
|
666 \pre Either \ref run() or \ref init() must be called before |
|
667 using this function. |
|
668 |
|
669 \sa barrierMap() |
578 \sa checkBarrier() |
670 \sa checkBarrier() |
579 \sa run() |
|
580 */ |
671 */ |
581 template<class GT> |
672 bool barrier(const Node& node) |
582 void barrierMap(GT &bar) |
673 { |
|
674 return (*_level)[node] >= _el; |
|
675 } |
|
676 |
|
677 /// \brief Gives back a barrier. |
|
678 /// |
|
679 /// This function sets \c bar to the characteristic vector of the |
|
680 /// found barrier. \c bar should be a \ref concepts::WriteMap "writable" |
|
681 /// node map with \c bool (or convertible) value type. |
|
682 /// |
|
683 /// If a feasible circulation is found, the function gives back an |
|
684 /// empty set, so \c bar[v] will be \c false for all nodes \c v. |
|
685 /// |
|
686 /// \note This function calls \ref barrier() for each node, |
|
687 /// so it runs in \f$O(n)\f$ time. |
|
688 /// |
|
689 /// \pre Either \ref run() or \ref init() must be called before |
|
690 /// using this function. |
|
691 /// |
|
692 /// \sa barrier() |
|
693 /// \sa checkBarrier() |
|
694 template<class BarrierMap> |
|
695 void barrierMap(BarrierMap &bar) |
583 { |
696 { |
584 for(NodeIt n(_g);n!=INVALID;++n) |
697 for(NodeIt n(_g);n!=INVALID;++n) |
585 bar.set(n, (*_level)[n] >= _el); |
698 bar.set(n, (*_level)[n] >= _el); |
586 } |
699 } |
587 |
700 |
588 ///Returns true if the node is in the barrier |
|
589 |
|
590 ///Returns true if the node is in the barrier |
|
591 ///\sa barrierMap() |
|
592 bool barrier(const Node& node) |
|
593 { |
|
594 return (*_level)[node] >= _el; |
|
595 } |
|
596 |
|
597 /// \brief Returns the flow on the arc. |
|
598 /// |
|
599 /// Sets the \c flowMap to the flow on the arcs. This method can |
|
600 /// be called after the second phase of algorithm. |
|
601 Value flow(const Arc& arc) const { |
|
602 return (*_flow)[arc]; |
|
603 } |
|
604 |
|
605 /// @} |
701 /// @} |
606 |
702 |
607 /// \name Checker Functions |
703 /// \name Checker Functions |
608 /// The feasibility of the results can be checked using |
704 /// The feasibility of the results can be checked using |
609 /// these functions. |
705 /// these functions.\n |
610 /// \n |
706 /// Either \ref run() or \ref start() should be called before |
611 /// Before the use of these functions, |
707 /// using them. |
612 /// either run() or start() must be called. |
|
613 |
708 |
614 ///@{ |
709 ///@{ |
615 |
710 |
616 ///Check if the \c flow is a feasible circulation |
711 ///Check if the found flow is a feasible circulation |
|
712 |
|
713 ///Check if the found flow is a feasible circulation, |
|
714 /// |
617 bool checkFlow() { |
715 bool checkFlow() { |
618 for(ArcIt e(_g);e!=INVALID;++e) |
716 for(ArcIt e(_g);e!=INVALID;++e) |
619 if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false; |
717 if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false; |
620 for(NodeIt n(_g);n!=INVALID;++n) |
718 for(NodeIt n(_g);n!=INVALID;++n) |
621 { |
719 { |