# Changeset 657:dacc2cee2b4c in lemon for lemon/circulation.h

Ignore:
Timestamp:
04/17/09 18:14:35 (11 years ago)
Branch:
default
Phase:
public
Message:

Slightly modify the interface of Circulation and Preflow (#266)
in order to synchronize them to the interface of NetworkSimplex?.

Circulation:

• The "delta" notation is replaced by "supply".
• lowerCapMap(), upperCapMap() are renamed to lowerMap() and upperMap().
• Value is renamed to Flow.

Preflow:

• Value is renamed to Flow.
File:
1 edited

Unmodified
Removed
• ## lemon/circulation.h

 r525 /// /// 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 { typedef GR Digraph; /// \brief The type of the map that stores the circulation lower /// bound. /// /// The type of the map that stores the circulation lower bound. /// It must meet the \ref concepts::ReadMap "ReadMap" concept. typedef LM LCapMap; /// \brief The type of the map that stores the circulation upper /// bound. /// /// The type of the map that stores the circulation upper bound. /// It must meet the \ref concepts::ReadMap "ReadMap" concept. typedef UM UCapMap; /// \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 lower bound for the supply /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap" /// \brief The type of the lower bound map. /// /// 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 upper bound (capacity) map. /// /// 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 supply map. /// /// 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 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; /// \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 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) { /// /// 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. /// /// The tolerance used by the algorithm to handle inexact computation. typedef lemon::Tolerance Tolerance; typedef lemon::Tolerance Tolerance; }; \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. \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$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. \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". */ typename LM, typename UM, typename DM, typename SM, typename TR > #else 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 { 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; typedef typename Traits::Flow Flow; ///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; 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_level; typedef typename Digraph::template NodeMap ExcessMap; typedef typename Digraph::template NodeMap ExcessMap; ExcessMap* _excess; template struct SetFlowMap : public Circulation > { typedef Circulation > Create; }; template struct SetElevator : public Circulation > { typedef Circulation > Create; }; template struct SetStandardElevator : public Circulation > { typedef Circulation > Create; }; public: /// Constructor. /// The constructor of the class. /// 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. public: /// Sets the lower bound capacity map. /// Sets the lower bound capacity map. /// Sets the lower bound 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 lower bound map for the supply of the nodes. /// Sets the supply map. /// Sets the supply map. /// \return (*this) Circulation& deltaMap(const DeltaMap& map) { _delta = ↦ Circulation& supplyMap(const SupplyMap& map) { _supply = ↦ return *this; } for(NodeIt n(_g);n!=INVALID;++n) { _excess->set(n, (*_delta)[n]); _excess->set(n, (*_supply)[n]); } for(NodeIt n(_g);n!=INVALID;++n) { _excess->set(n, (*_delta)[n]); _excess->set(n, (*_supply)[n]); } _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); 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]
Note: See TracChangeset for help on using the changeset viewer.