1.1 --- a/lemon/circulation.h Mon Dec 01 14:07:58 2008 +0000
1.2 +++ b/lemon/circulation.h Sun Nov 30 14:51:05 2008 +0100
1.3 @@ -19,28 +19,28 @@
1.4 #ifndef LEMON_CIRCULATION_H
1.5 #define LEMON_CIRCULATION_H
1.6
1.7 -#include <iostream>
1.8 -#include <queue>
1.9 #include <lemon/tolerance.h>
1.10 #include <lemon/elevator.h>
1.11
1.12 ///\ingroup max_flow
1.13 ///\file
1.14 -///\brief Push-prelabel algorithm for finding a feasible circulation.
1.15 +///\brief Push-relabel algorithm for finding a feasible circulation.
1.16 ///
1.17 namespace lemon {
1.18
1.19 /// \brief Default traits class of Circulation class.
1.20 ///
1.21 /// Default traits class of Circulation class.
1.22 - /// \param _Graph Digraph type.
1.23 - /// \param _CapacityMap Type of capacity map.
1.24 - template <typename _Graph, typename _LCapMap,
1.25 + /// \tparam _Diraph Digraph type.
1.26 + /// \tparam _LCapMap Lower bound capacity map type.
1.27 + /// \tparam _UCapMap Upper bound capacity map type.
1.28 + /// \tparam _DeltaMap Delta map type.
1.29 + template <typename _Diraph, typename _LCapMap,
1.30 typename _UCapMap, typename _DeltaMap>
1.31 struct CirculationDefaultTraits {
1.32
1.33 - /// \brief The digraph type the algorithm runs on.
1.34 - typedef _Graph Digraph;
1.35 + /// \brief The type of the digraph the algorithm runs on.
1.36 + typedef _Diraph Digraph;
1.37
1.38 /// \brief The type of the map that stores the circulation lower
1.39 /// bound.
1.40 @@ -56,20 +56,20 @@
1.41 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.42 typedef _UCapMap UCapMap;
1.43
1.44 - /// \brief The type of the map that stores the upper bound of
1.45 - /// node excess.
1.46 + /// \brief The type of the map that stores the lower bound for
1.47 + /// the supply of the nodes.
1.48 ///
1.49 - /// The type of the map that stores the lower bound of node
1.50 - /// excess. It must meet the \ref concepts::ReadMap "ReadMap"
1.51 + /// The type of the map that stores the lower bound for the supply
1.52 + /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
1.53 /// concept.
1.54 typedef _DeltaMap DeltaMap;
1.55
1.56 - /// \brief The type of the length of the arcs.
1.57 + /// \brief The type of the flow values.
1.58 typedef typename DeltaMap::Value Value;
1.59
1.60 - /// \brief The map type that stores the flow values.
1.61 + /// \brief The type of the map that stores the flow values.
1.62 ///
1.63 - /// The map type that stores the flow values.
1.64 + /// The type of the map that stores the flow values.
1.65 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.66 typedef typename Digraph::template ArcMap<Value> FlowMap;
1.67
1.68 @@ -82,9 +82,9 @@
1.69 return new FlowMap(digraph);
1.70 }
1.71
1.72 - /// \brief The eleavator type used by Circulation algorithm.
1.73 + /// \brief The elevator type used by the algorithm.
1.74 ///
1.75 - /// The elevator type used by Circulation algorithm.
1.76 + /// The elevator type used by the algorithm.
1.77 ///
1.78 /// \sa Elevator
1.79 /// \sa LinkedElevator
1.80 @@ -92,7 +92,7 @@
1.81
1.82 /// \brief Instantiates an Elevator.
1.83 ///
1.84 - /// This function instantiates a \ref Elevator.
1.85 + /// This function instantiates an \ref Elevator.
1.86 /// \param digraph The digraph, to which we would like to define
1.87 /// the elevator.
1.88 /// \param max_level The maximum level of the elevator.
1.89 @@ -107,40 +107,88 @@
1.90
1.91 };
1.92
1.93 - ///Push-relabel algorithm for the Network Circulation Problem.
1.94 + /**
1.95 + \brief Push-relabel algorithm for the network circulation problem.
1.96
1.97 - /**
1.98 \ingroup max_flow
1.99 - This class implements a push-relabel algorithm
1.100 - or the Network Circulation Problem.
1.101 + This class implements a push-relabel algorithm for the network
1.102 + circulation problem.
1.103 + It is to find a feasible circulation when lower and upper bounds
1.104 + are given for the flow values on the arcs and lower bounds
1.105 + are given for the supply values of the nodes.
1.106 +
1.107 The exact formulation of this problem is the following.
1.108 - \f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq
1.109 - -delta(v)\quad \forall v\in V \f]
1.110 - \f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f]
1.111 + Let \f$G=(V,A)\f$ be a digraph,
1.112 + \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
1.113 + \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
1.114 + \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
1.115 + \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
1.116 + \geq delta(v) \quad \forall v\in V, \f]
1.117 + \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
1.118 + \note \f$delta(v)\f$ specifies a lower bound for the supply of node
1.119 + \f$v\f$. It can be either positive or negative, however note that
1.120 + \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
1.121 + have a feasible solution.
1.122 +
1.123 + \note A special case of this problem is when
1.124 + \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
1.125 + will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
1.126 + Thus a feasible solution for the
1.127 + \ref min_cost_flow "minimum cost flow" problem can be calculated
1.128 + in this way.
1.129 +
1.130 + \tparam _Digraph The type of the digraph the algorithm runs on.
1.131 + \tparam _LCapMap The type of the lower bound capacity map. The default
1.132 + map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
1.133 + \tparam _UCapMap The type of the upper bound capacity map. The default
1.134 + map type is \c _LCapMap.
1.135 + \tparam _DeltaMap The type of the map that stores the lower bound
1.136 + for the supply of the nodes. The default map type is
1.137 + \c _Digraph::ArcMap<_UCapMap::Value>.
1.138 */
1.139 - template<class _Graph,
1.140 - class _LCapMap=typename _Graph::template ArcMap<int>,
1.141 - class _UCapMap=_LCapMap,
1.142 - class _DeltaMap=typename _Graph::template NodeMap<
1.143 - typename _UCapMap::Value>,
1.144 - class _Traits=CirculationDefaultTraits<_Graph, _LCapMap,
1.145 - _UCapMap, _DeltaMap> >
1.146 +#ifdef DOXYGEN
1.147 +template< typename _Digraph,
1.148 + typename _LCapMap,
1.149 + typename _UCapMap,
1.150 + typename _DeltaMap,
1.151 + typename _Traits >
1.152 +#else
1.153 +template< typename _Digraph,
1.154 + typename _LCapMap = typename _Digraph::template ArcMap<int>,
1.155 + typename _UCapMap = _LCapMap,
1.156 + typename _DeltaMap = typename _Digraph::
1.157 + template NodeMap<typename _UCapMap::Value>,
1.158 + typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap,
1.159 + _UCapMap, _DeltaMap> >
1.160 +#endif
1.161 class Circulation {
1.162 + public:
1.163
1.164 + ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
1.165 typedef _Traits Traits;
1.166 + ///The type of the digraph the algorithm runs on.
1.167 typedef typename Traits::Digraph Digraph;
1.168 - TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.169 -
1.170 + ///The type of the flow values.
1.171 typedef typename Traits::Value Value;
1.172
1.173 + /// The type of the lower bound capacity map.
1.174 typedef typename Traits::LCapMap LCapMap;
1.175 + /// The type of the upper bound capacity map.
1.176 typedef typename Traits::UCapMap UCapMap;
1.177 + /// \brief The type of the map that stores the lower bound for
1.178 + /// the supply of the nodes.
1.179 typedef typename Traits::DeltaMap DeltaMap;
1.180 + ///The type of the flow map.
1.181 typedef typename Traits::FlowMap FlowMap;
1.182 +
1.183 + ///The type of the elevator.
1.184 typedef typename Traits::Elevator Elevator;
1.185 + ///The type of the tolerance.
1.186 typedef typename Traits::Tolerance Tolerance;
1.187
1.188 - typedef typename Digraph::template NodeMap<Value> ExcessMap;
1.189 + private:
1.190 +
1.191 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.192
1.193 const Digraph &_g;
1.194 int _node_num;
1.195 @@ -155,6 +203,7 @@
1.196 Elevator* _level;
1.197 bool _local_level;
1.198
1.199 + typedef typename Digraph::template NodeMap<Value> ExcessMap;
1.200 ExcessMap* _excess;
1.201
1.202 Tolerance _tol;
1.203 @@ -164,7 +213,7 @@
1.204
1.205 typedef Circulation Create;
1.206
1.207 - ///\name Named template parameters
1.208 + ///\name Named Template Parameters
1.209
1.210 ///@{
1.211
1.212 @@ -181,7 +230,7 @@
1.213 /// FlowMap type
1.214 ///
1.215 /// \ref named-templ-param "Named parameter" for setting FlowMap
1.216 - /// type
1.217 + /// type.
1.218 template <typename _FlowMap>
1.219 struct SetFlowMap
1.220 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.221 @@ -203,7 +252,11 @@
1.222 /// Elevator type
1.223 ///
1.224 /// \ref named-templ-param "Named parameter" for setting Elevator
1.225 - /// type
1.226 + /// type. If this named parameter is used, then an external
1.227 + /// elevator object must be passed to the algorithm using the
1.228 + /// \ref elevator(Elevator&) "elevator()" function before calling
1.229 + /// \ref run() or \ref init().
1.230 + /// \sa SetStandardElevator
1.231 template <typename _Elevator>
1.232 struct SetElevator
1.233 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.234 @@ -221,11 +274,17 @@
1.235 };
1.236
1.237 /// \brief \ref named-templ-param "Named parameter" for setting
1.238 - /// Elevator type
1.239 + /// Elevator type with automatic allocation
1.240 ///
1.241 /// \ref named-templ-param "Named parameter" for setting Elevator
1.242 - /// type. The Elevator should be standard constructor interface, ie.
1.243 - /// the digraph and the maximum level should be passed to it.
1.244 + /// type with automatic allocation.
1.245 + /// The Elevator should have standard constructor interface to be
1.246 + /// able to automatically created by the algorithm (i.e. the
1.247 + /// digraph and the maximum level should be passed to it).
1.248 + /// However an external elevator object could also be passed to the
1.249 + /// algorithm with the \ref elevator(Elevator&) "elevator()" function
1.250 + /// before calling \ref run() or \ref init().
1.251 + /// \sa SetElevator
1.252 template <typename _Elevator>
1.253 struct SetStandardElevator
1.254 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.255 @@ -248,18 +307,19 @@
1.256 /// \param g The digraph the algorithm runs on.
1.257 /// \param lo The lower bound capacity of the arcs.
1.258 /// \param up The upper bound capacity of the arcs.
1.259 - /// \param delta The lower bound on node excess.
1.260 + /// \param delta The lower bound for the supply of the nodes.
1.261 Circulation(const Digraph &g,const LCapMap &lo,
1.262 const UCapMap &up,const DeltaMap &delta)
1.263 : _g(g), _node_num(),
1.264 _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
1.265 _level(0), _local_level(false), _excess(0), _el() {}
1.266
1.267 - /// Destrcutor.
1.268 + /// Destructor.
1.269 ~Circulation() {
1.270 destroyStructures();
1.271 }
1.272
1.273 +
1.274 private:
1.275
1.276 void createStructures() {
1.277 @@ -295,7 +355,7 @@
1.278 /// Sets the lower bound capacity map.
1.279
1.280 /// Sets the lower bound capacity map.
1.281 - /// \return \c (*this)
1.282 + /// \return <tt>(*this)</tt>
1.283 Circulation& lowerCapMap(const LCapMap& map) {
1.284 _lo = ↦
1.285 return *this;
1.286 @@ -304,25 +364,29 @@
1.287 /// Sets the upper bound capacity map.
1.288
1.289 /// Sets the upper bound capacity map.
1.290 - /// \return \c (*this)
1.291 + /// \return <tt>(*this)</tt>
1.292 Circulation& upperCapMap(const LCapMap& map) {
1.293 _up = ↦
1.294 return *this;
1.295 }
1.296
1.297 - /// Sets the lower bound map on excess.
1.298 + /// Sets the lower bound map for the supply of the nodes.
1.299
1.300 - /// Sets the lower bound map on excess.
1.301 - /// \return \c (*this)
1.302 + /// Sets the lower bound map for the supply of the nodes.
1.303 + /// \return <tt>(*this)</tt>
1.304 Circulation& deltaMap(const DeltaMap& map) {
1.305 _delta = ↦
1.306 return *this;
1.307 }
1.308
1.309 + /// \brief Sets the flow map.
1.310 + ///
1.311 /// Sets the flow map.
1.312 -
1.313 - /// Sets the flow map.
1.314 - /// \return \c (*this)
1.315 + /// If you don't use this function before calling \ref run() or
1.316 + /// \ref init(), an instance will be allocated automatically.
1.317 + /// The destructor deallocates this automatically allocated map,
1.318 + /// of course.
1.319 + /// \return <tt>(*this)</tt>
1.320 Circulation& flowMap(FlowMap& map) {
1.321 if (_local_flow) {
1.322 delete _flow;
1.323 @@ -332,18 +396,14 @@
1.324 return *this;
1.325 }
1.326
1.327 - /// Returns the flow map.
1.328 -
1.329 - /// \return The flow map.
1.330 + /// \brief Sets the elevator used by algorithm.
1.331 ///
1.332 - const FlowMap& flowMap() {
1.333 - return *_flow;
1.334 - }
1.335 -
1.336 - /// Sets the elevator.
1.337 -
1.338 - /// Sets the elevator.
1.339 - /// \return \c (*this)
1.340 + /// Sets the elevator used by algorithm.
1.341 + /// If you don't use this function before calling \ref run() or
1.342 + /// \ref init(), an instance will be allocated automatically.
1.343 + /// The destructor deallocates this automatically allocated elevator,
1.344 + /// of course.
1.345 + /// \return <tt>(*this)</tt>
1.346 Circulation& elevator(Elevator& elevator) {
1.347 if (_local_level) {
1.348 delete _level;
1.349 @@ -353,47 +413,43 @@
1.350 return *this;
1.351 }
1.352
1.353 - /// Returns the elevator.
1.354 -
1.355 - /// \return The elevator.
1.356 + /// \brief Returns a const reference to the elevator.
1.357 ///
1.358 + /// Returns a const reference to the elevator.
1.359 + ///
1.360 + /// \pre Either \ref run() or \ref init() must be called before
1.361 + /// using this function.
1.362 const Elevator& elevator() {
1.363 return *_level;
1.364 }
1.365
1.366 + /// \brief Sets the tolerance used by algorithm.
1.367 + ///
1.368 /// Sets the tolerance used by algorithm.
1.369 -
1.370 - /// Sets the tolerance used by algorithm.
1.371 - ///
1.372 Circulation& tolerance(const Tolerance& tolerance) const {
1.373 _tol = tolerance;
1.374 return *this;
1.375 }
1.376
1.377 - /// Returns the tolerance used by algorithm.
1.378 -
1.379 - /// Returns the tolerance used by algorithm.
1.380 + /// \brief Returns a const reference to the tolerance.
1.381 ///
1.382 + /// Returns a const reference to the tolerance.
1.383 const Tolerance& tolerance() const {
1.384 return tolerance;
1.385 }
1.386
1.387 - /// \name Execution control
1.388 - /// The simplest way to execute the algorithm is to use one of the
1.389 - /// member functions called \c run().
1.390 - /// \n
1.391 - /// If you need more control on initial solution or execution then
1.392 - /// you have to call one \ref init() function and then the start()
1.393 - /// function.
1.394 + /// \name Execution Control
1.395 + /// The simplest way to execute the algorithm is to call \ref run().\n
1.396 + /// If you need more control on the initial solution or the execution,
1.397 + /// first you have to call one of the \ref init() functions, then
1.398 + /// the \ref start() function.
1.399
1.400 ///@{
1.401
1.402 /// Initializes the internal data structures.
1.403
1.404 - /// Initializes the internal data structures. This function sets
1.405 - /// all flow values to the lower bound.
1.406 - /// \return This function returns false if the initialization
1.407 - /// process found a barrier.
1.408 + /// Initializes the internal data structures and sets all flow values
1.409 + /// to the lower bound.
1.410 void init()
1.411 {
1.412 createStructures();
1.413 @@ -419,10 +475,10 @@
1.414 _level->activate(n);
1.415 }
1.416
1.417 - /// Initializes the internal data structures.
1.418 + /// Initializes the internal data structures using a greedy approach.
1.419
1.420 - /// Initializes the internal data structures. This functions uses
1.421 - /// greedy approach to construct the initial solution.
1.422 + /// Initializes the internal data structures using a greedy approach
1.423 + /// to construct the initial solution.
1.424 void greedyInit()
1.425 {
1.426 createStructures();
1.427 @@ -457,12 +513,14 @@
1.428 _level->activate(n);
1.429 }
1.430
1.431 - ///Starts the algorithm
1.432 + ///Executes the algorithm
1.433
1.434 - ///This function starts the algorithm.
1.435 - ///\return This function returns true if it found a feasible circulation.
1.436 + ///This function executes the algorithm.
1.437 + ///
1.438 + ///\return \c true if a feasible circulation is found.
1.439 ///
1.440 ///\sa barrier()
1.441 + ///\sa barrierMap()
1.442 bool start()
1.443 {
1.444
1.445 @@ -543,13 +601,17 @@
1.446 return true;
1.447 }
1.448
1.449 - /// Runs the circulation algorithm.
1.450 + /// Runs the algorithm.
1.451
1.452 - /// Runs the circulation algorithm.
1.453 - /// \note fc.run() is just a shortcut of the following code.
1.454 + /// This function runs the algorithm.
1.455 + ///
1.456 + /// \return \c true if a feasible circulation is found.
1.457 + ///
1.458 + /// \note Apart from the return value, c.run() is just a shortcut of
1.459 + /// the following code.
1.460 /// \code
1.461 - /// fc.greedyInit();
1.462 - /// return fc.start();
1.463 + /// c.greedyInit();
1.464 + /// c.start();
1.465 /// \endcode
1.466 bool run() {
1.467 greedyInit();
1.468 @@ -559,61 +621,97 @@
1.469 /// @}
1.470
1.471 /// \name Query Functions
1.472 - /// The result of the %Circulation algorithm can be obtained using
1.473 - /// these functions.
1.474 - /// \n
1.475 - /// Before the use of these functions,
1.476 - /// either run() or start() must be called.
1.477 + /// The results of the circulation algorithm can be obtained using
1.478 + /// these functions.\n
1.479 + /// Either \ref run() or \ref start() should be called before
1.480 + /// using them.
1.481
1.482 ///@{
1.483
1.484 + /// \brief Returns the flow on the given arc.
1.485 + ///
1.486 + /// Returns the flow on the given arc.
1.487 + ///
1.488 + /// \pre Either \ref run() or \ref init() must be called before
1.489 + /// using this function.
1.490 + Value flow(const Arc& arc) const {
1.491 + return (*_flow)[arc];
1.492 + }
1.493 +
1.494 + /// \brief Returns a const reference to the flow map.
1.495 + ///
1.496 + /// Returns a const reference to the arc map storing the found flow.
1.497 + ///
1.498 + /// \pre Either \ref run() or \ref init() must be called before
1.499 + /// using this function.
1.500 + const FlowMap& flowMap() {
1.501 + return *_flow;
1.502 + }
1.503 +
1.504 /**
1.505 - \brief Returns a barrier
1.506 -
1.507 + \brief Returns \c true if the given node is in a barrier.
1.508 +
1.509 Barrier is a set \e B of nodes for which
1.510 - \f[ \sum_{v\in B}-delta(v)<
1.511 - \sum_{e\in\rho(B)}lo(e)-\sum_{e\in\delta(B)}up(e) \f]
1.512 - holds. The existence of a set with this property prooves that a feasible
1.513 - flow cannot exists.
1.514 +
1.515 + \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
1.516 + \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
1.517 +
1.518 + holds. The existence of a set with this property prooves that a
1.519 + feasible circualtion cannot exist.
1.520 +
1.521 + This function returns \c true if the given node is in the found
1.522 + barrier. If a feasible circulation is found, the function
1.523 + gives back \c false for every node.
1.524 +
1.525 + \pre Either \ref run() or \ref init() must be called before
1.526 + using this function.
1.527 +
1.528 + \sa barrierMap()
1.529 \sa checkBarrier()
1.530 - \sa run()
1.531 */
1.532 - template<class GT>
1.533 - void barrierMap(GT &bar)
1.534 + bool barrier(const Node& node)
1.535 + {
1.536 + return (*_level)[node] >= _el;
1.537 + }
1.538 +
1.539 + /// \brief Gives back a barrier.
1.540 + ///
1.541 + /// This function sets \c bar to the characteristic vector of the
1.542 + /// found barrier. \c bar should be a \ref concepts::WriteMap "writable"
1.543 + /// node map with \c bool (or convertible) value type.
1.544 + ///
1.545 + /// If a feasible circulation is found, the function gives back an
1.546 + /// empty set, so \c bar[v] will be \c false for all nodes \c v.
1.547 + ///
1.548 + /// \note This function calls \ref barrier() for each node,
1.549 + /// so it runs in \f$O(n)\f$ time.
1.550 + ///
1.551 + /// \pre Either \ref run() or \ref init() must be called before
1.552 + /// using this function.
1.553 + ///
1.554 + /// \sa barrier()
1.555 + /// \sa checkBarrier()
1.556 + template<class BarrierMap>
1.557 + void barrierMap(BarrierMap &bar)
1.558 {
1.559 for(NodeIt n(_g);n!=INVALID;++n)
1.560 bar.set(n, (*_level)[n] >= _el);
1.561 }
1.562
1.563 - ///Returns true if the node is in the barrier
1.564 -
1.565 - ///Returns true if the node is in the barrier
1.566 - ///\sa barrierMap()
1.567 - bool barrier(const Node& node)
1.568 - {
1.569 - return (*_level)[node] >= _el;
1.570 - }
1.571 -
1.572 - /// \brief Returns the flow on the arc.
1.573 - ///
1.574 - /// Sets the \c flowMap to the flow on the arcs. This method can
1.575 - /// be called after the second phase of algorithm.
1.576 - Value flow(const Arc& arc) const {
1.577 - return (*_flow)[arc];
1.578 - }
1.579 -
1.580 /// @}
1.581
1.582 /// \name Checker Functions
1.583 - /// The feasibility of the results can be checked using
1.584 - /// these functions.
1.585 - /// \n
1.586 - /// Before the use of these functions,
1.587 - /// either run() or start() must be called.
1.588 + /// The feasibility of the results can be checked using
1.589 + /// these functions.\n
1.590 + /// Either \ref run() or \ref start() should be called before
1.591 + /// using them.
1.592
1.593 ///@{
1.594
1.595 - ///Check if the \c flow is a feasible circulation
1.596 + ///Check if the found flow is a feasible circulation
1.597 +
1.598 + ///Check if the found flow is a feasible circulation,
1.599 + ///
1.600 bool checkFlow() {
1.601 for(ArcIt e(_g);e!=INVALID;++e)
1.602 if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
1.603 @@ -629,8 +727,9 @@
1.604
1.605 ///Check whether or not the last execution provides a barrier
1.606
1.607 - ///Check whether or not the last execution provides a barrier
1.608 + ///Check whether or not the last execution provides a barrier.
1.609 ///\sa barrier()
1.610 + ///\sa barrierMap()
1.611 bool checkBarrier()
1.612 {
1.613 Value delta=0;