Many doc improvements for Circulation (#175)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 30 Nov 2008 14:51:05 +0100
changeset 402235be9d4b6ab
parent 401 26fd85a3087e
child 403 940587667b47
Many doc improvements for Circulation (#175)

- More precise doc for members.
- Several doc fixes.
- Add doc for public types.
- Better formulations.
- Add useful notes to the problem description.
- Use supply instead of excess in the doc.
- Hide the doc of the traits class parameter.
- Use \tparam for template parameters.
lemon/circulation.h
     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 = &map;
   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 = &map;
   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 = &map;
   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;