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