lemon-1.2: comparison lemon/circulation.h

equal deleted inserted replaced

-:88dc2922b202
+:c29974b8ce22
 */
 #ifndef LEMON_CIRCULATION_H
 #define LEMON_CIRCULATION_H
-#include <iostream>
-#include <queue>
 #include <lemon/tolerance.h>
 #include <lemon/elevator.h>
 ///\ingroup max_flow
 ///\file
-///\brief Push-prelabel algorithm for finding a feasible circulation.
+///\brief Push-relabel algorithm for finding a feasible circulation.
 ///
 namespace lemon {
 /// \brief Default traits class of Circulation class.
 ///
 /// Default traits class of Circulation class.
-/// \param _Graph Digraph type.
+/// \tparam _Diraph Digraph type.
-/// \param _CapacityMap Type of capacity map.
+/// \tparam _LCapMap Lower bound capacity map type.
-template <typename _Graph, typename _LCapMap,
+/// \tparam _UCapMap Upper bound capacity map type.
+/// \tparam _DeltaMap Delta map type.
+template <typename _Diraph, typename _LCapMap,
 typename _UCapMap, typename _DeltaMap>
 struct CirculationDefaultTraits {
-/// \brief The digraph type the algorithm runs on.
+/// \brief The type of the digraph the algorithm runs on.
-typedef _Graph Digraph;
+typedef _Diraph Digraph;
 /// \brief The type of the map that stores the circulation lower
 /// bound.
 ///
 /// The type of the map that stores the circulation lower bound.
 ///
 /// The type of the map that stores the circulation upper bound.
 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 typedef _UCapMap UCapMap;
-/// \brief The type of the map that stores the upper bound of
+/// \brief The type of the map that stores the lower bound for
-/// node excess.
+/// the supply of the nodes.
 ///
-/// The type of the map that stores the lower bound of node
+/// The type of the map that stores the lower bound for the supply
-/// excess. It must meet the \ref concepts::ReadMap "ReadMap"
+/// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
 /// concept.
 typedef _DeltaMap DeltaMap;
-/// \brief The type of the length of the arcs.
+/// \brief The type of the flow values.
 typedef typename DeltaMap::Value Value;
-/// \brief The map type that stores the flow values.
+/// \brief The type of the map that stores the flow values.
 ///
-/// The map type that stores the flow values.
+/// The type of the map that stores the flow values.
 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 typedef typename Digraph::template ArcMap<Value> FlowMap;
 /// \brief Instantiates a FlowMap.
 ///
 /// the flow map.
 static FlowMap* createFlowMap(const Digraph& digraph) {
 return new FlowMap(digraph);
 }
-/// \brief The eleavator type used by Circulation algorithm.
+/// \brief The elevator type used by the algorithm.
 ///
-/// The elevator type used by Circulation algorithm.
+/// The elevator type used by the algorithm.
 ///
 /// \sa Elevator
 /// \sa LinkedElevator
 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 /// \brief Instantiates an Elevator.
 ///
-/// This function instantiates a \ref Elevator.
+/// This function instantiates an \ref Elevator.
 /// \param digraph The digraph, to which we would like to define
 /// the elevator.
 /// \param max_level The maximum level of the elevator.
 static Elevator* createElevator(const Digraph& digraph, int max_level) {
 return new Elevator(digraph, max_level);
 /// The tolerance used by the algorithm to handle inexact computation.
 typedef lemon::Tolerance<Value> Tolerance;
 };
-///Push-relabel algorithm for the Network Circulation Problem.
 /**
+\brief Push-relabel algorithm for the network circulation problem.
 \ingroup max_flow
-This class implements a push-relabel algorithm
+This class implements a push-relabel algorithm for the network
-or the Network Circulation Problem.
+circulation problem.
+It is to find a feasible circulation when lower and upper bounds
+are given for the flow values on the arcs and lower bounds
+are given for the supply values of the nodes.
 The exact formulation of this problem is the following.
-\f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq
+Let \f$G=(V,A)\f$ be a digraph,
--delta(v)\quad \forall v\in V \f]
+\f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
-\f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f]
+\f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
+\f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
+\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
+\geq delta(v) \quad \forall v\in V, \f]
+\f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
+\note \f$delta(v)\f$ specifies a lower bound for the supply of node
+\f$v\f$. It can be either positive or negative, however note that
+\f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
+have a feasible solution.
+\note A special case of this problem is when
+\f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
+will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
+Thus a feasible solution for the
+\ref min_cost_flow "minimum cost flow" problem can be calculated
+in this way.
+\tparam _Digraph The type of the digraph the algorithm runs on.
+\tparam _LCapMap The type of the lower bound capacity map. The default
+map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
+\tparam _UCapMap The type of the upper bound capacity map. The default
+map type is \c _LCapMap.
+\tparam _DeltaMap The type of the map that stores the lower bound
+for the supply of the nodes. The default map type is
+\c _Digraph::ArcMap<_UCapMap::Value>.
 */
-template<class _Graph,
+#ifdef DOXYGEN
-class _LCapMap=typename _Graph::template ArcMap<int>,
+template< typename _Digraph,
-class _UCapMap=_LCapMap,
+typename _LCapMap,
-class _DeltaMap=typename _Graph::template NodeMap<
+typename _UCapMap,
-typename _UCapMap::Value>,
+typename _DeltaMap,
-class _Traits=CirculationDefaultTraits<_Graph, _LCapMap,
+typename _Traits >
-_UCapMap, _DeltaMap> >
+#else
+template< typename _Digraph,
+typename _LCapMap = typename _Digraph::template ArcMap<int>,
+typename _UCapMap = _LCapMap,
+typename _DeltaMap = typename _Digraph::
+template NodeMap<typename _UCapMap::Value>,
+typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap,
+_UCapMap, _DeltaMap> >
+#endif
 class Circulation {
+public:
+///The \ref CirculationDefaultTraits "traits class" of the algorithm.
 typedef _Traits Traits;
+///The type of the digraph the algorithm runs on.
 typedef typename Traits::Digraph Digraph;
+///The type of the flow values.
+typedef typename Traits::Value Value;
+/// The type of the lower bound capacity map.
+typedef typename Traits::LCapMap LCapMap;
+/// The type of the upper bound capacity map.
+typedef typename Traits::UCapMap UCapMap;
+/// \brief The type of the map that stores the lower bound for
+/// the supply of the nodes.
+typedef typename Traits::DeltaMap DeltaMap;
+///The type of the flow map.
+typedef typename Traits::FlowMap FlowMap;
+///The type of the elevator.
+typedef typename Traits::Elevator Elevator;
+///The type of the tolerance.
+typedef typename Traits::Tolerance Tolerance;
+private:
 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
-typedef typename Traits::Value Value;
-typedef typename Traits::LCapMap LCapMap;
-typedef typename Traits::UCapMap UCapMap;
-typedef typename Traits::DeltaMap DeltaMap;
-typedef typename Traits::FlowMap FlowMap;
-typedef typename Traits::Elevator Elevator;
-typedef typename Traits::Tolerance Tolerance;
-typedef typename Digraph::template NodeMap<Value> ExcessMap;
 const Digraph &_g;
 int _node_num;
 const LCapMap *_lo;
 bool _local_flow;
 Elevator* _level;
 bool _local_level;
+typedef typename Digraph::template NodeMap<Value> ExcessMap;
 ExcessMap* _excess;
 Tolerance _tol;
 int _el;
 public:
 typedef Circulation Create;
-///\name Named template parameters
+///\name Named Template Parameters
 ///@{
 template <typename _FlowMap>
 struct SetFlowMapTraits : public Traits {
 /// \brief \ref named-templ-param "Named parameter" for setting
 /// FlowMap type
 ///
 /// \ref named-templ-param "Named parameter" for setting FlowMap
-/// type
+/// type.
 template <typename _FlowMap>
 struct SetFlowMap
 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 SetFlowMapTraits<_FlowMap> > {
 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 /// \brief \ref named-templ-param "Named parameter" for setting
 /// Elevator type
 ///
 /// \ref named-templ-param "Named parameter" for setting Elevator
-/// type
+/// type. If this named parameter is used, then an external
+/// elevator object must be passed to the algorithm using the
+/// \ref elevator(Elevator&) "elevator()" function before calling
+/// \ref run() or \ref init().
+/// \sa SetStandardElevator
 template <typename _Elevator>
 struct SetElevator
 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 SetElevatorTraits<_Elevator> > {
 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 return new Elevator(digraph, max_level);
 }
 };
 /// \brief \ref named-templ-param "Named parameter" for setting
-/// Elevator type
+/// Elevator type with automatic allocation
 ///
 /// \ref named-templ-param "Named parameter" for setting Elevator
-/// type. The Elevator should be standard constructor interface, ie.
+/// type with automatic allocation.
-/// the digraph and the maximum level should be passed to it.
+/// The Elevator should have standard constructor interface to be
+/// able to automatically created by the algorithm (i.e. the
+/// digraph and the maximum level should be passed to it).
+/// However an external elevator object could also be passed to the
+/// algorithm with the \ref elevator(Elevator&) "elevator()" function
+/// before calling \ref run() or \ref init().
+/// \sa SetElevator
 template <typename _Elevator>
 struct SetStandardElevator
 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 SetStandardElevatorTraits<_Elevator> > {
 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 /// The constructor of the class.
 /// \param g The digraph the algorithm runs on.
 /// \param lo The lower bound capacity of the arcs.
 /// \param up The upper bound capacity of the arcs.
-/// \param delta The lower bound on node excess.
+/// \param delta The lower bound for the supply of the nodes.
 Circulation(const Digraph &g,const LCapMap &lo,
 const UCapMap &up,const DeltaMap &delta)
 : _g(g), _node_num(),
 _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
 _level(0), _local_level(false), _excess(0), _el() {}
-/// Destrcutor.
+/// Destructor.
 ~Circulation() {
 destroyStructures();
 }
 private:
 void createStructures() {
 _node_num = _el = countNodes(_g);
 public:
 /// Sets the lower bound capacity map.
 /// Sets the lower bound capacity map.
-/// \return \c (*this)
+/// \return <tt>(*this)</tt>
 Circulation& lowerCapMap(const LCapMap& map) {
 _lo = &map;
 return *this;
 }
 /// Sets the upper bound capacity map.
 /// Sets the upper bound capacity map.
-/// \return \c (*this)
+/// \return <tt>(*this)</tt>
 Circulation& upperCapMap(const LCapMap& map) {
 _up = &map;
 return *this;
 }
-/// Sets the lower bound map on excess.
+/// Sets the lower bound map for the supply of the nodes.
-/// Sets the lower bound map on excess.
+/// Sets the lower bound map for the supply of the nodes.
-/// \return \c (*this)
+/// \return <tt>(*this)</tt>
 Circulation& deltaMap(const DeltaMap& map) {
 _delta = &map;
 return *this;
 }
+/// \brief Sets the flow map.
+///
 /// Sets the flow map.
+/// If you don't use this function before calling \ref run() or
-/// Sets the flow map.
+/// \ref init(), an instance will be allocated automatically.
-/// \return \c (*this)
+/// The destructor deallocates this automatically allocated map,
+/// of course.
+/// \return <tt>(*this)</tt>
 Circulation& flowMap(FlowMap& map) {
 if (_local_flow) {
 delete _flow;
 _local_flow = false;
 }
 _flow = &map;
 return *this;
 }
-/// Returns the flow map.
+/// \brief Sets the elevator used by algorithm.
+///
-/// \return The flow map.
+/// Sets the elevator used by algorithm.
-///
+/// If you don't use this function before calling \ref run() or
-const FlowMap& flowMap() {
+/// \ref init(), an instance will be allocated automatically.
-return *_flow;
+/// The destructor deallocates this automatically allocated elevator,
-}
+/// of course.
+/// \return <tt>(*this)</tt>
-/// Sets the elevator.
-/// Sets the elevator.
-/// \return \c (*this)
 Circulation& elevator(Elevator& elevator) {
 if (_local_level) {
 delete _level;
 _local_level = false;
 }
 _level = &elevator;
 return *this;
 }
-/// Returns the elevator.
+/// \brief Returns a const reference to the elevator.
+///
-/// \return The elevator.
+/// Returns a const reference to the elevator.
 ///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
 const Elevator& elevator() {
 return *_level;
 }
+/// \brief Sets the tolerance used by algorithm.
+///
 /// Sets the tolerance used by algorithm.
-/// Sets the tolerance used by algorithm.
-///
 Circulation& tolerance(const Tolerance& tolerance) const {
 _tol = tolerance;
 return *this;
 }
-/// Returns the tolerance used by algorithm.
+/// \brief Returns a const reference to the tolerance.
+///
-/// Returns the tolerance used by algorithm.
+/// Returns a const reference to the tolerance.
-///
 const Tolerance& tolerance() const {
 return tolerance;
 }
-/// \name Execution control
+/// \name Execution Control
-/// The simplest way to execute the algorithm is to use one of the
+/// The simplest way to execute the algorithm is to call \ref run().\n
-/// member functions called \c run().
+/// If you need more control on the initial solution or the execution,
-/// \n
+/// first you have to call one of the \ref init() functions, then
-/// If you need more control on initial solution or execution then
+/// the \ref start() function.
-/// you have to call one \ref init() function and then the start()
-/// function.
 ///@{
 /// Initializes the internal data structures.
-/// Initializes the internal data structures. This function sets
+/// Initializes the internal data structures and sets all flow values
-/// all flow values to the lower bound.
+/// to the lower bound.
-/// \return This function returns false if the initialization
-/// process found a barrier.
 void init()
 {
 createStructures();
 for(NodeIt n(_g);n!=INVALID;++n) {
 for(NodeIt n(_g);n!=INVALID;++n)
 if(_tol.positive((*_excess)[n]))
 _level->activate(n);
 }
-/// Initializes the internal data structures.
+/// Initializes the internal data structures using a greedy approach.
-/// Initializes the internal data structures. This functions uses
+/// Initializes the internal data structures using a greedy approach
-/// greedy approach to construct the initial solution.
+/// to construct the initial solution.
 void greedyInit()
 {
 createStructures();
 for(NodeIt n(_g);n!=INVALID;++n) {
 for(NodeIt n(_g);n!=INVALID;++n)
 if(_tol.positive((*_excess)[n]))
 _level->activate(n);
 }
-///Starts the algorithm
+///Executes the algorithm
-///This function starts the algorithm.
+///This function executes the algorithm.
-///\return This function returns true if it found a feasible circulation.
+///
+///\return \c true if a feasible circulation is found.
 ///
 ///\sa barrier()
+///\sa barrierMap()
 bool start()
 {
 Node act;
 Node bact=INVALID;
 ;
 }
 return true;
 }
-/// Runs the circulation algorithm.
+/// Runs the algorithm.
-/// Runs the circulation algorithm.
+/// This function runs the algorithm.
-/// \note fc.run() is just a shortcut of the following code.
+///
+/// \return \c true if a feasible circulation is found.
+///
+/// \note Apart from the return value, c.run() is just a shortcut of
+/// the following code.
 /// \code
-///   fc.greedyInit();
+///   c.greedyInit();
-///   return fc.start();
+///   c.start();
 /// \endcode
 bool run() {
 greedyInit();
 return start();
 }
 /// @}
 /// \name Query Functions
-/// The result of the %Circulation algorithm can be obtained using
+/// The results of the circulation algorithm can be obtained using
-/// these functions.
+/// these functions.\n
-/// \n
+/// Either \ref run() or \ref start() should be called before
-/// Before the use of these functions,
+/// using them.
-/// either run() or start() must be called.
 ///@{
+/// \brief Returns the flow on the given arc.
+///
+/// Returns the flow on the given arc.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
+Value flow(const Arc& arc) const {
+return (*_flow)[arc];
+}
+/// \brief Returns a const reference to the flow map.
+///
+/// Returns a const reference to the arc map storing the found flow.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
+const FlowMap& flowMap() {
+return *_flow;
+}
 /**
-\brief Returns a barrier
+\brief Returns \c true if the given node is in a barrier.
 Barrier is a set \e B of nodes for which
-\f[ \sum_{v\in B}-delta(v)<
-\sum_{e\in\rho(B)}lo(e)-\sum_{e\in\delta(B)}up(e) \f]
+\f[ \sum_{a\in\delta_{out}(B)} upper(a) -
-holds. The existence of a set with this property prooves that a feasible
+\sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
-flow cannot exists.
+holds. The existence of a set with this property prooves that a
+feasible circualtion cannot exist.
+This function returns \c true if the given node is in the found
+barrier. If a feasible circulation is found, the function
+gives back \c false for every node.
+\pre Either \ref run() or \ref init() must be called before
+using this function.
+\sa barrierMap()
 \sa checkBarrier()
-\sa run()
 */
-template<class GT>
+bool barrier(const Node& node)
-void barrierMap(GT &bar)
+{
+return (*_level)[node] >= _el;
+}
+/// \brief Gives back a barrier.
+///
+/// This function sets \c bar to the characteristic vector of the
+/// found barrier. \c bar should be a \ref concepts::WriteMap "writable"
+/// node map with \c bool (or convertible) value type.
+///
+/// If a feasible circulation is found, the function gives back an
+/// empty set, so \c bar[v] will be \c false for all nodes \c v.
+///
+/// \note This function calls \ref barrier() for each node,
+/// so it runs in \f$O(n)\f$ time.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
+///
+/// \sa barrier()
+/// \sa checkBarrier()
+template<class BarrierMap>
+void barrierMap(BarrierMap &bar)
 {
 for(NodeIt n(_g);n!=INVALID;++n)
 bar.set(n, (*_level)[n] >= _el);
 }
-///Returns true if the node is in the barrier
-///Returns true if the node is in the barrier
-///\sa barrierMap()
-bool barrier(const Node& node)
-{
-return (*_level)[node] >= _el;
-}
-/// \brief Returns the flow on the arc.
-///
-/// Sets the \c flowMap to the flow on the arcs. This method can
-/// be called after the second phase of algorithm.
-Value flow(const Arc& arc) const {
-return (*_flow)[arc];
-}
 /// @}
 /// \name Checker Functions
-/// The feasibility  of the results can be checked using
+/// The feasibility of the results can be checked using
-/// these functions.
+/// these functions.\n
-/// \n
+/// Either \ref run() or \ref start() should be called before
-/// Before the use of these functions,
+/// using them.
-/// either run() or start() must be called.
 ///@{
-///Check if the  \c flow is a feasible circulation
+///Check if the found flow is a feasible circulation
+///Check if the found flow is a feasible circulation,
+///
 bool checkFlow() {
 for(ArcIt e(_g);e!=INVALID;++e)
 if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
 for(NodeIt n(_g);n!=INVALID;++n)
 {
 return true;
 }
 ///Check whether or not the last execution provides a barrier
-///Check whether or not the last execution provides a barrier
+///Check whether or not the last execution provides a barrier.
 ///\sa barrier()
+///\sa barrierMap()
 bool checkBarrier()
 {
 Value delta=0;
 for(NodeIt n(_g);n!=INVALID;++n)
 if(barrier(n))

changeset 431	9dfaf6efc36f
parent 401	26fd85a3087e
child 420	6a2a33ad261b