diff --git a/lemon/circulation.h b/lemon/circulation.h --- a/lemon/circulation.h +++ b/lemon/circulation.h @@ -31,52 +31,52 @@ /// \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 UM Upper bound capacity map type. - /// \tparam DM Delta map type. + /// + /// \tparam GR Type of the digraph the algorithm runs on. + /// \tparam LM The type of the lower bound map. + /// \tparam UM The type of the upper bound (capacity) map. + /// \tparam SM The type of the supply map. template + 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 - /// bound. + /// \brief The type of the lower bound map. /// - /// The type of the map that stores the circulation lower bound. - /// It must meet the \ref concepts::ReadMap "ReadMap" concept. - typedef LM LCapMap; + /// The type of the map that stores the lower bounds on the arcs. + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. + typedef LM LowerMap; - /// \brief The type of the map that stores the circulation upper - /// bound. + /// \brief The type of the upper bound (capacity) map. /// - /// The type of the map that stores the circulation upper bound. - /// It must meet the \ref concepts::ReadMap "ReadMap" concept. - typedef UM UCapMap; + /// The type of the map that stores the upper bounds (capacities) + /// on the arcs. + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. + typedef UM UpperMap; - /// \brief The type of the map that stores the lower bound for - /// the supply of the nodes. + /// \brief The type of supply map. /// - /// The type of the map that stores the lower bound for the supply - /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap" - /// concept. - typedef DM DeltaMap; + /// The type of the map that stores the signed supply values of the + /// nodes. + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. + typedef SM SupplyMap; /// \brief The type of the flow values. - typedef typename DeltaMap::Value Value; + 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 meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. - typedef typename Digraph::template ArcMap FlowMap; + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" + /// concept. + typedef typename Digraph::template ArcMap 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); @@ -93,7 +93,7 @@ /// \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) { @@ -103,7 +103,7 @@ /// \brief The tolerance used by the algorithm /// /// The tolerance used by the algorithm to handle inexact computation. - typedef lemon::Tolerance Tolerance; + typedef lemon::Tolerance Tolerance; }; @@ -111,53 +111,69 @@ \brief Push-relabel algorithm for the network circulation problem. \ingroup max_flow - This class implements a push-relabel algorithm for the network - circulation problem. + This class implements a push-relabel algorithm for the \e network + \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 supply values of the nodes. + are given for the flow values on the arcs and lower bounds are + 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$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. + \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and + upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$ + holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$ + denotes the signed supply values of the nodes. + If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ + supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with + \f$-sup(u)\f$ demand. + A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ + solution of the following problem. - \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. + \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) + \geq sup(u) \quad \forall u\in V, \f] + \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f] + + The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be + zero or negative in order to have a feasible solution (since the sum + 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". - \tparam UM The type of the upper bound capacity map. The default - map type is \c LM. - \tparam DM The type of the map that stores the lower bound - for the supply of the nodes. The default map type is + \tparam UM The type of the upper bound (capacity) map. + The default map type is \c LM. + \tparam SM The type of the supply map. The default map type is \ref concepts::Digraph::NodeMap "GR::NodeMap". */ #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, typename UM = LM, - typename DM = typename GR::template NodeMap, - typename TR = CirculationDefaultTraits > + typename SM = typename GR::template NodeMap, + typename TR = CirculationDefaultTraits > #endif class Circulation { public: @@ -167,15 +183,14 @@ ///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. - 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 lower bound map. + typedef typename Traits::LowerMap LowerMap; + ///The type of the upper bound (capacity) map. + typedef typename Traits::UpperMap UpperMap; + ///The type of the supply map. + typedef typename Traits::SupplyMap SupplyMap; ///The type of the flow map. typedef typename Traits::FlowMap FlowMap; @@ -191,9 +206,9 @@ const Digraph &_g; int _node_num; - const LCapMap *_lo; - const UCapMap *_up; - const DeltaMap *_delta; + const LowerMap *_lo; + const UpperMap *_up; + const SupplyMap *_supply; FlowMap *_flow; bool _local_flow; @@ -201,7 +216,7 @@ Elevator* _level; bool _local_level; - typedef typename Digraph::template NodeMap ExcessMap; + typedef typename Digraph::template NodeMap ExcessMap; ExcessMap* _excess; Tolerance _tol; @@ -231,9 +246,9 @@ /// type. template struct SetFlowMap - : public Circulation > { - typedef Circulation > Create; }; @@ -257,9 +272,9 @@ /// \sa SetStandardElevator template struct SetElevator - : public Circulation > { - typedef Circulation > Create; }; @@ -285,9 +300,9 @@ /// \sa SetElevator template struct SetStandardElevator - : public Circulation > { - typedef Circulation > Create; }; @@ -299,18 +314,20 @@ public: - /// The constructor of the class. + /// Constructor. /// 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 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() {} + /// + /// \param graph The digraph the algorithm runs on. + /// \param lower The lower bounds for the flow values on the arcs. + /// \param upper The upper bounds (capacities) for the flow values + /// on the arcs. + /// \param supply The signed supply values of the nodes. + Circulation(const Digraph &graph, const LowerMap &lower, + const UpperMap &upper, const SupplyMap &supply) + : _g(graph), _lo(&lower), _up(&upper), _supply(&supply), + _flow(NULL), _local_flow(false), _level(NULL), _local_level(false), + _excess(NULL) {} /// Destructor. ~Circulation() { @@ -350,30 +367,30 @@ public: - /// Sets the lower bound capacity map. + /// Sets the lower bound map. - /// Sets the lower bound capacity map. + /// Sets the lower bound map. /// \return (*this) - Circulation& lowerCapMap(const LCapMap& map) { + Circulation& lowerMap(const LowerMap& map) { _lo = ↦ 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 (*this) - Circulation& upperCapMap(const LCapMap& map) { + Circulation& upperMap(const LowerMap& map) { _up = ↦ 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 (*this) - Circulation& deltaMap(const DeltaMap& map) { - _delta = ↦ + Circulation& supplyMap(const SupplyMap& map) { + _supply = ↦ return *this; } @@ -453,7 +470,7 @@ createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { - _excess->set(n, (*_delta)[n]); + _excess->set(n, (*_supply)[n]); } for (ArcIt e(_g);e!=INVALID;++e) { @@ -482,7 +499,7 @@ createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { - _excess->set(n, (*_delta)[n]); + _excess->set(n, (*_supply)[n]); } for (ArcIt e(_g);e!=INVALID;++e) { @@ -495,7 +512,7 @@ _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]); _excess->set(_g.source(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->set(_g.target(e), 0); _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc); @@ -528,11 +545,11 @@ 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](*_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; @@ -730,10 +747,10 @@ ///\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); diff --git a/lemon/preflow.h b/lemon/preflow.h --- a/lemon/preflow.h +++ b/lemon/preflow.h @@ -46,18 +46,18 @@ typedef CM CapacityMap; /// \brief The type of the flow values. - typedef typename CapacityMap::Value Value; + typedef typename CapacityMap::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 meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. - typedef typename Digraph::template ArcMap FlowMap; + typedef typename Digraph::template ArcMap 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); @@ -74,7 +74,7 @@ /// \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) { @@ -84,7 +84,7 @@ /// \brief The tolerance used by the algorithm /// /// The tolerance used by the algorithm to handle inexact computation. - typedef lemon::Tolerance Tolerance; + typedef lemon::Tolerance Tolerance; }; @@ -124,7 +124,7 @@ ///The type of the capacity map. typedef typename Traits::CapacityMap CapacityMap; ///The type of the flow values. - typedef typename Traits::Value Value; + typedef typename Traits::Flow Flow; ///The type of the flow map. typedef typename Traits::FlowMap FlowMap; @@ -150,7 +150,7 @@ Elevator* _level; bool _local_level; - typedef typename Digraph::template NodeMap ExcessMap; + typedef typename Digraph::template NodeMap ExcessMap; ExcessMap* _excess; Tolerance _tolerance; @@ -469,7 +469,7 @@ } for (NodeIt n(_graph); n != INVALID; ++n) { - Value excess = 0; + Flow excess = 0; for (InArcIt e(_graph, n); e != INVALID; ++e) { excess += (*_flow)[e]; } @@ -518,7 +518,7 @@ _level->initFinish(); for (OutArcIt e(_graph, _source); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; + Flow rem = (*_capacity)[e] - (*_flow)[e]; if (_tolerance.positive(rem)) { Node u = _graph.target(e); if ((*_level)[u] == _level->maxLevel()) continue; @@ -530,7 +530,7 @@ } } for (InArcIt e(_graph, _source); e != INVALID; ++e) { - Value rem = (*_flow)[e]; + Flow rem = (*_flow)[e]; if (_tolerance.positive(rem)) { Node v = _graph.source(e); if ((*_level)[v] == _level->maxLevel()) continue; @@ -563,11 +563,11 @@ int num = _node_num; while (num > 0 && n != INVALID) { - Value excess = (*_excess)[n]; + Flow excess = (*_excess)[n]; int new_level = _level->maxLevel(); for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; + Flow rem = (*_capacity)[e] - (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.target(e); if ((*_level)[v] < level) { @@ -590,7 +590,7 @@ } for (InArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_flow)[e]; + Flow rem = (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.source(e); if ((*_level)[v] < level) { @@ -636,11 +636,11 @@ num = _node_num * 20; while (num > 0 && n != INVALID) { - Value excess = (*_excess)[n]; + Flow excess = (*_excess)[n]; int new_level = _level->maxLevel(); for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; + Flow rem = (*_capacity)[e] - (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.target(e); if ((*_level)[v] < level) { @@ -663,7 +663,7 @@ } for (InArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_flow)[e]; + Flow rem = (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.source(e); if ((*_level)[v] < level) { @@ -777,12 +777,12 @@ Node n; while ((n = _level->highestActive()) != INVALID) { - Value excess = (*_excess)[n]; + Flow excess = (*_excess)[n]; int level = _level->highestActiveLevel(); int new_level = _level->maxLevel(); for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; + Flow rem = (*_capacity)[e] - (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.target(e); if ((*_level)[v] < level) { @@ -805,7 +805,7 @@ } for (InArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_flow)[e]; + Flow rem = (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.source(e); if ((*_level)[v] < level) { @@ -896,7 +896,7 @@ /// /// \pre Either \ref run() or \ref init() must be called before /// using this function. - Value flowValue() const { + Flow flowValue() const { return (*_excess)[_target]; } @@ -907,7 +907,7 @@ /// /// \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]; } diff --git a/test/circulation_test.cc b/test/circulation_test.cc --- a/test/circulation_test.cc +++ b/test/circulation_test.cc @@ -57,7 +57,7 @@ typedef Digraph::Node Node; typedef Digraph::Arc Arc; typedef concepts::ReadMap CapMap; - typedef concepts::ReadMap DeltaMap; + typedef concepts::ReadMap SupplyMap; typedef concepts::ReadWriteMap FlowMap; typedef concepts::WriteMap BarrierMap; @@ -68,19 +68,19 @@ Node n; Arc a; CapMap lcap, ucap; - DeltaMap delta; + SupplyMap supply; FlowMap flow; BarrierMap bar; - Circulation + Circulation ::SetFlowMap ::SetElevator ::SetStandardElevator - ::Create circ_test(g,lcap,ucap,delta); + ::Create circ_test(g,lcap,ucap,supply); - circ_test.lowerCapMap(lcap); - circ_test.upperCapMap(ucap); - circ_test.deltaMap(delta); + circ_test.lowerMap(lcap); + circ_test.upperMap(ucap); + circ_test.supplyMap(supply); flow = circ_test.flowMap(); circ_test.flowMap(flow);