1.1 --- a/lemon/network_simplex.h Wed Apr 29 03:15:24 2009 +0200
1.2 +++ b/lemon/network_simplex.h Wed Apr 29 14:25:51 2009 +0200
1.3 @@ -56,10 +56,10 @@
1.4 /// specified, then default values will be used.
1.5 ///
1.6 /// \tparam GR The digraph type the algorithm runs on.
1.7 - /// \tparam F The value type used for flow amounts, capacity bounds
1.8 + /// \tparam V The value type used for flow amounts, capacity bounds
1.9 /// and supply values in the algorithm. By default it is \c int.
1.10 /// \tparam C The value type used for costs and potentials in the
1.11 - /// algorithm. By default it is the same as \c F.
1.12 + /// algorithm. By default it is the same as \c V.
1.13 ///
1.14 /// \warning Both value types must be signed and all input data must
1.15 /// be integer.
1.16 @@ -67,23 +67,23 @@
1.17 /// \note %NetworkSimplex provides five different pivot rule
1.18 /// implementations, from which the most efficient one is used
1.19 /// by default. For more information see \ref PivotRule.
1.20 - template <typename GR, typename F = int, typename C = F>
1.21 + template <typename GR, typename V = int, typename C = V>
1.22 class NetworkSimplex
1.23 {
1.24 public:
1.25
1.26 /// The flow type of the algorithm
1.27 - typedef F Flow;
1.28 + typedef V Value;
1.29 /// The cost type of the algorithm
1.30 typedef C Cost;
1.31 #ifdef DOXYGEN
1.32 /// The type of the flow map
1.33 - typedef GR::ArcMap<Flow> FlowMap;
1.34 + typedef GR::ArcMap<Value> FlowMap;
1.35 /// The type of the potential map
1.36 typedef GR::NodeMap<Cost> PotentialMap;
1.37 #else
1.38 /// The type of the flow map
1.39 - typedef typename GR::template ArcMap<Flow> FlowMap;
1.40 + typedef typename GR::template ArcMap<Value> FlowMap;
1.41 /// The type of the potential map
1.42 typedef typename GR::template NodeMap<Cost> PotentialMap;
1.43 #endif
1.44 @@ -206,15 +206,15 @@
1.45
1.46 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.47
1.48 - typedef typename GR::template ArcMap<Flow> FlowArcMap;
1.49 + typedef typename GR::template ArcMap<Value> ValueArcMap;
1.50 typedef typename GR::template ArcMap<Cost> CostArcMap;
1.51 - typedef typename GR::template NodeMap<Flow> FlowNodeMap;
1.52 + typedef typename GR::template NodeMap<Value> ValueNodeMap;
1.53
1.54 typedef std::vector<Arc> ArcVector;
1.55 typedef std::vector<Node> NodeVector;
1.56 typedef std::vector<int> IntVector;
1.57 typedef std::vector<bool> BoolVector;
1.58 - typedef std::vector<Flow> FlowVector;
1.59 + typedef std::vector<Value> FlowVector;
1.60 typedef std::vector<Cost> CostVector;
1.61
1.62 // State constants for arcs
1.63 @@ -232,16 +232,16 @@
1.64 int _arc_num;
1.65
1.66 // Parameters of the problem
1.67 - FlowArcMap *_plower;
1.68 - FlowArcMap *_pupper;
1.69 + ValueArcMap *_plower;
1.70 + ValueArcMap *_pupper;
1.71 CostArcMap *_pcost;
1.72 - FlowNodeMap *_psupply;
1.73 + ValueNodeMap *_psupply;
1.74 bool _pstsup;
1.75 Node _psource, _ptarget;
1.76 - Flow _pstflow;
1.77 + Value _pstflow;
1.78 SupplyType _stype;
1.79
1.80 - Flow _sum_supply;
1.81 + Value _sum_supply;
1.82
1.83 // Result maps
1.84 FlowMap *_flow_map;
1.85 @@ -278,16 +278,16 @@
1.86 int in_arc, join, u_in, v_in, u_out, v_out;
1.87 int first, second, right, last;
1.88 int stem, par_stem, new_stem;
1.89 - Flow delta;
1.90 + Value delta;
1.91
1.92 public:
1.93
1.94 /// \brief Constant for infinite upper bounds (capacities).
1.95 ///
1.96 /// Constant for infinite upper bounds (capacities).
1.97 - /// It is \c std::numeric_limits<Flow>::infinity() if available,
1.98 - /// \c std::numeric_limits<Flow>::max() otherwise.
1.99 - const Flow INF;
1.100 + /// It is \c std::numeric_limits<Value>::infinity() if available,
1.101 + /// \c std::numeric_limits<Value>::max() otherwise.
1.102 + const Value INF;
1.103
1.104 private:
1.105
1.106 @@ -695,12 +695,12 @@
1.107 _flow_map(NULL), _potential_map(NULL),
1.108 _local_flow(false), _local_potential(false),
1.109 _node_id(graph),
1.110 - INF(std::numeric_limits<Flow>::has_infinity ?
1.111 - std::numeric_limits<Flow>::infinity() :
1.112 - std::numeric_limits<Flow>::max())
1.113 + INF(std::numeric_limits<Value>::has_infinity ?
1.114 + std::numeric_limits<Value>::infinity() :
1.115 + std::numeric_limits<Value>::max())
1.116 {
1.117 // Check the value types
1.118 - LEMON_ASSERT(std::numeric_limits<Flow>::is_signed,
1.119 + LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
1.120 "The flow type of NetworkSimplex must be signed");
1.121 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
1.122 "The cost type of NetworkSimplex must be signed");
1.123 @@ -725,14 +725,14 @@
1.124 /// will be set to zero on all arcs.
1.125 ///
1.126 /// \param map An arc map storing the lower bounds.
1.127 - /// Its \c Value type must be convertible to the \c Flow type
1.128 + /// Its \c Value type must be convertible to the \c Value type
1.129 /// of the algorithm.
1.130 ///
1.131 /// \return <tt>(*this)</tt>
1.132 template <typename LowerMap>
1.133 NetworkSimplex& lowerMap(const LowerMap& map) {
1.134 delete _plower;
1.135 - _plower = new FlowArcMap(_graph);
1.136 + _plower = new ValueArcMap(_graph);
1.137 for (ArcIt a(_graph); a != INVALID; ++a) {
1.138 (*_plower)[a] = map[a];
1.139 }
1.140 @@ -747,14 +747,14 @@
1.141 /// unbounded from above on each arc).
1.142 ///
1.143 /// \param map An arc map storing the upper bounds.
1.144 - /// Its \c Value type must be convertible to the \c Flow type
1.145 + /// Its \c Value type must be convertible to the \c Value type
1.146 /// of the algorithm.
1.147 ///
1.148 /// \return <tt>(*this)</tt>
1.149 template<typename UpperMap>
1.150 NetworkSimplex& upperMap(const UpperMap& map) {
1.151 delete _pupper;
1.152 - _pupper = new FlowArcMap(_graph);
1.153 + _pupper = new ValueArcMap(_graph);
1.154 for (ArcIt a(_graph); a != INVALID; ++a) {
1.155 (*_pupper)[a] = map[a];
1.156 }
1.157 @@ -790,7 +790,7 @@
1.158 /// (It makes sense only if non-zero lower bounds are given.)
1.159 ///
1.160 /// \param map A node map storing the supply values.
1.161 - /// Its \c Value type must be convertible to the \c Flow type
1.162 + /// Its \c Value type must be convertible to the \c Value type
1.163 /// of the algorithm.
1.164 ///
1.165 /// \return <tt>(*this)</tt>
1.166 @@ -798,7 +798,7 @@
1.167 NetworkSimplex& supplyMap(const SupplyMap& map) {
1.168 delete _psupply;
1.169 _pstsup = false;
1.170 - _psupply = new FlowNodeMap(_graph);
1.171 + _psupply = new ValueNodeMap(_graph);
1.172 for (NodeIt n(_graph); n != INVALID; ++n) {
1.173 (*_psupply)[n] = map[n];
1.174 }
1.175 @@ -823,7 +823,7 @@
1.176 /// (i.e. the supply of \c s and the demand of \c t).
1.177 ///
1.178 /// \return <tt>(*this)</tt>
1.179 - NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
1.180 + NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
1.181 delete _psupply;
1.182 _psupply = NULL;
1.183 _pstsup = true;
1.184 @@ -1025,7 +1025,7 @@
1.185 /// This function returns the flow on the given arc.
1.186 ///
1.187 /// \pre \ref run() must be called before using this function.
1.188 - Flow flow(const Arc& a) const {
1.189 + Value flow(const Arc& a) const {
1.190 return (*_flow_map)[a];
1.191 }
1.192
1.193 @@ -1204,7 +1204,7 @@
1.194 // Remove non-zero lower bounds
1.195 if (_plower) {
1.196 for (int i = 0; i != _arc_num; ++i) {
1.197 - Flow c = (*_plower)[_arc_ref[i]];
1.198 + Value c = (*_plower)[_arc_ref[i]];
1.199 if (c > 0) {
1.200 if (_cap[i] < INF) _cap[i] -= c;
1.201 _supply[_source[i]] -= c;
1.202 @@ -1275,7 +1275,7 @@
1.203 }
1.204 delta = _cap[in_arc];
1.205 int result = 0;
1.206 - Flow d;
1.207 + Value d;
1.208 int e;
1.209
1.210 // Search the cycle along the path form the first node to the root
1.211 @@ -1315,7 +1315,7 @@
1.212 void changeFlow(bool change) {
1.213 // Augment along the cycle
1.214 if (delta > 0) {
1.215 - Flow val = _state[in_arc] * delta;
1.216 + Value val = _state[in_arc] * delta;
1.217 _flow[in_arc] += val;
1.218 for (int u = _source[in_arc]; u != join; u = _parent[u]) {
1.219 _flow[_pred[u]] += _forward[u] ? -val : val;