1.1 --- a/lemon/circulation.h Tue Apr 21 13:08:19 2009 +0100
1.2 +++ b/lemon/circulation.h Tue Apr 21 15:18:54 2009 +0100
1.3 @@ -31,52 +31,52 @@
1.4 /// \brief Default traits class of Circulation class.
1.5 ///
1.6 /// Default traits class of Circulation class.
1.7 - /// \tparam GR Digraph type.
1.8 - /// \tparam LM Lower bound capacity map type.
1.9 - /// \tparam UM Upper bound capacity map type.
1.10 - /// \tparam DM Delta map type.
1.11 + ///
1.12 + /// \tparam GR Type of the digraph the algorithm runs on.
1.13 + /// \tparam LM The type of the lower bound map.
1.14 + /// \tparam UM The type of the upper bound (capacity) map.
1.15 + /// \tparam SM The type of the supply map.
1.16 template <typename GR, typename LM,
1.17 - typename UM, typename DM>
1.18 + typename UM, typename SM>
1.19 struct CirculationDefaultTraits {
1.20
1.21 /// \brief The type of the digraph the algorithm runs on.
1.22 typedef GR Digraph;
1.23
1.24 - /// \brief The type of the map that stores the circulation lower
1.25 - /// bound.
1.26 + /// \brief The type of the lower bound map.
1.27 ///
1.28 - /// The type of the map that stores the circulation lower bound.
1.29 - /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.30 - typedef LM LCapMap;
1.31 + /// The type of the map that stores the lower bounds on the arcs.
1.32 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.33 + typedef LM LowerMap;
1.34
1.35 - /// \brief The type of the map that stores the circulation upper
1.36 - /// bound.
1.37 + /// \brief The type of the upper bound (capacity) map.
1.38 ///
1.39 - /// The type of the map that stores the circulation upper bound.
1.40 - /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.41 - typedef UM UCapMap;
1.42 + /// The type of the map that stores the upper bounds (capacities)
1.43 + /// on the arcs.
1.44 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.45 + typedef UM UpperMap;
1.46
1.47 - /// \brief The type of the map that stores the lower bound for
1.48 - /// the supply of the nodes.
1.49 + /// \brief The type of supply map.
1.50 ///
1.51 - /// The type of the map that stores the lower bound for the supply
1.52 - /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
1.53 - /// concept.
1.54 - typedef DM DeltaMap;
1.55 + /// The type of the map that stores the signed supply values of the
1.56 + /// nodes.
1.57 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.58 + typedef SM SupplyMap;
1.59
1.60 /// \brief The type of the flow values.
1.61 - typedef typename DeltaMap::Value Value;
1.62 + typedef typename SupplyMap::Value Flow;
1.63
1.64 /// \brief The type of the map that stores the flow values.
1.65 ///
1.66 /// The type of the map that stores the flow values.
1.67 - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.68 - typedef typename Digraph::template ArcMap<Value> FlowMap;
1.69 + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
1.70 + /// concept.
1.71 + typedef typename Digraph::template ArcMap<Flow> FlowMap;
1.72
1.73 /// \brief Instantiates a FlowMap.
1.74 ///
1.75 /// This function instantiates a \ref FlowMap.
1.76 - /// \param digraph The digraph, to which we would like to define
1.77 + /// \param digraph The digraph for which we would like to define
1.78 /// the flow map.
1.79 static FlowMap* createFlowMap(const Digraph& digraph) {
1.80 return new FlowMap(digraph);
1.81 @@ -93,7 +93,7 @@
1.82 /// \brief Instantiates an Elevator.
1.83 ///
1.84 /// This function instantiates an \ref Elevator.
1.85 - /// \param digraph The digraph, to which we would like to define
1.86 + /// \param digraph The digraph for which we would like to define
1.87 /// the elevator.
1.88 /// \param max_level The maximum level of the elevator.
1.89 static Elevator* createElevator(const Digraph& digraph, int max_level) {
1.90 @@ -103,7 +103,7 @@
1.91 /// \brief The tolerance used by the algorithm
1.92 ///
1.93 /// The tolerance used by the algorithm to handle inexact computation.
1.94 - typedef lemon::Tolerance<Value> Tolerance;
1.95 + typedef lemon::Tolerance<Flow> Tolerance;
1.96
1.97 };
1.98
1.99 @@ -111,53 +111,69 @@
1.100 \brief Push-relabel algorithm for the network circulation problem.
1.101
1.102 \ingroup max_flow
1.103 - This class implements a push-relabel algorithm for the network
1.104 - circulation problem.
1.105 + This class implements a push-relabel algorithm for the \e network
1.106 + \e circulation problem.
1.107 It is to find a feasible circulation when lower and upper bounds
1.108 - are given for the flow values on the arcs and lower bounds
1.109 - are given for the supply values of the nodes.
1.110 + are given for the flow values on the arcs and lower bounds are
1.111 + given for the difference between the outgoing and incoming flow
1.112 + at the nodes.
1.113
1.114 The exact formulation of this problem is the following.
1.115 Let \f$G=(V,A)\f$ be a digraph,
1.116 - \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
1.117 - \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
1.118 - \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
1.119 - \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
1.120 - \geq delta(v) \quad \forall v\in V, \f]
1.121 - \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
1.122 - \note \f$delta(v)\f$ specifies a lower bound for the supply of node
1.123 - \f$v\f$. It can be either positive or negative, however note that
1.124 - \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
1.125 - have a feasible solution.
1.126 + \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
1.127 + upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
1.128 + holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
1.129 + denotes the signed supply values of the nodes.
1.130 + If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
1.131 + supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
1.132 + \f$-sup(u)\f$ demand.
1.133 + A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
1.134 + solution of the following problem.
1.135
1.136 - \note A special case of this problem is when
1.137 - \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
1.138 - will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
1.139 - Thus a feasible solution for the
1.140 - \ref min_cost_flow "minimum cost flow" problem can be calculated
1.141 - in this way.
1.142 + \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
1.143 + \geq sup(u) \quad \forall u\in V, \f]
1.144 + \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
1.145 +
1.146 + The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
1.147 + zero or negative in order to have a feasible solution (since the sum
1.148 + of the expressions on the left-hand side of the inequalities is zero).
1.149 + It means that the total demand must be greater or equal to the total
1.150 + supply and all the supplies have to be carried out from the supply nodes,
1.151 + but there could be demands that are not satisfied.
1.152 + If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
1.153 + constraints have to be satisfied with equality, i.e. all demands
1.154 + have to be satisfied and all supplies have to be used.
1.155 +
1.156 + If you need the opposite inequalities in the supply/demand constraints
1.157 + (i.e. the total demand is less than the total supply and all the demands
1.158 + have to be satisfied while there could be supplies that are not used),
1.159 + then you could easily transform the problem to the above form by reversing
1.160 + the direction of the arcs and taking the negative of the supply values
1.161 + (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
1.162 +
1.163 + Note that this algorithm also provides a feasible solution for the
1.164 + \ref min_cost_flow "minimum cost flow problem".
1.165
1.166 \tparam GR The type of the digraph the algorithm runs on.
1.167 - \tparam LM The type of the lower bound capacity map. The default
1.168 + \tparam LM The type of the lower bound map. The default
1.169 map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.170 - \tparam UM The type of the upper bound capacity map. The default
1.171 - map type is \c LM.
1.172 - \tparam DM The type of the map that stores the lower bound
1.173 - for the supply of the nodes. The default map type is
1.174 + \tparam UM The type of the upper bound (capacity) map.
1.175 + The default map type is \c LM.
1.176 + \tparam SM The type of the supply map. The default map type is
1.177 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
1.178 */
1.179 #ifdef DOXYGEN
1.180 template< typename GR,
1.181 typename LM,
1.182 typename UM,
1.183 - typename DM,
1.184 + typename SM,
1.185 typename TR >
1.186 #else
1.187 template< typename GR,
1.188 typename LM = typename GR::template ArcMap<int>,
1.189 typename UM = LM,
1.190 - typename DM = typename GR::template NodeMap<typename UM::Value>,
1.191 - typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
1.192 + typename SM = typename GR::template NodeMap<typename UM::Value>,
1.193 + typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
1.194 #endif
1.195 class Circulation {
1.196 public:
1.197 @@ -167,15 +183,14 @@
1.198 ///The type of the digraph the algorithm runs on.
1.199 typedef typename Traits::Digraph Digraph;
1.200 ///The type of the flow values.
1.201 - typedef typename Traits::Value Value;
1.202 + typedef typename Traits::Flow Flow;
1.203
1.204 - /// The type of the lower bound capacity map.
1.205 - typedef typename Traits::LCapMap LCapMap;
1.206 - /// The type of the upper bound capacity map.
1.207 - typedef typename Traits::UCapMap UCapMap;
1.208 - /// \brief The type of the map that stores the lower bound for
1.209 - /// the supply of the nodes.
1.210 - typedef typename Traits::DeltaMap DeltaMap;
1.211 + ///The type of the lower bound map.
1.212 + typedef typename Traits::LowerMap LowerMap;
1.213 + ///The type of the upper bound (capacity) map.
1.214 + typedef typename Traits::UpperMap UpperMap;
1.215 + ///The type of the supply map.
1.216 + typedef typename Traits::SupplyMap SupplyMap;
1.217 ///The type of the flow map.
1.218 typedef typename Traits::FlowMap FlowMap;
1.219
1.220 @@ -191,9 +206,9 @@
1.221 const Digraph &_g;
1.222 int _node_num;
1.223
1.224 - const LCapMap *_lo;
1.225 - const UCapMap *_up;
1.226 - const DeltaMap *_delta;
1.227 + const LowerMap *_lo;
1.228 + const UpperMap *_up;
1.229 + const SupplyMap *_supply;
1.230
1.231 FlowMap *_flow;
1.232 bool _local_flow;
1.233 @@ -201,7 +216,7 @@
1.234 Elevator* _level;
1.235 bool _local_level;
1.236
1.237 - typedef typename Digraph::template NodeMap<Value> ExcessMap;
1.238 + typedef typename Digraph::template NodeMap<Flow> ExcessMap;
1.239 ExcessMap* _excess;
1.240
1.241 Tolerance _tol;
1.242 @@ -231,9 +246,9 @@
1.243 /// type.
1.244 template <typename T>
1.245 struct SetFlowMap
1.246 - : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.247 + : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.248 SetFlowMapTraits<T> > {
1.249 - typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.250 + typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.251 SetFlowMapTraits<T> > Create;
1.252 };
1.253
1.254 @@ -257,9 +272,9 @@
1.255 /// \sa SetStandardElevator
1.256 template <typename T>
1.257 struct SetElevator
1.258 - : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.259 + : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.260 SetElevatorTraits<T> > {
1.261 - typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.262 + typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.263 SetElevatorTraits<T> > Create;
1.264 };
1.265
1.266 @@ -285,9 +300,9 @@
1.267 /// \sa SetElevator
1.268 template <typename T>
1.269 struct SetStandardElevator
1.270 - : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.271 + : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.272 SetStandardElevatorTraits<T> > {
1.273 - typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.274 + typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.275 SetStandardElevatorTraits<T> > Create;
1.276 };
1.277
1.278 @@ -299,18 +314,20 @@
1.279
1.280 public:
1.281
1.282 - /// The constructor of the class.
1.283 + /// Constructor.
1.284
1.285 /// The constructor of the class.
1.286 - /// \param g The digraph the algorithm runs on.
1.287 - /// \param lo The lower bound capacity of the arcs.
1.288 - /// \param up The upper bound capacity of the arcs.
1.289 - /// \param delta The lower bound for the supply of the nodes.
1.290 - Circulation(const Digraph &g,const LCapMap &lo,
1.291 - const UCapMap &up,const DeltaMap &delta)
1.292 - : _g(g), _node_num(),
1.293 - _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
1.294 - _level(0), _local_level(false), _excess(0), _el() {}
1.295 + ///
1.296 + /// \param graph The digraph the algorithm runs on.
1.297 + /// \param lower The lower bounds for the flow values on the arcs.
1.298 + /// \param upper The upper bounds (capacities) for the flow values
1.299 + /// on the arcs.
1.300 + /// \param supply The signed supply values of the nodes.
1.301 + Circulation(const Digraph &graph, const LowerMap &lower,
1.302 + const UpperMap &upper, const SupplyMap &supply)
1.303 + : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
1.304 + _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
1.305 + _excess(NULL) {}
1.306
1.307 /// Destructor.
1.308 ~Circulation() {
1.309 @@ -350,30 +367,30 @@
1.310
1.311 public:
1.312
1.313 - /// Sets the lower bound capacity map.
1.314 + /// Sets the lower bound map.
1.315
1.316 - /// Sets the lower bound capacity map.
1.317 + /// Sets the lower bound map.
1.318 /// \return <tt>(*this)</tt>
1.319 - Circulation& lowerCapMap(const LCapMap& map) {
1.320 + Circulation& lowerMap(const LowerMap& map) {
1.321 _lo = ↦
1.322 return *this;
1.323 }
1.324
1.325 - /// Sets the upper bound capacity map.
1.326 + /// Sets the upper bound (capacity) map.
1.327
1.328 - /// Sets the upper bound capacity map.
1.329 + /// Sets the upper bound (capacity) map.
1.330 /// \return <tt>(*this)</tt>
1.331 - Circulation& upperCapMap(const LCapMap& map) {
1.332 + Circulation& upperMap(const LowerMap& map) {
1.333 _up = ↦
1.334 return *this;
1.335 }
1.336
1.337 - /// Sets the lower bound map for the supply of the nodes.
1.338 + /// Sets the supply map.
1.339
1.340 - /// Sets the lower bound map for the supply of the nodes.
1.341 + /// Sets the supply map.
1.342 /// \return <tt>(*this)</tt>
1.343 - Circulation& deltaMap(const DeltaMap& map) {
1.344 - _delta = ↦
1.345 + Circulation& supplyMap(const SupplyMap& map) {
1.346 + _supply = ↦
1.347 return *this;
1.348 }
1.349
1.350 @@ -453,7 +470,7 @@
1.351 createStructures();
1.352
1.353 for(NodeIt n(_g);n!=INVALID;++n) {
1.354 - (*_excess)[n] = (*_delta)[n];
1.355 + (*_excess)[n] = (*_supply)[n];
1.356 }
1.357
1.358 for (ArcIt e(_g);e!=INVALID;++e) {
1.359 @@ -482,7 +499,7 @@
1.360 createStructures();
1.361
1.362 for(NodeIt n(_g);n!=INVALID;++n) {
1.363 - (*_excess)[n] = (*_delta)[n];
1.364 + (*_excess)[n] = (*_supply)[n];
1.365 }
1.366
1.367 for (ArcIt e(_g);e!=INVALID;++e) {
1.368 @@ -495,7 +512,7 @@
1.369 (*_excess)[_g.target(e)] += (*_lo)[e];
1.370 (*_excess)[_g.source(e)] -= (*_lo)[e];
1.371 } else {
1.372 - Value fc = -(*_excess)[_g.target(e)];
1.373 + Flow fc = -(*_excess)[_g.target(e)];
1.374 _flow->set(e, fc);
1.375 (*_excess)[_g.target(e)] = 0;
1.376 (*_excess)[_g.source(e)] -= fc;
1.377 @@ -528,11 +545,11 @@
1.378 while((act=_level->highestActive())!=INVALID) {
1.379 int actlevel=(*_level)[act];
1.380 int mlevel=_node_num;
1.381 - Value exc=(*_excess)[act];
1.382 + Flow exc=(*_excess)[act];
1.383
1.384 for(OutArcIt e(_g,act);e!=INVALID; ++e) {
1.385 Node v = _g.target(e);
1.386 - Value fc=(*_up)[e]-(*_flow)[e];
1.387 + Flow fc=(*_up)[e]-(*_flow)[e];
1.388 if(!_tol.positive(fc)) continue;
1.389 if((*_level)[v]<actlevel) {
1.390 if(!_tol.less(fc, exc)) {
1.391 @@ -556,7 +573,7 @@
1.392 }
1.393 for(InArcIt e(_g,act);e!=INVALID; ++e) {
1.394 Node v = _g.source(e);
1.395 - Value fc=(*_flow)[e]-(*_lo)[e];
1.396 + Flow fc=(*_flow)[e]-(*_lo)[e];
1.397 if(!_tol.positive(fc)) continue;
1.398 if((*_level)[v]<actlevel) {
1.399 if(!_tol.less(fc, exc)) {
1.400 @@ -632,7 +649,7 @@
1.401 ///
1.402 /// \pre Either \ref run() or \ref init() must be called before
1.403 /// using this function.
1.404 - Value flow(const Arc& arc) const {
1.405 + Flow flow(const Arc& arc) const {
1.406 return (*_flow)[arc];
1.407 }
1.408
1.409 @@ -651,8 +668,8 @@
1.410
1.411 Barrier is a set \e B of nodes for which
1.412
1.413 - \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
1.414 - \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
1.415 + \f[ \sum_{uv\in A: u\in B} upper(uv) -
1.416 + \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
1.417
1.418 holds. The existence of a set with this property prooves that a
1.419 feasible circualtion cannot exist.
1.420 @@ -715,7 +732,7 @@
1.421 if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
1.422 for(NodeIt n(_g);n!=INVALID;++n)
1.423 {
1.424 - Value dif=-(*_delta)[n];
1.425 + Flow dif=-(*_supply)[n];
1.426 for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
1.427 for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
1.428 if(_tol.negative(dif)) return false;
1.429 @@ -730,10 +747,10 @@
1.430 ///\sa barrierMap()
1.431 bool checkBarrier() const
1.432 {
1.433 - Value delta=0;
1.434 + Flow delta=0;
1.435 for(NodeIt n(_g);n!=INVALID;++n)
1.436 if(barrier(n))
1.437 - delta-=(*_delta)[n];
1.438 + delta-=(*_supply)[n];
1.439 for(ArcIt e(_g);e!=INVALID;++e)
1.440 {
1.441 Node s=_g.source(e);