# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1239984875 -7200
# Node ID dacc2cee2b4c4ec7481d3edec47aaf834b5db47c
# Parent e6927fe719e6e2cc97345c5f89f1cb0d66d2d0c9
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.
diff -r e6927fe719e6 -r dacc2cee2b4c lemon/circulation.h
--- a/lemon/circulation.h Fri Apr 17 18:04:36 2009 +0200
+++ b/lemon/circulation.h Fri Apr 17 18:14:35 2009 +0200
@@ -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 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
- /// 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<Value> FlowMap;
+ /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
+ /// concept.
+ typedef typename Digraph::template ArcMap<Flow> 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<Value> Tolerance;
+ typedef lemon::Tolerance<Flow> 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<int>".
- \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<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 TR = CirculationDefaultTraits<GR, LM, UM, DM> >
+ typename SM = typename GR::template NodeMap<typename UM::Value>,
+ typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
#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<Value> ExcessMap;
+ typedef typename Digraph::template NodeMap<Flow> ExcessMap;
ExcessMap* _excess;
Tolerance _tol;
@@ -231,9 +246,9 @@
/// type.
template <typename _FlowMap>
struct SetFlowMap
- : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+ : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
SetFlowMapTraits<_FlowMap> > {
- typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+ typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
SetFlowMapTraits<_FlowMap> > Create;
};
@@ -257,9 +272,9 @@
/// \sa SetStandardElevator
template <typename _Elevator>
struct SetElevator
- : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+ : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
SetElevatorTraits<_Elevator> > {
- typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+ typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
SetElevatorTraits<_Elevator> > Create;
};
@@ -285,9 +300,9 @@
/// \sa SetElevator
template <typename _Elevator>
struct SetStandardElevator
- : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+ : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
SetStandardElevatorTraits<_Elevator> > {
- typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+ typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
SetStandardElevatorTraits<_Elevator> > 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 <tt>(*this)</tt>
- 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 <tt>(*this)</tt>
- 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 <tt>(*this)</tt>
- 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]<actlevel) {
if(!_tol.less(fc, exc)) {
@@ -556,7 +573,7 @@
}
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)) {
@@ -632,7 +649,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];
}
@@ -651,8 +668,8 @@
Barrier is a set \e B of nodes for which
- \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
- \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
+ \f[ \sum_{uv\in A: u\in B} upper(uv) -
+ \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.
@@ -715,7 +732,7 @@
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;
@@ -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 -r e6927fe719e6 -r dacc2cee2b4c lemon/preflow.h
--- a/lemon/preflow.h Fri Apr 17 18:04:36 2009 +0200
+++ b/lemon/preflow.h Fri Apr 17 18:14:35 2009 +0200
@@ -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<Value> FlowMap;
+ typedef typename Digraph::template ArcMap<Flow> 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<Value> Tolerance;
+ typedef lemon::Tolerance<Flow> 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<Value> ExcessMap;
+ typedef typename Digraph::template NodeMap<Flow> 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 -r e6927fe719e6 -r dacc2cee2b4c test/circulation_test.cc
--- a/test/circulation_test.cc Fri Apr 17 18:04:36 2009 +0200
+++ b/test/circulation_test.cc Fri Apr 17 18:14:35 2009 +0200
@@ -57,7 +57,7 @@
typedef Digraph::Node Node;
typedef Digraph::Arc Arc;
typedef concepts::ReadMap<Arc,VType> CapMap;
- typedef concepts::ReadMap<Node,VType> DeltaMap;
+ typedef concepts::ReadMap<Node,VType> SupplyMap;
typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
typedef concepts::WriteMap<Node,bool> BarrierMap;
@@ -68,19 +68,19 @@
Node n;
Arc a;
CapMap lcap, ucap;
- DeltaMap delta;
+ SupplyMap supply;
FlowMap flow;
BarrierMap bar;
- Circulation<Digraph, CapMap, CapMap, DeltaMap>
+ Circulation<Digraph, CapMap, CapMap, SupplyMap>
::SetFlowMap<FlowMap>
::SetElevator<Elev>
::SetStandardElevator<LinkedElev>
- ::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);