1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/circulation.h Fri Nov 21 14:42:47 2008 +0000
1.3 @@ -0,0 +1,656 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_CIRCULATION_H
1.23 +#define LEMON_CIRCULATION_H
1.24 +
1.25 +#include <iostream>
1.26 +#include <queue>
1.27 +#include <lemon/tolerance.h>
1.28 +#include <lemon/elevator.h>
1.29 +
1.30 +///\ingroup max_flow
1.31 +///\file
1.32 +///\brief Push-prelabel algorithm for finding a feasible circulation.
1.33 +///
1.34 +namespace lemon {
1.35 +
1.36 + /// \brief Default traits class of Circulation class.
1.37 + ///
1.38 + /// Default traits class of Circulation class.
1.39 + /// \param _Graph Digraph type.
1.40 + /// \param _CapacityMap Type of capacity map.
1.41 + template <typename _Graph, typename _LCapMap,
1.42 + typename _UCapMap, typename _DeltaMap>
1.43 + struct CirculationDefaultTraits {
1.44 +
1.45 + /// \brief The digraph type the algorithm runs on.
1.46 + typedef _Graph Digraph;
1.47 +
1.48 + /// \brief The type of the map that stores the circulation lower
1.49 + /// bound.
1.50 + ///
1.51 + /// The type of the map that stores the circulation lower bound.
1.52 + /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.53 + typedef _LCapMap LCapMap;
1.54 +
1.55 + /// \brief The type of the map that stores the circulation upper
1.56 + /// bound.
1.57 + ///
1.58 + /// The type of the map that stores the circulation upper bound.
1.59 + /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.60 + typedef _UCapMap UCapMap;
1.61 +
1.62 + /// \brief The type of the map that stores the upper bound of
1.63 + /// node excess.
1.64 + ///
1.65 + /// The type of the map that stores the lower bound of node
1.66 + /// excess. It must meet the \ref concepts::ReadMap "ReadMap"
1.67 + /// concept.
1.68 + typedef _DeltaMap DeltaMap;
1.69 +
1.70 + /// \brief The type of the length of the arcs.
1.71 + typedef typename DeltaMap::Value Value;
1.72 +
1.73 + /// \brief The map type that stores the flow values.
1.74 + ///
1.75 + /// The map type that stores the flow values.
1.76 + /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.77 + typedef typename Digraph::template ArcMap<Value> FlowMap;
1.78 +
1.79 + /// \brief Instantiates a FlowMap.
1.80 + ///
1.81 + /// This function instantiates a \ref FlowMap.
1.82 + /// \param digraph The digraph, to which we would like to define
1.83 + /// the flow map.
1.84 + static FlowMap* createFlowMap(const Digraph& digraph) {
1.85 + return new FlowMap(digraph);
1.86 + }
1.87 +
1.88 + /// \brief The eleavator type used by Circulation algorithm.
1.89 + ///
1.90 + /// The elevator type used by Circulation algorithm.
1.91 + ///
1.92 + /// \sa Elevator
1.93 + /// \sa LinkedElevator
1.94 + typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
1.95 +
1.96 + /// \brief Instantiates an Elevator.
1.97 + ///
1.98 + /// This function instantiates a \ref Elevator.
1.99 + /// \param digraph The digraph, to which we would like to define
1.100 + /// the elevator.
1.101 + /// \param max_level The maximum level of the elevator.
1.102 + static Elevator* createElevator(const Digraph& digraph, int max_level) {
1.103 + return new Elevator(digraph, max_level);
1.104 + }
1.105 +
1.106 + /// \brief The tolerance used by the algorithm
1.107 + ///
1.108 + /// The tolerance used by the algorithm to handle inexact computation.
1.109 + typedef lemon::Tolerance<Value> Tolerance;
1.110 +
1.111 + };
1.112 +
1.113 + ///Push-relabel algorithm for the Network Circulation Problem.
1.114 +
1.115 + /**
1.116 + \ingroup max_flow
1.117 + This class implements a push-relabel algorithm
1.118 + or the Network Circulation Problem.
1.119 + The exact formulation of this problem is the following.
1.120 + \f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq
1.121 + -delta(v)\quad \forall v\in V \f]
1.122 + \f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f]
1.123 + */
1.124 + template<class _Graph,
1.125 + class _LCapMap=typename _Graph::template ArcMap<int>,
1.126 + class _UCapMap=_LCapMap,
1.127 + class _DeltaMap=typename _Graph::template NodeMap<
1.128 + typename _UCapMap::Value>,
1.129 + class _Traits=CirculationDefaultTraits<_Graph, _LCapMap,
1.130 + _UCapMap, _DeltaMap> >
1.131 + class Circulation {
1.132 +
1.133 + typedef _Traits Traits;
1.134 + typedef typename Traits::Digraph Digraph;
1.135 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.136 +
1.137 + typedef typename Traits::Value Value;
1.138 +
1.139 + typedef typename Traits::LCapMap LCapMap;
1.140 + typedef typename Traits::UCapMap UCapMap;
1.141 + typedef typename Traits::DeltaMap DeltaMap;
1.142 + typedef typename Traits::FlowMap FlowMap;
1.143 + typedef typename Traits::Elevator Elevator;
1.144 + typedef typename Traits::Tolerance Tolerance;
1.145 +
1.146 + typedef typename Digraph::template NodeMap<Value> ExcessMap;
1.147 +
1.148 + const Digraph &_g;
1.149 + int _node_num;
1.150 +
1.151 + const LCapMap *_lo;
1.152 + const UCapMap *_up;
1.153 + const DeltaMap *_delta;
1.154 +
1.155 + FlowMap *_flow;
1.156 + bool _local_flow;
1.157 +
1.158 + Elevator* _level;
1.159 + bool _local_level;
1.160 +
1.161 + ExcessMap* _excess;
1.162 +
1.163 + Tolerance _tol;
1.164 + int _el;
1.165 +
1.166 + public:
1.167 +
1.168 + typedef Circulation Create;
1.169 +
1.170 + ///\name Named template parameters
1.171 +
1.172 + ///@{
1.173 +
1.174 + template <typename _FlowMap>
1.175 + struct DefFlowMapTraits : public Traits {
1.176 + typedef _FlowMap FlowMap;
1.177 + static FlowMap *createFlowMap(const Digraph&) {
1.178 + LEMON_ASSERT(false, "FlowMap is not initialized");
1.179 + return 0; // ignore warnings
1.180 + }
1.181 + };
1.182 +
1.183 + /// \brief \ref named-templ-param "Named parameter" for setting
1.184 + /// FlowMap type
1.185 + ///
1.186 + /// \ref named-templ-param "Named parameter" for setting FlowMap
1.187 + /// type
1.188 + template <typename _FlowMap>
1.189 + struct DefFlowMap
1.190 + : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.191 + DefFlowMapTraits<_FlowMap> > {
1.192 + typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.193 + DefFlowMapTraits<_FlowMap> > Create;
1.194 + };
1.195 +
1.196 + template <typename _Elevator>
1.197 + struct DefElevatorTraits : public Traits {
1.198 + typedef _Elevator Elevator;
1.199 + static Elevator *createElevator(const Digraph&, int) {
1.200 + LEMON_ASSERT(false, "Elevator is not initialized");
1.201 + return 0; // ignore warnings
1.202 + }
1.203 + };
1.204 +
1.205 + /// \brief \ref named-templ-param "Named parameter" for setting
1.206 + /// Elevator type
1.207 + ///
1.208 + /// \ref named-templ-param "Named parameter" for setting Elevator
1.209 + /// type
1.210 + template <typename _Elevator>
1.211 + struct DefElevator
1.212 + : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.213 + DefElevatorTraits<_Elevator> > {
1.214 + typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.215 + DefElevatorTraits<_Elevator> > Create;
1.216 + };
1.217 +
1.218 + template <typename _Elevator>
1.219 + struct DefStandardElevatorTraits : public Traits {
1.220 + typedef _Elevator Elevator;
1.221 + static Elevator *createElevator(const Digraph& digraph, int max_level) {
1.222 + return new Elevator(digraph, max_level);
1.223 + }
1.224 + };
1.225 +
1.226 + /// \brief \ref named-templ-param "Named parameter" for setting
1.227 + /// Elevator type
1.228 + ///
1.229 + /// \ref named-templ-param "Named parameter" for setting Elevator
1.230 + /// type. The Elevator should be standard constructor interface, ie.
1.231 + /// the digraph and the maximum level should be passed to it.
1.232 + template <typename _Elevator>
1.233 + struct DefStandardElevator
1.234 + : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.235 + DefStandardElevatorTraits<_Elevator> > {
1.236 + typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.237 + DefStandardElevatorTraits<_Elevator> > Create;
1.238 + };
1.239 +
1.240 + /// @}
1.241 +
1.242 + protected:
1.243 +
1.244 + Circulation() {}
1.245 +
1.246 + public:
1.247 +
1.248 + /// The constructor of the class.
1.249 +
1.250 + /// The constructor of the class.
1.251 + /// \param g The digraph the algorithm runs on.
1.252 + /// \param lo The lower bound capacity of the arcs.
1.253 + /// \param up The upper bound capacity of the arcs.
1.254 + /// \param delta The lower bound on node excess.
1.255 + Circulation(const Digraph &g,const LCapMap &lo,
1.256 + const UCapMap &up,const DeltaMap &delta)
1.257 + : _g(g), _node_num(),
1.258 + _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
1.259 + _level(0), _local_level(false), _excess(0), _el() {}
1.260 +
1.261 + /// Destrcutor.
1.262 + ~Circulation() {
1.263 + destroyStructures();
1.264 + }
1.265 +
1.266 + private:
1.267 +
1.268 + void createStructures() {
1.269 + _node_num = _el = countNodes(_g);
1.270 +
1.271 + if (!_flow) {
1.272 + _flow = Traits::createFlowMap(_g);
1.273 + _local_flow = true;
1.274 + }
1.275 + if (!_level) {
1.276 + _level = Traits::createElevator(_g, _node_num);
1.277 + _local_level = true;
1.278 + }
1.279 + if (!_excess) {
1.280 + _excess = new ExcessMap(_g);
1.281 + }
1.282 + }
1.283 +
1.284 + void destroyStructures() {
1.285 + if (_local_flow) {
1.286 + delete _flow;
1.287 + }
1.288 + if (_local_level) {
1.289 + delete _level;
1.290 + }
1.291 + if (_excess) {
1.292 + delete _excess;
1.293 + }
1.294 + }
1.295 +
1.296 + public:
1.297 +
1.298 + /// Sets the lower bound capacity map.
1.299 +
1.300 + /// Sets the lower bound capacity map.
1.301 + /// \return \c (*this)
1.302 + Circulation& lowerCapMap(const LCapMap& map) {
1.303 + _lo = ↦
1.304 + return *this;
1.305 + }
1.306 +
1.307 + /// Sets the upper bound capacity map.
1.308 +
1.309 + /// Sets the upper bound capacity map.
1.310 + /// \return \c (*this)
1.311 + Circulation& upperCapMap(const LCapMap& map) {
1.312 + _up = ↦
1.313 + return *this;
1.314 + }
1.315 +
1.316 + /// Sets the lower bound map on excess.
1.317 +
1.318 + /// Sets the lower bound map on excess.
1.319 + /// \return \c (*this)
1.320 + Circulation& deltaMap(const DeltaMap& map) {
1.321 + _delta = ↦
1.322 + return *this;
1.323 + }
1.324 +
1.325 + /// Sets the flow map.
1.326 +
1.327 + /// Sets the flow map.
1.328 + /// \return \c (*this)
1.329 + Circulation& flowMap(FlowMap& map) {
1.330 + if (_local_flow) {
1.331 + delete _flow;
1.332 + _local_flow = false;
1.333 + }
1.334 + _flow = ↦
1.335 + return *this;
1.336 + }
1.337 +
1.338 + /// Returns the flow map.
1.339 +
1.340 + /// \return The flow map.
1.341 + ///
1.342 + const FlowMap& flowMap() {
1.343 + return *_flow;
1.344 + }
1.345 +
1.346 + /// Sets the elevator.
1.347 +
1.348 + /// Sets the elevator.
1.349 + /// \return \c (*this)
1.350 + Circulation& elevator(Elevator& elevator) {
1.351 + if (_local_level) {
1.352 + delete _level;
1.353 + _local_level = false;
1.354 + }
1.355 + _level = &elevator;
1.356 + return *this;
1.357 + }
1.358 +
1.359 + /// Returns the elevator.
1.360 +
1.361 + /// \return The elevator.
1.362 + ///
1.363 + const Elevator& elevator() {
1.364 + return *_level;
1.365 + }
1.366 +
1.367 + /// Sets the tolerance used by algorithm.
1.368 +
1.369 + /// Sets the tolerance used by algorithm.
1.370 + ///
1.371 + Circulation& tolerance(const Tolerance& tolerance) const {
1.372 + _tol = tolerance;
1.373 + return *this;
1.374 + }
1.375 +
1.376 + /// Returns the tolerance used by algorithm.
1.377 +
1.378 + /// Returns the tolerance used by algorithm.
1.379 + ///
1.380 + const Tolerance& tolerance() const {
1.381 + return tolerance;
1.382 + }
1.383 +
1.384 + /// \name Execution control
1.385 + /// The simplest way to execute the algorithm is to use one of the
1.386 + /// member functions called \c run().
1.387 + /// \n
1.388 + /// If you need more control on initial solution or execution then
1.389 + /// you have to call one \ref init() function and then the start()
1.390 + /// function.
1.391 +
1.392 + ///@{
1.393 +
1.394 + /// Initializes the internal data structures.
1.395 +
1.396 + /// Initializes the internal data structures. This function sets
1.397 + /// all flow values to the lower bound.
1.398 + /// \return This function returns false if the initialization
1.399 + /// process found a barrier.
1.400 + void init()
1.401 + {
1.402 + createStructures();
1.403 +
1.404 + for(NodeIt n(_g);n!=INVALID;++n) {
1.405 + _excess->set(n, (*_delta)[n]);
1.406 + }
1.407 +
1.408 + for (ArcIt e(_g);e!=INVALID;++e) {
1.409 + _flow->set(e, (*_lo)[e]);
1.410 + _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
1.411 + _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
1.412 + }
1.413 +
1.414 + // global relabeling tested, but in general case it provides
1.415 + // worse performance for random digraphs
1.416 + _level->initStart();
1.417 + for(NodeIt n(_g);n!=INVALID;++n)
1.418 + _level->initAddItem(n);
1.419 + _level->initFinish();
1.420 + for(NodeIt n(_g);n!=INVALID;++n)
1.421 + if(_tol.positive((*_excess)[n]))
1.422 + _level->activate(n);
1.423 + }
1.424 +
1.425 + /// Initializes the internal data structures.
1.426 +
1.427 + /// Initializes the internal data structures. This functions uses
1.428 + /// greedy approach to construct the initial solution.
1.429 + void greedyInit()
1.430 + {
1.431 + createStructures();
1.432 +
1.433 + for(NodeIt n(_g);n!=INVALID;++n) {
1.434 + _excess->set(n, (*_delta)[n]);
1.435 + }
1.436 +
1.437 + for (ArcIt e(_g);e!=INVALID;++e) {
1.438 + if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
1.439 + _flow->set(e, (*_up)[e]);
1.440 + _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
1.441 + _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
1.442 + } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
1.443 + _flow->set(e, (*_lo)[e]);
1.444 + _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
1.445 + _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
1.446 + } else {
1.447 + Value fc = -(*_excess)[_g.target(e)];
1.448 + _flow->set(e, fc);
1.449 + _excess->set(_g.target(e), 0);
1.450 + _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
1.451 + }
1.452 + }
1.453 +
1.454 + _level->initStart();
1.455 + for(NodeIt n(_g);n!=INVALID;++n)
1.456 + _level->initAddItem(n);
1.457 + _level->initFinish();
1.458 + for(NodeIt n(_g);n!=INVALID;++n)
1.459 + if(_tol.positive((*_excess)[n]))
1.460 + _level->activate(n);
1.461 + }
1.462 +
1.463 + ///Starts the algorithm
1.464 +
1.465 + ///This function starts the algorithm.
1.466 + ///\return This function returns true if it found a feasible circulation.
1.467 + ///
1.468 + ///\sa barrier()
1.469 + bool start()
1.470 + {
1.471 +
1.472 + Node act;
1.473 + Node bact=INVALID;
1.474 + Node last_activated=INVALID;
1.475 + while((act=_level->highestActive())!=INVALID) {
1.476 + int actlevel=(*_level)[act];
1.477 + int mlevel=_node_num;
1.478 + Value exc=(*_excess)[act];
1.479 +
1.480 + for(OutArcIt e(_g,act);e!=INVALID; ++e) {
1.481 + Node v = _g.target(e);
1.482 + Value fc=(*_up)[e]-(*_flow)[e];
1.483 + if(!_tol.positive(fc)) continue;
1.484 + if((*_level)[v]<actlevel) {
1.485 + if(!_tol.less(fc, exc)) {
1.486 + _flow->set(e, (*_flow)[e] + exc);
1.487 + _excess->set(v, (*_excess)[v] + exc);
1.488 + if(!_level->active(v) && _tol.positive((*_excess)[v]))
1.489 + _level->activate(v);
1.490 + _excess->set(act,0);
1.491 + _level->deactivate(act);
1.492 + goto next_l;
1.493 + }
1.494 + else {
1.495 + _flow->set(e, (*_up)[e]);
1.496 + _excess->set(v, (*_excess)[v] + fc);
1.497 + if(!_level->active(v) && _tol.positive((*_excess)[v]))
1.498 + _level->activate(v);
1.499 + exc-=fc;
1.500 + }
1.501 + }
1.502 + else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
1.503 + }
1.504 + for(InArcIt e(_g,act);e!=INVALID; ++e) {
1.505 + Node v = _g.source(e);
1.506 + Value fc=(*_flow)[e]-(*_lo)[e];
1.507 + if(!_tol.positive(fc)) continue;
1.508 + if((*_level)[v]<actlevel) {
1.509 + if(!_tol.less(fc, exc)) {
1.510 + _flow->set(e, (*_flow)[e] - exc);
1.511 + _excess->set(v, (*_excess)[v] + exc);
1.512 + if(!_level->active(v) && _tol.positive((*_excess)[v]))
1.513 + _level->activate(v);
1.514 + _excess->set(act,0);
1.515 + _level->deactivate(act);
1.516 + goto next_l;
1.517 + }
1.518 + else {
1.519 + _flow->set(e, (*_lo)[e]);
1.520 + _excess->set(v, (*_excess)[v] + fc);
1.521 + if(!_level->active(v) && _tol.positive((*_excess)[v]))
1.522 + _level->activate(v);
1.523 + exc-=fc;
1.524 + }
1.525 + }
1.526 + else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
1.527 + }
1.528 +
1.529 + _excess->set(act, exc);
1.530 + if(!_tol.positive(exc)) _level->deactivate(act);
1.531 + else if(mlevel==_node_num) {
1.532 + _level->liftHighestActiveToTop();
1.533 + _el = _node_num;
1.534 + return false;
1.535 + }
1.536 + else {
1.537 + _level->liftHighestActive(mlevel+1);
1.538 + if(_level->onLevel(actlevel)==0) {
1.539 + _el = actlevel;
1.540 + return false;
1.541 + }
1.542 + }
1.543 + next_l:
1.544 + ;
1.545 + }
1.546 + return true;
1.547 + }
1.548 +
1.549 + /// Runs the circulation algorithm.
1.550 +
1.551 + /// Runs the circulation algorithm.
1.552 + /// \note fc.run() is just a shortcut of the following code.
1.553 + /// \code
1.554 + /// fc.greedyInit();
1.555 + /// return fc.start();
1.556 + /// \endcode
1.557 + bool run() {
1.558 + greedyInit();
1.559 + return start();
1.560 + }
1.561 +
1.562 + /// @}
1.563 +
1.564 + /// \name Query Functions
1.565 + /// The result of the %Circulation algorithm can be obtained using
1.566 + /// these functions.
1.567 + /// \n
1.568 + /// Before the use of these functions,
1.569 + /// either run() or start() must be called.
1.570 +
1.571 + ///@{
1.572 +
1.573 + /**
1.574 + \brief Returns a barrier
1.575 +
1.576 + Barrier is a set \e B of nodes for which
1.577 + \f[ \sum_{v\in B}-delta(v)<
1.578 + \sum_{e\in\rho(B)}lo(e)-\sum_{e\in\delta(B)}up(e) \f]
1.579 + holds. The existence of a set with this property prooves that a feasible
1.580 + flow cannot exists.
1.581 + \sa checkBarrier()
1.582 + \sa run()
1.583 + */
1.584 + template<class GT>
1.585 + void barrierMap(GT &bar)
1.586 + {
1.587 + for(NodeIt n(_g);n!=INVALID;++n)
1.588 + bar.set(n, (*_level)[n] >= _el);
1.589 + }
1.590 +
1.591 + ///Returns true if the node is in the barrier
1.592 +
1.593 + ///Returns true if the node is in the barrier
1.594 + ///\sa barrierMap()
1.595 + bool barrier(const Node& node)
1.596 + {
1.597 + return (*_level)[node] >= _el;
1.598 + }
1.599 +
1.600 + /// \brief Returns the flow on the arc.
1.601 + ///
1.602 + /// Sets the \c flowMap to the flow on the arcs. This method can
1.603 + /// be called after the second phase of algorithm.
1.604 + Value flow(const Arc& arc) const {
1.605 + return (*_flow)[arc];
1.606 + }
1.607 +
1.608 + /// @}
1.609 +
1.610 + /// \name Checker Functions
1.611 + /// The feasibility of the results can be checked using
1.612 + /// these functions.
1.613 + /// \n
1.614 + /// Before the use of these functions,
1.615 + /// either run() or start() must be called.
1.616 +
1.617 + ///@{
1.618 +
1.619 + ///Check if the \c flow is a feasible circulation
1.620 + bool checkFlow() {
1.621 + for(ArcIt e(_g);e!=INVALID;++e)
1.622 + if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
1.623 + for(NodeIt n(_g);n!=INVALID;++n)
1.624 + {
1.625 + Value dif=-(*_delta)[n];
1.626 + for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
1.627 + for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
1.628 + if(_tol.negative(dif)) return false;
1.629 + }
1.630 + return true;
1.631 + }
1.632 +
1.633 + ///Check whether or not the last execution provides a barrier
1.634 +
1.635 + ///Check whether or not the last execution provides a barrier
1.636 + ///\sa barrier()
1.637 + bool checkBarrier()
1.638 + {
1.639 + Value delta=0;
1.640 + for(NodeIt n(_g);n!=INVALID;++n)
1.641 + if(barrier(n))
1.642 + delta-=(*_delta)[n];
1.643 + for(ArcIt e(_g);e!=INVALID;++e)
1.644 + {
1.645 + Node s=_g.source(e);
1.646 + Node t=_g.target(e);
1.647 + if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
1.648 + else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
1.649 + }
1.650 + return _tol.negative(delta);
1.651 + }
1.652 +
1.653 + /// @}
1.654 +
1.655 + };
1.656 +
1.657 +}
1.658 +
1.659 +#endif