lemon/circulation.h
changeset 408 69f33ef03334
parent 401 26fd85a3087e
child 420 6a2a33ad261b
equal deleted inserted replaced
1:88dc2922b202 2:c29974b8ce22
    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;
   153     bool _local_flow;
   201     bool _local_flow;
   154 
   202 
   155     Elevator* _level;
   203     Elevator* _level;
   156     bool _local_level;
   204     bool _local_level;
   157 
   205 
       
   206     typedef typename Digraph::template NodeMap<Value> ExcessMap;
   158     ExcessMap* _excess;
   207     ExcessMap* _excess;
   159 
   208 
   160     Tolerance _tol;
   209     Tolerance _tol;
   161     int _el;
   210     int _el;
   162 
   211 
   163   public:
   212   public:
   164 
   213 
   165     typedef Circulation Create;
   214     typedef Circulation Create;
   166 
   215 
   167     ///\name Named template parameters
   216     ///\name Named Template Parameters
   168 
   217 
   169     ///@{
   218     ///@{
   170 
   219 
   171     template <typename _FlowMap>
   220     template <typename _FlowMap>
   172     struct SetFlowMapTraits : public Traits {
   221     struct SetFlowMapTraits : public Traits {
   179 
   228 
   180     /// \brief \ref named-templ-param "Named parameter" for setting
   229     /// \brief \ref named-templ-param "Named parameter" for setting
   181     /// FlowMap type
   230     /// FlowMap type
   182     ///
   231     ///
   183     /// \ref named-templ-param "Named parameter" for setting FlowMap
   232     /// \ref named-templ-param "Named parameter" for setting FlowMap
   184     /// type
   233     /// type.
   185     template <typename _FlowMap>
   234     template <typename _FlowMap>
   186     struct SetFlowMap
   235     struct SetFlowMap
   187       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   236       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   188                            SetFlowMapTraits<_FlowMap> > {
   237                            SetFlowMapTraits<_FlowMap> > {
   189       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   238       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   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 = &map;
   360       _lo = &map;
   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 = &map;
   369       _up = &map;
   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 = &map;
   378       _delta = &map;
   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 = &map;
   395       _flow = &map;
   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) {
   417       for(NodeIt n(_g);n!=INVALID;++n)
   473       for(NodeIt n(_g);n!=INVALID;++n)
   418         if(_tol.positive((*_excess)[n]))
   474         if(_tol.positive((*_excess)[n]))
   419           _level->activate(n);
   475           _level->activate(n);
   420     }
   476     }
   421 
   477 
   422     /// Initializes the internal data structures.
   478     /// Initializes the internal data structures using a greedy approach.
   423 
   479 
   424     /// Initializes the internal data structures. This functions uses
   480     /// Initializes the internal data structures using a greedy approach
   425     /// greedy approach to construct the initial solution.
   481     /// to construct the initial solution.
   426     void greedyInit()
   482     void greedyInit()
   427     {
   483     {
   428       createStructures();
   484       createStructures();
   429 
   485 
   430       for(NodeIt n(_g);n!=INVALID;++n) {
   486       for(NodeIt n(_g);n!=INVALID;++n) {
   455       for(NodeIt n(_g);n!=INVALID;++n)
   511       for(NodeIt n(_g);n!=INVALID;++n)
   456         if(_tol.positive((*_excess)[n]))
   512         if(_tol.positive((*_excess)[n]))
   457           _level->activate(n);
   513           _level->activate(n);
   458     }
   514     }
   459 
   515 
   460     ///Starts the algorithm
   516     ///Executes the algorithm
   461 
   517 
   462     ///This function starts the algorithm.
   518     ///This function executes the algorithm.
   463     ///\return This function returns true if it found a feasible circulation.
   519     ///
       
   520     ///\return \c true if a feasible circulation is found.
   464     ///
   521     ///
   465     ///\sa barrier()
   522     ///\sa barrier()
       
   523     ///\sa barrierMap()
   466     bool start()
   524     bool start()
   467     {
   525     {
   468 
   526 
   469       Node act;
   527       Node act;
   470       Node bact=INVALID;
   528       Node bact=INVALID;
   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         {
   627       return true;
   725       return true;
   628     }
   726     }
   629 
   727 
   630     ///Check whether or not the last execution provides a barrier
   728     ///Check whether or not the last execution provides a barrier
   631 
   729 
   632     ///Check whether or not the last execution provides a barrier
   730     ///Check whether or not the last execution provides a barrier.
   633     ///\sa barrier()
   731     ///\sa barrier()
       
   732     ///\sa barrierMap()
   634     bool checkBarrier()
   733     bool checkBarrier()
   635     {
   734     {
   636       Value delta=0;
   735       Value delta=0;
   637       for(NodeIt n(_g);n!=INVALID;++n)
   736       for(NodeIt n(_g);n!=INVALID;++n)
   638         if(barrier(n))
   737         if(barrier(n))