lemon-main: comparison lemon/circulation.h

equal deleted inserted replaced

-:27531e6b14ad
+:6b2b32df34e3
 namespace lemon {
 /// \brief Default traits class of Circulation class.
 ///
 /// Default traits class of Circulation class.
-/// \tparam GR Digraph type.
+///
-/// \tparam LM Lower bound capacity map type.
+/// \tparam GR Type of the digraph the algorithm runs on.
-/// \tparam UM Upper bound capacity map type.
+/// \tparam LM The type of the lower bound map.
-/// \tparam DM Delta map type.
+/// \tparam UM The type of the upper bound (capacity) map.
+/// \tparam SM The type of the supply map.
 template <typename GR, typename LM,
-typename UM, typename DM>
+typename UM, typename SM>
 struct CirculationDefaultTraits {
 /// \brief The type of the digraph the algorithm runs on.
 typedef GR Digraph;
-/// \brief The type of the map that stores the circulation lower
+/// \brief The type of the lower bound map.
-/// bound.
+///
-///
+/// The type of the map that stores the lower bounds on the arcs.
-/// The type of the map that stores the circulation lower bound.
+/// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
-/// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+typedef LM LowerMap;
-typedef LM LCapMap;
+/// \brief The type of the upper bound (capacity) map.
-/// \brief The type of the map that stores the circulation upper
+///
-/// bound.
+/// The type of the map that stores the upper bounds (capacities)
-///
+/// on the arcs.
-/// The type of the map that stores the circulation upper bound.
+/// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
-/// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+typedef UM UpperMap;
-typedef UM UCapMap;
+/// \brief The type of supply map.
-/// \brief The type of the map that stores the lower bound for
+///
-/// the supply of the nodes.
+/// The type of the map that stores the signed supply values of the
-///
+/// nodes.
-/// The type of the map that stores the lower bound for the supply
+/// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
-/// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
+typedef SM SupplyMap;
+/// \brief The type of the flow values.
+typedef typename SupplyMap::Value Flow;
+/// \brief The type of the map that stores the flow values.
+///
+/// The type of the map that stores the flow values.
+/// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
 /// concept.
-typedef DM DeltaMap;
+typedef typename Digraph::template ArcMap<Flow> FlowMap;
-/// \brief The type of the flow values.
-typedef typename DeltaMap::Value Value;
-/// \brief The type of the map 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.
 ///
 /// This function instantiates a \ref FlowMap.
-/// \param digraph The digraph, to which we would like to define
+/// \param digraph The digraph for which we would like to define
 /// the flow map.
 static FlowMap* createFlowMap(const Digraph& digraph) {
 return new FlowMap(digraph);
 }
 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 /// \brief Instantiates an Elevator.
 ///
 /// This function instantiates an \ref Elevator.
-/// \param digraph The digraph, to which we would like to define
+/// \param digraph The digraph for 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);
 }
 /// \brief The tolerance used by the algorithm
 ///
 /// The tolerance used by the algorithm to handle inexact computation.
-typedef lemon::Tolerance<Value> Tolerance;
+typedef lemon::Tolerance<Flow> Tolerance;
 };
 /**
 \brief Push-relabel algorithm for the network circulation problem.
 \ingroup max_flow
-This class implements a push-relabel algorithm for the network
+This class implements a push-relabel algorithm for the \e network
-circulation problem.
+\e 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 flow values on the arcs and lower bounds are
-are given for the supply values of the nodes.
+given for the difference between the outgoing and incoming flow
+at the nodes.
 The exact formulation of this problem is the following.
 Let \f$G=(V,A)\f$ be a digraph,
-\f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
+\f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
-\f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
+upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
-\f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
+holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
-\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
+denotes the signed supply values of the nodes.
-\geq delta(v) \quad \forall v\in V, \f]
+If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
-\f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
+supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
-\note \f$delta(v)\f$ specifies a lower bound for the supply of node
+\f$-sup(u)\f$ demand.
-\f$v\f$. It can be either positive or negative, however note that
+A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
-\f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
+solution of the following problem.
-have a feasible solution.
+\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
-\note A special case of this problem is when
+\geq sup(u) \quad \forall u\in V, \f]
-\f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
+\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
-will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
-Thus a feasible solution for the
+The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
-\ref min_cost_flow "minimum cost flow" problem can be calculated
+zero or negative in order to have a feasible solution (since the sum
-in this way.
+of the expressions on the left-hand side of the inequalities is zero).
+It means that the total demand must be greater or equal to the total
+supply and all the supplies have to be carried out from the supply nodes,
+but there could be demands that are not satisfied.
+If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
+constraints have to be satisfied with equality, i.e. all demands
+have to be satisfied and all supplies have to be used.
+If you need the opposite inequalities in the supply/demand constraints
+(i.e. the total demand is less than the total supply and all the demands
+have to be satisfied while there could be supplies that are not used),
+then you could easily transform the problem to the above form by reversing
+the direction of the arcs and taking the negative of the supply values
+(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
+Note that this algorithm also provides a feasible solution for the
+\ref min_cost_flow "minimum cost flow problem".
 \tparam GR The type of the digraph the algorithm runs on.
-\tparam LM The type of the lower bound capacity map. The default
+\tparam LM The type of the lower bound map. The default
 map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
-\tparam UM The type of the upper bound capacity map. The default
+\tparam UM The type of the upper bound (capacity) map.
-map type is \c LM.
+The default map type is \c LM.
-\tparam DM The type of the map that stores the lower bound
+\tparam SM The type of the supply map. The default map type is
-for the supply of the nodes. The default map type is
 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
 */
 #ifdef DOXYGEN
 template< typename GR,
 typename LM,
 typename UM,
