1.1 --- a/lemon/maps.h Fri Nov 13 12:33:33 2009 +0100
1.2 +++ b/lemon/maps.h Thu Dec 10 17:05:35 2009 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
1.8 + * Copyright (C) 2003-2009
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -63,9 +63,10 @@
1.13 template<typename K, typename V>
1.14 class NullMap : public MapBase<K, V> {
1.15 public:
1.16 - typedef MapBase<K, V> Parent;
1.17 - typedef typename Parent::Key Key;
1.18 - typedef typename Parent::Value Value;
1.19 + ///\e
1.20 + typedef K Key;
1.21 + ///\e
1.22 + typedef V Value;
1.23
1.24 /// Gives back a default constructed element.
1.25 Value operator[](const Key&) const { return Value(); }
1.26 @@ -102,9 +103,10 @@
1.27 private:
1.28 V _value;
1.29 public:
1.30 - typedef MapBase<K, V> Parent;
1.31 - typedef typename Parent::Key Key;
1.32 - typedef typename Parent::Value Value;
1.33 + ///\e
1.34 + typedef K Key;
1.35 + ///\e
1.36 + typedef V Value;
1.37
1.38 /// Default constructor
1.39
1.40 @@ -168,9 +170,10 @@
1.41 template<typename K, typename V, V v>
1.42 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
1.43 public:
1.44 - typedef MapBase<K, V> Parent;
1.45 - typedef typename Parent::Key Key;
1.46 - typedef typename Parent::Value Value;
1.47 + ///\e
1.48 + typedef K Key;
1.49 + ///\e
1.50 + typedef V Value;
1.51
1.52 /// Constructor.
1.53 ConstMap() {}
1.54 @@ -202,9 +205,10 @@
1.55 template <typename T>
1.56 class IdentityMap : public MapBase<T, T> {
1.57 public:
1.58 - typedef MapBase<T, T> Parent;
1.59 - typedef typename Parent::Key Key;
1.60 - typedef typename Parent::Value Value;
1.61 + ///\e
1.62 + typedef T Key;
1.63 + ///\e
1.64 + typedef T Value;
1.65
1.66 /// Gives back the given value without any modification.
1.67 Value operator[](const Key &k) const {
1.68 @@ -245,11 +249,10 @@
1.69
1.70 public:
1.71
1.72 - typedef MapBase<int, V> Parent;
1.73 /// Key type
1.74 - typedef typename Parent::Key Key;
1.75 + typedef int Key;
1.76 /// Value type
1.77 - typedef typename Parent::Value Value;
1.78 + typedef V Value;
1.79 /// Reference type
1.80 typedef typename Vector::reference Reference;
1.81 /// Const reference type
1.82 @@ -353,17 +356,16 @@
1.83 ///
1.84 /// The simplest way of using this map is through the sparseMap()
1.85 /// function.
1.86 - template <typename K, typename V, typename Compare = std::less<K> >
1.87 + template <typename K, typename V, typename Comp = std::less<K> >
1.88 class SparseMap : public MapBase<K, V> {
1.89 template <typename K1, typename V1, typename C1>
1.90 friend class SparseMap;
1.91 public:
1.92
1.93 - typedef MapBase<K, V> Parent;
1.94 /// Key type
1.95 - typedef typename Parent::Key Key;
1.96 + typedef K Key;
1.97 /// Value type
1.98 - typedef typename Parent::Value Value;
1.99 + typedef V Value;
1.100 /// Reference type
1.101 typedef Value& Reference;
1.102 /// Const reference type
1.103 @@ -373,7 +375,7 @@
1.104
1.105 private:
1.106
1.107 - typedef std::map<K, V, Compare> Map;
1.108 + typedef std::map<K, V, Comp> Map;
1.109 Map _map;
1.110 Value _value;
1.111
1.112 @@ -489,14 +491,15 @@
1.113 const M1 &_m1;
1.114 const M2 &_m2;
1.115 public:
1.116 - typedef MapBase<typename M2::Key, typename M1::Value> Parent;
1.117 - typedef typename Parent::Key Key;
1.118 - typedef typename Parent::Value Value;
1.119 + ///\e
1.120 + typedef typename M2::Key Key;
1.121 + ///\e
1.122 + typedef typename M1::Value Value;
1.123
1.124 /// Constructor
1.125 ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.126
1.127 - /// \e
1.128 + ///\e
1.129 typename MapTraits<M1>::ConstReturnValue
1.130 operator[](const Key &k) const { return _m1[_m2[k]]; }
1.131 };
1.132 @@ -545,14 +548,15 @@
1.133 const M2 &_m2;
1.134 F _f;
1.135 public:
1.136 - typedef MapBase<typename M1::Key, V> Parent;
1.137 - typedef typename Parent::Key Key;
1.138 - typedef typename Parent::Value Value;
1.139 + ///\e
1.140 + typedef typename M1::Key Key;
1.141 + ///\e
1.142 + typedef V Value;
1.143
1.144 /// Constructor
1.145 CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
1.146 : _m1(m1), _m2(m2), _f(f) {}
1.147 - /// \e
1.148 + ///\e
1.149 Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
1.150 };
1.151
1.152 @@ -615,13 +619,14 @@
1.153 class FunctorToMap : public MapBase<K, V> {
1.154 F _f;
1.155 public:
1.156 - typedef MapBase<K, V> Parent;
1.157 - typedef typename Parent::Key Key;
1.158 - typedef typename Parent::Value Value;
1.159 + ///\e
1.160 + typedef K Key;
1.161 + ///\e
1.162 + typedef V Value;
1.163
1.164 /// Constructor
1.165 FunctorToMap(const F &f = F()) : _f(f) {}
1.166 - /// \e
1.167 + ///\e
1.168 Value operator[](const Key &k) const { return _f(k); }
1.169 };
1.170
1.171 @@ -669,18 +674,19 @@
1.172 class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
1.173 const M &_m;
1.174 public:
1.175 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.176 - typedef typename Parent::Key Key;
1.177 - typedef typename Parent::Value Value;
1.178 -
1.179 - typedef typename Parent::Key argument_type;
1.180 - typedef typename Parent::Value result_type;
1.181 + ///\e
1.182 + typedef typename M::Key Key;
1.183 + ///\e
1.184 + typedef typename M::Value Value;
1.185 +
1.186 + typedef typename M::Key argument_type;
1.187 + typedef typename M::Value result_type;
1.188
1.189 /// Constructor
1.190 MapToFunctor(const M &m) : _m(m) {}
1.191 - /// \e
1.192 + ///\e
1.193 Value operator()(const Key &k) const { return _m[k]; }
1.194 - /// \e
1.195 + ///\e
1.196 Value operator[](const Key &k) const { return _m[k]; }
1.197 };
1.198
1.199 @@ -709,9 +715,10 @@
1.200 class ConvertMap : public MapBase<typename M::Key, V> {
1.201 const M &_m;
1.202 public:
1.203 - typedef MapBase<typename M::Key, V> Parent;
1.204 - typedef typename Parent::Key Key;
1.205 - typedef typename Parent::Value Value;
1.206 + ///\e
1.207 + typedef typename M::Key Key;
1.208 + ///\e
1.209 + typedef V Value;
1.210
1.211 /// Constructor
1.212
1.213 @@ -719,7 +726,7 @@
1.214 /// \param m The underlying map.
1.215 ConvertMap(const M &m) : _m(m) {}
1.216
1.217 - /// \e
1.218 + ///\e
1.219 Value operator[](const Key &k) const { return _m[k]; }
1.220 };
1.221
1.222 @@ -751,9 +758,10 @@
1.223 M1 &_m1;
1.224 M2 &_m2;
1.225 public:
1.226 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.227 - typedef typename Parent::Key Key;
1.228 - typedef typename Parent::Value Value;
1.229 + ///\e
1.230 + typedef typename M1::Key Key;
1.231 + ///\e
1.232 + typedef typename M1::Value Value;
1.233
1.234 /// Constructor
1.235 ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
1.236 @@ -797,13 +805,14 @@
1.237 const M1 &_m1;
1.238 const M2 &_m2;
1.239 public:
1.240 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.241 - typedef typename Parent::Key Key;
1.242 - typedef typename Parent::Value Value;
1.243 + ///\e
1.244 + typedef typename M1::Key Key;
1.245 + ///\e
1.246 + typedef typename M1::Value Value;
1.247
1.248 /// Constructor
1.249 AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.250 - /// \e
1.251 + ///\e
1.252 Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
1.253 };
1.254
1.255 @@ -845,13 +854,14 @@
1.256 const M1 &_m1;
1.257 const M2 &_m2;
1.258 public:
1.259 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.260 - typedef typename Parent::Key Key;
1.261 - typedef typename Parent::Value Value;
1.262 + ///\e
1.263 + typedef typename M1::Key Key;
1.264 + ///\e
1.265 + typedef typename M1::Value Value;
1.266
1.267 /// Constructor
1.268 SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.269 - /// \e
1.270 + ///\e
1.271 Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
1.272 };
1.273
1.274 @@ -894,13 +904,14 @@
1.275 const M1 &_m1;
1.276 const M2 &_m2;
1.277 public:
1.278 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.279 - typedef typename Parent::Key Key;
1.280 - typedef typename Parent::Value Value;
1.281 + ///\e
1.282 + typedef typename M1::Key Key;
1.283 + ///\e
1.284 + typedef typename M1::Value Value;
1.285
1.286 /// Constructor
1.287 MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
1.288 - /// \e
1.289 + ///\e
1.290 Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
1.291 };
1.292
1.293 @@ -942,13 +953,14 @@
1.294 const M1 &_m1;
1.295 const M2 &_m2;
1.296 public:
1.297 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.298 - typedef typename Parent::Key Key;
1.299 - typedef typename Parent::Value Value;
1.300 + ///\e
1.301 + typedef typename M1::Key Key;
1.302 + ///\e
1.303 + typedef typename M1::Value Value;
1.304
1.305 /// Constructor
1.306 DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
1.307 - /// \e
1.308 + ///\e
1.309 Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
1.310 };
1.311
1.312 @@ -992,9 +1004,10 @@
1.313 const M &_m;
1.314 C _v;
1.315 public:
1.316 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.317 - typedef typename Parent::Key Key;
1.318 - typedef typename Parent::Value Value;
1.319 + ///\e
1.320 + typedef typename M::Key Key;
1.321 + ///\e
1.322 + typedef typename M::Value Value;
1.323
1.324 /// Constructor
1.325
1.326 @@ -1002,7 +1015,7 @@
1.327 /// \param m The undelying map.
1.328 /// \param v The constant value.
1.329 ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
1.330 - /// \e
1.331 + ///\e
1.332 Value operator[](const Key &k) const { return _m[k]+_v; }
1.333 };
1.334
1.335 @@ -1022,9 +1035,10 @@
1.336 M &_m;
1.337 C _v;
1.338 public:
1.339 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.340 - typedef typename Parent::Key Key;
1.341 - typedef typename Parent::Value Value;
1.342 + ///\e
1.343 + typedef typename M::Key Key;
1.344 + ///\e
1.345 + typedef typename M::Value Value;
1.346
1.347 /// Constructor
1.348
1.349 @@ -1032,9 +1046,9 @@
1.350 /// \param m The undelying map.
1.351 /// \param v The constant value.
1.352 ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1.353 - /// \e
1.354 + ///\e
1.355 Value operator[](const Key &k) const { return _m[k]+_v; }
1.356 - /// \e
1.357 + ///\e
1.358 void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
1.359 };
1.360
1.361 @@ -1093,9 +1107,10 @@
1.362 const M &_m;
1.363 C _v;
1.364 public:
1.365 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.366 - typedef typename Parent::Key Key;
1.367 - typedef typename Parent::Value Value;
1.368 + ///\e
1.369 + typedef typename M::Key Key;
1.370 + ///\e
1.371 + typedef typename M::Value Value;
1.372
1.373 /// Constructor
1.374
1.375 @@ -1103,7 +1118,7 @@
1.376 /// \param m The undelying map.
1.377 /// \param v The constant value.
1.378 ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
1.379 - /// \e
1.380 + ///\e
1.381 Value operator[](const Key &k) const { return _v*_m[k]; }
1.382 };
1.383
1.384 @@ -1124,9 +1139,10 @@
1.385 M &_m;
1.386 C _v;
1.387 public:
1.388 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.389 - typedef typename Parent::Key Key;
1.390 - typedef typename Parent::Value Value;
1.391 + ///\e
1.392 + typedef typename M::Key Key;
1.393 + ///\e
1.394 + typedef typename M::Value Value;
1.395
1.396 /// Constructor
1.397
1.398 @@ -1134,9 +1150,9 @@
1.399 /// \param m The undelying map.
1.400 /// \param v The constant value.
1.401 ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1.402 - /// \e
1.403 + ///\e
1.404 Value operator[](const Key &k) const { return _v*_m[k]; }
1.405 - /// \e
1.406 + ///\e
1.407 void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
1.408 };
1.409
1.410 @@ -1193,13 +1209,14 @@
1.411 class NegMap : public MapBase<typename M::Key, typename M::Value> {
1.412 const M& _m;
1.413 public:
1.414 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.415 - typedef typename Parent::Key Key;
1.416 - typedef typename Parent::Value Value;
1.417 + ///\e
1.418 + typedef typename M::Key Key;
1.419 + ///\e
1.420 + typedef typename M::Value Value;
1.421
1.422 /// Constructor
1.423 NegMap(const M &m) : _m(m) {}
1.424 - /// \e
1.425 + ///\e
1.426 Value operator[](const Key &k) const { return -_m[k]; }
1.427 };
1.428
1.429 @@ -1228,15 +1245,16 @@
1.430 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.431 M &_m;
1.432 public:
1.433 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.434 - typedef typename Parent::Key Key;
1.435 - typedef typename Parent::Value Value;
1.436 + ///\e
1.437 + typedef typename M::Key Key;
1.438 + ///\e
1.439 + typedef typename M::Value Value;
1.440
1.441 /// Constructor
1.442 NegWriteMap(M &m) : _m(m) {}
1.443 - /// \e
1.444 + ///\e
1.445 Value operator[](const Key &k) const { return -_m[k]; }
1.446 - /// \e
1.447 + ///\e
1.448 void set(const Key &k, const Value &v) { _m.set(k, -v); }
1.449 };
1.450
1.451 @@ -1282,13 +1300,14 @@
1.452 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1.453 const M &_m;
1.454 public:
1.455 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.456 - typedef typename Parent::Key Key;
1.457 - typedef typename Parent::Value Value;
1.458 + ///\e
1.459 + typedef typename M::Key Key;
1.460 + ///\e
1.461 + typedef typename M::Value Value;
1.462
1.463 /// Constructor
1.464 AbsMap(const M &m) : _m(m) {}
1.465 - /// \e
1.466 + ///\e
1.467 Value operator[](const Key &k) const {
1.468 Value tmp = _m[k];
1.469 return tmp >= 0 ? tmp : -tmp;
1.470 @@ -1337,9 +1356,10 @@
1.471 template <typename K>
1.472 class TrueMap : public MapBase<K, bool> {
1.473 public:
1.474 - typedef MapBase<K, bool> Parent;
1.475 - typedef typename Parent::Key Key;
1.476 - typedef typename Parent::Value Value;
1.477 + ///\e
1.478 + typedef K Key;
1.479 + ///\e
1.480 + typedef bool Value;
1.481
1.482 /// Gives back \c true.
1.483 Value operator[](const Key&) const { return true; }
1.484 @@ -1374,9 +1394,10 @@
1.485 template <typename K>
1.486 class FalseMap : public MapBase<K, bool> {
1.487 public:
1.488 - typedef MapBase<K, bool> Parent;
1.489 - typedef typename Parent::Key Key;
1.490 - typedef typename Parent::Value Value;
1.491 + ///\e
1.492 + typedef K Key;
1.493 + ///\e
1.494 + typedef bool Value;
1.495
1.496 /// Gives back \c false.
1.497 Value operator[](const Key&) const { return false; }
1.498 @@ -1419,13 +1440,14 @@
1.499 const M1 &_m1;
1.500 const M2 &_m2;
1.501 public:
1.502 - typedef MapBase<typename M1::Key, bool> Parent;
1.503 - typedef typename Parent::Key Key;
1.504 - typedef typename Parent::Value Value;
1.505 + ///\e
1.506 + typedef typename M1::Key Key;
1.507 + ///\e
1.508 + typedef bool Value;
1.509
1.510 /// Constructor
1.511 AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.512 - /// \e
1.513 + ///\e
1.514 Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
1.515 };
1.516
1.517 @@ -1467,13 +1489,14 @@
1.518 const M1 &_m1;
1.519 const M2 &_m2;
1.520 public:
1.521 - typedef MapBase<typename M1::Key, bool> Parent;
1.522 - typedef typename Parent::Key Key;
1.523 - typedef typename Parent::Value Value;
1.524 + ///\e
1.525 + typedef typename M1::Key Key;
1.526 + ///\e
1.527 + typedef bool Value;
1.528
1.529 /// Constructor
1.530 OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.531 - /// \e
1.532 + ///\e
1.533 Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
1.534 };
1.535
1.536 @@ -1506,13 +1529,14 @@
1.537 class NotMap : public MapBase<typename M::Key, bool> {
1.538 const M &_m;
1.539 public:
1.540 - typedef MapBase<typename M::Key, bool> Parent;
1.541 - typedef typename Parent::Key Key;
1.542 - typedef typename Parent::Value Value;
1.543 + ///\e
1.544 + typedef typename M::Key Key;
1.545 + ///\e
1.546 + typedef bool Value;
1.547
1.548 /// Constructor
1.549 NotMap(const M &m) : _m(m) {}
1.550 - /// \e
1.551 + ///\e
1.552 Value operator[](const Key &k) const { return !_m[k]; }
1.553 };
1.554
1.555 @@ -1532,15 +1556,16 @@
1.556 class NotWriteMap : public MapBase<typename M::Key, bool> {
1.557 M &_m;
1.558 public:
1.559 - typedef MapBase<typename M::Key, bool> Parent;
1.560 - typedef typename Parent::Key Key;
1.561 - typedef typename Parent::Value Value;
1.562 + ///\e
1.563 + typedef typename M::Key Key;
1.564 + ///\e
1.565 + typedef bool Value;
1.566
1.567 /// Constructor
1.568 NotWriteMap(M &m) : _m(m) {}
1.569 - /// \e
1.570 + ///\e
1.571 Value operator[](const Key &k) const { return !_m[k]; }
1.572 - /// \e
1.573 + ///\e
1.574 void set(const Key &k, bool v) { _m.set(k, !v); }
1.575 };
1.576
1.577 @@ -1595,13 +1620,14 @@
1.578 const M1 &_m1;
1.579 const M2 &_m2;
1.580 public:
1.581 - typedef MapBase<typename M1::Key, bool> Parent;
1.582 - typedef typename Parent::Key Key;
1.583 - typedef typename Parent::Value Value;
1.584 + ///\e
1.585 + typedef typename M1::Key Key;
1.586 + ///\e
1.587 + typedef bool Value;
1.588
1.589 /// Constructor
1.590 EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.591 - /// \e
1.592 + ///\e
1.593 Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
1.594 };
1.595
1.596 @@ -1643,13 +1669,14 @@
1.597 const M1 &_m1;
1.598 const M2 &_m2;
1.599 public:
1.600 - typedef MapBase<typename M1::Key, bool> Parent;
1.601 - typedef typename Parent::Key Key;
1.602 - typedef typename Parent::Value Value;
1.603 + ///\e
1.604 + typedef typename M1::Key Key;
1.605 + ///\e
1.606 + typedef bool Value;
1.607
1.608 /// Constructor
1.609 LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.610 - /// \e
1.611 + ///\e
1.612 Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
1.613 };
1.614
1.615 @@ -1705,24 +1732,27 @@
1.616 /// The simplest way of using this map is through the loggerBoolMap()
1.617 /// function.
1.618 ///
1.619 - /// \tparam It The type of the iterator.
1.620 - /// \tparam Ke The key type of the map. The default value set
1.621 + /// \tparam IT The type of the iterator.
1.622 + /// \tparam KEY The key type of the map. The default value set
1.623 /// according to the iterator type should work in most cases.
1.624 ///
1.625 /// \note The container of the iterator must contain enough space
1.626 /// for the elements or the iterator should be an inserter iterator.
1.627 #ifdef DOXYGEN
1.628 - template <typename It, typename Ke>
1.629 + template <typename IT, typename KEY>
1.630 #else
1.631 - template <typename It,
1.632 - typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
1.633 + template <typename IT,
1.634 + typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
1.635 #endif
1.636 - class LoggerBoolMap {
1.637 + class LoggerBoolMap : public MapBase<KEY, bool> {
1.638 public:
1.639 - typedef It Iterator;
1.640 -
1.641 - typedef Ke Key;
1.642 +
1.643 + ///\e
1.644 + typedef KEY Key;
1.645 + ///\e
1.646 typedef bool Value;
1.647 + ///\e
1.648 + typedef IT Iterator;
1.649
1.650 /// Constructor
1.651 LoggerBoolMap(Iterator it)
1.652 @@ -1785,23 +1815,36 @@
1.653 /// \addtogroup graph_maps
1.654 /// @{
1.655
1.656 - /// Provides an immutable and unique id for each item in the graph.
1.657 -
1.658 - /// The IdMap class provides a unique and immutable id for each item of the
1.659 - /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1.660 - /// different items (nodes) get different ids <li>\b immutable: the id of an
1.661 - /// item (node) does not change (even if you delete other nodes). </ul>
1.662 - /// Through this map you get access (i.e. can read) the inner id values of
1.663 - /// the items stored in the graph. This map can be inverted with its member
1.664 + /// \brief Provides an immutable and unique id for each item in a graph.
1.665 + ///
1.666 + /// IdMap provides a unique and immutable id for each item of the
1.667 + /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
1.668 + /// - \b unique: different items get different ids,
1.669 + /// - \b immutable: the id of an item does not change (even if you
1.670 + /// delete other nodes).
1.671 + ///
1.672 + /// Using this map you get access (i.e. can read) the inner id values of
1.673 + /// the items stored in the graph, which is returned by the \c id()
1.674 + /// function of the graph. This map can be inverted with its member
1.675 /// class \c InverseMap or with the \c operator() member.
1.676 ///
1.677 - template <typename _Graph, typename _Item>
1.678 - class IdMap {
1.679 + /// \tparam GR The graph type.
1.680 + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1.681 + /// \c GR::Edge).
1.682 + ///
1.683 + /// \see RangeIdMap
1.684 + template <typename GR, typename K>
1.685 + class IdMap : public MapBase<K, int> {
1.686 public:
1.687 - typedef _Graph Graph;
1.688 + /// The graph type of IdMap.
1.689 + typedef GR Graph;
1.690 + typedef GR Digraph;
1.691 + /// The key type of IdMap (\c Node, \c Arc or \c Edge).
1.692 + typedef K Item;
1.693 + /// The key type of IdMap (\c Node, \c Arc or \c Edge).
1.694 + typedef K Key;
1.695 + /// The value type of IdMap.
1.696 typedef int Value;
1.697 - typedef _Item Item;
1.698 - typedef _Item Key;
1.699
1.700 /// \brief Constructor.
1.701 ///
1.702 @@ -1813,9 +1856,9 @@
1.703 /// Gives back the immutable and unique \e id of the item.
1.704 int operator[](const Item& item) const { return _graph->id(item);}
1.705
1.706 - /// \brief Gives back the item by its id.
1.707 + /// \brief Gives back the \e item by its id.
1.708 ///
1.709 - /// Gives back the item by its id.
1.710 + /// Gives back the \e item by its id.
1.711 Item operator()(int id) { return _graph->fromId(id, Item()); }
1.712
1.713 private:
1.714 @@ -1823,9 +1866,9 @@
1.715
1.716 public:
1.717
1.718 - /// \brief The class represents the inverse of its owner (IdMap).
1.719 + /// \brief This class represents the inverse of its owner (IdMap).
1.720 ///
1.721 - /// The class represents the inverse of its owner (IdMap).
1.722 + /// This class represents the inverse of its owner (IdMap).
1.723 /// \see inverse()
1.724 class InverseMap {
1.725 public:
1.726 @@ -1843,7 +1886,6 @@
1.727 /// \brief Gives back the given item from its id.
1.728 ///
1.729 /// Gives back the given item from its id.
1.730 - ///
1.731 Item operator[](int id) const { return _graph->fromId(id, Item());}
1.732
1.733 private:
1.734 @@ -1854,59 +1896,61 @@
1.735 ///
1.736 /// Gives back the inverse of the IdMap.
1.737 InverseMap inverse() const { return InverseMap(*_graph);}
1.738 -
1.739 };
1.740
1.741
1.742 - /// \brief General invertable graph-map type.
1.743 -
1.744 - /// This type provides simple invertable graph-maps.
1.745 - /// The InvertableMap wraps an arbitrary ReadWriteMap
1.746 + /// \brief General cross reference graph map type.
1.747 +
1.748 + /// This class provides simple invertable graph maps.
1.749 + /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
1.750 /// and if a key is set to a new value then store it
1.751 /// in the inverse map.
1.752 ///
1.753 /// The values of the map can be accessed
1.754 /// with stl compatible forward iterator.
1.755 ///
1.756 - /// \tparam _Graph The graph type.
1.757 - /// \tparam _Item The item type of the graph.
1.758 - /// \tparam _Value The value type of the map.
1.759 + /// \tparam GR The graph type.
1.760 + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1.761 + /// \c GR::Edge).
1.762 + /// \tparam V The value type of the map.
1.763 ///
1.764 /// \see IterableValueMap
1.765 - template <typename _Graph, typename _Item, typename _Value>
1.766 - class InvertableMap
1.767 - : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
1.768 + template <typename GR, typename K, typename V>
1.769 + class CrossRefMap
1.770 + : protected ItemSetTraits<GR, K>::template Map<V>::Type {
1.771 private:
1.772
1.773 - typedef typename ItemSetTraits<_Graph, _Item>::
1.774 - template Map<_Value>::Type Map;
1.775 - typedef _Graph Graph;
1.776 -
1.777 - typedef std::map<_Value, _Item> Container;
1.778 + typedef typename ItemSetTraits<GR, K>::
1.779 + template Map<V>::Type Map;
1.780 +
1.781 + typedef std::map<V, K> Container;
1.782 Container _inv_map;
1.783
1.784 public:
1.785
1.786 - /// The key type of InvertableMap (Node, Arc, Edge).
1.787 - typedef typename Map::Key Key;
1.788 - /// The value type of the InvertableMap.
1.789 - typedef typename Map::Value Value;
1.790 + /// The graph type of CrossRefMap.
1.791 + typedef GR Graph;
1.792 + typedef GR Digraph;
1.793 + /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
1.794 + typedef K Item;
1.795 + /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
1.796 + typedef K Key;
1.797 + /// The value type of CrossRefMap.
1.798 + typedef V Value;
1.799
1.800 /// \brief Constructor.
1.801 ///
1.802 - /// Construct a new InvertableMap for the graph.
1.803 - ///
1.804 - explicit InvertableMap(const Graph& graph) : Map(graph) {}
1.805 + /// Construct a new CrossRefMap for the given graph.
1.806 + explicit CrossRefMap(const Graph& graph) : Map(graph) {}
1.807
1.808 /// \brief Forward iterator for values.
1.809 ///
1.810 /// This iterator is an stl compatible forward
1.811 /// iterator on the values of the map. The values can
1.812 - /// be accessed in the [beginValue, endValue) range.
1.813 - ///
1.814 + /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1.815 class ValueIterator
1.816 : public std::iterator<std::forward_iterator_tag, Value> {
1.817 - friend class InvertableMap;
1.818 + friend class CrossRefMap;
1.819 private:
1.820 ValueIterator(typename Container::const_iterator _it)
1.821 : it(_it) {}
1.822 @@ -1935,7 +1979,7 @@
1.823 ///
1.824 /// Returns an stl compatible iterator to the
1.825 /// first value of the map. The values of the
1.826 - /// map can be accessed in the [beginValue, endValue)
1.827 + /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.828 /// range.
1.829 ValueIterator beginValue() const {
1.830 return ValueIterator(_inv_map.begin());
1.831 @@ -1945,15 +1989,15 @@
1.832 ///
1.833 /// Returns an stl compatible iterator after the
1.834 /// last value of the map. The values of the
1.835 - /// map can be accessed in the [beginValue, endValue)
1.836 + /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.837 /// range.
1.838 ValueIterator endValue() const {
1.839 return ValueIterator(_inv_map.end());
1.840 }
1.841
1.842 - /// \brief The setter function of the map.
1.843 + /// \brief Sets the value associated with the given key.
1.844 ///
1.845 - /// Sets the mapped value.
1.846 + /// Sets the value associated with the given key.
1.847 void set(const Key& key, const Value& val) {
1.848 Value oldval = Map::operator[](key);
1.849 typename Container::iterator it = _inv_map.find(oldval);
1.850 @@ -1964,9 +2008,9 @@
1.851 Map::set(key, val);
1.852 }
1.853
1.854 - /// \brief The getter function of the map.
1.855 + /// \brief Returns the value associated with the given key.
1.856 ///
1.857 - /// It gives back the value associated with the key.
1.858 + /// Returns the value associated with the given key.
1.859 typename MapTraits<Map>::ConstReturnValue
1.860 operator[](const Key& key) const {
1.861 return Map::operator[](key);
1.862 @@ -1982,9 +2026,9 @@
1.863
1.864 protected:
1.865
1.866 - /// \brief Erase the key from the map.
1.867 + /// \brief Erase the key from the map and the inverse map.
1.868 ///
1.869 - /// Erase the key to the map. It is called by the
1.870 + /// Erase the key from the map and the inverse map. It is called by the
1.871 /// \c AlterationNotifier.
1.872 virtual void erase(const Key& key) {
1.873 Value val = Map::operator[](key);
1.874 @@ -1995,9 +2039,9 @@
1.875 Map::erase(key);
1.876 }
1.877
1.878 - /// \brief Erase more keys from the map.
1.879 + /// \brief Erase more keys from the map and the inverse map.
1.880 ///
1.881 - /// Erase more keys from the map. It is called by the
1.882 + /// Erase more keys from the map and the inverse map. It is called by the
1.883 /// \c AlterationNotifier.
1.884 virtual void erase(const std::vector<Key>& keys) {
1.885 for (int i = 0; i < int(keys.size()); ++i) {
1.886 @@ -2010,9 +2054,9 @@
1.887 Map::erase(keys);
1.888 }
1.889
1.890 - /// \brief Clear the keys from the map and inverse map.
1.891 + /// \brief Clear the keys from the map and the inverse map.
1.892 ///
1.893 - /// Clear the keys from the map and inverse map. It is called by the
1.894 + /// Clear the keys from the map and the inverse map. It is called by the
1.895 /// \c AlterationNotifier.
1.896 virtual void clear() {
1.897 _inv_map.clear();
1.898 @@ -2024,76 +2068,84 @@
1.899 /// \brief The inverse map type.
1.900 ///
1.901 /// The inverse of this map. The subscript operator of the map
1.902 - /// gives back always the item what was last assigned to the value.
1.903 + /// gives back the item that was last assigned to the value.
1.904 class InverseMap {
1.905 public:
1.906 - /// \brief Constructor of the InverseMap.
1.907 + /// \brief Constructor
1.908 ///
1.909 /// Constructor of the InverseMap.
1.910 - explicit InverseMap(const InvertableMap& inverted)
1.911 + explicit InverseMap(const CrossRefMap& inverted)
1.912 : _inverted(inverted) {}
1.913
1.914 /// The value type of the InverseMap.
1.915 - typedef typename InvertableMap::Key Value;
1.916 + typedef typename CrossRefMap::Key Value;
1.917 /// The key type of the InverseMap.
1.918 - typedef typename InvertableMap::Value Key;
1.919 + typedef typename CrossRefMap::Value Key;
1.920
1.921 /// \brief Subscript operator.
1.922 ///
1.923 - /// Subscript operator. It gives back always the item
1.924 - /// what was last assigned to the value.
1.925 + /// Subscript operator. It gives back the item
1.926 + /// that was last assigned to the given value.
1.927 Value operator[](const Key& key) const {
1.928 return _inverted(key);
1.929 }
1.930
1.931 private:
1.932 - const InvertableMap& _inverted;
1.933 + const CrossRefMap& _inverted;
1.934 };
1.935
1.936 - /// \brief It gives back the just readable inverse map.
1.937 + /// \brief It gives back the read-only inverse map.
1.938 ///
1.939 - /// It gives back the just readable inverse map.
1.940 + /// It gives back the read-only inverse map.
1.941 InverseMap inverse() const {
1.942 return InverseMap(*this);
1.943 }
1.944
1.945 };
1.946
1.947 - /// \brief Provides a mutable, continuous and unique descriptor for each
1.948 - /// item in the graph.
1.949 + /// \brief Provides continuous and unique ID for the
1.950 + /// items of a graph.
1.951 ///
1.952 - /// The DescriptorMap class provides a unique and continuous (but mutable)
1.953 - /// descriptor (id) for each item of the same type (e.g. node) in the
1.954 - /// graph. This id is <ul><li>\b unique: different items (nodes) get
1.955 - /// different ids <li>\b continuous: the range of the ids is the set of
1.956 - /// integers between 0 and \c n-1, where \c n is the number of the items of
1.957 - /// this type (e.g. nodes) (so the id of a node can change if you delete an
1.958 - /// other node, i.e. this id is mutable). </ul> This map can be inverted
1.959 - /// with its member class \c InverseMap, or with the \c operator() member.
1.960 + /// RangeIdMap provides a unique and continuous
1.961 + /// ID for each item of a given type (\c Node, \c Arc or
1.962 + /// \c Edge) in a graph. This id is
1.963 + /// - \b unique: different items get different ids,
1.964 + /// - \b continuous: the range of the ids is the set of integers
1.965 + /// between 0 and \c n-1, where \c n is the number of the items of
1.966 + /// this type (\c Node, \c Arc or \c Edge).
1.967 + /// - So, the ids can change when deleting an item of the same type.
1.968 ///
1.969 - /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
1.970 - /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
1.971 - /// Edge.
1.972 - template <typename _Graph, typename _Item>
1.973 - class DescriptorMap
1.974 - : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
1.975 -
1.976 - typedef _Item Item;
1.977 - typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
1.978 + /// Thus this id is not (necessarily) the same as what can get using
1.979 + /// the \c id() function of the graph or \ref IdMap.
1.980 + /// This map can be inverted with its member class \c InverseMap,
1.981 + /// or with the \c operator() member.
1.982 + ///
1.983 + /// \tparam GR The graph type.
1.984 + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1.985 + /// \c GR::Edge).
1.986 + ///
1.987 + /// \see IdMap
1.988 + template <typename GR, typename K>
1.989 + class RangeIdMap
1.990 + : protected ItemSetTraits<GR, K>::template Map<int>::Type {
1.991 +
1.992 + typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
1.993
1.994 public:
1.995 - /// The graph class of DescriptorMap.
1.996 - typedef _Graph Graph;
1.997 -
1.998 - /// The key type of DescriptorMap (Node, Arc, Edge).
1.999 - typedef typename Map::Key Key;
1.1000 - /// The value type of DescriptorMap.
1.1001 - typedef typename Map::Value Value;
1.1002 + /// The graph type of RangeIdMap.
1.1003 + typedef GR Graph;
1.1004 + typedef GR Digraph;
1.1005 + /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
1.1006 + typedef K Item;
1.1007 + /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
1.1008 + typedef K Key;
1.1009 + /// The value type of RangeIdMap.
1.1010 + typedef int Value;
1.1011
1.1012 /// \brief Constructor.
1.1013 ///
1.1014 - /// Constructor for descriptor map.
1.1015 - explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1.1016 + /// Constructor.
1.1017 + explicit RangeIdMap(const Graph& gr) : Map(gr) {
1.1018 Item it;
1.1019 const typename Map::Notifier* nf = Map::notifier();
1.1020 for (nf->first(it); it != INVALID; nf->next(it)) {
1.1021 @@ -2104,7 +2156,7 @@
1.1022
1.1023 protected:
1.1024
1.1025 - /// \brief Add a new key to the map.
1.1026 + /// \brief Adds a new key to the map.
1.1027 ///
1.1028 /// Add a new key to the map. It is called by the
1.1029 /// \c AlterationNotifier.
1.1030 @@ -2194,16 +2246,16 @@
1.1031 _inv_map[pi] = q;
1.1032 }
1.1033
1.1034 - /// \brief Gives back the \e descriptor of the item.
1.1035 + /// \brief Gives back the \e RangeId of the item
1.1036 ///
1.1037 - /// Gives back the mutable and unique \e descriptor of the map.
1.1038 + /// Gives back the \e RangeId of the item.
1.1039 int operator[](const Item& item) const {
1.1040 return Map::operator[](item);
1.1041 }
1.1042
1.1043 - /// \brief Gives back the item by its descriptor.
1.1044 - ///
1.1045 - /// Gives back th item by its descriptor.
1.1046 + /// \brief Gives back the item belonging to a \e RangeId
1.1047 + ///
1.1048 + /// Gives back the item belonging to a \e RangeId.
1.1049 Item operator()(int id) const {
1.1050 return _inv_map[id];
1.1051 }
1.1052 @@ -2214,27 +2266,28 @@
1.1053 Container _inv_map;
1.1054
1.1055 public:
1.1056 - /// \brief The inverse map type of DescriptorMap.
1.1057 +
1.1058 + /// \brief The inverse map type of RangeIdMap.
1.1059 ///
1.1060 - /// The inverse map type of DescriptorMap.
1.1061 + /// The inverse map type of RangeIdMap.
1.1062 class InverseMap {
1.1063 public:
1.1064 - /// \brief Constructor of the InverseMap.
1.1065 + /// \brief Constructor
1.1066 ///
1.1067 /// Constructor of the InverseMap.
1.1068 - explicit InverseMap(const DescriptorMap& inverted)
1.1069 + explicit InverseMap(const RangeIdMap& inverted)
1.1070 : _inverted(inverted) {}
1.1071
1.1072
1.1073 /// The value type of the InverseMap.
1.1074 - typedef typename DescriptorMap::Key Value;
1.1075 + typedef typename RangeIdMap::Key Value;
1.1076 /// The key type of the InverseMap.
1.1077 - typedef typename DescriptorMap::Value Key;
1.1078 + typedef typename RangeIdMap::Value Key;
1.1079
1.1080 /// \brief Subscript operator.
1.1081 ///
1.1082 /// Subscript operator. It gives back the item
1.1083 - /// that the descriptor belongs to currently.
1.1084 + /// that the descriptor currently belongs to.
1.1085 Value operator[](const Key& key) const {
1.1086 return _inverted(key);
1.1087 }
1.1088 @@ -2247,7 +2300,7 @@
1.1089 }
1.1090
1.1091 private:
1.1092 - const DescriptorMap& _inverted;
1.1093 + const RangeIdMap& _inverted;
1.1094 };
1.1095
1.1096 /// \brief Gives back the inverse of the map.
1.1097 @@ -2258,230 +2311,199 @@
1.1098 }
1.1099 };
1.1100
1.1101 - /// \brief Returns the source of the given arc.
1.1102 + /// \brief Map of the source nodes of arcs in a digraph.
1.1103 ///
1.1104 - /// The SourceMap gives back the source Node of the given arc.
1.1105 + /// SourceMap provides access for the source node of each arc in a digraph,
1.1106 + /// which is returned by the \c source() function of the digraph.
1.1107 + /// \tparam GR The digraph type.
1.1108 /// \see TargetMap
1.1109 - template <typename Digraph>
1.1110 + template <typename GR>
1.1111 class SourceMap {
1.1112 public:
1.1113
1.1114 - typedef typename Digraph::Node Value;
1.1115 - typedef typename Digraph::Arc Key;
1.1116 + ///\e
1.1117 + typedef typename GR::Arc Key;
1.1118 + ///\e
1.1119 + typedef typename GR::Node Value;
1.1120
1.1121 /// \brief Constructor
1.1122 ///
1.1123 - /// Constructor
1.1124 + /// Constructor.
1.1125 /// \param digraph The digraph that the map belongs to.
1.1126 - explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
1.1127 -
1.1128 - /// \brief The subscript operator.
1.1129 + explicit SourceMap(const GR& digraph) : _graph(digraph) {}
1.1130 +
1.1131 + /// \brief Returns the source node of the given arc.
1.1132 ///
1.1133 - /// The subscript operator.
1.1134 - /// \param arc The arc
1.1135 - /// \return The source of the arc
1.1136 + /// Returns the source node of the given arc.
1.1137 Value operator[](const Key& arc) const {
1.1138 - return _digraph.source(arc);
1.1139 + return _graph.source(arc);
1.1140 }
1.1141
1.1142 private:
1.1143 - const Digraph& _digraph;
1.1144 + const GR& _graph;
1.1145 };
1.1146
1.1147 /// \brief Returns a \c SourceMap class.
1.1148 ///
1.1149 /// This function just returns an \c SourceMap class.
1.1150 /// \relates SourceMap
1.1151 - template <typename Digraph>
1.1152 - inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
1.1153 - return SourceMap<Digraph>(digraph);
1.1154 + template <typename GR>
1.1155 + inline SourceMap<GR> sourceMap(const GR& graph) {
1.1156 + return SourceMap<GR>(graph);
1.1157 }
1.1158
1.1159 - /// \brief Returns the target of the given arc.
1.1160 + /// \brief Map of the target nodes of arcs in a digraph.
1.1161 ///
1.1162 - /// The TargetMap gives back the target Node of the given arc.
1.1163 + /// TargetMap provides access for the target node of each arc in a digraph,
1.1164 + /// which is returned by the \c target() function of the digraph.
1.1165 + /// \tparam GR The digraph type.
1.1166 /// \see SourceMap
1.1167 - template <typename Digraph>
1.1168 + template <typename GR>
1.1169 class TargetMap {
1.1170 public:
1.1171
1.1172 - typedef typename Digraph::Node Value;
1.1173 - typedef typename Digraph::Arc Key;
1.1174 + ///\e
1.1175 + typedef typename GR::Arc Key;
1.1176 + ///\e
1.1177 + typedef typename GR::Node Value;
1.1178
1.1179 /// \brief Constructor
1.1180 ///
1.1181 - /// Constructor
1.1182 + /// Constructor.
1.1183 /// \param digraph The digraph that the map belongs to.
1.1184 - explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
1.1185 -
1.1186 - /// \brief The subscript operator.
1.1187 + explicit TargetMap(const GR& digraph) : _graph(digraph) {}
1.1188 +
1.1189 + /// \brief Returns the target node of the given arc.
1.1190 ///
1.1191 - /// The subscript operator.
1.1192 - /// \param e The arc
1.1193 - /// \return The target of the arc
1.1194 + /// Returns the target node of the given arc.
1.1195 Value operator[](const Key& e) const {
1.1196 - return _digraph.target(e);
1.1197 + return _graph.target(e);
1.1198 }
1.1199
1.1200 private:
1.1201 - const Digraph& _digraph;
1.1202 + const GR& _graph;
1.1203 };
1.1204
1.1205 /// \brief Returns a \c TargetMap class.
1.1206 ///
1.1207 /// This function just returns a \c TargetMap class.
1.1208 /// \relates TargetMap
1.1209 - template <typename Digraph>
1.1210 - inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
1.1211 - return TargetMap<Digraph>(digraph);
1.1212 + template <typename GR>
1.1213 + inline TargetMap<GR> targetMap(const GR& graph) {
1.1214 + return TargetMap<GR>(graph);
1.1215 }
1.1216
1.1217 - /// \brief Returns the "forward" directed arc view of an edge.
1.1218 + /// \brief Map of the "forward" directed arc view of edges in a graph.
1.1219 ///
1.1220 - /// Returns the "forward" directed arc view of an edge.
1.1221 + /// ForwardMap provides access for the "forward" directed arc view of
1.1222 + /// each edge in a graph, which is returned by the \c direct() function
1.1223 + /// of the graph with \c true parameter.
1.1224 + /// \tparam GR The graph type.
1.1225 /// \see BackwardMap
1.1226 - template <typename Graph>
1.1227 + template <typename GR>
1.1228 class ForwardMap {
1.1229 public:
1.1230
1.1231 - typedef typename Graph::Arc Value;
1.1232 - typedef typename Graph::Edge Key;
1.1233 + typedef typename GR::Arc Value;
1.1234 + typedef typename GR::Edge Key;
1.1235
1.1236 /// \brief Constructor
1.1237 ///
1.1238 - /// Constructor
1.1239 + /// Constructor.
1.1240 /// \param graph The graph that the map belongs to.
1.1241 - explicit ForwardMap(const Graph& graph) : _graph(graph) {}
1.1242 -
1.1243 - /// \brief The subscript operator.
1.1244 + explicit ForwardMap(const GR& graph) : _graph(graph) {}
1.1245 +
1.1246 + /// \brief Returns the "forward" directed arc view of the given edge.
1.1247 ///
1.1248 - /// The subscript operator.
1.1249 - /// \param key An edge
1.1250 - /// \return The "forward" directed arc view of edge
1.1251 + /// Returns the "forward" directed arc view of the given edge.
1.1252 Value operator[](const Key& key) const {
1.1253 return _graph.direct(key, true);
1.1254 }
1.1255
1.1256 private:
1.1257 - const Graph& _graph;
1.1258 + const GR& _graph;
1.1259 };
1.1260
1.1261 /// \brief Returns a \c ForwardMap class.
1.1262 ///
1.1263 /// This function just returns an \c ForwardMap class.
1.1264 /// \relates ForwardMap
1.1265 - template <typename Graph>
1.1266 - inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1.1267 - return ForwardMap<Graph>(graph);
1.1268 + template <typename GR>
1.1269 + inline ForwardMap<GR> forwardMap(const GR& graph) {
1.1270 + return ForwardMap<GR>(graph);
1.1271 }
1.1272
1.1273 - /// \brief Returns the "backward" directed arc view of an edge.
1.1274 + /// \brief Map of the "backward" directed arc view of edges in a graph.
1.1275 ///
1.1276 - /// Returns the "backward" directed arc view of an edge.
1.1277 + /// BackwardMap provides access for the "backward" directed arc view of
1.1278 + /// each edge in a graph, which is returned by the \c direct() function
1.1279 + /// of the graph with \c false parameter.
1.1280 + /// \tparam GR The graph type.
1.1281 /// \see ForwardMap
1.1282 - template <typename Graph>
1.1283 + template <typename GR>
1.1284 class BackwardMap {
1.1285 public:
1.1286
1.1287 - typedef typename Graph::Arc Value;
1.1288 - typedef typename Graph::Edge Key;
1.1289 + typedef typename GR::Arc Value;
1.1290 + typedef typename GR::Edge Key;
1.1291
1.1292 /// \brief Constructor
1.1293 ///
1.1294 - /// Constructor
1.1295 + /// Constructor.
1.1296 /// \param graph The graph that the map belongs to.
1.1297 - explicit BackwardMap(const Graph& graph) : _graph(graph) {}
1.1298 -
1.1299 - /// \brief The subscript operator.
1.1300 + explicit BackwardMap(const GR& graph) : _graph(graph) {}
1.1301 +
1.1302 + /// \brief Returns the "backward" directed arc view of the given edge.
1.1303 ///
1.1304 - /// The subscript operator.
1.1305 - /// \param key An edge
1.1306 - /// \return The "backward" directed arc view of edge
1.1307 + /// Returns the "backward" directed arc view of the given edge.
1.1308 Value operator[](const Key& key) const {
1.1309 return _graph.direct(key, false);
1.1310 }
1.1311
1.1312 private:
1.1313 - const Graph& _graph;
1.1314 + const GR& _graph;
1.1315 };
1.1316
1.1317 /// \brief Returns a \c BackwardMap class
1.1318
1.1319 /// This function just returns a \c BackwardMap class.
1.1320 /// \relates BackwardMap
1.1321 - template <typename Graph>
1.1322 - inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1.1323 - return BackwardMap<Graph>(graph);
1.1324 + template <typename GR>
1.1325 + inline BackwardMap<GR> backwardMap(const GR& graph) {
1.1326 + return BackwardMap<GR>(graph);
1.1327 }
1.1328
1.1329 - /// \brief Potential difference map
1.1330 - ///
1.1331 - /// If there is an potential map on the nodes then we
1.1332 - /// can get an arc map as we get the substraction of the
1.1333 - /// values of the target and source.
1.1334 - template <typename Digraph, typename NodeMap>
1.1335 - class PotentialDifferenceMap {
1.1336 - public:
1.1337 - typedef typename Digraph::Arc Key;
1.1338 - typedef typename NodeMap::Value Value;
1.1339 -
1.1340 - /// \brief Constructor
1.1341 - ///
1.1342 - /// Contructor of the map
1.1343 - explicit PotentialDifferenceMap(const Digraph& digraph,
1.1344 - const NodeMap& potential)
1.1345 - : _digraph(digraph), _potential(potential) {}
1.1346 -
1.1347 - /// \brief Const subscription operator
1.1348 - ///
1.1349 - /// Const subscription operator
1.1350 - Value operator[](const Key& arc) const {
1.1351 - return _potential[_digraph.target(arc)] -
1.1352 - _potential[_digraph.source(arc)];
1.1353 - }
1.1354 -
1.1355 - private:
1.1356 - const Digraph& _digraph;
1.1357 - const NodeMap& _potential;
1.1358 - };
1.1359 -
1.1360 - /// \brief Returns a PotentialDifferenceMap.
1.1361 - ///
1.1362 - /// This function just returns a PotentialDifferenceMap.
1.1363 - /// \relates PotentialDifferenceMap
1.1364 - template <typename Digraph, typename NodeMap>
1.1365 - PotentialDifferenceMap<Digraph, NodeMap>
1.1366 - potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
1.1367 - return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
1.1368 - }
1.1369 -
1.1370 - /// \brief Map of the node in-degrees.
1.1371 + /// \brief Map of the in-degrees of nodes in a digraph.
1.1372 ///
1.1373 /// This map returns the in-degree of a node. Once it is constructed,
1.1374 - /// the degrees are stored in a standard NodeMap, so each query is done
1.1375 + /// the degrees are stored in a standard \c NodeMap, so each query is done
1.1376 /// in constant time. On the other hand, the values are updated automatically
1.1377 /// whenever the digraph changes.
1.1378 ///
1.1379 - /// \warning Besides addNode() and addArc(), a digraph structure may provide
1.1380 - /// alternative ways to modify the digraph. The correct behavior of InDegMap
1.1381 - /// is not guarantied if these additional features are used. For example
1.1382 - /// the functions \ref ListDigraph::changeSource() "changeSource()",
1.1383 + /// \warning Besides \c addNode() and \c addArc(), a digraph structure
1.1384 + /// may provide alternative ways to modify the digraph.
1.1385 + /// The correct behavior of InDegMap is not guarantied if these additional
1.1386 + /// features are used. For example the functions
1.1387 + /// \ref ListDigraph::changeSource() "changeSource()",
1.1388 /// \ref ListDigraph::changeTarget() "changeTarget()" and
1.1389 /// \ref ListDigraph::reverseArc() "reverseArc()"
1.1390 /// of \ref ListDigraph will \e not update the degree values correctly.
1.1391 ///
1.1392 /// \sa OutDegMap
1.1393 -
1.1394 - template <typename _Digraph>
1.1395 + template <typename GR>
1.1396 class InDegMap
1.1397 - : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1.1398 + : protected ItemSetTraits<GR, typename GR::Arc>
1.1399 ::ItemNotifier::ObserverBase {
1.1400
1.1401 public:
1.1402 -
1.1403 - typedef _Digraph Digraph;
1.1404 +
1.1405 + /// The graph type of InDegMap
1.1406 + typedef GR Graph;
1.1407 + typedef GR Digraph;
1.1408 + /// The key type
1.1409 + typedef typename Digraph::Node Key;
1.1410 + /// The value type
1.1411 typedef int Value;
1.1412 - typedef typename Digraph::Node Key;
1.1413
1.1414 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1.1415 ::ItemNotifier::ObserverBase Parent;
1.1416 @@ -2523,9 +2545,9 @@
1.1417
1.1418 /// \brief Constructor.
1.1419 ///
1.1420 - /// Constructor for creating in-degree map.
1.1421 - explicit InDegMap(const Digraph& digraph)
1.1422 - : _digraph(digraph), _deg(digraph) {
1.1423 + /// Constructor for creating an in-degree map.
1.1424 + explicit InDegMap(const Digraph& graph)
1.1425 + : _digraph(graph), _deg(graph) {
1.1426 Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1.1427
1.1428 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1429 @@ -2533,6 +2555,8 @@
1.1430 }
1.1431 }
1.1432
1.1433 + /// \brief Gives back the in-degree of a Node.
1.1434 + ///
1.1435 /// Gives back the in-degree of a Node.
1.1436 int operator[](const Key& key) const {
1.1437 return _deg[key];
1.1438 @@ -2579,33 +2603,37 @@
1.1439 AutoNodeMap _deg;
1.1440 };
1.1441
1.1442 - /// \brief Map of the node out-degrees.
1.1443 + /// \brief Map of the out-degrees of nodes in a digraph.
1.1444 ///
1.1445 /// This map returns the out-degree of a node. Once it is constructed,
1.1446 - /// the degrees are stored in a standard NodeMap, so each query is done
1.1447 + /// the degrees are stored in a standard \c NodeMap, so each query is done
1.1448 /// in constant time. On the other hand, the values are updated automatically
1.1449 /// whenever the digraph changes.
1.1450 ///
1.1451 - /// \warning Besides addNode() and addArc(), a digraph structure may provide
1.1452 - /// alternative ways to modify the digraph. The correct behavior of OutDegMap
1.1453 - /// is not guarantied if these additional features are used. For example
1.1454 - /// the functions \ref ListDigraph::changeSource() "changeSource()",
1.1455 + /// \warning Besides \c addNode() and \c addArc(), a digraph structure
1.1456 + /// may provide alternative ways to modify the digraph.
1.1457 + /// The correct behavior of OutDegMap is not guarantied if these additional
1.1458 + /// features are used. For example the functions
1.1459 + /// \ref ListDigraph::changeSource() "changeSource()",
1.1460 /// \ref ListDigraph::changeTarget() "changeTarget()" and
1.1461 /// \ref ListDigraph::reverseArc() "reverseArc()"
1.1462 /// of \ref ListDigraph will \e not update the degree values correctly.
1.1463 ///
1.1464 /// \sa InDegMap
1.1465 -
1.1466 - template <typename _Digraph>
1.1467 + template <typename GR>
1.1468 class OutDegMap
1.1469 - : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1.1470 + : protected ItemSetTraits<GR, typename GR::Arc>
1.1471 ::ItemNotifier::ObserverBase {
1.1472
1.1473 public:
1.1474
1.1475 - typedef _Digraph Digraph;
1.1476 + /// The graph type of OutDegMap
1.1477 + typedef GR Graph;
1.1478 + typedef GR Digraph;
1.1479 + /// The key type
1.1480 + typedef typename Digraph::Node Key;
1.1481 + /// The value type
1.1482 typedef int Value;
1.1483 - typedef typename Digraph::Node Key;
1.1484
1.1485 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1.1486 ::ItemNotifier::ObserverBase Parent;
1.1487 @@ -2645,9 +2673,9 @@
1.1488
1.1489 /// \brief Constructor.
1.1490 ///
1.1491 - /// Constructor for creating out-degree map.
1.1492 - explicit OutDegMap(const Digraph& digraph)
1.1493 - : _digraph(digraph), _deg(digraph) {
1.1494 + /// Constructor for creating an out-degree map.
1.1495 + explicit OutDegMap(const Digraph& graph)
1.1496 + : _digraph(graph), _deg(graph) {
1.1497 Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1.1498
1.1499 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1500 @@ -2655,6 +2683,8 @@
1.1501 }
1.1502 }
1.1503
1.1504 + /// \brief Gives back the out-degree of a Node.
1.1505 + ///
1.1506 /// Gives back the out-degree of a Node.
1.1507 int operator[](const Key& key) const {
1.1508 return _deg[key];
1.1509 @@ -2701,6 +2731,56 @@
1.1510 AutoNodeMap _deg;
1.1511 };
1.1512
1.1513 + /// \brief Potential difference map
1.1514 + ///
1.1515 + /// PotentialDifferenceMap returns the difference between the potentials of
1.1516 + /// the source and target nodes of each arc in a digraph, i.e. it returns
1.1517 + /// \code
1.1518 + /// potential[gr.target(arc)] - potential[gr.source(arc)].
1.1519 + /// \endcode
1.1520 + /// \tparam GR The digraph type.
1.1521 + /// \tparam POT A node map storing the potentials.
1.1522 + template <typename GR, typename POT>
1.1523 + class PotentialDifferenceMap {
1.1524 + public:
1.1525 + /// Key type
1.1526 + typedef typename GR::Arc Key;
1.1527 + /// Value type
1.1528 + typedef typename POT::Value Value;
1.1529 +
1.1530 + /// \brief Constructor
1.1531 + ///
1.1532 + /// Contructor of the map.
1.1533 + explicit PotentialDifferenceMap(const GR& gr,
1.1534 + const POT& potential)
1.1535 + : _digraph(gr), _potential(potential) {}
1.1536 +
1.1537 + /// \brief Returns the potential difference for the given arc.
1.1538 + ///
1.1539 + /// Returns the potential difference for the given arc, i.e.
1.1540 + /// \code
1.1541 + /// potential[gr.target(arc)] - potential[gr.source(arc)].
1.1542 + /// \endcode
1.1543 + Value operator[](const Key& arc) const {
1.1544 + return _potential[_digraph.target(arc)] -
1.1545 + _potential[_digraph.source(arc)];
1.1546 + }
1.1547 +
1.1548 + private:
1.1549 + const GR& _digraph;
1.1550 + const POT& _potential;
1.1551 + };
1.1552 +
1.1553 + /// \brief Returns a PotentialDifferenceMap.
1.1554 + ///
1.1555 + /// This function just returns a PotentialDifferenceMap.
1.1556 + /// \relates PotentialDifferenceMap
1.1557 + template <typename GR, typename POT>
1.1558 + PotentialDifferenceMap<GR, POT>
1.1559 + potentialDifferenceMap(const GR& gr, const POT& potential) {
1.1560 + return PotentialDifferenceMap<GR, POT>(gr, potential);
1.1561 + }
1.1562 +
1.1563 /// @}
1.1564 }
1.1565