lemon/maps.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 17 Sep 2008 15:04:21 +0100
changeset 264 b6b9e7576af7
parent 209 765619b7cbb2
child 280 e7f8647ce760
permissions -rw-r--r--
Merge
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_MAPS_H
    20 #define LEMON_MAPS_H
    21 
    22 #include <iterator>
    23 #include <functional>
    24 #include <vector>
    25 
    26 #include <lemon/core.h>
    27 
    28 ///\file
    29 ///\ingroup maps
    30 ///\brief Miscellaneous property maps
    31 
    32 #include <map>
    33 
    34 namespace lemon {
    35 
    36   /// \addtogroup maps
    37   /// @{
    38 
    39   /// Base class of maps.
    40 
    41   /// Base class of maps. It provides the necessary type definitions
    42   /// required by the map %concepts.
    43   template<typename K, typename V>
    44   class MapBase {
    45   public:
    46     /// \biref The key type of the map.
    47     typedef K Key;
    48     /// \brief The value type of the map.
    49     /// (The type of objects associated with the keys).
    50     typedef V Value;
    51   };
    52 
    53 
    54   /// Null map. (a.k.a. DoNothingMap)
    55 
    56   /// This map can be used if you have to provide a map only for
    57   /// its type definitions, or if you have to provide a writable map,
    58   /// but data written to it is not required (i.e. it will be sent to
    59   /// <tt>/dev/null</tt>).
    60   /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    61   ///
    62   /// \sa ConstMap
    63   template<typename K, typename V>
    64   class NullMap : public MapBase<K, V> {
    65   public:
    66     typedef MapBase<K, V> Parent;
    67     typedef typename Parent::Key Key;
    68     typedef typename Parent::Value Value;
    69 
    70     /// Gives back a default constructed element.
    71     Value operator[](const Key&) const { return Value(); }
    72     /// Absorbs the value.
    73     void set(const Key&, const Value&) {}
    74   };
    75 
    76   /// Returns a \ref NullMap class
    77 
    78   /// This function just returns a \ref NullMap class.
    79   /// \relates NullMap
    80   template <typename K, typename V>
    81   NullMap<K, V> nullMap() {
    82     return NullMap<K, V>();
    83   }
    84 
    85 
    86   /// Constant map.
    87 
    88   /// This \ref concepts::ReadMap "readable map" assigns a specified
    89   /// value to each key.
    90   ///
    91   /// In other aspects it is equivalent to \ref NullMap.
    92   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
    93   /// concept, but it absorbs the data written to it.
    94   ///
    95   /// The simplest way of using this map is through the constMap()
    96   /// function.
    97   ///
    98   /// \sa NullMap
    99   /// \sa IdentityMap
   100   template<typename K, typename V>
   101   class ConstMap : public MapBase<K, V> {
   102   private:
   103     V _value;
   104   public:
   105     typedef MapBase<K, V> Parent;
   106     typedef typename Parent::Key Key;
   107     typedef typename Parent::Value Value;
   108 
   109     /// Default constructor
   110 
   111     /// Default constructor.
   112     /// The value of the map will be default constructed.
   113     ConstMap() {}
   114 
   115     /// Constructor with specified initial value
   116 
   117     /// Constructor with specified initial value.
   118     /// \param v The initial value of the map.
   119     ConstMap(const Value &v) : _value(v) {}
   120 
   121     /// Gives back the specified value.
   122     Value operator[](const Key&) const { return _value; }
   123 
   124     /// Absorbs the value.
   125     void set(const Key&, const Value&) {}
   126 
   127     /// Sets the value that is assigned to each key.
   128     void setAll(const Value &v) {
   129       _value = v;
   130     }
   131 
   132     template<typename V1>
   133     ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
   134   };
   135 
   136   /// Returns a \ref ConstMap class
   137 
   138   /// This function just returns a \ref ConstMap class.
   139   /// \relates ConstMap
   140   template<typename K, typename V>
   141   inline ConstMap<K, V> constMap(const V &v) {
   142     return ConstMap<K, V>(v);
   143   }
   144 
   145   template<typename K, typename V>
   146   inline ConstMap<K, V> constMap() {
   147     return ConstMap<K, V>();
   148   }
   149 
   150 
   151   template<typename T, T v>
   152   struct Const {};
   153 
   154   /// Constant map with inlined constant value.
   155 
   156   /// This \ref concepts::ReadMap "readable map" assigns a specified
   157   /// value to each key.
   158   ///
   159   /// In other aspects it is equivalent to \ref NullMap.
   160   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
   161   /// concept, but it absorbs the data written to it.
   162   ///
   163   /// The simplest way of using this map is through the constMap()
   164   /// function.
   165   ///
   166   /// \sa NullMap
   167   /// \sa IdentityMap
   168   template<typename K, typename V, V v>
   169   class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
   170   public:
   171     typedef MapBase<K, V> Parent;
   172     typedef typename Parent::Key Key;
   173     typedef typename Parent::Value Value;
   174 
   175     /// Constructor.
   176     ConstMap() {}
   177 
   178     /// Gives back the specified value.
   179     Value operator[](const Key&) const { return v; }
   180 
   181     /// Absorbs the value.
   182     void set(const Key&, const Value&) {}
   183   };
   184 
   185   /// Returns a \ref ConstMap class with inlined constant value
   186 
   187   /// This function just returns a \ref ConstMap class with inlined
   188   /// constant value.
   189   /// \relates ConstMap
   190   template<typename K, typename V, V v>
   191   inline ConstMap<K, Const<V, v> > constMap() {
   192     return ConstMap<K, Const<V, v> >();
   193   }
   194 
   195 
   196   /// Identity map.
   197 
   198   /// This \ref concepts::ReadMap "read-only map" gives back the given
   199   /// key as value without any modification.
   200   ///
   201   /// \sa ConstMap
   202   template <typename T>
   203   class IdentityMap : public MapBase<T, T> {
   204   public:
   205     typedef MapBase<T, T> Parent;
   206     typedef typename Parent::Key Key;
   207     typedef typename Parent::Value Value;
   208 
   209     /// Gives back the given value without any modification.
   210     Value operator[](const Key &k) const {
   211       return k;
   212     }
   213   };
   214 
   215   /// Returns an \ref IdentityMap class
   216 
   217   /// This function just returns an \ref IdentityMap class.
   218   /// \relates IdentityMap
   219   template<typename T>
   220   inline IdentityMap<T> identityMap() {
   221     return IdentityMap<T>();
   222   }
   223 
   224 
   225   /// \brief Map for storing values for integer keys from the range
   226   /// <tt>[0..size-1]</tt>.
   227   ///
   228   /// This map is essentially a wrapper for \c std::vector. It assigns
   229   /// values to integer keys from the range <tt>[0..size-1]</tt>.
   230   /// It can be used with some data structures, for example
   231   /// \ref UnionFind, \ref BinHeap, when the used items are small
   232   /// integers. This map conforms the \ref concepts::ReferenceMap
   233   /// "ReferenceMap" concept.
   234   ///
   235   /// The simplest way of using this map is through the rangeMap()
   236   /// function.
   237   template <typename V>
   238   class RangeMap : public MapBase<int, V> {
   239     template <typename V1>
   240     friend class RangeMap;
   241   private:
   242 
   243     typedef std::vector<V> Vector;
   244     Vector _vector;
   245 
   246   public:
   247 
   248     typedef MapBase<int, V> Parent;
   249     /// Key type
   250     typedef typename Parent::Key Key;
   251     /// Value type
   252     typedef typename Parent::Value Value;
   253     /// Reference type
   254     typedef typename Vector::reference Reference;
   255     /// Const reference type
   256     typedef typename Vector::const_reference ConstReference;
   257 
   258     typedef True ReferenceMapTag;
   259 
   260   public:
   261 
   262     /// Constructor with specified default value.
   263     RangeMap(int size = 0, const Value &value = Value())
   264       : _vector(size, value) {}
   265 
   266     /// Constructs the map from an appropriate \c std::vector.
   267     template <typename V1>
   268     RangeMap(const std::vector<V1>& vector)
   269       : _vector(vector.begin(), vector.end()) {}
   270 
   271     /// Constructs the map from another \ref RangeMap.
   272     template <typename V1>
   273     RangeMap(const RangeMap<V1> &c)
   274       : _vector(c._vector.begin(), c._vector.end()) {}
   275 
   276     /// Returns the size of the map.
   277     int size() {
   278       return _vector.size();
   279     }
   280 
   281     /// Resizes the map.
   282 
   283     /// Resizes the underlying \c std::vector container, so changes the
   284     /// keyset of the map.
   285     /// \param size The new size of the map. The new keyset will be the
   286     /// range <tt>[0..size-1]</tt>.
   287     /// \param value The default value to assign to the new keys.
   288     void resize(int size, const Value &value = Value()) {
   289       _vector.resize(size, value);
   290     }
   291 
   292   private:
   293 
   294     RangeMap& operator=(const RangeMap&);
   295 
   296   public:
   297 
   298     ///\e
   299     Reference operator[](const Key &k) {
   300       return _vector[k];
   301     }
   302 
   303     ///\e
   304     ConstReference operator[](const Key &k) const {
   305       return _vector[k];
   306     }
   307 
   308     ///\e
   309     void set(const Key &k, const Value &v) {
   310       _vector[k] = v;
   311     }
   312   };
   313 
   314   /// Returns a \ref RangeMap class
   315 
   316   /// This function just returns a \ref RangeMap class.
   317   /// \relates RangeMap
   318   template<typename V>
   319   inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
   320     return RangeMap<V>(size, value);
   321   }
   322 
   323   /// \brief Returns a \ref RangeMap class created from an appropriate
   324   /// \c std::vector
   325 
   326   /// This function just returns a \ref RangeMap class created from an
   327   /// appropriate \c std::vector.
   328   /// \relates RangeMap
   329   template<typename V>
   330   inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
   331     return RangeMap<V>(vector);
   332   }
   333 
   334 
   335   /// Map type based on \c std::map
   336 
   337   /// This map is essentially a wrapper for \c std::map with addition
   338   /// that you can specify a default value for the keys that are not
   339   /// stored actually. This value can be different from the default
   340   /// contructed value (i.e. \c %Value()).
   341   /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
   342   /// concept.
   343   ///
   344   /// This map is useful if a default value should be assigned to most of
   345   /// the keys and different values should be assigned only to a few
   346   /// keys (i.e. the map is "sparse").
   347   /// The name of this type also refers to this important usage.
   348   ///
   349   /// Apart form that this map can be used in many other cases since it
   350   /// is based on \c std::map, which is a general associative container.
   351   /// However keep in mind that it is usually not as efficient as other
   352   /// maps.
   353   ///
   354   /// The simplest way of using this map is through the sparseMap()
   355   /// function.
   356   template <typename K, typename V, typename Compare = std::less<K> >
   357   class SparseMap : public MapBase<K, V> {
   358     template <typename K1, typename V1, typename C1>
   359     friend class SparseMap;
   360   public:
   361 
   362     typedef MapBase<K, V> Parent;
   363     /// Key type
   364     typedef typename Parent::Key Key;
   365     /// Value type
   366     typedef typename Parent::Value Value;
   367     /// Reference type
   368     typedef Value& Reference;
   369     /// Const reference type
   370     typedef const Value& ConstReference;
   371 
   372     typedef True ReferenceMapTag;
   373 
   374   private:
   375 
   376     typedef std::map<K, V, Compare> Map;
   377     Map _map;
   378     Value _value;
   379 
   380   public:
   381 
   382     /// \brief Constructor with specified default value.
   383     SparseMap(const Value &value = Value()) : _value(value) {}
   384     /// \brief Constructs the map from an appropriate \c std::map, and
   385     /// explicitly specifies a default value.
   386     template <typename V1, typename Comp1>
   387     SparseMap(const std::map<Key, V1, Comp1> &map,
   388               const Value &value = Value())
   389       : _map(map.begin(), map.end()), _value(value) {}
   390 
   391     /// \brief Constructs the map from another \ref SparseMap.
   392     template<typename V1, typename Comp1>
   393     SparseMap(const SparseMap<Key, V1, Comp1> &c)
   394       : _map(c._map.begin(), c._map.end()), _value(c._value) {}
   395 
   396   private:
   397 
   398     SparseMap& operator=(const SparseMap&);
   399 
   400   public:
   401 
   402     ///\e
   403     Reference operator[](const Key &k) {
   404       typename Map::iterator it = _map.lower_bound(k);
   405       if (it != _map.end() && !_map.key_comp()(k, it->first))
   406         return it->second;
   407       else
   408         return _map.insert(it, std::make_pair(k, _value))->second;
   409     }
   410 
   411     ///\e
   412     ConstReference operator[](const Key &k) const {
   413       typename Map::const_iterator it = _map.find(k);
   414       if (it != _map.end())
   415         return it->second;
   416       else
   417         return _value;
   418     }
   419 
   420     ///\e
   421     void set(const Key &k, const Value &v) {
   422       typename Map::iterator it = _map.lower_bound(k);
   423       if (it != _map.end() && !_map.key_comp()(k, it->first))
   424         it->second = v;
   425       else
   426         _map.insert(it, std::make_pair(k, v));
   427     }
   428 
   429     ///\e
   430     void setAll(const Value &v) {
   431       _value = v;
   432       _map.clear();
   433     }
   434   };
   435 
   436   /// Returns a \ref SparseMap class
   437 
   438   /// This function just returns a \ref SparseMap class with specified
   439   /// default value.
   440   /// \relates SparseMap
   441   template<typename K, typename V, typename Compare>
   442   inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
   443     return SparseMap<K, V, Compare>(value);
   444   }
   445 
   446   template<typename K, typename V>
   447   inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
   448     return SparseMap<K, V, std::less<K> >(value);
   449   }
   450 
   451   /// \brief Returns a \ref SparseMap class created from an appropriate
   452   /// \c std::map
   453 
   454   /// This function just returns a \ref SparseMap class created from an
   455   /// appropriate \c std::map.
   456   /// \relates SparseMap
   457   template<typename K, typename V, typename Compare>
   458   inline SparseMap<K, V, Compare>
   459     sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
   460   {
   461     return SparseMap<K, V, Compare>(map, value);
   462   }
   463 
   464   /// @}
   465 
   466   /// \addtogroup map_adaptors
   467   /// @{
   468 
   469   /// Composition of two maps
   470 
   471   /// This \ref concepts::ReadMap "read-only map" returns the
   472   /// composition of two given maps. That is to say, if \c m1 is of
   473   /// type \c M1 and \c m2 is of \c M2, then for
   474   /// \code
   475   ///   ComposeMap<M1, M2> cm(m1,m2);
   476   /// \endcode
   477   /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
   478   ///
   479   /// The \c Key type of the map is inherited from \c M2 and the
   480   /// \c Value type is from \c M1.
   481   /// \c M2::Value must be convertible to \c M1::Key.
   482   ///
   483   /// The simplest way of using this map is through the composeMap()
   484   /// function.
   485   ///
   486   /// \sa CombineMap
   487   ///
   488   /// \todo Check the requirements.
   489   template <typename M1, typename M2>
   490   class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
   491     const M1 &_m1;
   492     const M2 &_m2;
   493   public:
   494     typedef MapBase<typename M2::Key, typename M1::Value> Parent;
   495     typedef typename Parent::Key Key;
   496     typedef typename Parent::Value Value;
   497 
   498     /// Constructor
   499     ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   500 
   501     /// \e
   502     typename MapTraits<M1>::ConstReturnValue
   503     operator[](const Key &k) const { return _m1[_m2[k]]; }
   504   };
   505 
   506   /// Returns a \ref ComposeMap class
   507 
   508   /// This function just returns a \ref ComposeMap class.
   509   ///
   510   /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
   511   /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
   512   /// will be equal to <tt>m1[m2[x]]</tt>.
   513   ///
   514   /// \relates ComposeMap
   515   template <typename M1, typename M2>
   516   inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
   517     return ComposeMap<M1, M2>(m1, m2);
   518   }
   519 
   520 
   521   /// Combination of two maps using an STL (binary) functor.
   522 
   523   /// This \ref concepts::ReadMap "read-only map" takes two maps and a
   524   /// binary functor and returns the combination of the two given maps
   525   /// using the functor.
   526   /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
   527   /// and \c f is of \c F, then for
   528   /// \code
   529   ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
   530   /// \endcode
   531   /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
   532   ///
   533   /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
   534   /// must be convertible to \c M2::Key) and the \c Value type is \c V.
   535   /// \c M2::Value and \c M1::Value must be convertible to the
   536   /// corresponding input parameter of \c F and the return type of \c F
   537   /// must be convertible to \c V.
   538   ///
   539   /// The simplest way of using this map is through the combineMap()
   540   /// function.
   541   ///
   542   /// \sa ComposeMap
   543   ///
   544   /// \todo Check the requirements.
   545   template<typename M1, typename M2, typename F,
   546            typename V = typename F::result_type>
   547   class CombineMap : public MapBase<typename M1::Key, V> {
   548     const M1 &_m1;
   549     const M2 &_m2;
   550     F _f;
   551   public:
   552     typedef MapBase<typename M1::Key, V> Parent;
   553     typedef typename Parent::Key Key;
   554     typedef typename Parent::Value Value;
   555 
   556     /// Constructor
   557     CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
   558       : _m1(m1), _m2(m2), _f(f) {}
   559     /// \e
   560     Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
   561   };
   562 
   563   /// Returns a \ref CombineMap class
   564 
   565   /// This function just returns a \ref CombineMap class.
   566   ///
   567   /// For example, if \c m1 and \c m2 are both maps with \c double
   568   /// values, then
   569   /// \code
   570   ///   combineMap(m1,m2,std::plus<double>())
   571   /// \endcode
   572   /// is equivalent to
   573   /// \code
   574   ///   addMap(m1,m2)
   575   /// \endcode
   576   ///
   577   /// This function is specialized for adaptable binary function
   578   /// classes and C++ functions.
   579   ///
   580   /// \relates CombineMap
   581   template<typename M1, typename M2, typename F, typename V>
   582   inline CombineMap<M1, M2, F, V>
   583   combineMap(const M1 &m1, const M2 &m2, const F &f) {
   584     return CombineMap<M1, M2, F, V>(m1,m2,f);
   585   }
   586 
   587   template<typename M1, typename M2, typename F>
   588   inline CombineMap<M1, M2, F, typename F::result_type>
   589   combineMap(const M1 &m1, const M2 &m2, const F &f) {
   590     return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
   591   }
   592 
   593   template<typename M1, typename M2, typename K1, typename K2, typename V>
   594   inline CombineMap<M1, M2, V (*)(K1, K2), V>
   595   combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
   596     return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
   597   }
   598 
   599 
   600   /// Converts an STL style (unary) functor to a map
   601 
   602   /// This \ref concepts::ReadMap "read-only map" returns the value
   603   /// of a given functor. Actually, it just wraps the functor and
   604   /// provides the \c Key and \c Value typedefs.
   605   ///
   606   /// Template parameters \c K and \c V will become its \c Key and
   607   /// \c Value. In most cases they have to be given explicitly because
   608   /// a functor typically does not provide \c argument_type and
   609   /// \c result_type typedefs.
   610   /// Parameter \c F is the type of the used functor.
   611   ///
   612   /// The simplest way of using this map is through the functorToMap()
   613   /// function.
   614   ///
   615   /// \sa MapToFunctor
   616   template<typename F,
   617            typename K = typename F::argument_type,
   618            typename V = typename F::result_type>
   619   class FunctorToMap : public MapBase<K, V> {
   620     F _f;
   621   public:
   622     typedef MapBase<K, V> Parent;
   623     typedef typename Parent::Key Key;
   624     typedef typename Parent::Value Value;
   625 
   626     /// Constructor
   627     FunctorToMap(const F &f = F()) : _f(f) {}
   628     /// \e
   629     Value operator[](const Key &k) const { return _f(k); }
   630   };
   631 
   632   /// Returns a \ref FunctorToMap class
   633 
   634   /// This function just returns a \ref FunctorToMap class.
   635   ///
   636   /// This function is specialized for adaptable binary function
   637   /// classes and C++ functions.
   638   ///
   639   /// \relates FunctorToMap
   640   template<typename K, typename V, typename F>
   641   inline FunctorToMap<F, K, V> functorToMap(const F &f) {
   642     return FunctorToMap<F, K, V>(f);
   643   }
   644 
   645   template <typename F>
   646   inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
   647     functorToMap(const F &f)
   648   {
   649     return FunctorToMap<F, typename F::argument_type,
   650       typename F::result_type>(f);
   651   }
   652 
   653   template <typename K, typename V>
   654   inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
   655     return FunctorToMap<V (*)(K), K, V>(f);
   656   }
   657 
   658 
   659   /// Converts a map to an STL style (unary) functor
   660 
   661   /// This class converts a map to an STL style (unary) functor.
   662   /// That is it provides an <tt>operator()</tt> to read its values.
   663   ///
   664   /// For the sake of convenience it also works as a usual
   665   /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
   666   /// and the \c Key and \c Value typedefs also exist.
   667   ///
   668   /// The simplest way of using this map is through the mapToFunctor()
   669   /// function.
   670   ///
   671   ///\sa FunctorToMap
   672   template <typename M>
   673   class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
   674     const M &_m;
   675   public:
   676     typedef MapBase<typename M::Key, typename M::Value> Parent;
   677     typedef typename Parent::Key Key;
   678     typedef typename Parent::Value Value;
   679 
   680     typedef typename Parent::Key argument_type;
   681     typedef typename Parent::Value result_type;
   682 
   683     /// Constructor
   684     MapToFunctor(const M &m) : _m(m) {}
   685     /// \e
   686     Value operator()(const Key &k) const { return _m[k]; }
   687     /// \e
   688     Value operator[](const Key &k) const { return _m[k]; }
   689   };
   690 
   691   /// Returns a \ref MapToFunctor class
   692 
   693   /// This function just returns a \ref MapToFunctor class.
   694   /// \relates MapToFunctor
   695   template<typename M>
   696   inline MapToFunctor<M> mapToFunctor(const M &m) {
   697     return MapToFunctor<M>(m);
   698   }
   699 
   700 
   701   /// \brief Map adaptor to convert the \c Value type of a map to
   702   /// another type using the default conversion.
   703 
   704   /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
   705   /// "readable map" to another type using the default conversion.
   706   /// The \c Key type of it is inherited from \c M and the \c Value
   707   /// type is \c V.
   708   /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
   709   ///
   710   /// The simplest way of using this map is through the convertMap()
   711   /// function.
   712   template <typename M, typename V>
   713   class ConvertMap : public MapBase<typename M::Key, V> {
   714     const M &_m;
   715   public:
   716     typedef MapBase<typename M::Key, V> Parent;
   717     typedef typename Parent::Key Key;
   718     typedef typename Parent::Value Value;
   719 
   720     /// Constructor
   721 
   722     /// Constructor.
   723     /// \param m The underlying map.
   724     ConvertMap(const M &m) : _m(m) {}
   725 
   726     /// \e
   727     Value operator[](const Key &k) const { return _m[k]; }
   728   };
   729 
   730   /// Returns a \ref ConvertMap class
   731 
   732   /// This function just returns a \ref ConvertMap class.
   733   /// \relates ConvertMap
   734   template<typename V, typename M>
   735   inline ConvertMap<M, V> convertMap(const M &map) {
   736     return ConvertMap<M, V>(map);
   737   }
   738 
   739 
   740   /// Applies all map setting operations to two maps
   741 
   742   /// This map has two \ref concepts::WriteMap "writable map" parameters
   743   /// and each write request will be passed to both of them.
   744   /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
   745   /// operations will return the corresponding values of \c M1.
   746   ///
   747   /// The \c Key and \c Value types are inherited from \c M1.
   748   /// The \c Key and \c Value of \c M2 must be convertible from those
   749   /// of \c M1.
   750   ///
   751   /// The simplest way of using this map is through the forkMap()
   752   /// function.
   753   template<typename  M1, typename M2>
   754   class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
   755     M1 &_m1;
   756     M2 &_m2;
   757   public:
   758     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   759     typedef typename Parent::Key Key;
   760     typedef typename Parent::Value Value;
   761 
   762     /// Constructor
   763     ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
   764     /// Returns the value associated with the given key in the first map.
   765     Value operator[](const Key &k) const { return _m1[k]; }
   766     /// Sets the value associated with the given key in both maps.
   767     void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
   768   };
   769 
   770   /// Returns a \ref ForkMap class
   771 
   772   /// This function just returns a \ref ForkMap class.
   773   /// \relates ForkMap
   774   template <typename M1, typename M2>
   775   inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
   776     return ForkMap<M1,M2>(m1,m2);
   777   }
   778 
   779 
   780   /// Sum of two maps
   781 
   782   /// This \ref concepts::ReadMap "read-only map" returns the sum
   783   /// of the values of the two given maps.
   784   /// Its \c Key and \c Value types are inherited from \c M1.
   785   /// The \c Key and \c Value of \c M2 must be convertible to those of
   786   /// \c M1.
   787   ///
   788   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
   789   /// \code
   790   ///   AddMap<M1,M2> am(m1,m2);
   791   /// \endcode
   792   /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
   793   ///
   794   /// The simplest way of using this map is through the addMap()
   795   /// function.
   796   ///
   797   /// \sa SubMap, MulMap, DivMap
   798   /// \sa ShiftMap, ShiftWriteMap
   799   template<typename M1, typename M2>
   800   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
   801     const M1 &_m1;
   802     const M2 &_m2;
   803   public:
   804     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   805     typedef typename Parent::Key Key;
   806     typedef typename Parent::Value Value;
   807 
   808     /// Constructor
   809     AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   810     /// \e
   811     Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
   812   };
   813 
   814   /// Returns an \ref AddMap class
   815 
   816   /// This function just returns an \ref AddMap class.
   817   ///
   818   /// For example, if \c m1 and \c m2 are both maps with \c double
   819   /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
   820   /// <tt>m1[x]+m2[x]</tt>.
   821   ///
   822   /// \relates AddMap
   823   template<typename M1, typename M2>
   824   inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
   825     return AddMap<M1, M2>(m1,m2);
   826   }
   827 
   828 
   829   /// Difference of two maps
   830 
   831   /// This \ref concepts::ReadMap "read-only map" returns the difference
   832   /// of the values of the two given maps.
   833   /// Its \c Key and \c Value types are inherited from \c M1.
   834   /// The \c Key and \c Value of \c M2 must be convertible to those of
   835   /// \c M1.
   836   ///
   837   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
   838   /// \code
   839   ///   SubMap<M1,M2> sm(m1,m2);
   840   /// \endcode
   841   /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
   842   ///
   843   /// The simplest way of using this map is through the subMap()
   844   /// function.
   845   ///
   846   /// \sa AddMap, MulMap, DivMap
   847   template<typename M1, typename M2>
   848   class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
   849     const M1 &_m1;
   850     const M2 &_m2;
   851   public:
   852     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   853     typedef typename Parent::Key Key;
   854     typedef typename Parent::Value Value;
   855 
   856     /// Constructor
   857     SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   858     /// \e
   859     Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
   860   };
   861 
   862   /// Returns a \ref SubMap class
   863 
   864   /// This function just returns a \ref SubMap class.
   865   ///
   866   /// For example, if \c m1 and \c m2 are both maps with \c double
   867   /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
   868   /// <tt>m1[x]-m2[x]</tt>.
   869   ///
   870   /// \relates SubMap
   871   template<typename M1, typename M2>
   872   inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
   873     return SubMap<M1, M2>(m1,m2);
   874   }
   875 
   876 
   877   /// Product of two maps
   878 
   879   /// This \ref concepts::ReadMap "read-only map" returns the product
   880   /// of the values of the two given maps.
   881   /// Its \c Key and \c Value types are inherited from \c M1.
   882   /// The \c Key and \c Value of \c M2 must be convertible to those of
   883   /// \c M1.
   884   ///
   885   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
   886   /// \code
   887   ///   MulMap<M1,M2> mm(m1,m2);
   888   /// \endcode
   889   /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
   890   ///
   891   /// The simplest way of using this map is through the mulMap()
   892   /// function.
   893   ///
   894   /// \sa AddMap, SubMap, DivMap
   895   /// \sa ScaleMap, ScaleWriteMap
   896   template<typename M1, typename M2>
   897   class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
   898     const M1 &_m1;
   899     const M2 &_m2;
   900   public:
   901     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   902     typedef typename Parent::Key Key;
   903     typedef typename Parent::Value Value;
   904 
   905     /// Constructor
   906     MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   907     /// \e
   908     Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
   909   };
   910 
   911   /// Returns a \ref MulMap class
   912 
   913   /// This function just returns a \ref MulMap class.
   914   ///
   915   /// For example, if \c m1 and \c m2 are both maps with \c double
   916   /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
   917   /// <tt>m1[x]*m2[x]</tt>.
   918   ///
   919   /// \relates MulMap
   920   template<typename M1, typename M2>
   921   inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
   922     return MulMap<M1, M2>(m1,m2);
   923   }
   924 
   925 
   926   /// Quotient of two maps
   927 
   928   /// This \ref concepts::ReadMap "read-only map" returns the quotient
   929   /// of the values of the two given maps.
   930   /// Its \c Key and \c Value types are inherited from \c M1.
   931   /// The \c Key and \c Value of \c M2 must be convertible to those of
   932   /// \c M1.
   933   ///
   934   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
   935   /// \code
   936   ///   DivMap<M1,M2> dm(m1,m2);
   937   /// \endcode
   938   /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
   939   ///
   940   /// The simplest way of using this map is through the divMap()
   941   /// function.
   942   ///
   943   /// \sa AddMap, SubMap, MulMap
   944   template<typename M1, typename M2>
   945   class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
   946     const M1 &_m1;
   947     const M2 &_m2;
   948   public:
   949     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   950     typedef typename Parent::Key Key;
   951     typedef typename Parent::Value Value;
   952 
   953     /// Constructor
   954     DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   955     /// \e
   956     Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
   957   };
   958 
   959   /// Returns a \ref DivMap class
   960 
   961   /// This function just returns a \ref DivMap class.
   962   ///
   963   /// For example, if \c m1 and \c m2 are both maps with \c double
   964   /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
   965   /// <tt>m1[x]/m2[x]</tt>.
   966   ///
   967   /// \relates DivMap
   968   template<typename M1, typename M2>
   969   inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
   970     return DivMap<M1, M2>(m1,m2);
   971   }
   972 
   973 
   974   /// Shifts a map with a constant.
   975 
   976   /// This \ref concepts::ReadMap "read-only map" returns the sum of
   977   /// the given map and a constant value (i.e. it shifts the map with
   978   /// the constant). Its \c Key and \c Value are inherited from \c M.
   979   ///
   980   /// Actually,
   981   /// \code
   982   ///   ShiftMap<M> sh(m,v);
   983   /// \endcode
   984   /// is equivalent to
   985   /// \code
   986   ///   ConstMap<M::Key, M::Value> cm(v);
   987   ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
   988   /// \endcode
   989   ///
   990   /// The simplest way of using this map is through the shiftMap()
   991   /// function.
   992   ///
   993   /// \sa ShiftWriteMap
   994   template<typename M, typename C = typename M::Value>
   995   class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
   996     const M &_m;
   997     C _v;
   998   public:
   999     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1000     typedef typename Parent::Key Key;
  1001     typedef typename Parent::Value Value;
  1002 
  1003     /// Constructor
  1004 
  1005     /// Constructor.
  1006     /// \param m The undelying map.
  1007     /// \param v The constant value.
  1008     ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
  1009     /// \e
  1010     Value operator[](const Key &k) const { return _m[k]+_v; }
  1011   };
  1012 
  1013   /// Shifts a map with a constant (read-write version).
  1014 
  1015   /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
  1016   /// of the given map and a constant value (i.e. it shifts the map with
  1017   /// the constant). Its \c Key and \c Value are inherited from \c M.
  1018   /// It makes also possible to write the map.
  1019   ///
  1020   /// The simplest way of using this map is through the shiftWriteMap()
  1021   /// function.
  1022   ///
  1023   /// \sa ShiftMap
  1024   template<typename M, typename C = typename M::Value>
  1025   class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1026     M &_m;
  1027     C _v;
  1028   public:
  1029     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1030     typedef typename Parent::Key Key;
  1031     typedef typename Parent::Value Value;
  1032 
  1033     /// Constructor
  1034 
  1035     /// Constructor.
  1036     /// \param m The undelying map.
  1037     /// \param v The constant value.
  1038     ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  1039     /// \e
  1040     Value operator[](const Key &k) const { return _m[k]+_v; }
  1041     /// \e
  1042     void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
  1043   };
  1044 
  1045   /// Returns a \ref ShiftMap class
  1046 
  1047   /// This function just returns a \ref ShiftMap class.
  1048   ///
  1049   /// For example, if \c m is a map with \c double values and \c v is
  1050   /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
  1051   /// <tt>m[x]+v</tt>.
  1052   ///
  1053   /// \relates ShiftMap
  1054   template<typename M, typename C>
  1055   inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
  1056     return ShiftMap<M, C>(m,v);
  1057   }
  1058 
  1059   /// Returns a \ref ShiftWriteMap class
  1060 
  1061   /// This function just returns a \ref ShiftWriteMap class.
  1062   ///
  1063   /// For example, if \c m is a map with \c double values and \c v is
  1064   /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
  1065   /// <tt>m[x]+v</tt>.
  1066   /// Moreover it makes also possible to write the map.
  1067   ///
  1068   /// \relates ShiftWriteMap
  1069   template<typename M, typename C>
  1070   inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
  1071     return ShiftWriteMap<M, C>(m,v);
  1072   }
  1073 
  1074 
  1075   /// Scales a map with a constant.
  1076 
  1077   /// This \ref concepts::ReadMap "read-only map" returns the value of
  1078   /// the given map multiplied from the left side with a constant value.
  1079   /// Its \c Key and \c Value are inherited from \c M.
  1080   ///
  1081   /// Actually,
  1082   /// \code
  1083   ///   ScaleMap<M> sc(m,v);
  1084   /// \endcode
  1085   /// is equivalent to
  1086   /// \code
  1087   ///   ConstMap<M::Key, M::Value> cm(v);
  1088   ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
  1089   /// \endcode
  1090   ///
  1091   /// The simplest way of using this map is through the scaleMap()
  1092   /// function.
  1093   ///
  1094   /// \sa ScaleWriteMap
  1095   template<typename M, typename C = typename M::Value>
  1096   class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
  1097     const M &_m;
  1098     C _v;
  1099   public:
  1100     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1101     typedef typename Parent::Key Key;
  1102     typedef typename Parent::Value Value;
  1103 
  1104     /// Constructor
  1105 
  1106     /// Constructor.
  1107     /// \param m The undelying map.
  1108     /// \param v The constant value.
  1109     ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
  1110     /// \e
  1111     Value operator[](const Key &k) const { return _v*_m[k]; }
  1112   };
  1113 
  1114   /// Scales a map with a constant (read-write version).
  1115 
  1116   /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
  1117   /// the given map multiplied from the left side with a constant value.
  1118   /// Its \c Key and \c Value are inherited from \c M.
  1119   /// It can also be used as write map if the \c / operator is defined
  1120   /// between \c Value and \c C and the given multiplier is not zero.
  1121   ///
  1122   /// The simplest way of using this map is through the scaleWriteMap()
  1123   /// function.
  1124   ///
  1125   /// \sa ScaleMap
  1126   template<typename M, typename C = typename M::Value>
  1127   class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1128     M &_m;
  1129     C _v;
  1130   public:
  1131     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1132     typedef typename Parent::Key Key;
  1133     typedef typename Parent::Value Value;
  1134 
  1135     /// Constructor
  1136 
  1137     /// Constructor.
  1138     /// \param m The undelying map.
  1139     /// \param v The constant value.
  1140     ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  1141     /// \e
  1142     Value operator[](const Key &k) const { return _v*_m[k]; }
  1143     /// \e
  1144     void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
  1145   };
  1146 
  1147   /// Returns a \ref ScaleMap class
  1148 
  1149   /// This function just returns a \ref ScaleMap class.
  1150   ///
  1151   /// For example, if \c m is a map with \c double values and \c v is
  1152   /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
  1153   /// <tt>v*m[x]</tt>.
  1154   ///
  1155   /// \relates ScaleMap
  1156   template<typename M, typename C>
  1157   inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
  1158     return ScaleMap<M, C>(m,v);
  1159   }
  1160 
  1161   /// Returns a \ref ScaleWriteMap class
  1162 
  1163   /// This function just returns a \ref ScaleWriteMap class.
  1164   ///
  1165   /// For example, if \c m is a map with \c double values and \c v is
  1166   /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
  1167   /// <tt>v*m[x]</tt>.
  1168   /// Moreover it makes also possible to write the map.
  1169   ///
  1170   /// \relates ScaleWriteMap
  1171   template<typename M, typename C>
  1172   inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
  1173     return ScaleWriteMap<M, C>(m,v);
  1174   }
  1175 
  1176 
  1177   /// Negative of a map
  1178 
  1179   /// This \ref concepts::ReadMap "read-only map" returns the negative
  1180   /// of the values of the given map (using the unary \c - operator).
  1181   /// Its \c Key and \c Value are inherited from \c M.
  1182   ///
  1183   /// If M::Value is \c int, \c double etc., then
  1184   /// \code
  1185   ///   NegMap<M> neg(m);
  1186   /// \endcode
  1187   /// is equivalent to
  1188   /// \code
  1189   ///   ScaleMap<M> neg(m,-1);
  1190   /// \endcode
  1191   ///
  1192   /// The simplest way of using this map is through the negMap()
  1193   /// function.
  1194   ///
  1195   /// \sa NegWriteMap
  1196   template<typename M>
  1197   class NegMap : public MapBase<typename M::Key, typename M::Value> {
  1198     const M& _m;
  1199   public:
  1200     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1201     typedef typename Parent::Key Key;
  1202     typedef typename Parent::Value Value;
  1203 
  1204     /// Constructor
  1205     NegMap(const M &m) : _m(m) {}
  1206     /// \e
  1207     Value operator[](const Key &k) const { return -_m[k]; }
  1208   };
  1209 
  1210   /// Negative of a map (read-write version)
  1211 
  1212   /// This \ref concepts::ReadWriteMap "read-write map" returns the
  1213   /// negative of the values of the given map (using the unary \c -
  1214   /// operator).
  1215   /// Its \c Key and \c Value are inherited from \c M.
  1216   /// It makes also possible to write the map.
  1217   ///
  1218   /// If M::Value is \c int, \c double etc., then
  1219   /// \code
  1220   ///   NegWriteMap<M> neg(m);
  1221   /// \endcode
  1222   /// is equivalent to
  1223   /// \code
  1224   ///   ScaleWriteMap<M> neg(m,-1);
  1225   /// \endcode
  1226   ///
  1227   /// The simplest way of using this map is through the negWriteMap()
  1228   /// function.
  1229   ///
  1230   /// \sa NegMap
  1231   template<typename M>
  1232   class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1233     M &_m;
  1234   public:
  1235     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1236     typedef typename Parent::Key Key;
  1237     typedef typename Parent::Value Value;
  1238 
  1239     /// Constructor
  1240     NegWriteMap(M &m) : _m(m) {}
  1241     /// \e
  1242     Value operator[](const Key &k) const { return -_m[k]; }
  1243     /// \e
  1244     void set(const Key &k, const Value &v) { _m.set(k, -v); }
  1245   };
  1246 
  1247   /// Returns a \ref NegMap class
  1248 
  1249   /// This function just returns a \ref NegMap class.
  1250   ///
  1251   /// For example, if \c m is a map with \c double values, then
  1252   /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
  1253   ///
  1254   /// \relates NegMap
  1255   template <typename M>
  1256   inline NegMap<M> negMap(const M &m) {
  1257     return NegMap<M>(m);
  1258   }
  1259 
  1260   /// Returns a \ref NegWriteMap class
  1261 
  1262   /// This function just returns a \ref NegWriteMap class.
  1263   ///
  1264   /// For example, if \c m is a map with \c double values, then
  1265   /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
  1266   /// Moreover it makes also possible to write the map.
  1267   ///
  1268   /// \relates NegWriteMap
  1269   template <typename M>
  1270   inline NegWriteMap<M> negWriteMap(M &m) {
  1271     return NegWriteMap<M>(m);
  1272   }
  1273 
  1274 
  1275   /// Absolute value of a map
  1276 
  1277   /// This \ref concepts::ReadMap "read-only map" returns the absolute
  1278   /// value of the values of the given map.
  1279   /// Its \c Key and \c Value are inherited from \c M.
  1280   /// \c Value must be comparable to \c 0 and the unary \c -
  1281   /// operator must be defined for it, of course.
  1282   ///
  1283   /// The simplest way of using this map is through the absMap()
  1284   /// function.
  1285   template<typename M>
  1286   class AbsMap : public MapBase<typename M::Key, typename M::Value> {
  1287     const M &_m;
  1288   public:
  1289     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1290     typedef typename Parent::Key Key;
  1291     typedef typename Parent::Value Value;
  1292 
  1293     /// Constructor
  1294     AbsMap(const M &m) : _m(m) {}
  1295     /// \e
  1296     Value operator[](const Key &k) const {
  1297       Value tmp = _m[k];
  1298       return tmp >= 0 ? tmp : -tmp;
  1299     }
  1300 
  1301   };
  1302 
  1303   /// Returns an \ref AbsMap class
  1304 
  1305   /// This function just returns an \ref AbsMap class.
  1306   ///
  1307   /// For example, if \c m is a map with \c double values, then
  1308   /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
  1309   /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
  1310   /// negative.
  1311   ///
  1312   /// \relates AbsMap
  1313   template<typename M>
  1314   inline AbsMap<M> absMap(const M &m) {
  1315     return AbsMap<M>(m);
  1316   }
  1317 
  1318   /// @}
  1319 
  1320   // Logical maps and map adaptors:
  1321 
  1322   /// \addtogroup maps
  1323   /// @{
  1324 
  1325   /// Constant \c true map.
  1326 
  1327   /// This \ref concepts::ReadMap "read-only map" assigns \c true to
  1328   /// each key.
  1329   ///
  1330   /// Note that
  1331   /// \code
  1332   ///   TrueMap<K> tm;
  1333   /// \endcode
  1334   /// is equivalent to
  1335   /// \code
  1336   ///   ConstMap<K,bool> tm(true);
  1337   /// \endcode
  1338   ///
  1339   /// \sa FalseMap
  1340   /// \sa ConstMap
  1341   template <typename K>
  1342   class TrueMap : public MapBase<K, bool> {
  1343   public:
  1344     typedef MapBase<K, bool> Parent;
  1345     typedef typename Parent::Key Key;
  1346     typedef typename Parent::Value Value;
  1347 
  1348     /// Gives back \c true.
  1349     Value operator[](const Key&) const { return true; }
  1350   };
  1351 
  1352   /// Returns a \ref TrueMap class
  1353 
  1354   /// This function just returns a \ref TrueMap class.
  1355   /// \relates TrueMap
  1356   template<typename K>
  1357   inline TrueMap<K> trueMap() {
  1358     return TrueMap<K>();
  1359   }
  1360 
  1361 
  1362   /// Constant \c false map.
  1363 
  1364   /// This \ref concepts::ReadMap "read-only map" assigns \c false to
  1365   /// each key.
  1366   ///
  1367   /// Note that
  1368   /// \code
  1369   ///   FalseMap<K> fm;
  1370   /// \endcode
  1371   /// is equivalent to
  1372   /// \code
  1373   ///   ConstMap<K,bool> fm(false);
  1374   /// \endcode
  1375   ///
  1376   /// \sa TrueMap
  1377   /// \sa ConstMap
  1378   template <typename K>
  1379   class FalseMap : public MapBase<K, bool> {
  1380   public:
  1381     typedef MapBase<K, bool> Parent;
  1382     typedef typename Parent::Key Key;
  1383     typedef typename Parent::Value Value;
  1384 
  1385     /// Gives back \c false.
  1386     Value operator[](const Key&) const { return false; }
  1387   };
  1388 
  1389   /// Returns a \ref FalseMap class
  1390 
  1391   /// This function just returns a \ref FalseMap class.
  1392   /// \relates FalseMap
  1393   template<typename K>
  1394   inline FalseMap<K> falseMap() {
  1395     return FalseMap<K>();
  1396   }
  1397 
  1398   /// @}
  1399 
  1400   /// \addtogroup map_adaptors
  1401   /// @{
  1402 
  1403   /// Logical 'and' of two maps
  1404 
  1405   /// This \ref concepts::ReadMap "read-only map" returns the logical
  1406   /// 'and' of the values of the two given maps.
  1407   /// Its \c Key type is inherited from \c M1 and its \c Value type is
  1408   /// \c bool. \c M2::Key must be convertible to \c M1::Key.
  1409   ///
  1410   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
  1411   /// \code
  1412   ///   AndMap<M1,M2> am(m1,m2);
  1413   /// \endcode
  1414   /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
  1415   ///
  1416   /// The simplest way of using this map is through the andMap()
  1417   /// function.
  1418   ///
  1419   /// \sa OrMap
  1420   /// \sa NotMap, NotWriteMap
  1421   template<typename M1, typename M2>
  1422   class AndMap : public MapBase<typename M1::Key, bool> {
  1423     const M1 &_m1;
  1424     const M2 &_m2;
  1425   public:
  1426     typedef MapBase<typename M1::Key, bool> Parent;
  1427     typedef typename Parent::Key Key;
  1428     typedef typename Parent::Value Value;
  1429 
  1430     /// Constructor
  1431     AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1432     /// \e
  1433     Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
  1434   };
  1435 
  1436   /// Returns an \ref AndMap class
  1437 
  1438   /// This function just returns an \ref AndMap class.
  1439   ///
  1440   /// For example, if \c m1 and \c m2 are both maps with \c bool values,
  1441   /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
  1442   /// <tt>m1[x]&&m2[x]</tt>.
  1443   ///
  1444   /// \relates AndMap
  1445   template<typename M1, typename M2>
  1446   inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
  1447     return AndMap<M1, M2>(m1,m2);
  1448   }
  1449 
  1450 
  1451   /// Logical 'or' of two maps
  1452 
  1453   /// This \ref concepts::ReadMap "read-only map" returns the logical
  1454   /// 'or' of the values of the two given maps.
  1455   /// Its \c Key type is inherited from \c M1 and its \c Value type is
  1456   /// \c bool. \c M2::Key must be convertible to \c M1::Key.
  1457   ///
  1458   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
  1459   /// \code
  1460   ///   OrMap<M1,M2> om(m1,m2);
  1461   /// \endcode
  1462   /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
  1463   ///
  1464   /// The simplest way of using this map is through the orMap()
  1465   /// function.
  1466   ///
  1467   /// \sa AndMap
  1468   /// \sa NotMap, NotWriteMap
  1469   template<typename M1, typename M2>
  1470   class OrMap : public MapBase<typename M1::Key, bool> {
  1471     const M1 &_m1;
  1472     const M2 &_m2;
  1473   public:
  1474     typedef MapBase<typename M1::Key, bool> Parent;
  1475     typedef typename Parent::Key Key;
  1476     typedef typename Parent::Value Value;
  1477 
  1478     /// Constructor
  1479     OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1480     /// \e
  1481     Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
  1482   };
  1483 
  1484   /// Returns an \ref OrMap class
  1485 
  1486   /// This function just returns an \ref OrMap class.
  1487   ///
  1488   /// For example, if \c m1 and \c m2 are both maps with \c bool values,
  1489   /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
  1490   /// <tt>m1[x]||m2[x]</tt>.
  1491   ///
  1492   /// \relates OrMap
  1493   template<typename M1, typename M2>
  1494   inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
  1495     return OrMap<M1, M2>(m1,m2);
  1496   }
  1497 
  1498 
  1499   /// Logical 'not' of a map
  1500 
  1501   /// This \ref concepts::ReadMap "read-only map" returns the logical
  1502   /// negation of the values of the given map.
  1503   /// Its \c Key is inherited from \c M and its \c Value is \c bool.
  1504   ///
  1505   /// The simplest way of using this map is through the notMap()
  1506   /// function.
  1507   ///
  1508   /// \sa NotWriteMap
  1509   template <typename M>
  1510   class NotMap : public MapBase<typename M::Key, bool> {
  1511     const M &_m;
  1512   public:
  1513     typedef MapBase<typename M::Key, bool> Parent;
  1514     typedef typename Parent::Key Key;
  1515     typedef typename Parent::Value Value;
  1516 
  1517     /// Constructor
  1518     NotMap(const M &m) : _m(m) {}
  1519     /// \e
  1520     Value operator[](const Key &k) const { return !_m[k]; }
  1521   };
  1522 
  1523   /// Logical 'not' of a map (read-write version)
  1524 
  1525   /// This \ref concepts::ReadWriteMap "read-write map" returns the
  1526   /// logical negation of the values of the given map.
  1527   /// Its \c Key is inherited from \c M and its \c Value is \c bool.
  1528   /// It makes also possible to write the map. When a value is set,
  1529   /// the opposite value is set to the original map.
  1530   ///
  1531   /// The simplest way of using this map is through the notWriteMap()
  1532   /// function.
  1533   ///
  1534   /// \sa NotMap
  1535   template <typename M>
  1536   class NotWriteMap : public MapBase<typename M::Key, bool> {
  1537     M &_m;
  1538   public:
  1539     typedef MapBase<typename M::Key, bool> Parent;
  1540     typedef typename Parent::Key Key;
  1541     typedef typename Parent::Value Value;
  1542 
  1543     /// Constructor
  1544     NotWriteMap(M &m) : _m(m) {}
  1545     /// \e
  1546     Value operator[](const Key &k) const { return !_m[k]; }
  1547     /// \e
  1548     void set(const Key &k, bool v) { _m.set(k, !v); }
  1549   };
  1550 
  1551   /// Returns a \ref NotMap class
  1552 
  1553   /// This function just returns a \ref NotMap class.
  1554   ///
  1555   /// For example, if \c m is a map with \c bool values, then
  1556   /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
  1557   ///
  1558   /// \relates NotMap
  1559   template <typename M>
  1560   inline NotMap<M> notMap(const M &m) {
  1561     return NotMap<M>(m);
  1562   }
  1563 
  1564   /// Returns a \ref NotWriteMap class
  1565 
  1566   /// This function just returns a \ref NotWriteMap class.
  1567   ///
  1568   /// For example, if \c m is a map with \c bool values, then
  1569   /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
  1570   /// Moreover it makes also possible to write the map.
  1571   ///
  1572   /// \relates NotWriteMap
  1573   template <typename M>
  1574   inline NotWriteMap<M> notWriteMap(M &m) {
  1575     return NotWriteMap<M>(m);
  1576   }
  1577 
  1578 
  1579   /// Combination of two maps using the \c == operator
  1580 
  1581   /// This \ref concepts::ReadMap "read-only map" assigns \c true to
  1582   /// the keys for which the corresponding values of the two maps are
  1583   /// equal.
  1584   /// Its \c Key type is inherited from \c M1 and its \c Value type is
  1585   /// \c bool. \c M2::Key must be convertible to \c M1::Key.
  1586   ///
  1587   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
  1588   /// \code
  1589   ///   EqualMap<M1,M2> em(m1,m2);
  1590   /// \endcode
  1591   /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
  1592   ///
  1593   /// The simplest way of using this map is through the equalMap()
  1594   /// function.
  1595   ///
  1596   /// \sa LessMap
  1597   template<typename M1, typename M2>
  1598   class EqualMap : public MapBase<typename M1::Key, bool> {
  1599     const M1 &_m1;
  1600     const M2 &_m2;
  1601   public:
  1602     typedef MapBase<typename M1::Key, bool> Parent;
  1603     typedef typename Parent::Key Key;
  1604     typedef typename Parent::Value Value;
  1605 
  1606     /// Constructor
  1607     EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1608     /// \e
  1609     Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
  1610   };
  1611 
  1612   /// Returns an \ref EqualMap class
  1613 
  1614   /// This function just returns an \ref EqualMap class.
  1615   ///
  1616   /// For example, if \c m1 and \c m2 are maps with keys and values of
  1617   /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
  1618   /// <tt>m1[x]==m2[x]</tt>.
  1619   ///
  1620   /// \relates EqualMap
  1621   template<typename M1, typename M2>
  1622   inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
  1623     return EqualMap<M1, M2>(m1,m2);
  1624   }
  1625 
  1626 
  1627   /// Combination of two maps using the \c < operator
  1628 
  1629   /// This \ref concepts::ReadMap "read-only map" assigns \c true to
  1630   /// the keys for which the corresponding value of the first map is
  1631   /// less then the value of the second map.
  1632   /// Its \c Key type is inherited from \c M1 and its \c Value type is
  1633   /// \c bool. \c M2::Key must be convertible to \c M1::Key.
  1634   ///
  1635   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
  1636   /// \code
  1637   ///   LessMap<M1,M2> lm(m1,m2);
  1638   /// \endcode
  1639   /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
  1640   ///
  1641   /// The simplest way of using this map is through the lessMap()
  1642   /// function.
  1643   ///
  1644   /// \sa EqualMap
  1645   template<typename M1, typename M2>
  1646   class LessMap : public MapBase<typename M1::Key, bool> {
  1647     const M1 &_m1;
  1648     const M2 &_m2;
  1649   public:
  1650     typedef MapBase<typename M1::Key, bool> Parent;
  1651     typedef typename Parent::Key Key;
  1652     typedef typename Parent::Value Value;
  1653 
  1654     /// Constructor
  1655     LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1656     /// \e
  1657     Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
  1658   };
  1659 
  1660   /// Returns an \ref LessMap class
  1661 
  1662   /// This function just returns an \ref LessMap class.
  1663   ///
  1664   /// For example, if \c m1 and \c m2 are maps with keys and values of
  1665   /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
  1666   /// <tt>m1[x]<m2[x]</tt>.
  1667   ///
  1668   /// \relates LessMap
  1669   template<typename M1, typename M2>
  1670   inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
  1671     return LessMap<M1, M2>(m1,m2);
  1672   }
  1673 
  1674   namespace _maps_bits {
  1675 
  1676     template <typename _Iterator, typename Enable = void>
  1677     struct IteratorTraits {
  1678       typedef typename std::iterator_traits<_Iterator>::value_type Value;
  1679     };
  1680 
  1681     template <typename _Iterator>
  1682     struct IteratorTraits<_Iterator,
  1683       typename exists<typename _Iterator::container_type>::type>
  1684     {
  1685       typedef typename _Iterator::container_type::value_type Value;
  1686     };
  1687 
  1688   }
  1689 
  1690   /// \brief Writable bool map for logging each \c true assigned element
  1691   ///
  1692   /// A \ref concepts::WriteMap "writable" bool map for logging
  1693   /// each \c true assigned element, i.e it copies subsequently each
  1694   /// keys set to \c true to the given iterator.
  1695   /// The most important usage of it is storing certain nodes or arcs
  1696   /// that were marked \c true by an algorithm.
  1697   ///
  1698   /// There are several algorithms that provide solutions through bool
  1699   /// maps and most of them assign \c true at most once for each key.
  1700   /// In these cases it is a natural request to store each \c true
  1701   /// assigned elements (in order of the assignment), which can be
  1702   /// easily done with LoggerBoolMap.
  1703   ///
  1704   /// The simplest way of using this map is through the loggerBoolMap()
  1705   /// function.
  1706   ///
  1707   /// \tparam It The type of the iterator.
  1708   /// \tparam Ke The key type of the map. The default value set
  1709   /// according to the iterator type should work in most cases.
  1710   ///
  1711   /// \note The container of the iterator must contain enough space
  1712   /// for the elements or the iterator should be an inserter iterator.
  1713 #ifdef DOXYGEN
  1714   template <typename It, typename Ke>
  1715 #else
  1716   template <typename It,
  1717             typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
  1718 #endif
  1719   class LoggerBoolMap {
  1720   public:
  1721     typedef It Iterator;
  1722 
  1723     typedef Ke Key;
  1724     typedef bool Value;
  1725 
  1726     /// Constructor
  1727     LoggerBoolMap(Iterator it)
  1728       : _begin(it), _end(it) {}
  1729 
  1730     /// Gives back the given iterator set for the first key
  1731     Iterator begin() const {
  1732       return _begin;
  1733     }
  1734 
  1735     /// Gives back the the 'after the last' iterator
  1736     Iterator end() const {
  1737       return _end;
  1738     }
  1739 
  1740     /// The set function of the map
  1741     void set(const Key& key, Value value) {
  1742       if (value) {
  1743         *_end++ = key;
  1744       }
  1745     }
  1746 
  1747   private:
  1748     Iterator _begin;
  1749     Iterator _end;
  1750   };
  1751 
  1752   /// Returns a \ref LoggerBoolMap class
  1753 
  1754   /// This function just returns a \ref LoggerBoolMap class.
  1755   ///
  1756   /// The most important usage of it is storing certain nodes or arcs
  1757   /// that were marked \c true by an algorithm.
  1758   /// For example it makes easier to store the nodes in the processing
  1759   /// order of Dfs algorithm, as the following examples show.
  1760   /// \code
  1761   ///   std::vector<Node> v;
  1762   ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
  1763   /// \endcode
  1764   /// \code
  1765   ///   std::vector<Node> v(countNodes(g));
  1766   ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
  1767   /// \endcode
  1768   ///
  1769   /// \note The container of the iterator must contain enough space
  1770   /// for the elements or the iterator should be an inserter iterator.
  1771   ///
  1772   /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
  1773   /// it cannot be used when a readable map is needed, for example as
  1774   /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
  1775   ///
  1776   /// \relates LoggerBoolMap
  1777   template<typename Iterator>
  1778   inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
  1779     return LoggerBoolMap<Iterator>(it);
  1780   }
  1781 
  1782   /// Provides an immutable and unique id for each item in the graph.
  1783 
  1784   /// The IdMap class provides a unique and immutable id for each item of the
  1785   /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
  1786   /// different items (nodes) get different ids <li>\b immutable: the id of an
  1787   /// item (node) does not change (even if you delete other nodes).  </ul>
  1788   /// Through this map you get access (i.e. can read) the inner id values of
  1789   /// the items stored in the graph. This map can be inverted with its member
  1790   /// class \c InverseMap or with the \c operator() member.
  1791   ///
  1792   template <typename _Graph, typename _Item>
  1793   class IdMap {
  1794   public:
  1795     typedef _Graph Graph;
  1796     typedef int Value;
  1797     typedef _Item Item;
  1798     typedef _Item Key;
  1799 
  1800     /// \brief Constructor.
  1801     ///
  1802     /// Constructor of the map.
  1803     explicit IdMap(const Graph& graph) : _graph(&graph) {}
  1804 
  1805     /// \brief Gives back the \e id of the item.
  1806     ///
  1807     /// Gives back the immutable and unique \e id of the item.
  1808     int operator[](const Item& item) const { return _graph->id(item);}
  1809 
  1810     /// \brief Gives back the item by its id.
  1811     ///
  1812     /// Gives back the item by its id.
  1813     Item operator()(int id) { return _graph->fromId(id, Item()); }
  1814 
  1815   private:
  1816     const Graph* _graph;
  1817 
  1818   public:
  1819 
  1820     /// \brief The class represents the inverse of its owner (IdMap).
  1821     ///
  1822     /// The class represents the inverse of its owner (IdMap).
  1823     /// \see inverse()
  1824     class InverseMap {
  1825     public:
  1826 
  1827       /// \brief Constructor.
  1828       ///
  1829       /// Constructor for creating an id-to-item map.
  1830       explicit InverseMap(const Graph& graph) : _graph(&graph) {}
  1831 
  1832       /// \brief Constructor.
  1833       ///
  1834       /// Constructor for creating an id-to-item map.
  1835       explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
  1836 
  1837       /// \brief Gives back the given item from its id.
  1838       ///
  1839       /// Gives back the given item from its id.
  1840       ///
  1841       Item operator[](int id) const { return _graph->fromId(id, Item());}
  1842 
  1843     private:
  1844       const Graph* _graph;
  1845     };
  1846 
  1847     /// \brief Gives back the inverse of the map.
  1848     ///
  1849     /// Gives back the inverse of the IdMap.
  1850     InverseMap inverse() const { return InverseMap(*_graph);}
  1851 
  1852   };
  1853 
  1854 
  1855   /// \brief General invertable graph-map type.
  1856 
  1857   /// This type provides simple invertable graph-maps.
  1858   /// The InvertableMap wraps an arbitrary ReadWriteMap
  1859   /// and if a key is set to a new value then store it
  1860   /// in the inverse map.
  1861   ///
  1862   /// The values of the map can be accessed
  1863   /// with stl compatible forward iterator.
  1864   ///
  1865   /// \tparam _Graph The graph type.
  1866   /// \tparam _Item The item type of the graph.
  1867   /// \tparam _Value The value type of the map.
  1868   ///
  1869   /// \see IterableValueMap
  1870   template <typename _Graph, typename _Item, typename _Value>
  1871   class InvertableMap
  1872     : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
  1873   private:
  1874 
  1875     typedef typename ItemSetTraits<_Graph, _Item>::
  1876     template Map<_Value>::Type Map;
  1877     typedef _Graph Graph;
  1878 
  1879     typedef std::map<_Value, _Item> Container;
  1880     Container _inv_map;
  1881 
  1882   public:
  1883 
  1884     /// The key type of InvertableMap (Node, Arc, Edge).
  1885     typedef typename Map::Key Key;
  1886     /// The value type of the InvertableMap.
  1887     typedef typename Map::Value Value;
  1888 
  1889 
  1890 
  1891     /// \brief Constructor.
  1892     ///
  1893     /// Construct a new InvertableMap for the graph.
  1894     ///
  1895     explicit InvertableMap(const Graph& graph) : Map(graph) {}
  1896 
  1897     /// \brief Forward iterator for values.
  1898     ///
  1899     /// This iterator is an stl compatible forward
  1900     /// iterator on the values of the map. The values can
  1901     /// be accessed in the [beginValue, endValue) range.
  1902     ///
  1903     class ValueIterator
  1904       : public std::iterator<std::forward_iterator_tag, Value> {
  1905       friend class InvertableMap;
  1906     private:
  1907       ValueIterator(typename Container::const_iterator _it)
  1908         : it(_it) {}
  1909     public:
  1910 
  1911       ValueIterator() {}
  1912 
  1913       ValueIterator& operator++() { ++it; return *this; }
  1914       ValueIterator operator++(int) {
  1915         ValueIterator tmp(*this);
  1916         operator++();
  1917         return tmp;
  1918       }
  1919 
  1920       const Value& operator*() const { return it->first; }
  1921       const Value* operator->() const { return &(it->first); }
  1922 
  1923       bool operator==(ValueIterator jt) const { return it == jt.it; }
  1924       bool operator!=(ValueIterator jt) const { return it != jt.it; }
  1925 
  1926     private:
  1927       typename Container::const_iterator it;
  1928     };
  1929 
  1930     /// \brief Returns an iterator to the first value.
  1931     ///
  1932     /// Returns an stl compatible iterator to the
  1933     /// first value of the map. The values of the
  1934     /// map can be accessed in the [beginValue, endValue)
  1935     /// range.
  1936     ValueIterator beginValue() const {
  1937       return ValueIterator(_inv_map.begin());
  1938     }
  1939 
  1940     /// \brief Returns an iterator after the last value.
  1941     ///
  1942     /// Returns an stl compatible iterator after the
  1943     /// last value of the map. The values of the
  1944     /// map can be accessed in the [beginValue, endValue)
  1945     /// range.
  1946     ValueIterator endValue() const {
  1947       return ValueIterator(_inv_map.end());
  1948     }
  1949 
  1950     /// \brief The setter function of the map.
  1951     ///
  1952     /// Sets the mapped value.
  1953     void set(const Key& key, const Value& val) {
  1954       Value oldval = Map::operator[](key);
  1955       typename Container::iterator it = _inv_map.find(oldval);
  1956       if (it != _inv_map.end() && it->second == key) {
  1957         _inv_map.erase(it);
  1958       }
  1959       _inv_map.insert(make_pair(val, key));
  1960       Map::set(key, val);
  1961     }
  1962 
  1963     /// \brief The getter function of the map.
  1964     ///
  1965     /// It gives back the value associated with the key.
  1966     typename MapTraits<Map>::ConstReturnValue
  1967     operator[](const Key& key) const {
  1968       return Map::operator[](key);
  1969     }
  1970 
  1971     /// \brief Gives back the item by its value.
  1972     ///
  1973     /// Gives back the item by its value.
  1974     Key operator()(const Value& key) const {
  1975       typename Container::const_iterator it = _inv_map.find(key);
  1976       return it != _inv_map.end() ? it->second : INVALID;
  1977     }
  1978 
  1979   protected:
  1980 
  1981     /// \brief Erase the key from the map.
  1982     ///
  1983     /// Erase the key to the map. It is called by the
  1984     /// \c AlterationNotifier.
  1985     virtual void erase(const Key& key) {
  1986       Value val = Map::operator[](key);
  1987       typename Container::iterator it = _inv_map.find(val);
  1988       if (it != _inv_map.end() && it->second == key) {
  1989         _inv_map.erase(it);
  1990       }
  1991       Map::erase(key);
  1992     }
  1993 
  1994     /// \brief Erase more keys from the map.
  1995     ///
  1996     /// Erase more keys from the map. It is called by the
  1997     /// \c AlterationNotifier.
  1998     virtual void erase(const std::vector<Key>& keys) {
  1999       for (int i = 0; i < int(keys.size()); ++i) {
  2000         Value val = Map::operator[](keys[i]);
  2001         typename Container::iterator it = _inv_map.find(val);
  2002         if (it != _inv_map.end() && it->second == keys[i]) {
  2003           _inv_map.erase(it);
  2004         }
  2005       }
  2006       Map::erase(keys);
  2007     }
  2008 
  2009     /// \brief Clear the keys from the map and inverse map.
  2010     ///
  2011     /// Clear the keys from the map and inverse map. It is called by the
  2012     /// \c AlterationNotifier.
  2013     virtual void clear() {
  2014       _inv_map.clear();
  2015       Map::clear();
  2016     }
  2017 
  2018   public:
  2019 
  2020     /// \brief The inverse map type.
  2021     ///
  2022     /// The inverse of this map. The subscript operator of the map
  2023     /// gives back always the item what was last assigned to the value.
  2024     class InverseMap {
  2025     public:
  2026       /// \brief Constructor of the InverseMap.
  2027       ///
  2028       /// Constructor of the InverseMap.
  2029       explicit InverseMap(const InvertableMap& inverted)
  2030         : _inverted(inverted) {}
  2031 
  2032       /// The value type of the InverseMap.
  2033       typedef typename InvertableMap::Key Value;
  2034       /// The key type of the InverseMap.
  2035       typedef typename InvertableMap::Value Key;
  2036 
  2037       /// \brief Subscript operator.
  2038       ///
  2039       /// Subscript operator. It gives back always the item
  2040       /// what was last assigned to the value.
  2041       Value operator[](const Key& key) const {
  2042         return _inverted(key);
  2043       }
  2044 
  2045     private:
  2046       const InvertableMap& _inverted;
  2047     };
  2048 
  2049     /// \brief It gives back the just readable inverse map.
  2050     ///
  2051     /// It gives back the just readable inverse map.
  2052     InverseMap inverse() const {
  2053       return InverseMap(*this);
  2054     }
  2055 
  2056 
  2057 
  2058   };
  2059 
  2060   /// \brief Provides a mutable, continuous and unique descriptor for each
  2061   /// item in the graph.
  2062   ///
  2063   /// The DescriptorMap class provides a unique and continuous (but mutable)
  2064   /// descriptor (id) for each item of the same type (e.g. node) in the
  2065   /// graph. This id is <ul><li>\b unique: different items (nodes) get
  2066   /// different ids <li>\b continuous: the range of the ids is the set of
  2067   /// integers between 0 and \c n-1, where \c n is the number of the items of
  2068   /// this type (e.g. nodes) (so the id of a node can change if you delete an
  2069   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
  2070   /// with its member class \c InverseMap, or with the \c operator() member.
  2071   ///
  2072   /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
  2073   /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
  2074   /// Edge.
  2075   template <typename _Graph, typename _Item>
  2076   class DescriptorMap
  2077     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
  2078 
  2079     typedef _Item Item;
  2080     typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
  2081 
  2082   public:
  2083     /// The graph class of DescriptorMap.
  2084     typedef _Graph Graph;
  2085 
  2086     /// The key type of DescriptorMap (Node, Arc, Edge).
  2087     typedef typename Map::Key Key;
  2088     /// The value type of DescriptorMap.
  2089     typedef typename Map::Value Value;
  2090 
  2091     /// \brief Constructor.
  2092     ///
  2093     /// Constructor for descriptor map.
  2094     explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
  2095       Item it;
  2096       const typename Map::Notifier* nf = Map::notifier();
  2097       for (nf->first(it); it != INVALID; nf->next(it)) {
  2098         Map::set(it, _inv_map.size());
  2099         _inv_map.push_back(it);
  2100       }
  2101     }
  2102 
  2103   protected:
  2104 
  2105     /// \brief Add a new key to the map.
  2106     ///
  2107     /// Add a new key to the map. It is called by the
  2108     /// \c AlterationNotifier.
  2109     virtual void add(const Item& item) {
  2110       Map::add(item);
  2111       Map::set(item, _inv_map.size());
  2112       _inv_map.push_back(item);
  2113     }
  2114 
  2115     /// \brief Add more new keys to the map.
  2116     ///
  2117     /// Add more new keys to the map. It is called by the
  2118     /// \c AlterationNotifier.
  2119     virtual void add(const std::vector<Item>& items) {
  2120       Map::add(items);
  2121       for (int i = 0; i < int(items.size()); ++i) {
  2122         Map::set(items[i], _inv_map.size());
  2123         _inv_map.push_back(items[i]);
  2124       }
  2125     }
  2126 
  2127     /// \brief Erase the key from the map.
  2128     ///
  2129     /// Erase the key from the map. It is called by the
  2130     /// \c AlterationNotifier.
  2131     virtual void erase(const Item& item) {
  2132       Map::set(_inv_map.back(), Map::operator[](item));
  2133       _inv_map[Map::operator[](item)] = _inv_map.back();
  2134       _inv_map.pop_back();
  2135       Map::erase(item);
  2136     }
  2137 
  2138     /// \brief Erase more keys from the map.
  2139     ///
  2140     /// Erase more keys from the map. It is called by the
  2141     /// \c AlterationNotifier.
  2142     virtual void erase(const std::vector<Item>& items) {
  2143       for (int i = 0; i < int(items.size()); ++i) {
  2144         Map::set(_inv_map.back(), Map::operator[](items[i]));
  2145         _inv_map[Map::operator[](items[i])] = _inv_map.back();
  2146         _inv_map.pop_back();
  2147       }
  2148       Map::erase(items);
  2149     }
  2150 
  2151     /// \brief Build the unique map.
  2152     ///
  2153     /// Build the unique map. It is called by the
  2154     /// \c AlterationNotifier.
  2155     virtual void build() {
  2156       Map::build();
  2157       Item it;
  2158       const typename Map::Notifier* nf = Map::notifier();
  2159       for (nf->first(it); it != INVALID; nf->next(it)) {
  2160         Map::set(it, _inv_map.size());
  2161         _inv_map.push_back(it);
  2162       }
  2163     }
  2164 
  2165     /// \brief Clear the keys from the map.
  2166     ///
  2167     /// Clear the keys from the map. It is called by the
  2168     /// \c AlterationNotifier.
  2169     virtual void clear() {
  2170       _inv_map.clear();
  2171       Map::clear();
  2172     }
  2173 
  2174   public:
  2175 
  2176     /// \brief Returns the maximal value plus one.
  2177     ///
  2178     /// Returns the maximal value plus one in the map.
  2179     unsigned int size() const {
  2180       return _inv_map.size();
  2181     }
  2182 
  2183     /// \brief Swaps the position of the two items in the map.
  2184     ///
  2185     /// Swaps the position of the two items in the map.
  2186     void swap(const Item& p, const Item& q) {
  2187       int pi = Map::operator[](p);
  2188       int qi = Map::operator[](q);
  2189       Map::set(p, qi);
  2190       _inv_map[qi] = p;
  2191       Map::set(q, pi);
  2192       _inv_map[pi] = q;
  2193     }
  2194 
  2195     /// \brief Gives back the \e descriptor of the item.
  2196     ///
  2197     /// Gives back the mutable and unique \e descriptor of the map.
  2198     int operator[](const Item& item) const {
  2199       return Map::operator[](item);
  2200     }
  2201 
  2202     /// \brief Gives back the item by its descriptor.
  2203     ///
  2204     /// Gives back th item by its descriptor.
  2205     Item operator()(int id) const {
  2206       return _inv_map[id];
  2207     }
  2208 
  2209   private:
  2210 
  2211     typedef std::vector<Item> Container;
  2212     Container _inv_map;
  2213 
  2214   public:
  2215     /// \brief The inverse map type of DescriptorMap.
  2216     ///
  2217     /// The inverse map type of DescriptorMap.
  2218     class InverseMap {
  2219     public:
  2220       /// \brief Constructor of the InverseMap.
  2221       ///
  2222       /// Constructor of the InverseMap.
  2223       explicit InverseMap(const DescriptorMap& inverted)
  2224         : _inverted(inverted) {}
  2225 
  2226 
  2227       /// The value type of the InverseMap.
  2228       typedef typename DescriptorMap::Key Value;
  2229       /// The key type of the InverseMap.
  2230       typedef typename DescriptorMap::Value Key;
  2231 
  2232       /// \brief Subscript operator.
  2233       ///
  2234       /// Subscript operator. It gives back the item
  2235       /// that the descriptor belongs to currently.
  2236       Value operator[](const Key& key) const {
  2237         return _inverted(key);
  2238       }
  2239 
  2240       /// \brief Size of the map.
  2241       ///
  2242       /// Returns the size of the map.
  2243       unsigned int size() const {
  2244         return _inverted.size();
  2245       }
  2246 
  2247     private:
  2248       const DescriptorMap& _inverted;
  2249     };
  2250 
  2251     /// \brief Gives back the inverse of the map.
  2252     ///
  2253     /// Gives back the inverse of the map.
  2254     const InverseMap inverse() const {
  2255       return InverseMap(*this);
  2256     }
  2257   };
  2258 
  2259   /// \brief Returns the source of the given arc.
  2260   ///
  2261   /// The SourceMap gives back the source Node of the given arc.
  2262   /// \see TargetMap
  2263   template <typename Digraph>
  2264   class SourceMap {
  2265   public:
  2266 
  2267     typedef typename Digraph::Node Value;
  2268     typedef typename Digraph::Arc Key;
  2269 
  2270     /// \brief Constructor
  2271     ///
  2272     /// Constructor
  2273     /// \param _digraph The digraph that the map belongs to.
  2274     explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
  2275 
  2276     /// \brief The subscript operator.
  2277     ///
  2278     /// The subscript operator.
  2279     /// \param arc The arc
  2280     /// \return The source of the arc
  2281     Value operator[](const Key& arc) const {
  2282       return _digraph.source(arc);
  2283     }
  2284 
  2285   private:
  2286     const Digraph& _digraph;
  2287   };
  2288 
  2289   /// \brief Returns a \ref SourceMap class.
  2290   ///
  2291   /// This function just returns an \ref SourceMap class.
  2292   /// \relates SourceMap
  2293   template <typename Digraph>
  2294   inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
  2295     return SourceMap<Digraph>(digraph);
  2296   }
  2297 
  2298   /// \brief Returns the target of the given arc.
  2299   ///
  2300   /// The TargetMap gives back the target Node of the given arc.
  2301   /// \see SourceMap
  2302   template <typename Digraph>
  2303   class TargetMap {
  2304   public:
  2305 
  2306     typedef typename Digraph::Node Value;
  2307     typedef typename Digraph::Arc Key;
  2308 
  2309     /// \brief Constructor
  2310     ///
  2311     /// Constructor
  2312     /// \param _digraph The digraph that the map belongs to.
  2313     explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
  2314 
  2315     /// \brief The subscript operator.
  2316     ///
  2317     /// The subscript operator.
  2318     /// \param e The arc
  2319     /// \return The target of the arc
  2320     Value operator[](const Key& e) const {
  2321       return _digraph.target(e);
  2322     }
  2323 
  2324   private:
  2325     const Digraph& _digraph;
  2326   };
  2327 
  2328   /// \brief Returns a \ref TargetMap class.
  2329   ///
  2330   /// This function just returns a \ref TargetMap class.
  2331   /// \relates TargetMap
  2332   template <typename Digraph>
  2333   inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
  2334     return TargetMap<Digraph>(digraph);
  2335   }
  2336 
  2337   /// \brief Returns the "forward" directed arc view of an edge.
  2338   ///
  2339   /// Returns the "forward" directed arc view of an edge.
  2340   /// \see BackwardMap
  2341   template <typename Graph>
  2342   class ForwardMap {
  2343   public:
  2344 
  2345     typedef typename Graph::Arc Value;
  2346     typedef typename Graph::Edge Key;
  2347 
  2348     /// \brief Constructor
  2349     ///
  2350     /// Constructor
  2351     /// \param _graph The graph that the map belongs to.
  2352     explicit ForwardMap(const Graph& graph) : _graph(graph) {}
  2353 
  2354     /// \brief The subscript operator.
  2355     ///
  2356     /// The subscript operator.
  2357     /// \param key An edge
  2358     /// \return The "forward" directed arc view of edge
  2359     Value operator[](const Key& key) const {
  2360       return _graph.direct(key, true);
  2361     }
  2362 
  2363   private:
  2364     const Graph& _graph;
  2365   };
  2366 
  2367   /// \brief Returns a \ref ForwardMap class.
  2368   ///
  2369   /// This function just returns an \ref ForwardMap class.
  2370   /// \relates ForwardMap
  2371   template <typename Graph>
  2372   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
  2373     return ForwardMap<Graph>(graph);
  2374   }
  2375 
  2376   /// \brief Returns the "backward" directed arc view of an edge.
  2377   ///
  2378   /// Returns the "backward" directed arc view of an edge.
  2379   /// \see ForwardMap
  2380   template <typename Graph>
  2381   class BackwardMap {
  2382   public:
  2383 
  2384     typedef typename Graph::Arc Value;
  2385     typedef typename Graph::Edge Key;
  2386 
  2387     /// \brief Constructor
  2388     ///
  2389     /// Constructor
  2390     /// \param _graph The graph that the map belongs to.
  2391     explicit BackwardMap(const Graph& graph) : _graph(graph) {}
  2392 
  2393     /// \brief The subscript operator.
  2394     ///
  2395     /// The subscript operator.
  2396     /// \param key An edge
  2397     /// \return The "backward" directed arc view of edge
  2398     Value operator[](const Key& key) const {
  2399       return _graph.direct(key, false);
  2400     }
  2401 
  2402   private:
  2403     const Graph& _graph;
  2404   };
  2405 
  2406   /// \brief Returns a \ref BackwardMap class
  2407 
  2408   /// This function just returns a \ref BackwardMap class.
  2409   /// \relates BackwardMap
  2410   template <typename Graph>
  2411   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
  2412     return BackwardMap<Graph>(graph);
  2413   }
  2414 
  2415   /// \brief Potential difference map
  2416   ///
  2417   /// If there is an potential map on the nodes then we
  2418   /// can get an arc map as we get the substraction of the
  2419   /// values of the target and source.
  2420   template <typename Digraph, typename NodeMap>
  2421   class PotentialDifferenceMap {
  2422   public:
  2423     typedef typename Digraph::Arc Key;
  2424     typedef typename NodeMap::Value Value;
  2425 
  2426     /// \brief Constructor
  2427     ///
  2428     /// Contructor of the map
  2429     explicit PotentialDifferenceMap(const Digraph& digraph,
  2430                                     const NodeMap& potential)
  2431       : _digraph(digraph), _potential(potential) {}
  2432 
  2433     /// \brief Const subscription operator
  2434     ///
  2435     /// Const subscription operator
  2436     Value operator[](const Key& arc) const {
  2437       return _potential[_digraph.target(arc)] -
  2438         _potential[_digraph.source(arc)];
  2439     }
  2440 
  2441   private:
  2442     const Digraph& _digraph;
  2443     const NodeMap& _potential;
  2444   };
  2445 
  2446   /// \brief Returns a PotentialDifferenceMap.
  2447   ///
  2448   /// This function just returns a PotentialDifferenceMap.
  2449   /// \relates PotentialDifferenceMap
  2450   template <typename Digraph, typename NodeMap>
  2451   PotentialDifferenceMap<Digraph, NodeMap>
  2452   potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
  2453     return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
  2454   }
  2455 
  2456   /// \brief Map of the node in-degrees.
  2457   ///
  2458   /// This map returns the in-degree of a node. Once it is constructed,
  2459   /// the degrees are stored in a standard NodeMap, so each query is done
  2460   /// in constant time. On the other hand, the values are updated automatically
  2461   /// whenever the digraph changes.
  2462   ///
  2463   /// \warning Besides addNode() and addArc(), a digraph structure may provide
  2464   /// alternative ways to modify the digraph. The correct behavior of InDegMap
  2465   /// is not guarantied if these additional features are used. For example
  2466   /// the functions \ref ListDigraph::changeSource() "changeSource()",
  2467   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  2468   /// \ref ListDigraph::reverseArc() "reverseArc()"
  2469   /// of \ref ListDigraph will \e not update the degree values correctly.
  2470   ///
  2471   /// \sa OutDegMap
  2472 
  2473   template <typename _Digraph>
  2474   class InDegMap
  2475     : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
  2476       ::ItemNotifier::ObserverBase {
  2477 
  2478   public:
  2479 
  2480     typedef _Digraph Digraph;
  2481     typedef int Value;
  2482     typedef typename Digraph::Node Key;
  2483 
  2484     typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
  2485     ::ItemNotifier::ObserverBase Parent;
  2486 
  2487   private:
  2488 
  2489     class AutoNodeMap
  2490       : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
  2491     public:
  2492 
  2493       typedef typename ItemSetTraits<Digraph, Key>::
  2494       template Map<int>::Type Parent;
  2495 
  2496       AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
  2497 
  2498       virtual void add(const Key& key) {
  2499         Parent::add(key);
  2500         Parent::set(key, 0);
  2501       }
  2502 
  2503       virtual void add(const std::vector<Key>& keys) {
  2504         Parent::add(keys);
  2505         for (int i = 0; i < int(keys.size()); ++i) {
  2506           Parent::set(keys[i], 0);
  2507         }
  2508       }
  2509 
  2510       virtual void build() {
  2511         Parent::build();
  2512         Key it;
  2513         typename Parent::Notifier* nf = Parent::notifier();
  2514         for (nf->first(it); it != INVALID; nf->next(it)) {
  2515           Parent::set(it, 0);
  2516         }
  2517       }
  2518     };
  2519 
  2520   public:
  2521 
  2522     /// \brief Constructor.
  2523     ///
  2524     /// Constructor for creating in-degree map.
  2525     explicit InDegMap(const Digraph& digraph)
  2526       : _digraph(digraph), _deg(digraph) {
  2527       Parent::attach(_digraph.notifier(typename Digraph::Arc()));
  2528 
  2529       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2530         _deg[it] = countInArcs(_digraph, it);
  2531       }
  2532     }
  2533 
  2534     /// Gives back the in-degree of a Node.
  2535     int operator[](const Key& key) const {
  2536       return _deg[key];
  2537     }
  2538 
  2539   protected:
  2540 
  2541     typedef typename Digraph::Arc Arc;
  2542 
  2543     virtual void add(const Arc& arc) {
  2544       ++_deg[_digraph.target(arc)];
  2545     }
  2546 
  2547     virtual void add(const std::vector<Arc>& arcs) {
  2548       for (int i = 0; i < int(arcs.size()); ++i) {
  2549         ++_deg[_digraph.target(arcs[i])];
  2550       }
  2551     }
  2552 
  2553     virtual void erase(const Arc& arc) {
  2554       --_deg[_digraph.target(arc)];
  2555     }
  2556 
  2557     virtual void erase(const std::vector<Arc>& arcs) {
  2558       for (int i = 0; i < int(arcs.size()); ++i) {
  2559         --_deg[_digraph.target(arcs[i])];
  2560       }
  2561     }
  2562 
  2563     virtual void build() {
  2564       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2565         _deg[it] = countInArcs(_digraph, it);
  2566       }
  2567     }
  2568 
  2569     virtual void clear() {
  2570       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2571         _deg[it] = 0;
  2572       }
  2573     }
  2574   private:
  2575 
  2576     const Digraph& _digraph;
  2577     AutoNodeMap _deg;
  2578   };
  2579 
  2580   /// \brief Map of the node out-degrees.
  2581   ///
  2582   /// This map returns the out-degree of a node. Once it is constructed,
  2583   /// the degrees are stored in a standard NodeMap, so each query is done
  2584   /// in constant time. On the other hand, the values are updated automatically
  2585   /// whenever the digraph changes.
  2586   ///
  2587   /// \warning Besides addNode() and addArc(), a digraph structure may provide
  2588   /// alternative ways to modify the digraph. The correct behavior of OutDegMap
  2589   /// is not guarantied if these additional features are used. For example
  2590   /// the functions \ref ListDigraph::changeSource() "changeSource()",
  2591   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  2592   /// \ref ListDigraph::reverseArc() "reverseArc()"
  2593   /// of \ref ListDigraph will \e not update the degree values correctly.
  2594   ///
  2595   /// \sa InDegMap
  2596 
  2597   template <typename _Digraph>
  2598   class OutDegMap
  2599     : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
  2600       ::ItemNotifier::ObserverBase {
  2601 
  2602   public:
  2603 
  2604     typedef _Digraph Digraph;
  2605     typedef int Value;
  2606     typedef typename Digraph::Node Key;
  2607 
  2608     typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
  2609     ::ItemNotifier::ObserverBase Parent;
  2610 
  2611   private:
  2612 
  2613     class AutoNodeMap
  2614       : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
  2615     public:
  2616 
  2617       typedef typename ItemSetTraits<Digraph, Key>::
  2618       template Map<int>::Type Parent;
  2619 
  2620       AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
  2621 
  2622       virtual void add(const Key& key) {
  2623         Parent::add(key);
  2624         Parent::set(key, 0);
  2625       }
  2626       virtual void add(const std::vector<Key>& keys) {
  2627         Parent::add(keys);
  2628         for (int i = 0; i < int(keys.size()); ++i) {
  2629           Parent::set(keys[i], 0);
  2630         }
  2631       }
  2632       virtual void build() {
  2633         Parent::build();
  2634         Key it;
  2635         typename Parent::Notifier* nf = Parent::notifier();
  2636         for (nf->first(it); it != INVALID; nf->next(it)) {
  2637           Parent::set(it, 0);
  2638         }
  2639       }
  2640     };
  2641 
  2642   public:
  2643 
  2644     /// \brief Constructor.
  2645     ///
  2646     /// Constructor for creating out-degree map.
  2647     explicit OutDegMap(const Digraph& digraph)
  2648       : _digraph(digraph), _deg(digraph) {
  2649       Parent::attach(_digraph.notifier(typename Digraph::Arc()));
  2650 
  2651       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2652         _deg[it] = countOutArcs(_digraph, it);
  2653       }
  2654     }
  2655 
  2656     /// Gives back the out-degree of a Node.
  2657     int operator[](const Key& key) const {
  2658       return _deg[key];
  2659     }
  2660 
  2661   protected:
  2662 
  2663     typedef typename Digraph::Arc Arc;
  2664 
  2665     virtual void add(const Arc& arc) {
  2666       ++_deg[_digraph.source(arc)];
  2667     }
  2668 
  2669     virtual void add(const std::vector<Arc>& arcs) {
  2670       for (int i = 0; i < int(arcs.size()); ++i) {
  2671         ++_deg[_digraph.source(arcs[i])];
  2672       }
  2673     }
  2674 
  2675     virtual void erase(const Arc& arc) {
  2676       --_deg[_digraph.source(arc)];
  2677     }
  2678 
  2679     virtual void erase(const std::vector<Arc>& arcs) {
  2680       for (int i = 0; i < int(arcs.size()); ++i) {
  2681         --_deg[_digraph.source(arcs[i])];
  2682       }
  2683     }
  2684 
  2685     virtual void build() {
  2686       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2687         _deg[it] = countOutArcs(_digraph, it);
  2688       }
  2689     }
  2690 
  2691     virtual void clear() {
  2692       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2693         _deg[it] = 0;
  2694       }
  2695     }
  2696   private:
  2697 
  2698     const Digraph& _digraph;
  2699     AutoNodeMap _deg;
  2700   };
  2701 
  2702   /// @}
  2703 }
  2704 
  2705 #endif // LEMON_MAPS_H