-typename DM,
+typename SM,
 typename TR >
 #else
 template< typename GR,
 typename LM = typename GR::template ArcMap<int>,
 typename UM = LM,
-typename DM = typename GR::template NodeMap<typename UM::Value>,
+typename SM = typename GR::template NodeMap<typename UM::Value>,
-typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
+typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
 #endif
 class Circulation {
 public:
 ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
 typedef TR 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;
+typedef typename Traits::Flow Flow;
-/// The type of the lower bound capacity map.
+///The type of the lower bound map.
-typedef typename Traits::LCapMap LCapMap;
+typedef typename Traits::LowerMap LowerMap;
-/// The type of the upper bound capacity map.
+///The type of the upper bound (capacity) map.
-typedef typename Traits::UCapMap UCapMap;
+typedef typename Traits::UpperMap UpperMap;
-/// \brief The type of the map that stores the lower bound for
+///The type of the supply map.
-/// the supply of the nodes.
+typedef typename Traits::SupplyMap SupplyMap;
-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;
 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 const Digraph &_g;
 int _node_num;
-const LCapMap *_lo;
+const LowerMap *_lo;
-const UCapMap *_up;
+const UpperMap *_up;
-const DeltaMap *_delta;
+const SupplyMap *_supply;
 FlowMap *_flow;
 bool _local_flow;
 Elevator* _level;
 bool _local_level;
-typedef typename Digraph::template NodeMap<Value> ExcessMap;
+typedef typename Digraph::template NodeMap<Flow> ExcessMap;
 ExcessMap* _excess;
 Tolerance _tol;
 int _el;
 ///
 /// \ref named-templ-param "Named parameter" for setting FlowMap
 /// type.
 template <typename T>
 struct SetFlowMap
-: public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+: public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 SetFlowMapTraits<T> > {
-typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 SetFlowMapTraits<T> > Create;
 };
 template <typename T>
 struct SetElevatorTraits : public Traits {
 /// \ref elevator(Elevator&) "elevator()" function before calling
 /// \ref run() or \ref init().
 /// \sa SetStandardElevator
 template <typename T>
 struct SetElevator
-: public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+: public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 SetElevatorTraits<T> > {
-typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 SetElevatorTraits<T> > Create;
 };
 template <typename T>
 struct SetStandardElevatorTraits : public Traits {
 /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 /// before calling \ref run() or \ref init().
 /// \sa SetElevator
 template <typename T>
 struct SetStandardElevator
-: public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+: public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 SetStandardElevatorTraits<T> > {
-typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 SetStandardElevatorTraits<T> > Create;
 };
 /// @}
 Circulation() {}
 public:
+/// Constructor.
 /// The constructor of the class.
+///
-/// The constructor of the class.
+/// \param graph The digraph the algorithm runs on.
-/// \param g The digraph the algorithm runs on.
+/// \param lower The lower bounds for the flow values on the arcs.
-/// \param lo The lower bound capacity of the arcs.
+/// \param upper The upper bounds (capacities) for the flow values
-/// \param up The upper bound capacity of the arcs.
+/// on the arcs.
-/// \param delta The lower bound for the supply of the nodes.
+/// \param supply The signed supply values of the nodes.
-Circulation(const Digraph &g,const LCapMap &lo,
+Circulation(const Digraph &graph, const LowerMap &lower,
-const UCapMap &up,const DeltaMap &delta)
+const UpperMap &upper, const SupplyMap &supply)
-: _g(g), _node_num(),
+: _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
-_lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
+_flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
-_level(0), _local_level(false), _excess(0), _el() {}
+_excess(NULL) {}
 /// Destructor.
 ~Circulation() {
 destroyStructures();
 }
 }
 }
 public:
-/// Sets the lower bound capacity map.
+/// Sets the lower bound map.
-/// Sets the lower bound capacity map.
+/// Sets the lower bound map.
 /// \return <tt>(*this)</tt>
-Circulation& lowerCapMap(const LCapMap& map) {
+Circulation& lowerMap(const LowerMap& map) {
 _lo = &map;
 return *this;
 }
-/// Sets the upper bound capacity map.
+/// Sets the upper bound (capacity) map.
-/// Sets the upper bound capacity map.
+/// Sets the upper bound (capacity) map.
 /// \return <tt>(*this)</tt>
-Circulation& upperCapMap(const LCapMap& map) {
+Circulation& upperMap(const LowerMap& map) {
 _up = &map;
 return *this;
 }
-/// Sets the lower bound map for the supply of the nodes.
+/// Sets the supply map.
-/// Sets the lower bound map for the supply of the nodes.
+/// Sets the supply map.
 /// \return <tt>(*this)</tt>
-Circulation& deltaMap(const DeltaMap& map) {
+Circulation& supplyMap(const SupplyMap& map) {
-_delta = &map;
+_supply = &map;
 return *this;
 }
 /// \brief Sets the flow map.
 ///
 void init()
 {
 createStructures();
 for(NodeIt n(_g);n!=INVALID;++n) {
-(*_excess)[n] = (*_delta)[n];
+(*_excess)[n] = (*_supply)[n];
 }
 for (ArcIt e(_g);e!=INVALID;++e) {
 _flow->set(e, (*_lo)[e]);
 (*_excess)[_g.target(e)] += (*_flow)[e];
 void greedyInit()
 {
 createStructures();
 for(NodeIt n(_g);n!=INVALID;++n) {
-(*_excess)[n] = (*_delta)[n];
+(*_excess)[n] = (*_supply)[n];
 }
 for (ArcIt e(_g);e!=INVALID;++e) {
 if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
 _flow->set(e, (*_up)[e]);
 } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
 _flow->set(e, (*_lo)[e]);
 (*_excess)[_g.target(e)] += (*_lo)[e];
 (*_excess)[_g.source(e)] -= (*_lo)[e];
 } else {
-Value fc = -(*_excess)[_g.target(e)];
+Flow fc = -(*_excess)[_g.target(e)];
 _flow->set(e, fc);
 (*_excess)[_g.target(e)] = 0;
 (*_excess)[_g.source(e)] -= fc;
 }
 }
 Node bact=INVALID;
 Node last_activated=INVALID;
 while((act=_level->highestActive())!=INVALID) {
 int actlevel=(*_level)[act];
 int mlevel=_node_num;
-Value exc=(*_excess)[act];
+Flow exc=(*_excess)[act];
 for(OutArcIt e(_g,act);e!=INVALID; ++e) {
 Node v = _g.target(e);
-Value fc=(*_up)[e]-(*_flow)[e];
+Flow fc=(*_up)[e]-(*_flow)[e];
 if(!_tol.positive(fc)) continue;
 if((*_level)[v]<actlevel) {
 if(!_tol.less(fc, exc)) {
 _flow->set(e, (*_flow)[e] + exc);
 (*_excess)[v] += exc;
 }
 else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
 }
 for(InArcIt e(_g,act);e!=INVALID; ++e) {
 Node v = _g.source(e);
-Value fc=(*_flow)[e]-(*_lo)[e];
+Flow fc=(*_flow)[e]-(*_lo)[e];
 if(!_tol.positive(fc)) continue;
 if((*_level)[v]<actlevel) {
 if(!_tol.less(fc, exc)) {
 _flow->set(e, (*_flow)[e] - exc);
 (*_excess)[v] += exc;
 ///
 /// 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 {
+Flow flow(const Arc& arc) const {
 return (*_flow)[arc];
 }
 /// \brief Returns a const reference to the flow map.
 ///
 /**
 \brief Returns \c true if the given node is in a barrier.
 Barrier is a set \e B of nodes for which
-\f[ \sum_{a\in\delta_{out}(B)} upper(a) -
+\f[ \sum_{uv\in A: u\in B} upper(uv) -
-\sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
+\sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
 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
 bool checkFlow() const {
 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)
 {
-Value dif=-(*_delta)[n];
+Flow dif=-(*_supply)[n];
 for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
 for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
 if(_tol.negative(dif)) return false;
 }
 return true;
 ///Check whether or not the last execution provides a barrier.
 ///\sa barrier()
 ///\sa barrierMap()
 bool checkBarrier() const
 {
-Value delta=0;
+Flow delta=0;
 for(NodeIt n(_g);n!=INVALID;++n)
 if(barrier(n))
-delta-=(*_delta)[n];
+delta-=(*_supply)[n];
 for(ArcIt e(_g);e!=INVALID;++e)
 {
 Node s=_g.source(e);
 Node t=_g.target(e);
 if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];

changeset 611	85cb3aa71cce
parent 581	aa1804409f29
parent 610	dacc2cee2b4c
child 622	28f58740b6f8