# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1241007951 -7200
# Node ID 756a5ec551c8ac56edf0c4bca1eb28a4da300b71
# Parent 6c408d864fa1066df1ba3f323b9396d940c9cc19
Rename Flow to Value in the flow algorithms (#266)
We agreed that using Flow for the value type is misleading, since
a flow should be rather a function on the arcs, not a single value.
This patch reverts the changes of [dacc2cee2b4c] for Preflow and
Circulation.
diff -r 6c408d864fa1 -r 756a5ec551c8 lemon/circulation.h
--- a/lemon/circulation.h Wed Apr 29 03:15:24 2009 +0200
+++ b/lemon/circulation.h Wed Apr 29 14:25:51 2009 +0200
@@ -64,15 +64,15 @@
/// 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 flow and supply values.
+ typedef typename SupplyMap::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 conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
/// concept.
- typedef typename Digraph::template ArcMap<Flow> FlowMap;
+ typedef typename Digraph::template ArcMap<Value> FlowMap;
/// \brief Instantiates a FlowMap.
///
@@ -104,7 +104,7 @@
/// \brief The tolerance used by the algorithm
///
/// The tolerance used by the algorithm to handle inexact computation.
- typedef lemon::Tolerance<Flow> Tolerance;
+ typedef lemon::Tolerance<Value> Tolerance;
};
@@ -187,8 +187,8 @@
typedef TR Traits;
///The type of the digraph the algorithm runs on.
typedef typename Traits::Digraph Digraph;
- ///The type of the flow values.
- typedef typename Traits::Flow Flow;
+ ///The type of the flow and supply values.
+ typedef typename Traits::Value Value;
///The type of the lower bound map.
typedef typename Traits::LowerMap LowerMap;
@@ -221,7 +221,7 @@
Elevator* _level;
bool _local_level;
- typedef typename Digraph::template NodeMap<Flow> ExcessMap;
+ typedef typename Digraph::template NodeMap<Value> ExcessMap;
ExcessMap* _excess;
Tolerance _tol;
@@ -530,7 +530,7 @@
(*_excess)[_g.target(e)] += (*_lo)[e];
(*_excess)[_g.source(e)] -= (*_lo)[e];
} else {
- Flow fc = -(*_excess)[_g.target(e)];
+ Value fc = -(*_excess)[_g.target(e)];
_flow->set(e, fc);
(*_excess)[_g.target(e)] = 0;
(*_excess)[_g.source(e)] -= fc;
@@ -563,11 +563,11 @@
while((act=_level->highestActive())!=INVALID) {
int actlevel=(*_level)[act];
int mlevel=_node_num;
- Flow exc=(*_excess)[act];
+ Value exc=(*_excess)[act];
for(OutArcIt e(_g,act);e!=INVALID; ++e) {
Node v = _g.target(e);
- Flow fc=(*_up)[e]-(*_flow)[e];
+ Value fc=(*_up)[e]-(*_flow)[e];
if(!_tol.positive(fc)) continue;
if((*_level)[v]<actlevel) {
if(!_tol.less(fc, exc)) {
@@ -591,7 +591,7 @@
}
for(InArcIt e(_g,act);e!=INVALID; ++e) {
Node v = _g.source(e);
- Flow fc=(*_flow)[e]-(*_lo)[e];
+ Value fc=(*_flow)[e]-(*_lo)[e];
if(!_tol.positive(fc)) continue;
if((*_level)[v]<actlevel) {
if(!_tol.less(fc, exc)) {
@@ -661,13 +661,13 @@
///@{
- /// \brief Returns the flow on the given arc.
+ /// \brief Returns the flow value on the given arc.
///
- /// Returns the flow on the given arc.
+ /// Returns the flow value on the given arc.
///
/// \pre Either \ref run() or \ref init() must be called before
/// using this function.
- Flow flow(const Arc& arc) const {
+ Value flow(const Arc& arc) const {
return (*_flow)[arc];
}
@@ -750,7 +750,7 @@
if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
for(NodeIt n(_g);n!=INVALID;++n)
{
- Flow dif=-(*_supply)[n];
+ Value 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;
@@ -765,10 +765,10 @@
///\sa barrierMap()
bool checkBarrier() const
{
- Flow delta=0;
- Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
- std::numeric_limits<Flow>::infinity() :
- std::numeric_limits<Flow>::max();
+ Value delta=0;
+ Value inf_cap = std::numeric_limits<Value>::has_infinity ?
+ std::numeric_limits<Value>::infinity() :
+ std::numeric_limits<Value>::max();
for(NodeIt n(_g);n!=INVALID;++n)
if(barrier(n))
delta-=(*_supply)[n];
diff -r 6c408d864fa1 -r 756a5ec551c8 lemon/network_simplex.h
--- a/lemon/network_simplex.h Wed Apr 29 03:15:24 2009 +0200
+++ b/lemon/network_simplex.h Wed Apr 29 14:25:51 2009 +0200
@@ -56,10 +56,10 @@
/// specified, then default values will be used.
///
/// \tparam GR The digraph type the algorithm runs on.
- /// \tparam F The value type used for flow amounts, capacity bounds
+ /// \tparam V The value type used for flow amounts, capacity bounds
/// and supply values in the algorithm. By default it is \c int.
/// \tparam C The value type used for costs and potentials in the
- /// algorithm. By default it is the same as \c F.
+ /// algorithm. By default it is the same as \c V.
///
/// \warning Both value types must be signed and all input data must
/// be integer.
@@ -67,23 +67,23 @@
/// \note %NetworkSimplex provides five different pivot rule
/// implementations, from which the most efficient one is used
/// by default. For more information see \ref PivotRule.
- template <typename GR, typename F = int, typename C = F>
+ template <typename GR, typename V = int, typename C = V>
class NetworkSimplex
{
public:
/// The flow type of the algorithm
- typedef F Flow;
+ typedef V Value;
/// The cost type of the algorithm
typedef C Cost;
#ifdef DOXYGEN
/// The type of the flow map
- typedef GR::ArcMap<Flow> FlowMap;
+ typedef GR::ArcMap<Value> FlowMap;
/// The type of the potential map
typedef GR::NodeMap<Cost> PotentialMap;
#else
/// The type of the flow map
- typedef typename GR::template ArcMap<Flow> FlowMap;
+ typedef typename GR::template ArcMap<Value> FlowMap;
/// The type of the potential map
typedef typename GR::template NodeMap<Cost> PotentialMap;
#endif
@@ -206,15 +206,15 @@
TEMPLATE_DIGRAPH_TYPEDEFS(GR);
- typedef typename GR::template ArcMap<Flow> FlowArcMap;
+ typedef typename GR::template ArcMap<Value> ValueArcMap;
typedef typename GR::template ArcMap<Cost> CostArcMap;
- typedef typename GR::template NodeMap<Flow> FlowNodeMap;
+ typedef typename GR::template NodeMap<Value> ValueNodeMap;
typedef std::vector<Arc> ArcVector;
typedef std::vector<Node> NodeVector;
typedef std::vector<int> IntVector;
typedef std::vector<bool> BoolVector;
- typedef std::vector<Flow> FlowVector;
+ typedef std::vector<Value> FlowVector;
typedef std::vector<Cost> CostVector;
// State constants for arcs
@@ -232,16 +232,16 @@
int _arc_num;
// Parameters of the problem
- FlowArcMap *_plower;
- FlowArcMap *_pupper;
+ ValueArcMap *_plower;
+ ValueArcMap *_pupper;
CostArcMap *_pcost;
- FlowNodeMap *_psupply;
+ ValueNodeMap *_psupply;
bool _pstsup;
Node _psource, _ptarget;
- Flow _pstflow;
+ Value _pstflow;
SupplyType _stype;
- Flow _sum_supply;
+ Value _sum_supply;
// Result maps
FlowMap *_flow_map;
@@ -278,16 +278,16 @@
int in_arc, join, u_in, v_in, u_out, v_out;
int first, second, right, last;
int stem, par_stem, new_stem;
- Flow delta;
+ Value delta;
public:
/// \brief Constant for infinite upper bounds (capacities).
///
/// Constant for infinite upper bounds (capacities).
- /// It is \c std::numeric_limits<Flow>::infinity() if available,
- /// \c std::numeric_limits<Flow>::max() otherwise.
- const Flow INF;
+ /// It is \c std::numeric_limits<Value>::infinity() if available,
+ /// \c std::numeric_limits<Value>::max() otherwise.
+ const Value INF;
private:
@@ -695,12 +695,12 @@
_flow_map(NULL), _potential_map(NULL),
_local_flow(false), _local_potential(false),
_node_id(graph),
- INF(std::numeric_limits<Flow>::has_infinity ?
- std::numeric_limits<Flow>::infinity() :
- std::numeric_limits<Flow>::max())
+ INF(std::numeric_limits<Value>::has_infinity ?
+ std::numeric_limits<Value>::infinity() :
+ std::numeric_limits<Value>::max())
{
// Check the value types
- LEMON_ASSERT(std::numeric_limits<Flow>::is_signed,
+ LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
"The flow type of NetworkSimplex must be signed");
LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
"The cost type of NetworkSimplex must be signed");
@@ -725,14 +725,14 @@
/// will be set to zero on all arcs.
///
/// \param map An arc map storing the lower bounds.
- /// Its \c Value type must be convertible to the \c Flow type
+ /// Its \c Value type must be convertible to the \c Value type
/// of the algorithm.
///
/// \return <tt>(*this)</tt>
template <typename LowerMap>
NetworkSimplex& lowerMap(const LowerMap& map) {
delete _plower;
- _plower = new FlowArcMap(_graph);
+ _plower = new ValueArcMap(_graph);
for (ArcIt a(_graph); a != INVALID; ++a) {
(*_plower)[a] = map[a];
}
@@ -747,14 +747,14 @@
/// unbounded from above on each arc).
///
/// \param map An arc map storing the upper bounds.
- /// Its \c Value type must be convertible to the \c Flow type
+ /// Its \c Value type must be convertible to the \c Value type
/// of the algorithm.
///
/// \return <tt>(*this)</tt>
template<typename UpperMap>
NetworkSimplex& upperMap(const UpperMap& map) {
delete _pupper;
- _pupper = new FlowArcMap(_graph);
+ _pupper = new ValueArcMap(_graph);
for (ArcIt a(_graph); a != INVALID; ++a) {
(*_pupper)[a] = map[a];
}
@@ -790,7 +790,7 @@
/// (It makes sense only if non-zero lower bounds are given.)
///
/// \param map A node map storing the supply values.
- /// Its \c Value type must be convertible to the \c Flow type
+ /// Its \c Value type must be convertible to the \c Value type
/// of the algorithm.
///
/// \return <tt>(*this)</tt>
@@ -798,7 +798,7 @@
NetworkSimplex& supplyMap(const SupplyMap& map) {
delete _psupply;
_pstsup = false;
- _psupply = new FlowNodeMap(_graph);
+ _psupply = new ValueNodeMap(_graph);
for (NodeIt n(_graph); n != INVALID; ++n) {
(*_psupply)[n] = map[n];
}
@@ -823,7 +823,7 @@
/// (i.e. the supply of \c s and the demand of \c t).
///
/// \return <tt>(*this)</tt>
- NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
+ NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
delete _psupply;
_psupply = NULL;
_pstsup = true;
@@ -1025,7 +1025,7 @@
/// This function returns the flow on the given arc.
///
/// \pre \ref run() must be called before using this function.
- Flow flow(const Arc& a) const {
+ Value flow(const Arc& a) const {
return (*_flow_map)[a];
}
@@ -1204,7 +1204,7 @@
// Remove non-zero lower bounds
if (_plower) {
for (int i = 0; i != _arc_num; ++i) {
- Flow c = (*_plower)[_arc_ref[i]];
+ Value c = (*_plower)[_arc_ref[i]];
if (c > 0) {
if (_cap[i] < INF) _cap[i] -= c;
_supply[_source[i]] -= c;
@@ -1275,7 +1275,7 @@
}
delta = _cap[in_arc];
int result = 0;
- Flow d;
+ Value d;
int e;
// Search the cycle along the path form the first node to the root
@@ -1315,7 +1315,7 @@
void changeFlow(bool change) {
// Augment along the cycle
if (delta > 0) {
- Flow val = _state[in_arc] * delta;
+ Value val = _state[in_arc] * delta;
_flow[in_arc] += val;
for (int u = _source[in_arc]; u != join; u = _parent[u]) {
_flow[_pred[u]] += _forward[u] ? -val : val;
diff -r 6c408d864fa1 -r 756a5ec551c8 lemon/preflow.h
--- a/lemon/preflow.h Wed Apr 29 03:15:24 2009 +0200
+++ b/lemon/preflow.h Wed Apr 29 14:25:51 2009 +0200
@@ -46,13 +46,13 @@
typedef CAP CapacityMap;
/// \brief The type of the flow values.
- typedef typename CapacityMap::Value Flow;
+ typedef typename CapacityMap::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<Flow> FlowMap;
+ typedef typename Digraph::template ArcMap<Value> FlowMap;
/// \brief Instantiates a FlowMap.
///
@@ -84,7 +84,7 @@
/// \brief The tolerance used by the algorithm
///
/// The tolerance used by the algorithm to handle inexact computation.
- typedef lemon::Tolerance<Flow> Tolerance;
+ typedef lemon::Tolerance<Value> Tolerance;
};
@@ -125,7 +125,7 @@
///The type of the capacity map.
typedef typename Traits::CapacityMap CapacityMap;
///The type of the flow values.
- typedef typename Traits::Flow Flow;
+ typedef typename Traits::Value Value;
///The type of the flow map.
typedef typename Traits::FlowMap FlowMap;
@@ -151,7 +151,7 @@
Elevator* _level;
bool _local_level;
- typedef typename Digraph::template NodeMap<Flow> ExcessMap;
+ typedef typename Digraph::template NodeMap<Value> ExcessMap;
ExcessMap* _excess;
Tolerance _tolerance;
@@ -470,7 +470,7 @@
}
for (NodeIt n(_graph); n != INVALID; ++n) {
- Flow excess = 0;
+ Value excess = 0;
for (InArcIt e(_graph, n); e != INVALID; ++e) {
excess += (*_flow)[e];
}
@@ -519,7 +519,7 @@
_level->initFinish();
for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
- Flow rem = (*_capacity)[e] - (*_flow)[e];
+ Value rem = (*_capacity)[e] - (*_flow)[e];
if (_tolerance.positive(rem)) {
Node u = _graph.target(e);
if ((*_level)[u] == _level->maxLevel()) continue;
@@ -531,7 +531,7 @@
}
}
for (InArcIt e(_graph, _source); e != INVALID; ++e) {
- Flow rem = (*_flow)[e];
+ Value rem = (*_flow)[e];
if (_tolerance.positive(rem)) {
Node v = _graph.source(e);
if ((*_level)[v] == _level->maxLevel()) continue;
@@ -564,11 +564,11 @@
int num = _node_num;
while (num > 0 && n != INVALID) {
- Flow excess = (*_excess)[n];
+ Value excess = (*_excess)[n];
int new_level = _level->maxLevel();
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
- Flow rem = (*_capacity)[e] - (*_flow)[e];
+ Value rem = (*_capacity)[e] - (*_flow)[e];
if (!_tolerance.positive(rem)) continue;
Node v = _graph.target(e);
if ((*_level)[v] < level) {
@@ -591,7 +591,7 @@
}
for (InArcIt e(_graph, n); e != INVALID; ++e) {
- Flow rem = (*_flow)[e];
+ Value rem = (*_flow)[e];
if (!_tolerance.positive(rem)) continue;
Node v = _graph.source(e);
if ((*_level)[v] < level) {
@@ -637,11 +637,11 @@
num = _node_num * 20;
while (num > 0 && n != INVALID) {
- Flow excess = (*_excess)[n];
+ Value excess = (*_excess)[n];
int new_level = _level->maxLevel();
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
- Flow rem = (*_capacity)[e] - (*_flow)[e];
+ Value rem = (*_capacity)[e] - (*_flow)[e];
if (!_tolerance.positive(rem)) continue;
Node v = _graph.target(e);
if ((*_level)[v] < level) {
@@ -664,7 +664,7 @@
}
for (InArcIt e(_graph, n); e != INVALID; ++e) {
- Flow rem = (*_flow)[e];
+ Value rem = (*_flow)[e];
if (!_tolerance.positive(rem)) continue;
Node v = _graph.source(e);
if ((*_level)[v] < level) {
@@ -778,12 +778,12 @@
Node n;
while ((n = _level->highestActive()) != INVALID) {
- Flow excess = (*_excess)[n];
+ Value excess = (*_excess)[n];
int level = _level->highestActiveLevel();
int new_level = _level->maxLevel();
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
- Flow rem = (*_capacity)[e] - (*_flow)[e];
+ Value rem = (*_capacity)[e] - (*_flow)[e];
if (!_tolerance.positive(rem)) continue;
Node v = _graph.target(e);
if ((*_level)[v] < level) {
@@ -806,7 +806,7 @@
}
for (InArcIt e(_graph, n); e != INVALID; ++e) {
- Flow rem = (*_flow)[e];
+ Value rem = (*_flow)[e];
if (!_tolerance.positive(rem)) continue;
Node v = _graph.source(e);
if ((*_level)[v] < level) {
@@ -897,18 +897,18 @@
///
/// \pre Either \ref run() or \ref init() must be called before
/// using this function.
- Flow flowValue() const {
+ Value flowValue() const {
return (*_excess)[_target];
}
- /// \brief Returns the flow on the given arc.
+ /// \brief Returns the flow value on the given arc.
///
- /// Returns the flow on the given arc. This method can
+ /// Returns the flow value on the given arc. This method can
/// be called after the second phase of the algorithm.
///
/// \pre Either \ref run() or \ref init() must be called before
/// using this function.
- Flow flow(const Arc& arc) const {
+ Value flow(const Arc& arc) const {
return (*_flow)[arc];
}