1.1 --- a/lemon/circulation.h Fri Apr 17 18:04:36 2009 +0200
1.2 +++ b/lemon/circulation.h Fri Apr 17 18:14:35 2009 +0200
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 _FlowMap>
1.245 struct SetFlowMap
1.246 - : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.247 + : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.248 SetFlowMapTraits<_FlowMap> > {
1.249 - typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.250 + typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.251 SetFlowMapTraits<_FlowMap> > Create;
1.252 };
1.253
1.254 @@ -257,9 +272,9 @@
1.255 /// \sa SetStandardElevator
1.256 template <typename _Elevator>
1.257 struct SetElevator
1.258 - : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.259 + : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.260 SetElevatorTraits<_Elevator> > {
1.261 - typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.262 + typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.263 SetElevatorTraits<_Elevator> > Create;
1.264 };
1.265
1.266 @@ -285,9 +300,9 @@
1.267 /// \sa SetElevator
1.268 template <typename _Elevator>
1.269 struct SetStandardElevator
1.270 - : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.271 + : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.272 SetStandardElevatorTraits<_Elevator> > {
1.273 - typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
1.274 + typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
1.275 SetStandardElevatorTraits<_Elevator> > 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->set(n, (*_delta)[n]);
1.355 + _excess->set(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->set(n, (*_delta)[n]);
1.364 + _excess->set(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->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
1.370 _excess->set(_g.source(e), (*_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->set(_g.target(e), 0);
1.376 _excess->set(_g.source(e), (*_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);
2.1 --- a/lemon/preflow.h Fri Apr 17 18:04:36 2009 +0200
2.2 +++ b/lemon/preflow.h Fri Apr 17 18:14:35 2009 +0200
2.3 @@ -46,18 +46,18 @@
2.4 typedef CM CapacityMap;
2.5
2.6 /// \brief The type of the flow values.
2.7 - typedef typename CapacityMap::Value Value;
2.8 + typedef typename CapacityMap::Value Flow;
2.9
2.10 /// \brief The type of the map that stores the flow values.
2.11 ///
2.12 /// The type of the map that stores the flow values.
2.13 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
2.14 - typedef typename Digraph::template ArcMap<Value> FlowMap;
2.15 + typedef typename Digraph::template ArcMap<Flow> FlowMap;
2.16
2.17 /// \brief Instantiates a FlowMap.
2.18 ///
2.19 /// This function instantiates a \ref FlowMap.
2.20 - /// \param digraph The digraph, to which we would like to define
2.21 + /// \param digraph The digraph for which we would like to define
2.22 /// the flow map.
2.23 static FlowMap* createFlowMap(const Digraph& digraph) {
2.24 return new FlowMap(digraph);
2.25 @@ -74,7 +74,7 @@
2.26 /// \brief Instantiates an Elevator.
2.27 ///
2.28 /// This function instantiates an \ref Elevator.
2.29 - /// \param digraph The digraph, to which we would like to define
2.30 + /// \param digraph The digraph for which we would like to define
2.31 /// the elevator.
2.32 /// \param max_level The maximum level of the elevator.
2.33 static Elevator* createElevator(const Digraph& digraph, int max_level) {
2.34 @@ -84,7 +84,7 @@
2.35 /// \brief The tolerance used by the algorithm
2.36 ///
2.37 /// The tolerance used by the algorithm to handle inexact computation.
2.38 - typedef lemon::Tolerance<Value> Tolerance;
2.39 + typedef lemon::Tolerance<Flow> Tolerance;
2.40
2.41 };
2.42
2.43 @@ -124,7 +124,7 @@
2.44 ///The type of the capacity map.
2.45 typedef typename Traits::CapacityMap CapacityMap;
2.46 ///The type of the flow values.
2.47 - typedef typename Traits::Value Value;
2.48 + typedef typename Traits::Flow Flow;
2.49
2.50 ///The type of the flow map.
2.51 typedef typename Traits::FlowMap FlowMap;
2.52 @@ -150,7 +150,7 @@
2.53 Elevator* _level;
2.54 bool _local_level;
2.55
2.56 - typedef typename Digraph::template NodeMap<Value> ExcessMap;
2.57 + typedef typename Digraph::template NodeMap<Flow> ExcessMap;
2.58 ExcessMap* _excess;
2.59
2.60 Tolerance _tolerance;
2.61 @@ -469,7 +469,7 @@
2.62 }
2.63
2.64 for (NodeIt n(_graph); n != INVALID; ++n) {
2.65 - Value excess = 0;
2.66 + Flow excess = 0;
2.67 for (InArcIt e(_graph, n); e != INVALID; ++e) {
2.68 excess += (*_flow)[e];
2.69 }
2.70 @@ -518,7 +518,7 @@
2.71 _level->initFinish();
2.72
2.73 for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
2.74 - Value rem = (*_capacity)[e] - (*_flow)[e];
2.75 + Flow rem = (*_capacity)[e] - (*_flow)[e];
2.76 if (_tolerance.positive(rem)) {
2.77 Node u = _graph.target(e);
2.78 if ((*_level)[u] == _level->maxLevel()) continue;
2.79 @@ -530,7 +530,7 @@
2.80 }
2.81 }
2.82 for (InArcIt e(_graph, _source); e != INVALID; ++e) {
2.83 - Value rem = (*_flow)[e];
2.84 + Flow rem = (*_flow)[e];
2.85 if (_tolerance.positive(rem)) {
2.86 Node v = _graph.source(e);
2.87 if ((*_level)[v] == _level->maxLevel()) continue;
2.88 @@ -563,11 +563,11 @@
2.89 int num = _node_num;
2.90
2.91 while (num > 0 && n != INVALID) {
2.92 - Value excess = (*_excess)[n];
2.93 + Flow excess = (*_excess)[n];
2.94 int new_level = _level->maxLevel();
2.95
2.96 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
2.97 - Value rem = (*_capacity)[e] - (*_flow)[e];
2.98 + Flow rem = (*_capacity)[e] - (*_flow)[e];
2.99 if (!_tolerance.positive(rem)) continue;
2.100 Node v = _graph.target(e);
2.101 if ((*_level)[v] < level) {
2.102 @@ -590,7 +590,7 @@
2.103 }
2.104
2.105 for (InArcIt e(_graph, n); e != INVALID; ++e) {
2.106 - Value rem = (*_flow)[e];
2.107 + Flow rem = (*_flow)[e];
2.108 if (!_tolerance.positive(rem)) continue;
2.109 Node v = _graph.source(e);
2.110 if ((*_level)[v] < level) {
2.111 @@ -636,11 +636,11 @@
2.112
2.113 num = _node_num * 20;
2.114 while (num > 0 && n != INVALID) {
2.115 - Value excess = (*_excess)[n];
2.116 + Flow excess = (*_excess)[n];
2.117 int new_level = _level->maxLevel();
2.118
2.119 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
2.120 - Value rem = (*_capacity)[e] - (*_flow)[e];
2.121 + Flow rem = (*_capacity)[e] - (*_flow)[e];
2.122 if (!_tolerance.positive(rem)) continue;
2.123 Node v = _graph.target(e);
2.124 if ((*_level)[v] < level) {
2.125 @@ -663,7 +663,7 @@
2.126 }
2.127
2.128 for (InArcIt e(_graph, n); e != INVALID; ++e) {
2.129 - Value rem = (*_flow)[e];
2.130 + Flow rem = (*_flow)[e];
2.131 if (!_tolerance.positive(rem)) continue;
2.132 Node v = _graph.source(e);
2.133 if ((*_level)[v] < level) {
2.134 @@ -777,12 +777,12 @@
2.135
2.136 Node n;
2.137 while ((n = _level->highestActive()) != INVALID) {
2.138 - Value excess = (*_excess)[n];
2.139 + Flow excess = (*_excess)[n];
2.140 int level = _level->highestActiveLevel();
2.141 int new_level = _level->maxLevel();
2.142
2.143 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
2.144 - Value rem = (*_capacity)[e] - (*_flow)[e];
2.145 + Flow rem = (*_capacity)[e] - (*_flow)[e];
2.146 if (!_tolerance.positive(rem)) continue;
2.147 Node v = _graph.target(e);
2.148 if ((*_level)[v] < level) {
2.149 @@ -805,7 +805,7 @@
2.150 }
2.151
2.152 for (InArcIt e(_graph, n); e != INVALID; ++e) {
2.153 - Value rem = (*_flow)[e];
2.154 + Flow rem = (*_flow)[e];
2.155 if (!_tolerance.positive(rem)) continue;
2.156 Node v = _graph.source(e);
2.157 if ((*_level)[v] < level) {
2.158 @@ -896,7 +896,7 @@
2.159 ///
2.160 /// \pre Either \ref run() or \ref init() must be called before
2.161 /// using this function.
2.162 - Value flowValue() const {
2.163 + Flow flowValue() const {
2.164 return (*_excess)[_target];
2.165 }
2.166
2.167 @@ -907,7 +907,7 @@
2.168 ///
2.169 /// \pre Either \ref run() or \ref init() must be called before
2.170 /// using this function.
2.171 - Value flow(const Arc& arc) const {
2.172 + Flow flow(const Arc& arc) const {
2.173 return (*_flow)[arc];
2.174 }
2.175
3.1 --- a/test/circulation_test.cc Fri Apr 17 18:04:36 2009 +0200
3.2 +++ b/test/circulation_test.cc Fri Apr 17 18:14:35 2009 +0200
3.3 @@ -57,7 +57,7 @@
3.4 typedef Digraph::Node Node;
3.5 typedef Digraph::Arc Arc;
3.6 typedef concepts::ReadMap<Arc,VType> CapMap;
3.7 - typedef concepts::ReadMap<Node,VType> DeltaMap;
3.8 + typedef concepts::ReadMap<Node,VType> SupplyMap;
3.9 typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
3.10 typedef concepts::WriteMap<Node,bool> BarrierMap;
3.11
3.12 @@ -68,19 +68,19 @@
3.13 Node n;
3.14 Arc a;
3.15 CapMap lcap, ucap;
3.16 - DeltaMap delta;
3.17 + SupplyMap supply;
3.18 FlowMap flow;
3.19 BarrierMap bar;
3.20
3.21 - Circulation<Digraph, CapMap, CapMap, DeltaMap>
3.22 + Circulation<Digraph, CapMap, CapMap, SupplyMap>
3.23 ::SetFlowMap<FlowMap>
3.24 ::SetElevator<Elev>
3.25 ::SetStandardElevator<LinkedElev>
3.26 - ::Create circ_test(g,lcap,ucap,delta);
3.27 + ::Create circ_test(g,lcap,ucap,supply);
3.28
3.29 - circ_test.lowerCapMap(lcap);
3.30 - circ_test.upperCapMap(ucap);
3.31 - circ_test.deltaMap(delta);
3.32 + circ_test.lowerMap(lcap);
3.33 + circ_test.upperMap(ucap);
3.34 + circ_test.supplyMap(supply);
3.35 flow = circ_test.flowMap();
3.36 circ_test.flowMap(flow);
3.37