1.1 --- a/lemon/maps.h Sun Oct 04 10:15:32 2009 +0200
1.2 +++ b/lemon/maps.h Wed Dec 09 11:14:06 2009 +0100
1.3 @@ -56,7 +56,7 @@
1.4 /// its type definitions, or if you have to provide a writable map,
1.5 /// but data written to it is not required (i.e. it will be sent to
1.6 /// <tt>/dev/null</tt>).
1.7 - /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.8 + /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.9 ///
1.10 /// \sa ConstMap
1.11 template<typename K, typename V>
1.12 @@ -89,7 +89,7 @@
1.13 /// value to each key.
1.14 ///
1.15 /// In other aspects it is equivalent to \c NullMap.
1.16 - /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
1.17 + /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
1.18 /// concept, but it absorbs the data written to it.
1.19 ///
1.20 /// The simplest way of using this map is through the constMap()
1.21 @@ -158,7 +158,7 @@
1.22 /// value to each key.
1.23 ///
1.24 /// In other aspects it is equivalent to \c NullMap.
1.25 - /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
1.26 + /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
1.27 /// concept, but it absorbs the data written to it.
1.28 ///
1.29 /// The simplest way of using this map is through the constMap()
1.30 @@ -230,10 +230,10 @@
1.31 ///
1.32 /// This map is essentially a wrapper for \c std::vector. It assigns
1.33 /// values to integer keys from the range <tt>[0..size-1]</tt>.
1.34 - /// It can be used with some data structures, for example
1.35 - /// \c UnionFind, \c BinHeap, when the used items are small
1.36 - /// integers. This map conforms the \ref concepts::ReferenceMap
1.37 - /// "ReferenceMap" concept.
1.38 + /// It can be used together with some data structures, e.g.
1.39 + /// heap types and \c UnionFind, when the used items are small
1.40 + /// integers. This map conforms to the \ref concepts::ReferenceMap
1.41 + /// "ReferenceMap" concept.
1.42 ///
1.43 /// The simplest way of using this map is through the rangeMap()
1.44 /// function.
1.45 @@ -340,7 +340,7 @@
1.46 /// that you can specify a default value for the keys that are not
1.47 /// stored actually. This value can be different from the default
1.48 /// contructed value (i.e. \c %Value()).
1.49 - /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
1.50 + /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
1.51 /// concept.
1.52 ///
1.53 /// This map is useful if a default value should be assigned to most of
1.54 @@ -348,9 +348,9 @@
1.55 /// keys (i.e. the map is "sparse").
1.56 /// The name of this type also refers to this important usage.
1.57 ///
1.58 - /// Apart form that this map can be used in many other cases since it
1.59 + /// Apart form that, this map can be used in many other cases since it
1.60 /// is based on \c std::map, which is a general associative container.
1.61 - /// However keep in mind that it is usually not as efficient as other
1.62 + /// However, keep in mind that it is usually not as efficient as other
1.63 /// maps.
1.64 ///
1.65 /// The simplest way of using this map is through the sparseMap()
1.66 @@ -706,7 +706,7 @@
1.67 /// "readable map" to another type using the default conversion.
1.68 /// The \c Key type of it is inherited from \c M and the \c Value
1.69 /// type is \c V.
1.70 - /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
1.71 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.72 ///
1.73 /// The simplest way of using this map is through the convertMap()
1.74 /// function.
1.75 @@ -1785,22 +1785,22 @@
1.76 ///
1.77 /// The most important usage of it is storing certain nodes or arcs
1.78 /// that were marked \c true by an algorithm.
1.79 - /// For example it makes easier to store the nodes in the processing
1.80 + /// For example, it makes easier to store the nodes in the processing
1.81 /// order of Dfs algorithm, as the following examples show.
1.82 /// \code
1.83 /// std::vector<Node> v;
1.84 - /// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
1.85 + /// dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
1.86 /// \endcode
1.87 /// \code
1.88 /// std::vector<Node> v(countNodes(g));
1.89 - /// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
1.90 + /// dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
1.91 /// \endcode
1.92 ///
1.93 /// \note The container of the iterator must contain enough space
1.94 /// for the elements or the iterator should be an inserter iterator.
1.95 ///
1.96 /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
1.97 - /// it cannot be used when a readable map is needed, for example as
1.98 + /// it cannot be used when a readable map is needed, for example, as
1.99 /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
1.100 ///
1.101 /// \relates LoggerBoolMap
1.102 @@ -1825,7 +1825,7 @@
1.103 /// Using this map you get access (i.e. can read) the inner id values of
1.104 /// the items stored in the graph, which is returned by the \c id()
1.105 /// function of the graph. This map can be inverted with its member
1.106 - /// class \c InverseMap or with the \c operator() member.
1.107 + /// class \c InverseMap or with the \c operator()() member.
1.108 ///
1.109 /// \tparam GR The graph type.
1.110 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1.111 @@ -1865,9 +1865,11 @@
1.112
1.113 public:
1.114
1.115 - /// \brief This class represents the inverse of its owner (IdMap).
1.116 + /// \brief The inverse map type of IdMap.
1.117 ///
1.118 - /// This class represents the inverse of its owner (IdMap).
1.119 + /// The inverse map type of IdMap. The subscript operator gives back
1.120 + /// an item by its id.
1.121 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.122 /// \see inverse()
1.123 class InverseMap {
1.124 public:
1.125 @@ -1882,9 +1884,9 @@
1.126 /// Constructor for creating an id-to-item map.
1.127 explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1.128
1.129 - /// \brief Gives back the given item from its id.
1.130 + /// \brief Gives back an item by its id.
1.131 ///
1.132 - /// Gives back the given item from its id.
1.133 + /// Gives back an item by its id.
1.134 Item operator[](int id) const { return _graph->fromId(id, Item());}
1.135
1.136 private:
1.137 @@ -1897,14 +1899,31 @@
1.138 InverseMap inverse() const { return InverseMap(*_graph);}
1.139 };
1.140
1.141 + /// \brief Returns an \c IdMap class.
1.142 + ///
1.143 + /// This function just returns an \c IdMap class.
1.144 + /// \relates IdMap
1.145 + template <typename K, typename GR>
1.146 + inline IdMap<GR, K> idMap(const GR& graph) {
1.147 + return IdMap<GR, K>(graph);
1.148 + }
1.149
1.150 /// \brief General cross reference graph map type.
1.151
1.152 /// This class provides simple invertable graph maps.
1.153 /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
1.154 /// and if a key is set to a new value, then stores it in the inverse map.
1.155 - /// The values of the map can be accessed
1.156 - /// with stl compatible forward iterator.
1.157 + /// The graph items can be accessed by their values either using
1.158 + /// \c InverseMap or \c operator()(), and the values of the map can be
1.159 + /// accessed with an STL compatible forward iterator (\c ValueIt).
1.160 + ///
1.161 + /// This map is intended to be used when all associated values are
1.162 + /// different (the map is actually invertable) or there are only a few
1.163 + /// items with the same value.
1.164 + /// Otherwise consider to use \c IterableValueMap, which is more
1.165 + /// suitable and more efficient for such cases. It provides iterators
1.166 + /// to traverse the items with the same associated value, but
1.167 + /// it does not have \c InverseMap.
1.168 ///
1.169 /// This type is not reference map, so it cannot be modified with
1.170 /// the subscript operator.
1.171 @@ -1945,56 +1964,66 @@
1.172
1.173 /// \brief Forward iterator for values.
1.174 ///
1.175 - /// This iterator is an stl compatible forward
1.176 + /// This iterator is an STL compatible forward
1.177 /// iterator on the values of the map. The values can
1.178 /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1.179 /// They are considered with multiplicity, so each value is
1.180 /// traversed for each item it is assigned to.
1.181 - class ValueIterator
1.182 + class ValueIt
1.183 : public std::iterator<std::forward_iterator_tag, Value> {
1.184 friend class CrossRefMap;
1.185 private:
1.186 - ValueIterator(typename Container::const_iterator _it)
1.187 + ValueIt(typename Container::const_iterator _it)
1.188 : it(_it) {}
1.189 public:
1.190
1.191 - ValueIterator() {}
1.192 -
1.193 - ValueIterator& operator++() { ++it; return *this; }
1.194 - ValueIterator operator++(int) {
1.195 - ValueIterator tmp(*this);
1.196 + /// Constructor
1.197 + ValueIt() {}
1.198 +
1.199 + /// \e
1.200 + ValueIt& operator++() { ++it; return *this; }
1.201 + /// \e
1.202 + ValueIt operator++(int) {
1.203 + ValueIt tmp(*this);
1.204 operator++();
1.205 return tmp;
1.206 }
1.207
1.208 + /// \e
1.209 const Value& operator*() const { return it->first; }
1.210 + /// \e
1.211 const Value* operator->() const { return &(it->first); }
1.212
1.213 - bool operator==(ValueIterator jt) const { return it == jt.it; }
1.214 - bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.215 + /// \e
1.216 + bool operator==(ValueIt jt) const { return it == jt.it; }
1.217 + /// \e
1.218 + bool operator!=(ValueIt jt) const { return it != jt.it; }
1.219
1.220 private:
1.221 typename Container::const_iterator it;
1.222 };
1.223 +
1.224 + /// Alias for \c ValueIt
1.225 + typedef ValueIt ValueIterator;
1.226
1.227 /// \brief Returns an iterator to the first value.
1.228 ///
1.229 - /// Returns an stl compatible iterator to the
1.230 + /// Returns an STL compatible iterator to the
1.231 /// first value of the map. The values of the
1.232 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.233 /// range.
1.234 - ValueIterator beginValue() const {
1.235 - return ValueIterator(_inv_map.begin());
1.236 + ValueIt beginValue() const {
1.237 + return ValueIt(_inv_map.begin());
1.238 }
1.239
1.240 /// \brief Returns an iterator after the last value.
1.241 ///
1.242 - /// Returns an stl compatible iterator after the
1.243 + /// Returns an STL compatible iterator after the
1.244 /// last value of the map. The values of the
1.245 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.246 /// range.
1.247 - ValueIterator endValue() const {
1.248 - return ValueIterator(_inv_map.end());
1.249 + ValueIt endValue() const {
1.250 + return ValueIt(_inv_map.end());
1.251 }
1.252
1.253 /// \brief Sets the value associated with the given key.
1.254 @@ -2032,6 +2061,14 @@
1.255 typename Container::const_iterator it = _inv_map.find(val);
1.256 return it != _inv_map.end() ? it->second : INVALID;
1.257 }
1.258 +
1.259 + /// \brief Returns the number of items with the given value.
1.260 + ///
1.261 + /// This function returns the number of items with the given value
1.262 + /// associated with it.
1.263 + int count(const Value &val) const {
1.264 + return _inv_map.count(val);
1.265 + }
1.266
1.267 protected:
1.268
1.269 @@ -2082,10 +2119,12 @@
1.270
1.271 public:
1.272
1.273 - /// \brief The inverse map type.
1.274 + /// \brief The inverse map type of CrossRefMap.
1.275 ///
1.276 - /// The inverse of this map. The subscript operator of the map
1.277 - /// gives back the item that was last assigned to the value.
1.278 + /// The inverse map type of CrossRefMap. The subscript operator gives
1.279 + /// back an item by its value.
1.280 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.281 + /// \see inverse()
1.282 class InverseMap {
1.283 public:
1.284 /// \brief Constructor
1.285 @@ -2112,20 +2151,20 @@
1.286 const CrossRefMap& _inverted;
1.287 };
1.288
1.289 - /// \brief It gives back the read-only inverse map.
1.290 + /// \brief Gives back the inverse of the map.
1.291 ///
1.292 - /// It gives back the read-only inverse map.
1.293 + /// Gives back the inverse of the CrossRefMap.
1.294 InverseMap inverse() const {
1.295 return InverseMap(*this);
1.296 }
1.297
1.298 };
1.299
1.300 - /// \brief Provides continuous and unique ID for the
1.301 + /// \brief Provides continuous and unique id for the
1.302 /// items of a graph.
1.303 ///
1.304 /// RangeIdMap provides a unique and continuous
1.305 - /// ID for each item of a given type (\c Node, \c Arc or
1.306 + /// id for each item of a given type (\c Node, \c Arc or
1.307 /// \c Edge) in a graph. This id is
1.308 /// - \b unique: different items get different ids,
1.309 /// - \b continuous: the range of the ids is the set of integers
1.310 @@ -2136,7 +2175,7 @@
1.311 /// Thus this id is not (necessarily) the same as what can get using
1.312 /// the \c id() function of the graph or \ref IdMap.
1.313 /// This map can be inverted with its member class \c InverseMap,
1.314 - /// or with the \c operator() member.
1.315 + /// or with the \c operator()() member.
1.316 ///
1.317 /// \tparam GR The graph type.
1.318 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1.319 @@ -2264,16 +2303,16 @@
1.320 _inv_map[pi] = q;
1.321 }
1.322
1.323 - /// \brief Gives back the \e RangeId of the item
1.324 + /// \brief Gives back the \e range \e id of the item
1.325 ///
1.326 - /// Gives back the \e RangeId of the item.
1.327 + /// Gives back the \e range \e id of the item.
1.328 int operator[](const Item& item) const {
1.329 return Map::operator[](item);
1.330 }
1.331
1.332 - /// \brief Gives back the item belonging to a \e RangeId
1.333 + /// \brief Gives back the item belonging to a \e range \e id
1.334 ///
1.335 - /// Gives back the item belonging to a \e RangeId.
1.336 + /// Gives back the item belonging to the given \e range \e id.
1.337 Item operator()(int id) const {
1.338 return _inv_map[id];
1.339 }
1.340 @@ -2287,7 +2326,9 @@
1.341
1.342 /// \brief The inverse map type of RangeIdMap.
1.343 ///
1.344 - /// The inverse map type of RangeIdMap.
1.345 + /// The inverse map type of RangeIdMap. The subscript operator gives
1.346 + /// back an item by its \e range \e id.
1.347 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.348 class InverseMap {
1.349 public:
1.350 /// \brief Constructor
1.351 @@ -2305,7 +2346,7 @@
1.352 /// \brief Subscript operator.
1.353 ///
1.354 /// Subscript operator. It gives back the item
1.355 - /// that the descriptor currently belongs to.
1.356 + /// that the given \e range \e id currently belongs to.
1.357 Value operator[](const Key& key) const {
1.358 return _inverted(key);
1.359 }
1.360 @@ -2323,18 +2364,27 @@
1.361
1.362 /// \brief Gives back the inverse of the map.
1.363 ///
1.364 - /// Gives back the inverse of the map.
1.365 + /// Gives back the inverse of the RangeIdMap.
1.366 const InverseMap inverse() const {
1.367 return InverseMap(*this);
1.368 }
1.369 };
1.370
1.371 + /// \brief Returns a \c RangeIdMap class.
1.372 + ///
1.373 + /// This function just returns an \c RangeIdMap class.
1.374 + /// \relates RangeIdMap
1.375 + template <typename K, typename GR>
1.376 + inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
1.377 + return RangeIdMap<GR, K>(graph);
1.378 + }
1.379 +
1.380 /// \brief Dynamic iterable \c bool map.
1.381 ///
1.382 /// This class provides a special graph map type which can store a
1.383 /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
1.384 /// For both \c true and \c false values it is possible to iterate on
1.385 - /// the keys.
1.386 + /// the keys mapped to the value.
1.387 ///
1.388 /// This type is a reference map, so it can be modified with the
1.389 /// subscript operator.
1.390 @@ -2703,6 +2753,11 @@
1.391 /// For each non-negative value it is possible to iterate on the keys
1.392 /// mapped to the value.
1.393 ///
1.394 + /// This map is intended to be used with small integer values, for which
1.395 + /// it is efficient, and supports iteration only for non-negative values.
1.396 + /// If you need large values and/or iteration for negative integers,
1.397 + /// consider to use \ref IterableValueMap instead.
1.398 + ///
1.399 /// This type is a reference map, so it can be modified with the
1.400 /// subscript operator.
1.401 ///
1.402 @@ -2984,15 +3039,17 @@
1.403
1.404 /// \brief Dynamic iterable map for comparable values.
1.405 ///
1.406 - /// This class provides a special graph map type which can store an
1.407 + /// This class provides a special graph map type which can store a
1.408 /// comparable value for graph items (\c Node, \c Arc or \c Edge).
1.409 /// For each value it is possible to iterate on the keys mapped to
1.410 - /// the value.
1.411 + /// the value (\c ItemIt), and the values of the map can be accessed
1.412 + /// with an STL compatible forward iterator (\c ValueIt).
1.413 + /// The map stores a linked list for each value, which contains
1.414 + /// the items mapped to the value, and the used values are stored
1.415 + /// in balanced binary tree (\c std::map).
1.416 ///
1.417 - /// The map stores for each value a linked list with
1.418 - /// the items which mapped to the value, and the values are stored
1.419 - /// in balanced binary tree. The values of the map can be accessed
1.420 - /// with stl compatible forward iterator.
1.421 + /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
1.422 + /// specialized for \c bool and \c int values, respectively.
1.423 ///
1.424 /// This type is not reference map, so it cannot be modified with
1.425 /// the subscript operator.
1.426 @@ -3071,31 +3128,38 @@
1.427
1.428 /// \brief Forward iterator for values.
1.429 ///
1.430 - /// This iterator is an stl compatible forward
1.431 + /// This iterator is an STL compatible forward
1.432 /// iterator on the values of the map. The values can
1.433 /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1.434 - class ValueIterator
1.435 + class ValueIt
1.436 : public std::iterator<std::forward_iterator_tag, Value> {
1.437 friend class IterableValueMap;
1.438 private:
1.439 - ValueIterator(typename std::map<Value, Key>::const_iterator _it)
1.440 + ValueIt(typename std::map<Value, Key>::const_iterator _it)
1.441 : it(_it) {}
1.442 public:
1.443
1.444 - ValueIterator() {}
1.445 -
1.446 - ValueIterator& operator++() { ++it; return *this; }
1.447 - ValueIterator operator++(int) {
1.448 - ValueIterator tmp(*this);
1.449 + /// Constructor
1.450 + ValueIt() {}
1.451 +
1.452 + /// \e
1.453 + ValueIt& operator++() { ++it; return *this; }
1.454 + /// \e
1.455 + ValueIt operator++(int) {
1.456 + ValueIt tmp(*this);
1.457 operator++();
1.458 return tmp;
1.459 }
1.460
1.461 + /// \e
1.462 const Value& operator*() const { return it->first; }
1.463 + /// \e
1.464 const Value* operator->() const { return &(it->first); }
1.465
1.466 - bool operator==(ValueIterator jt) const { return it == jt.it; }
1.467 - bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.468 + /// \e
1.469 + bool operator==(ValueIt jt) const { return it == jt.it; }
1.470 + /// \e
1.471 + bool operator!=(ValueIt jt) const { return it != jt.it; }
1.472
1.473 private:
1.474 typename std::map<Value, Key>::const_iterator it;
1.475 @@ -3103,22 +3167,22 @@
1.476
1.477 /// \brief Returns an iterator to the first value.
1.478 ///
1.479 - /// Returns an stl compatible iterator to the
1.480 + /// Returns an STL compatible iterator to the
1.481 /// first value of the map. The values of the
1.482 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.483 /// range.
1.484 - ValueIterator beginValue() const {
1.485 - return ValueIterator(_first.begin());
1.486 + ValueIt beginValue() const {
1.487 + return ValueIt(_first.begin());
1.488 }
1.489
1.490 /// \brief Returns an iterator after the last value.
1.491 ///
1.492 - /// Returns an stl compatible iterator after the
1.493 + /// Returns an STL compatible iterator after the
1.494 /// last value of the map. The values of the
1.495 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.496 /// range.
1.497 - ValueIterator endValue() const {
1.498 - return ValueIterator(_first.end());
1.499 + ValueIt endValue() const {
1.500 + return ValueIt(_first.end());
1.501 }
1.502
1.503 /// \brief Set operation of the map.
1.504 @@ -3236,9 +3300,9 @@
1.505 class SourceMap {
1.506 public:
1.507
1.508 - ///\e
1.509 + /// The key type (the \c Arc type of the digraph).
1.510 typedef typename GR::Arc Key;
1.511 - ///\e
1.512 + /// The value type (the \c Node type of the digraph).
1.513 typedef typename GR::Node Value;
1.514
1.515 /// \brief Constructor
1.516 @@ -3277,9 +3341,9 @@
1.517 class TargetMap {
1.518 public:
1.519
1.520 - ///\e
1.521 + /// The key type (the \c Arc type of the digraph).
1.522 typedef typename GR::Arc Key;
1.523 - ///\e
1.524 + /// The value type (the \c Node type of the digraph).
1.525 typedef typename GR::Node Value;
1.526
1.527 /// \brief Constructor
1.528 @@ -3319,8 +3383,10 @@
1.529 class ForwardMap {
1.530 public:
1.531
1.532 + /// The key type (the \c Edge type of the digraph).
1.533 + typedef typename GR::Edge Key;
1.534 + /// The value type (the \c Arc type of the digraph).
1.535 typedef typename GR::Arc Value;
1.536 - typedef typename GR::Edge Key;
1.537
1.538 /// \brief Constructor
1.539 ///
1.540 @@ -3359,8 +3425,10 @@
1.541 class BackwardMap {
1.542 public:
1.543
1.544 + /// The key type (the \c Edge type of the digraph).
1.545 + typedef typename GR::Edge Key;
1.546 + /// The value type (the \c Arc type of the digraph).
1.547 typedef typename GR::Arc Value;
1.548 - typedef typename GR::Edge Key;
1.549
1.550 /// \brief Constructor
1.551 ///
1.552 @@ -3398,7 +3466,7 @@
1.553 /// \warning Besides \c addNode() and \c addArc(), a digraph structure
1.554 /// may provide alternative ways to modify the digraph.
1.555 /// The correct behavior of InDegMap is not guarantied if these additional
1.556 - /// features are used. For example the functions
1.557 + /// features are used. For example, the functions
1.558 /// \ref ListDigraph::changeSource() "changeSource()",
1.559 /// \ref ListDigraph::changeTarget() "changeTarget()" and
1.560 /// \ref ListDigraph::reverseArc() "reverseArc()"
1.561 @@ -3528,7 +3596,7 @@
1.562 /// \warning Besides \c addNode() and \c addArc(), a digraph structure
1.563 /// may provide alternative ways to modify the digraph.
1.564 /// The correct behavior of OutDegMap is not guarantied if these additional
1.565 - /// features are used. For example the functions
1.566 + /// features are used. For example, the functions
1.567 /// \ref ListDigraph::changeSource() "changeSource()",
1.568 /// \ref ListDigraph::changeTarget() "changeTarget()" and
1.569 /// \ref ListDigraph::reverseArc() "reverseArc()"
1.570 @@ -3696,6 +3764,293 @@
1.571 return PotentialDifferenceMap<GR, POT>(gr, potential);
1.572 }
1.573
1.574 +
1.575 + /// \brief Copy the values of a graph map to another map.
1.576 + ///
1.577 + /// This function copies the values of a graph map to another graph map.
1.578 + /// \c To::Key must be equal or convertible to \c From::Key and
1.579 + /// \c From::Value must be equal or convertible to \c To::Value.
1.580 + ///
1.581 + /// For example, an edge map of \c int value type can be copied to
1.582 + /// an arc map of \c double value type in an undirected graph, but
1.583 + /// an arc map cannot be copied to an edge map.
1.584 + /// Note that even a \ref ConstMap can be copied to a standard graph map,
1.585 + /// but \ref mapFill() can also be used for this purpose.
1.586 + ///
1.587 + /// \param gr The graph for which the maps are defined.
1.588 + /// \param from The map from which the values have to be copied.
1.589 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.590 + /// \param to The map to which the values have to be copied.
1.591 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.592 + template <typename GR, typename From, typename To>
1.593 + void mapCopy(const GR& gr, const From& from, To& to) {
1.594 + typedef typename To::Key Item;
1.595 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.596 +
1.597 + for (ItemIt it(gr); it != INVALID; ++it) {
1.598 + to.set(it, from[it]);
1.599 + }
1.600 + }
1.601 +
1.602 + /// \brief Compare two graph maps.
1.603 + ///
1.604 + /// This function compares the values of two graph maps. It returns
1.605 + /// \c true if the maps assign the same value for all items in the graph.
1.606 + /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
1.607 + /// and their \c Value types must be comparable using \c %operator==().
1.608 + ///
1.609 + /// \param gr The graph for which the maps are defined.
1.610 + /// \param map1 The first map.
1.611 + /// \param map2 The second map.
1.612 + template <typename GR, typename Map1, typename Map2>
1.613 + bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
1.614 + typedef typename Map2::Key Item;
1.615 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.616 +
1.617 + for (ItemIt it(gr); it != INVALID; ++it) {
1.618 + if (!(map1[it] == map2[it])) return false;
1.619 + }
1.620 + return true;
1.621 + }
1.622 +
1.623 + /// \brief Return an item having minimum value of a graph map.
1.624 + ///
1.625 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.626 + /// minimum value of the given graph map.
1.627 + /// If the item set is empty, it returns \c INVALID.
1.628 + ///
1.629 + /// \param gr The graph for which the map is defined.
1.630 + /// \param map The graph map.
1.631 + template <typename GR, typename Map>
1.632 + typename Map::Key mapMin(const GR& gr, const Map& map) {
1.633 + return mapMin(gr, map, std::less<typename Map::Value>());
1.634 + }
1.635 +
1.636 + /// \brief Return an item having minimum value of a graph map.
1.637 + ///
1.638 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.639 + /// minimum value of the given graph map.
1.640 + /// If the item set is empty, it returns \c INVALID.
1.641 + ///
1.642 + /// \param gr The graph for which the map is defined.
1.643 + /// \param map The graph map.
1.644 + /// \param comp Comparison function object.
1.645 + template <typename GR, typename Map, typename Comp>
1.646 + typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
1.647 + typedef typename Map::Key Item;
1.648 + typedef typename Map::Value Value;
1.649 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.650 +
1.651 + ItemIt min_item(gr);
1.652 + if (min_item == INVALID) return INVALID;
1.653 + Value min = map[min_item];
1.654 + for (ItemIt it(gr); it != INVALID; ++it) {
1.655 + if (comp(map[it], min)) {
1.656 + min = map[it];
1.657 + min_item = it;
1.658 + }
1.659 + }
1.660 + return min_item;
1.661 + }
1.662 +
1.663 + /// \brief Return an item having maximum value of a graph map.
1.664 + ///
1.665 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.666 + /// maximum value of the given graph map.
1.667 + /// If the item set is empty, it returns \c INVALID.
1.668 + ///
1.669 + /// \param gr The graph for which the map is defined.
1.670 + /// \param map The graph map.
1.671 + template <typename GR, typename Map>
1.672 + typename Map::Key mapMax(const GR& gr, const Map& map) {
1.673 + return mapMax(gr, map, std::less<typename Map::Value>());
1.674 + }
1.675 +
1.676 + /// \brief Return an item having maximum value of a graph map.
1.677 + ///
1.678 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.679 + /// maximum value of the given graph map.
1.680 + /// If the item set is empty, it returns \c INVALID.
1.681 + ///
1.682 + /// \param gr The graph for which the map is defined.
1.683 + /// \param map The graph map.
1.684 + /// \param comp Comparison function object.
1.685 + template <typename GR, typename Map, typename Comp>
1.686 + typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
1.687 + typedef typename Map::Key Item;
1.688 + typedef typename Map::Value Value;
1.689 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.690 +
1.691 + ItemIt max_item(gr);
1.692 + if (max_item == INVALID) return INVALID;
1.693 + Value max = map[max_item];
1.694 + for (ItemIt it(gr); it != INVALID; ++it) {
1.695 + if (comp(max, map[it])) {
1.696 + max = map[it];
1.697 + max_item = it;
1.698 + }
1.699 + }
1.700 + return max_item;
1.701 + }
1.702 +
1.703 + /// \brief Return the minimum value of a graph map.
1.704 + ///
1.705 + /// This function returns the minimum value of the given graph map.
1.706 + /// The corresponding item set of the graph must not be empty.
1.707 + ///
1.708 + /// \param gr The graph for which the map is defined.
1.709 + /// \param map The graph map.
1.710 + template <typename GR, typename Map>
1.711 + typename Map::Value mapMinValue(const GR& gr, const Map& map) {
1.712 + return map[mapMin(gr, map, std::less<typename Map::Value>())];
1.713 + }
1.714 +
1.715 + /// \brief Return the minimum value of a graph map.
1.716 + ///
1.717 + /// This function returns the minimum value of the given graph map.
1.718 + /// The corresponding item set of the graph must not be empty.
1.719 + ///
1.720 + /// \param gr The graph for which the map is defined.
1.721 + /// \param map The graph map.
1.722 + /// \param comp Comparison function object.
1.723 + template <typename GR, typename Map, typename Comp>
1.724 + typename Map::Value
1.725 + mapMinValue(const GR& gr, const Map& map, const Comp& comp) {
1.726 + return map[mapMin(gr, map, comp)];
1.727 + }
1.728 +
1.729 + /// \brief Return the maximum value of a graph map.
1.730 + ///
1.731 + /// This function returns the maximum value of the given graph map.
1.732 + /// The corresponding item set of the graph must not be empty.
1.733 + ///
1.734 + /// \param gr The graph for which the map is defined.
1.735 + /// \param map The graph map.
1.736 + template <typename GR, typename Map>
1.737 + typename Map::Value mapMaxValue(const GR& gr, const Map& map) {
1.738 + return map[mapMax(gr, map, std::less<typename Map::Value>())];
1.739 + }
1.740 +
1.741 + /// \brief Return the maximum value of a graph map.
1.742 + ///
1.743 + /// This function returns the maximum value of the given graph map.
1.744 + /// The corresponding item set of the graph must not be empty.
1.745 + ///
1.746 + /// \param gr The graph for which the map is defined.
1.747 + /// \param map The graph map.
1.748 + /// \param comp Comparison function object.
1.749 + template <typename GR, typename Map, typename Comp>
1.750 + typename Map::Value
1.751 + mapMaxValue(const GR& gr, const Map& map, const Comp& comp) {
1.752 + return map[mapMax(gr, map, comp)];
1.753 + }
1.754 +
1.755 + /// \brief Return an item having a specified value in a graph map.
1.756 + ///
1.757 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.758 + /// the specified assigned value in the given graph map.
1.759 + /// If no such item exists, it returns \c INVALID.
1.760 + ///
1.761 + /// \param gr The graph for which the map is defined.
1.762 + /// \param map The graph map.
1.763 + /// \param val The value that have to be found.
1.764 + template <typename GR, typename Map>
1.765 + typename Map::Key
1.766 + mapFind(const GR& gr, const Map& map, const typename Map::Value& val) {
1.767 + typedef typename Map::Key Item;
1.768 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.769 +
1.770 + for (ItemIt it(gr); it != INVALID; ++it) {
1.771 + if (map[it] == val) return it;
1.772 + }
1.773 + return INVALID;
1.774 + }
1.775 +
1.776 + /// \brief Return an item having value for which a certain predicate is
1.777 + /// true in a graph map.
1.778 + ///
1.779 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.780 + /// such assigned value for which the specified predicate is true
1.781 + /// in the given graph map.
1.782 + /// If no such item exists, it returns \c INVALID.
1.783 + ///
1.784 + /// \param gr The graph for which the map is defined.
1.785 + /// \param map The graph map.
1.786 + /// \param pred The predicate function object.
1.787 + template <typename GR, typename Map, typename Pred>
1.788 + typename Map::Key
1.789 + mapFindIf(const GR& gr, const Map& map, const Pred& pred) {
1.790 + typedef typename Map::Key Item;
1.791 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.792 +
1.793 + for (ItemIt it(gr); it != INVALID; ++it) {
1.794 + if (pred(map[it])) return it;
1.795 + }
1.796 + return INVALID;
1.797 + }
1.798 +
1.799 + /// \brief Return the number of items having a specified value in a
1.800 + /// graph map.
1.801 + ///
1.802 + /// This function returns the number of items (\c Node, \c Arc or \c Edge)
1.803 + /// having the specified assigned value in the given graph map.
1.804 + ///
1.805 + /// \param gr The graph for which the map is defined.
1.806 + /// \param map The graph map.
1.807 + /// \param val The value that have to be counted.
1.808 + template <typename GR, typename Map>
1.809 + int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) {
1.810 + typedef typename Map::Key Item;
1.811 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.812 +
1.813 + int cnt = 0;
1.814 + for (ItemIt it(gr); it != INVALID; ++it) {
1.815 + if (map[it] == val) ++cnt;
1.816 + }
1.817 + return cnt;
1.818 + }
1.819 +
1.820 + /// \brief Return the number of items having values for which a certain
1.821 + /// predicate is true in a graph map.
1.822 + ///
1.823 + /// This function returns the number of items (\c Node, \c Arc or \c Edge)
1.824 + /// having such assigned values for which the specified predicate is true
1.825 + /// in the given graph map.
1.826 + ///
1.827 + /// \param gr The graph for which the map is defined.
1.828 + /// \param map The graph map.
1.829 + /// \param pred The predicate function object.
1.830 + template <typename GR, typename Map, typename Pred>
1.831 + int mapCountIf(const GR& gr, const Map& map, const Pred& pred) {
1.832 + typedef typename Map::Key Item;
1.833 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.834 +
1.835 + int cnt = 0;
1.836 + for (ItemIt it(gr); it != INVALID; ++it) {
1.837 + if (pred(map[it])) ++cnt;
1.838 + }
1.839 + return cnt;
1.840 + }
1.841 +
1.842 + /// \brief Fill a graph map with a certain value.
1.843 + ///
1.844 + /// This function sets the specified value for all items (\c Node,
1.845 + /// \c Arc or \c Edge) in the given graph map.
1.846 + ///
1.847 + /// \param gr The graph for which the map is defined.
1.848 + /// \param map The graph map. It must conform to the
1.849 + /// \ref concepts::WriteMap "WriteMap" concept.
1.850 + /// \param val The value.
1.851 + template <typename GR, typename Map>
1.852 + void mapFill(const GR& gr, Map& map, const typename Map::Value& val) {
1.853 + typedef typename Map::Key Item;
1.854 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.855 +
1.856 + for (ItemIt it(gr); it != INVALID; ++it) {
1.857 + map.set(it, val);
1.858 + }
1.859 + }
1.860 +
1.861 /// @}
1.862 }
1.863