1.1 --- a/lemon/circulation.h Wed Apr 29 03:15:24 2009 +0200
1.2 +++ b/lemon/circulation.h Wed Apr 29 14:25:51 2009 +0200
1.3 @@ -64,15 +64,15 @@
1.4 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.5 typedef SM SupplyMap;
1.6
1.7 - /// \brief The type of the flow values.
1.8 - typedef typename SupplyMap::Value Flow;
1.9 + /// \brief The type of the flow and supply values.
1.10 + typedef typename SupplyMap::Value Value;
1.11
1.12 /// \brief The type of the map that stores the flow values.
1.13 ///
1.14 /// The type of the map that stores the flow values.
1.15 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
1.16 /// concept.
1.17 - typedef typename Digraph::template ArcMap<Flow> FlowMap;
1.18 + typedef typename Digraph::template ArcMap<Value> FlowMap;
1.19
1.20 /// \brief Instantiates a FlowMap.
1.21 ///
1.22 @@ -104,7 +104,7 @@
1.23 /// \brief The tolerance used by the algorithm
1.24 ///
1.25 /// The tolerance used by the algorithm to handle inexact computation.
1.26 - typedef lemon::Tolerance<Flow> Tolerance;
1.27 + typedef lemon::Tolerance<Value> Tolerance;
1.28
1.29 };
1.30
1.31 @@ -187,8 +187,8 @@
1.32 typedef TR Traits;
1.33 ///The type of the digraph the algorithm runs on.
1.34 typedef typename Traits::Digraph Digraph;
1.35 - ///The type of the flow values.
1.36 - typedef typename Traits::Flow Flow;
1.37 + ///The type of the flow and supply values.
1.38 + typedef typename Traits::Value Value;
1.39
1.40 ///The type of the lower bound map.
1.41 typedef typename Traits::LowerMap LowerMap;
1.42 @@ -221,7 +221,7 @@
1.43 Elevator* _level;
1.44 bool _local_level;
1.45
1.46 - typedef typename Digraph::template NodeMap<Flow> ExcessMap;
1.47 + typedef typename Digraph::template NodeMap<Value> ExcessMap;
1.48 ExcessMap* _excess;
1.49
1.50 Tolerance _tol;
1.51 @@ -530,7 +530,7 @@
1.52 (*_excess)[_g.target(e)] += (*_lo)[e];
1.53 (*_excess)[_g.source(e)] -= (*_lo)[e];
1.54 } else {
1.55 - Flow fc = -(*_excess)[_g.target(e)];
1.56 + Value fc = -(*_excess)[_g.target(e)];
1.57 _flow->set(e, fc);
1.58 (*_excess)[_g.target(e)] = 0;
1.59 (*_excess)[_g.source(e)] -= fc;
1.60 @@ -563,11 +563,11 @@
1.61 while((act=_level->highestActive())!=INVALID) {
1.62 int actlevel=(*_level)[act];
1.63 int mlevel=_node_num;
1.64 - Flow exc=(*_excess)[act];
1.65 + Value exc=(*_excess)[act];
1.66
1.67 for(OutArcIt e(_g,act);e!=INVALID; ++e) {
1.68 Node v = _g.target(e);
1.69 - Flow fc=(*_up)[e]-(*_flow)[e];
1.70 + Value fc=(*_up)[e]-(*_flow)[e];
1.71 if(!_tol.positive(fc)) continue;
1.72 if((*_level)[v]<actlevel) {
1.73 if(!_tol.less(fc, exc)) {
1.74 @@ -591,7 +591,7 @@
1.75 }
1.76 for(InArcIt e(_g,act);e!=INVALID; ++e) {
1.77 Node v = _g.source(e);
1.78 - Flow fc=(*_flow)[e]-(*_lo)[e];
1.79 + Value fc=(*_flow)[e]-(*_lo)[e];
1.80 if(!_tol.positive(fc)) continue;
1.81 if((*_level)[v]<actlevel) {
1.82 if(!_tol.less(fc, exc)) {
1.83 @@ -661,13 +661,13 @@
1.84
1.85 ///@{
1.86
1.87 - /// \brief Returns the flow on the given arc.
1.88 + /// \brief Returns the flow value on the given arc.
1.89 ///
1.90 - /// Returns the flow on the given arc.
1.91 + /// Returns the flow value on the given arc.
1.92 ///
1.93 /// \pre Either \ref run() or \ref init() must be called before
1.94 /// using this function.
1.95 - Flow flow(const Arc& arc) const {
1.96 + Value flow(const Arc& arc) const {
1.97 return (*_flow)[arc];
1.98 }
1.99
1.100 @@ -750,7 +750,7 @@
1.101 if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
1.102 for(NodeIt n(_g);n!=INVALID;++n)
1.103 {
1.104 - Flow dif=-(*_supply)[n];
1.105 + Value dif=-(*_supply)[n];
1.106 for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
1.107 for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
1.108 if(_tol.negative(dif)) return false;
1.109 @@ -765,10 +765,10 @@
1.110 ///\sa barrierMap()
1.111 bool checkBarrier() const
1.112 {
1.113 - Flow delta=0;
1.114 - Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
1.115 - std::numeric_limits<Flow>::infinity() :
1.116 - std::numeric_limits<Flow>::max();
1.117 + Value delta=0;
1.118 + Value inf_cap = std::numeric_limits<Value>::has_infinity ?
1.119 + std::numeric_limits<Value>::infinity() :
1.120 + std::numeric_limits<Value>::max();
1.121 for(NodeIt n(_g);n!=INVALID;++n)
1.122 if(barrier(n))
1.123 delta-=(*_supply)[n];
2.1 --- a/lemon/network_simplex.h Wed Apr 29 03:15:24 2009 +0200
2.2 +++ b/lemon/network_simplex.h Wed Apr 29 14:25:51 2009 +0200
2.3 @@ -56,10 +56,10 @@
2.4 /// specified, then default values will be used.
2.5 ///
2.6 /// \tparam GR The digraph type the algorithm runs on.
2.7 - /// \tparam F The value type used for flow amounts, capacity bounds
2.8 + /// \tparam V The value type used for flow amounts, capacity bounds
2.9 /// and supply values in the algorithm. By default it is \c int.
2.10 /// \tparam C The value type used for costs and potentials in the
2.11 - /// algorithm. By default it is the same as \c F.
2.12 + /// algorithm. By default it is the same as \c V.
2.13 ///
2.14 /// \warning Both value types must be signed and all input data must
2.15 /// be integer.
2.16 @@ -67,23 +67,23 @@
2.17 /// \note %NetworkSimplex provides five different pivot rule
2.18 /// implementations, from which the most efficient one is used
2.19 /// by default. For more information see \ref PivotRule.
2.20 - template <typename GR, typename F = int, typename C = F>
2.21 + template <typename GR, typename V = int, typename C = V>
2.22 class NetworkSimplex
2.23 {
2.24 public:
2.25
2.26 /// The flow type of the algorithm
2.27 - typedef F Flow;
2.28 + typedef V Value;
2.29 /// The cost type of the algorithm
2.30 typedef C Cost;
2.31 #ifdef DOXYGEN
2.32 /// The type of the flow map
2.33 - typedef GR::ArcMap<Flow> FlowMap;
2.34 + typedef GR::ArcMap<Value> FlowMap;
2.35 /// The type of the potential map
2.36 typedef GR::NodeMap<Cost> PotentialMap;
2.37 #else
2.38 /// The type of the flow map
2.39 - typedef typename GR::template ArcMap<Flow> FlowMap;
2.40 + typedef typename GR::template ArcMap<Value> FlowMap;
2.41 /// The type of the potential map
2.42 typedef typename GR::template NodeMap<Cost> PotentialMap;
2.43 #endif
2.44 @@ -206,15 +206,15 @@
2.45
2.46 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
2.47
2.48 - typedef typename GR::template ArcMap<Flow> FlowArcMap;
2.49 + typedef typename GR::template ArcMap<Value> ValueArcMap;
2.50 typedef typename GR::template ArcMap<Cost> CostArcMap;
2.51 - typedef typename GR::template NodeMap<Flow> FlowNodeMap;
2.52 + typedef typename GR::template NodeMap<Value> ValueNodeMap;
2.53
2.54 typedef std::vector<Arc> ArcVector;
2.55 typedef std::vector<Node> NodeVector;
2.56 typedef std::vector<int> IntVector;
2.57 typedef std::vector<bool> BoolVector;
2.58 - typedef std::vector<Flow> FlowVector;
2.59 + typedef std::vector<Value> FlowVector;
2.60 typedef std::vector<Cost> CostVector;
2.61
2.62 // State constants for arcs
2.63 @@ -232,16 +232,16 @@
2.64 int _arc_num;
2.65
2.66 // Parameters of the problem
2.67 - FlowArcMap *_plower;
2.68 - FlowArcMap *_pupper;
2.69 + ValueArcMap *_plower;
2.70 + ValueArcMap *_pupper;
2.71 CostArcMap *_pcost;
2.72 - FlowNodeMap *_psupply;
2.73 + ValueNodeMap *_psupply;
2.74 bool _pstsup;
2.75 Node _psource, _ptarget;
2.76 - Flow _pstflow;
2.77 + Value _pstflow;
2.78 SupplyType _stype;
2.79
2.80 - Flow _sum_supply;
2.81 + Value _sum_supply;
2.82
2.83 // Result maps
2.84 FlowMap *_flow_map;
2.85 @@ -278,16 +278,16 @@
2.86 int in_arc, join, u_in, v_in, u_out, v_out;
2.87 int first, second, right, last;
2.88 int stem, par_stem, new_stem;
2.89 - Flow delta;
2.90 + Value delta;
2.91
2.92 public:
2.93
2.94 /// \brief Constant for infinite upper bounds (capacities).
2.95 ///
2.96 /// Constant for infinite upper bounds (capacities).
2.97 - /// It is \c std::numeric_limits<Flow>::infinity() if available,
2.98 - /// \c std::numeric_limits<Flow>::max() otherwise.
2.99 - const Flow INF;
2.100 + /// It is \c std::numeric_limits<Value>::infinity() if available,
2.101 + /// \c std::numeric_limits<Value>::max() otherwise.
2.102 + const Value INF;
2.103
2.104 private:
2.105
2.106 @@ -695,12 +695,12 @@
2.107 _flow_map(NULL), _potential_map(NULL),
2.108 _local_flow(false), _local_potential(false),
2.109 _node_id(graph),
2.110 - INF(std::numeric_limits<Flow>::has_infinity ?
2.111 - std::numeric_limits<Flow>::infinity() :
2.112 - std::numeric_limits<Flow>::max())
2.113 + INF(std::numeric_limits<Value>::has_infinity ?
2.114 + std::numeric_limits<Value>::infinity() :
2.115 + std::numeric_limits<Value>::max())
2.116 {
2.117 // Check the value types
2.118 - LEMON_ASSERT(std::numeric_limits<Flow>::is_signed,
2.119 + LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
2.120 "The flow type of NetworkSimplex must be signed");
2.121 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
2.122 "The cost type of NetworkSimplex must be signed");
2.123 @@ -725,14 +725,14 @@
2.124 /// will be set to zero on all arcs.
2.125 ///
2.126 /// \param map An arc map storing the lower bounds.
2.127 - /// Its \c Value type must be convertible to the \c Flow type
2.128 + /// Its \c Value type must be convertible to the \c Value type
2.129 /// of the algorithm.
2.130 ///
2.131 /// \return <tt>(*this)</tt>
2.132 template <typename LowerMap>
2.133 NetworkSimplex& lowerMap(const LowerMap& map) {
2.134 delete _plower;
2.135 - _plower = new FlowArcMap(_graph);
2.136 + _plower = new ValueArcMap(_graph);
2.137 for (ArcIt a(_graph); a != INVALID; ++a) {
2.138 (*_plower)[a] = map[a];
2.139 }
2.140 @@ -747,14 +747,14 @@
2.141 /// unbounded from above on each arc).
2.142 ///
2.143 /// \param map An arc map storing the upper bounds.
2.144 - /// Its \c Value type must be convertible to the \c Flow type
2.145 + /// Its \c Value type must be convertible to the \c Value type
2.146 /// of the algorithm.
2.147 ///
2.148 /// \return <tt>(*this)</tt>
2.149 template<typename UpperMap>
2.150 NetworkSimplex& upperMap(const UpperMap& map) {
2.151 delete _pupper;
2.152 - _pupper = new FlowArcMap(_graph);
2.153 + _pupper = new ValueArcMap(_graph);
2.154 for (ArcIt a(_graph); a != INVALID; ++a) {
2.155 (*_pupper)[a] = map[a];
2.156 }
2.157 @@ -790,7 +790,7 @@
2.158 /// (It makes sense only if non-zero lower bounds are given.)
2.159 ///
2.160 /// \param map A node map storing the supply values.
2.161 - /// Its \c Value type must be convertible to the \c Flow type
2.162 + /// Its \c Value type must be convertible to the \c Value type
2.163 /// of the algorithm.
2.164 ///
2.165 /// \return <tt>(*this)</tt>
2.166 @@ -798,7 +798,7 @@
2.167 NetworkSimplex& supplyMap(const SupplyMap& map) {
2.168 delete _psupply;
2.169 _pstsup = false;
2.170 - _psupply = new FlowNodeMap(_graph);
2.171 + _psupply = new ValueNodeMap(_graph);
2.172 for (NodeIt n(_graph); n != INVALID; ++n) {
2.173 (*_psupply)[n] = map[n];
2.174 }
2.175 @@ -823,7 +823,7 @@
2.176 /// (i.e. the supply of \c s and the demand of \c t).
2.177 ///
2.178 /// \return <tt>(*this)</tt>
2.179 - NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
2.180 + NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
2.181 delete _psupply;
2.182 _psupply = NULL;
2.183 _pstsup = true;
2.184 @@ -1025,7 +1025,7 @@
2.185 /// This function returns the flow on the given arc.
2.186 ///
2.187 /// \pre \ref run() must be called before using this function.
2.188 - Flow flow(const Arc& a) const {
2.189 + Value flow(const Arc& a) const {
2.190 return (*_flow_map)[a];
2.191 }
2.192
2.193 @@ -1204,7 +1204,7 @@
2.194 // Remove non-zero lower bounds
2.195 if (_plower) {
2.196 for (int i = 0; i != _arc_num; ++i) {
2.197 - Flow c = (*_plower)[_arc_ref[i]];
2.198 + Value c = (*_plower)[_arc_ref[i]];
2.199 if (c > 0) {
2.200 if (_cap[i] < INF) _cap[i] -= c;
2.201 _supply[_source[i]] -= c;
2.202 @@ -1275,7 +1275,7 @@
2.203 }
2.204 delta = _cap[in_arc];
2.205 int result = 0;
2.206 - Flow d;
2.207 + Value d;
2.208 int e;
2.209
2.210 // Search the cycle along the path form the first node to the root
2.211 @@ -1315,7 +1315,7 @@
2.212 void changeFlow(bool change) {
2.213 // Augment along the cycle
2.214 if (delta > 0) {
2.215 - Flow val = _state[in_arc] * delta;
2.216 + Value val = _state[in_arc] * delta;
2.217 _flow[in_arc] += val;
2.218 for (int u = _source[in_arc]; u != join; u = _parent[u]) {
2.219 _flow[_pred[u]] += _forward[u] ? -val : val;
3.1 --- a/lemon/preflow.h Wed Apr 29 03:15:24 2009 +0200
3.2 +++ b/lemon/preflow.h Wed Apr 29 14:25:51 2009 +0200
3.3 @@ -46,13 +46,13 @@
3.4 typedef CAP CapacityMap;
3.5
3.6 /// \brief The type of the flow values.
3.7 - typedef typename CapacityMap::Value Flow;
3.8 + typedef typename CapacityMap::Value Value;
3.9
3.10 /// \brief The type of the map that stores the flow values.
3.11 ///
3.12 /// The type of the map that stores the flow values.
3.13 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
3.14 - typedef typename Digraph::template ArcMap<Flow> FlowMap;
3.15 + typedef typename Digraph::template ArcMap<Value> FlowMap;
3.16
3.17 /// \brief Instantiates a FlowMap.
3.18 ///
3.19 @@ -84,7 +84,7 @@
3.20 /// \brief The tolerance used by the algorithm
3.21 ///
3.22 /// The tolerance used by the algorithm to handle inexact computation.
3.23 - typedef lemon::Tolerance<Flow> Tolerance;
3.24 + typedef lemon::Tolerance<Value> Tolerance;
3.25
3.26 };
3.27
3.28 @@ -125,7 +125,7 @@
3.29 ///The type of the capacity map.
3.30 typedef typename Traits::CapacityMap CapacityMap;
3.31 ///The type of the flow values.
3.32 - typedef typename Traits::Flow Flow;
3.33 + typedef typename Traits::Value Value;
3.34
3.35 ///The type of the flow map.
3.36 typedef typename Traits::FlowMap FlowMap;
3.37 @@ -151,7 +151,7 @@
3.38 Elevator* _level;
3.39 bool _local_level;
3.40
3.41 - typedef typename Digraph::template NodeMap<Flow> ExcessMap;
3.42 + typedef typename Digraph::template NodeMap<Value> ExcessMap;
3.43 ExcessMap* _excess;
3.44
3.45 Tolerance _tolerance;
3.46 @@ -470,7 +470,7 @@
3.47 }
3.48
3.49 for (NodeIt n(_graph); n != INVALID; ++n) {
3.50 - Flow excess = 0;
3.51 + Value excess = 0;
3.52 for (InArcIt e(_graph, n); e != INVALID; ++e) {
3.53 excess += (*_flow)[e];
3.54 }
3.55 @@ -519,7 +519,7 @@
3.56 _level->initFinish();
3.57
3.58 for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
3.59 - Flow rem = (*_capacity)[e] - (*_flow)[e];
3.60 + Value rem = (*_capacity)[e] - (*_flow)[e];
3.61 if (_tolerance.positive(rem)) {
3.62 Node u = _graph.target(e);
3.63 if ((*_level)[u] == _level->maxLevel()) continue;
3.64 @@ -531,7 +531,7 @@
3.65 }
3.66 }
3.67 for (InArcIt e(_graph, _source); e != INVALID; ++e) {
3.68 - Flow rem = (*_flow)[e];
3.69 + Value rem = (*_flow)[e];
3.70 if (_tolerance.positive(rem)) {
3.71 Node v = _graph.source(e);
3.72 if ((*_level)[v] == _level->maxLevel()) continue;
3.73 @@ -564,11 +564,11 @@
3.74 int num = _node_num;
3.75
3.76 while (num > 0 && n != INVALID) {
3.77 - Flow excess = (*_excess)[n];
3.78 + Value excess = (*_excess)[n];
3.79 int new_level = _level->maxLevel();
3.80
3.81 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
3.82 - Flow rem = (*_capacity)[e] - (*_flow)[e];
3.83 + Value rem = (*_capacity)[e] - (*_flow)[e];
3.84 if (!_tolerance.positive(rem)) continue;
3.85 Node v = _graph.target(e);
3.86 if ((*_level)[v] < level) {
3.87 @@ -591,7 +591,7 @@
3.88 }
3.89
3.90 for (InArcIt e(_graph, n); e != INVALID; ++e) {
3.91 - Flow rem = (*_flow)[e];
3.92 + Value rem = (*_flow)[e];
3.93 if (!_tolerance.positive(rem)) continue;
3.94 Node v = _graph.source(e);
3.95 if ((*_level)[v] < level) {
3.96 @@ -637,11 +637,11 @@
3.97
3.98 num = _node_num * 20;
3.99 while (num > 0 && n != INVALID) {
3.100 - Flow excess = (*_excess)[n];
3.101 + Value excess = (*_excess)[n];
3.102 int new_level = _level->maxLevel();
3.103
3.104 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
3.105 - Flow rem = (*_capacity)[e] - (*_flow)[e];
3.106 + Value rem = (*_capacity)[e] - (*_flow)[e];
3.107 if (!_tolerance.positive(rem)) continue;
3.108 Node v = _graph.target(e);
3.109 if ((*_level)[v] < level) {
3.110 @@ -664,7 +664,7 @@
3.111 }
3.112
3.113 for (InArcIt e(_graph, n); e != INVALID; ++e) {
3.114 - Flow rem = (*_flow)[e];
3.115 + Value rem = (*_flow)[e];
3.116 if (!_tolerance.positive(rem)) continue;
3.117 Node v = _graph.source(e);
3.118 if ((*_level)[v] < level) {
3.119 @@ -778,12 +778,12 @@
3.120
3.121 Node n;
3.122 while ((n = _level->highestActive()) != INVALID) {
3.123 - Flow excess = (*_excess)[n];
3.124 + Value excess = (*_excess)[n];
3.125 int level = _level->highestActiveLevel();
3.126 int new_level = _level->maxLevel();
3.127
3.128 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
3.129 - Flow rem = (*_capacity)[e] - (*_flow)[e];
3.130 + Value rem = (*_capacity)[e] - (*_flow)[e];
3.131 if (!_tolerance.positive(rem)) continue;
3.132 Node v = _graph.target(e);
3.133 if ((*_level)[v] < level) {
3.134 @@ -806,7 +806,7 @@
3.135 }
3.136
3.137 for (InArcIt e(_graph, n); e != INVALID; ++e) {
3.138 - Flow rem = (*_flow)[e];
3.139 + Value rem = (*_flow)[e];
3.140 if (!_tolerance.positive(rem)) continue;
3.141 Node v = _graph.source(e);
3.142 if ((*_level)[v] < level) {
3.143 @@ -897,18 +897,18 @@
3.144 ///
3.145 /// \pre Either \ref run() or \ref init() must be called before
3.146 /// using this function.
3.147 - Flow flowValue() const {
3.148 + Value flowValue() const {
3.149 return (*_excess)[_target];
3.150 }
3.151
3.152 - /// \brief Returns the flow on the given arc.
3.153 + /// \brief Returns the flow value on the given arc.
3.154 ///
3.155 - /// Returns the flow on the given arc. This method can
3.156 + /// Returns the flow value on the given arc. This method can
3.157 /// be called after the second phase of the algorithm.
3.158 ///
3.159 /// \pre Either \ref run() or \ref init() must be called before
3.160 /// using this function.
3.161 - Flow flow(const Arc& arc) const {
3.162 + Value flow(const Arc& arc) const {
3.163 return (*_flow)[arc];
3.164 }
3.165