lemon/maps.h
changeset 557 7ab97e2a0c33
parent 440 88ed40ad0d4f
child 564 be6646ac5d89
equal deleted inserted replaced
28:82bfc715d7c7 29:a57b20ae1999
    61   ///
    61   ///
    62   /// \sa ConstMap
    62   /// \sa ConstMap
    63   template<typename K, typename V>
    63   template<typename K, typename V>
    64   class NullMap : public MapBase<K, V> {
    64   class NullMap : public MapBase<K, V> {
    65   public:
    65   public:
    66     typedef MapBase<K, V> Parent;
    66     ///\e
    67     typedef typename Parent::Key Key;
    67     typedef K Key;
    68     typedef typename Parent::Value Value;
    68     ///\e
       
    69     typedef V Value;
    69 
    70 
    70     /// Gives back a default constructed element.
    71     /// Gives back a default constructed element.
    71     Value operator[](const Key&) const { return Value(); }
    72     Value operator[](const Key&) const { return Value(); }
    72     /// Absorbs the value.
    73     /// Absorbs the value.
    73     void set(const Key&, const Value&) {}
    74     void set(const Key&, const Value&) {}
   100   template<typename K, typename V>
   101   template<typename K, typename V>
   101   class ConstMap : public MapBase<K, V> {
   102   class ConstMap : public MapBase<K, V> {
   102   private:
   103   private:
   103     V _value;
   104     V _value;
   104   public:
   105   public:
   105     typedef MapBase<K, V> Parent;
   106     ///\e
   106     typedef typename Parent::Key Key;
   107     typedef K Key;
   107     typedef typename Parent::Value Value;
   108     ///\e
       
   109     typedef V Value;
   108 
   110 
   109     /// Default constructor
   111     /// Default constructor
   110 
   112 
   111     /// Default constructor.
   113     /// Default constructor.
   112     /// The value of the map will be default constructed.
   114     /// The value of the map will be default constructed.
   166   /// \sa NullMap
   168   /// \sa NullMap
   167   /// \sa IdentityMap
   169   /// \sa IdentityMap
   168   template<typename K, typename V, V v>
   170   template<typename K, typename V, V v>
   169   class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
   171   class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
   170   public:
   172   public:
   171     typedef MapBase<K, V> Parent;
   173     ///\e
   172     typedef typename Parent::Key Key;
   174     typedef K Key;
   173     typedef typename Parent::Value Value;
   175     ///\e
       
   176     typedef V Value;
   174 
   177 
   175     /// Constructor.
   178     /// Constructor.
   176     ConstMap() {}
   179     ConstMap() {}
   177 
   180 
   178     /// Gives back the specified value.
   181     /// Gives back the specified value.
   200   ///
   203   ///
   201   /// \sa ConstMap
   204   /// \sa ConstMap
   202   template <typename T>
   205   template <typename T>
   203   class IdentityMap : public MapBase<T, T> {
   206   class IdentityMap : public MapBase<T, T> {
   204   public:
   207   public:
   205     typedef MapBase<T, T> Parent;
   208     ///\e
   206     typedef typename Parent::Key Key;
   209     typedef T Key;
   207     typedef typename Parent::Value Value;
   210     ///\e
       
   211     typedef T Value;
   208 
   212 
   209     /// Gives back the given value without any modification.
   213     /// Gives back the given value without any modification.
   210     Value operator[](const Key &k) const {
   214     Value operator[](const Key &k) const {
   211       return k;
   215       return k;
   212     }
   216     }
   243     typedef std::vector<V> Vector;
   247     typedef std::vector<V> Vector;
   244     Vector _vector;
   248     Vector _vector;
   245 
   249 
   246   public:
   250   public:
   247 
   251 
   248     typedef MapBase<int, V> Parent;
       
   249     /// Key type
   252     /// Key type
   250     typedef typename Parent::Key Key;
   253     typedef int Key;
   251     /// Value type
   254     /// Value type
   252     typedef typename Parent::Value Value;
   255     typedef V Value;
   253     /// Reference type
   256     /// Reference type
   254     typedef typename Vector::reference Reference;
   257     typedef typename Vector::reference Reference;
   255     /// Const reference type
   258     /// Const reference type
   256     typedef typename Vector::const_reference ConstReference;
   259     typedef typename Vector::const_reference ConstReference;
   257 
   260 
   351   /// However keep in mind that it is usually not as efficient as other
   354   /// However keep in mind that it is usually not as efficient as other
   352   /// maps.
   355   /// maps.
   353   ///
   356   ///
   354   /// The simplest way of using this map is through the sparseMap()
   357   /// The simplest way of using this map is through the sparseMap()
   355   /// function.
   358   /// function.
   356   template <typename K, typename V, typename Compare = std::less<K> >
   359   template <typename K, typename V, typename Comp = std::less<K> >
   357   class SparseMap : public MapBase<K, V> {
   360   class SparseMap : public MapBase<K, V> {
   358     template <typename K1, typename V1, typename C1>
   361     template <typename K1, typename V1, typename C1>
   359     friend class SparseMap;
   362     friend class SparseMap;
   360   public:
   363   public:
   361 
   364 
   362     typedef MapBase<K, V> Parent;
       
   363     /// Key type
   365     /// Key type
   364     typedef typename Parent::Key Key;
   366     typedef K Key;
   365     /// Value type
   367     /// Value type
   366     typedef typename Parent::Value Value;
   368     typedef V Value;
   367     /// Reference type
   369     /// Reference type
   368     typedef Value& Reference;
   370     typedef Value& Reference;
   369     /// Const reference type
   371     /// Const reference type
   370     typedef const Value& ConstReference;
   372     typedef const Value& ConstReference;
   371 
   373 
   372     typedef True ReferenceMapTag;
   374     typedef True ReferenceMapTag;
   373 
   375 
   374   private:
   376   private:
   375 
   377 
   376     typedef std::map<K, V, Compare> Map;
   378     typedef std::map<K, V, Comp> Map;
   377     Map _map;
   379     Map _map;
   378     Value _value;
   380     Value _value;
   379 
   381 
   380   public:
   382   public:
   381 
   383 
   487   template <typename M1, typename M2>
   489   template <typename M1, typename M2>
   488   class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
   490   class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
   489     const M1 &_m1;
   491     const M1 &_m1;
   490     const M2 &_m2;
   492     const M2 &_m2;
   491   public:
   493   public:
   492     typedef MapBase<typename M2::Key, typename M1::Value> Parent;
   494     ///\e
   493     typedef typename Parent::Key Key;
   495     typedef typename M2::Key Key;
   494     typedef typename Parent::Value Value;
   496     ///\e
       
   497     typedef typename M1::Value Value;
   495 
   498 
   496     /// Constructor
   499     /// Constructor
   497     ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   500     ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   498 
   501 
   499     /// \e
   502     ///\e
   500     typename MapTraits<M1>::ConstReturnValue
   503     typename MapTraits<M1>::ConstReturnValue
   501     operator[](const Key &k) const { return _m1[_m2[k]]; }
   504     operator[](const Key &k) const { return _m1[_m2[k]]; }
   502   };
   505   };
   503 
   506 
   504   /// Returns a \c ComposeMap class
   507   /// Returns a \c ComposeMap class
   543   class CombineMap : public MapBase<typename M1::Key, V> {
   546   class CombineMap : public MapBase<typename M1::Key, V> {
   544     const M1 &_m1;
   547     const M1 &_m1;
   545     const M2 &_m2;
   548     const M2 &_m2;
   546     F _f;
   549     F _f;
   547   public:
   550   public:
   548     typedef MapBase<typename M1::Key, V> Parent;
   551     ///\e
   549     typedef typename Parent::Key Key;
   552     typedef typename M1::Key Key;
   550     typedef typename Parent::Value Value;
   553     ///\e
       
   554     typedef V Value;
   551 
   555 
   552     /// Constructor
   556     /// Constructor
   553     CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
   557     CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
   554       : _m1(m1), _m2(m2), _f(f) {}
   558       : _m1(m1), _m2(m2), _f(f) {}
   555     /// \e
   559     ///\e
   556     Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
   560     Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
   557   };
   561   };
   558 
   562 
   559   /// Returns a \c CombineMap class
   563   /// Returns a \c CombineMap class
   560 
   564 
   613            typename K = typename F::argument_type,
   617            typename K = typename F::argument_type,
   614            typename V = typename F::result_type>
   618            typename V = typename F::result_type>
   615   class FunctorToMap : public MapBase<K, V> {
   619   class FunctorToMap : public MapBase<K, V> {
   616     F _f;
   620     F _f;
   617   public:
   621   public:
   618     typedef MapBase<K, V> Parent;
   622     ///\e
   619     typedef typename Parent::Key Key;
   623     typedef K Key;
   620     typedef typename Parent::Value Value;
   624     ///\e
       
   625     typedef V Value;
   621 
   626 
   622     /// Constructor
   627     /// Constructor
   623     FunctorToMap(const F &f = F()) : _f(f) {}
   628     FunctorToMap(const F &f = F()) : _f(f) {}
   624     /// \e
   629     ///\e
   625     Value operator[](const Key &k) const { return _f(k); }
   630     Value operator[](const Key &k) const { return _f(k); }
   626   };
   631   };
   627 
   632 
   628   /// Returns a \c FunctorToMap class
   633   /// Returns a \c FunctorToMap class
   629 
   634 
   667   ///\sa FunctorToMap
   672   ///\sa FunctorToMap
   668   template <typename M>
   673   template <typename M>
   669   class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
   674   class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
   670     const M &_m;
   675     const M &_m;
   671   public:
   676   public:
   672     typedef MapBase<typename M::Key, typename M::Value> Parent;
   677     ///\e
   673     typedef typename Parent::Key Key;
   678     typedef typename M::Key Key;
   674     typedef typename Parent::Value Value;
   679     ///\e
   675 
   680     typedef typename M::Value Value;
   676     typedef typename Parent::Key argument_type;
   681 
   677     typedef typename Parent::Value result_type;
   682     typedef typename M::Key argument_type;
       
   683     typedef typename M::Value result_type;
   678 
   684 
   679     /// Constructor
   685     /// Constructor
   680     MapToFunctor(const M &m) : _m(m) {}
   686     MapToFunctor(const M &m) : _m(m) {}
   681     /// \e
   687     ///\e
   682     Value operator()(const Key &k) const { return _m[k]; }
   688     Value operator()(const Key &k) const { return _m[k]; }
   683     /// \e
   689     ///\e
   684     Value operator[](const Key &k) const { return _m[k]; }
   690     Value operator[](const Key &k) const { return _m[k]; }
   685   };
   691   };
   686 
   692 
   687   /// Returns a \c MapToFunctor class
   693   /// Returns a \c MapToFunctor class
   688 
   694 
   707   /// function.
   713   /// function.
   708   template <typename M, typename V>
   714   template <typename M, typename V>
   709   class ConvertMap : public MapBase<typename M::Key, V> {
   715   class ConvertMap : public MapBase<typename M::Key, V> {
   710     const M &_m;
   716     const M &_m;
   711   public:
   717   public:
   712     typedef MapBase<typename M::Key, V> Parent;
   718     ///\e
   713     typedef typename Parent::Key Key;
   719     typedef typename M::Key Key;
   714     typedef typename Parent::Value Value;
   720     ///\e
       
   721     typedef V Value;
   715 
   722 
   716     /// Constructor
   723     /// Constructor
   717 
   724 
   718     /// Constructor.
   725     /// Constructor.
   719     /// \param m The underlying map.
   726     /// \param m The underlying map.
   720     ConvertMap(const M &m) : _m(m) {}
   727     ConvertMap(const M &m) : _m(m) {}
   721 
   728 
   722     /// \e
   729     ///\e
   723     Value operator[](const Key &k) const { return _m[k]; }
   730     Value operator[](const Key &k) const { return _m[k]; }
   724   };
   731   };
   725 
   732 
   726   /// Returns a \c ConvertMap class
   733   /// Returns a \c ConvertMap class
   727 
   734 
   749   template<typename  M1, typename M2>
   756   template<typename  M1, typename M2>
   750   class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
   757   class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
   751     M1 &_m1;
   758     M1 &_m1;
   752     M2 &_m2;
   759     M2 &_m2;
   753   public:
   760   public:
   754     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   761     ///\e
   755     typedef typename Parent::Key Key;
   762     typedef typename M1::Key Key;
   756     typedef typename Parent::Value Value;
   763     ///\e
       
   764     typedef typename M1::Value Value;
   757 
   765 
   758     /// Constructor
   766     /// Constructor
   759     ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
   767     ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
   760     /// Returns the value associated with the given key in the first map.
   768     /// Returns the value associated with the given key in the first map.
   761     Value operator[](const Key &k) const { return _m1[k]; }
   769     Value operator[](const Key &k) const { return _m1[k]; }
   795   template<typename M1, typename M2>
   803   template<typename M1, typename M2>
   796   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
   804   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
   797     const M1 &_m1;
   805     const M1 &_m1;
   798     const M2 &_m2;
   806     const M2 &_m2;
   799   public:
   807   public:
   800     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   808     ///\e
   801     typedef typename Parent::Key Key;
   809     typedef typename M1::Key Key;
   802     typedef typename Parent::Value Value;
   810     ///\e
       
   811     typedef typename M1::Value Value;
   803 
   812 
   804     /// Constructor
   813     /// Constructor
   805     AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   814     AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   806     /// \e
   815     ///\e
   807     Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
   816     Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
   808   };
   817   };
   809 
   818 
   810   /// Returns an \c AddMap class
   819   /// Returns an \c AddMap class
   811 
   820 
   843   template<typename M1, typename M2>
   852   template<typename M1, typename M2>
   844   class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
   853   class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
   845     const M1 &_m1;
   854     const M1 &_m1;
   846     const M2 &_m2;
   855     const M2 &_m2;
   847   public:
   856   public:
   848     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   857     ///\e
   849     typedef typename Parent::Key Key;
   858     typedef typename M1::Key Key;
   850     typedef typename Parent::Value Value;
   859     ///\e
       
   860     typedef typename M1::Value Value;
   851 
   861 
   852     /// Constructor
   862     /// Constructor
   853     SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   863     SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   854     /// \e
   864     ///\e
   855     Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
   865     Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
   856   };
   866   };
   857 
   867 
   858   /// Returns a \c SubMap class
   868   /// Returns a \c SubMap class
   859 
   869 
   892   template<typename M1, typename M2>
   902   template<typename M1, typename M2>
   893   class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
   903   class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
   894     const M1 &_m1;
   904     const M1 &_m1;
   895     const M2 &_m2;
   905     const M2 &_m2;
   896   public:
   906   public:
   897     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   907     ///\e
   898     typedef typename Parent::Key Key;
   908     typedef typename M1::Key Key;
   899     typedef typename Parent::Value Value;
   909     ///\e
       
   910     typedef typename M1::Value Value;
   900 
   911 
   901     /// Constructor
   912     /// Constructor
   902     MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   913     MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   903     /// \e
   914     ///\e
   904     Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
   915     Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
   905   };
   916   };
   906 
   917 
   907   /// Returns a \c MulMap class
   918   /// Returns a \c MulMap class
   908 
   919 
   940   template<typename M1, typename M2>
   951   template<typename M1, typename M2>
   941   class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
   952   class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
   942     const M1 &_m1;
   953     const M1 &_m1;
   943     const M2 &_m2;
   954     const M2 &_m2;
   944   public:
   955   public:
   945     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   956     ///\e
   946     typedef typename Parent::Key Key;
   957     typedef typename M1::Key Key;
   947     typedef typename Parent::Value Value;
   958     ///\e
       
   959     typedef typename M1::Value Value;
   948 
   960 
   949     /// Constructor
   961     /// Constructor
   950     DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   962     DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   951     /// \e
   963     ///\e
   952     Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
   964     Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
   953   };
   965   };
   954 
   966 
   955   /// Returns a \c DivMap class
   967   /// Returns a \c DivMap class
   956 
   968 
   990   template<typename M, typename C = typename M::Value>
  1002   template<typename M, typename C = typename M::Value>
   991   class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
  1003   class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
   992     const M &_m;
  1004     const M &_m;
   993     C _v;
  1005     C _v;
   994   public:
  1006   public:
   995     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1007     ///\e
   996     typedef typename Parent::Key Key;
  1008     typedef typename M::Key Key;
   997     typedef typename Parent::Value Value;
  1009     ///\e
       
  1010     typedef typename M::Value Value;
   998 
  1011 
   999     /// Constructor
  1012     /// Constructor
  1000 
  1013 
  1001     /// Constructor.
  1014     /// Constructor.
  1002     /// \param m The undelying map.
  1015     /// \param m The undelying map.
  1003     /// \param v The constant value.
  1016     /// \param v The constant value.
  1004     ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
  1017     ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
  1005     /// \e
  1018     ///\e
  1006     Value operator[](const Key &k) const { return _m[k]+_v; }
  1019     Value operator[](const Key &k) const { return _m[k]+_v; }
  1007   };
  1020   };
  1008 
  1021 
  1009   /// Shifts a map with a constant (read-write version).
  1022   /// Shifts a map with a constant (read-write version).
  1010 
  1023 
  1020   template<typename M, typename C = typename M::Value>
  1033   template<typename M, typename C = typename M::Value>
  1021   class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1034   class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1022     M &_m;
  1035     M &_m;
  1023     C _v;
  1036     C _v;
  1024   public:
  1037   public:
  1025     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1038     ///\e
  1026     typedef typename Parent::Key Key;
  1039     typedef typename M::Key Key;
  1027     typedef typename Parent::Value Value;
  1040     ///\e
       
  1041     typedef typename M::Value Value;
  1028 
  1042 
  1029     /// Constructor
  1043     /// Constructor
  1030 
  1044 
  1031     /// Constructor.
  1045     /// Constructor.
  1032     /// \param m The undelying map.
  1046     /// \param m The undelying map.
  1033     /// \param v The constant value.
  1047     /// \param v The constant value.
  1034     ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  1048     ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  1035     /// \e
  1049     ///\e
  1036     Value operator[](const Key &k) const { return _m[k]+_v; }
  1050     Value operator[](const Key &k) const { return _m[k]+_v; }
  1037     /// \e
  1051     ///\e
  1038     void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
  1052     void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
  1039   };
  1053   };
  1040 
  1054 
  1041   /// Returns a \c ShiftMap class
  1055   /// Returns a \c ShiftMap class
  1042 
  1056 
  1091   template<typename M, typename C = typename M::Value>
  1105   template<typename M, typename C = typename M::Value>
  1092   class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
  1106   class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
  1093     const M &_m;
  1107     const M &_m;
  1094     C _v;
  1108     C _v;
  1095   public:
  1109   public:
  1096     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1110     ///\e
  1097     typedef typename Parent::Key Key;
  1111     typedef typename M::Key Key;
  1098     typedef typename Parent::Value Value;
  1112     ///\e
       
  1113     typedef typename M::Value Value;
  1099 
  1114 
  1100     /// Constructor
  1115     /// Constructor
  1101 
  1116 
  1102     /// Constructor.
  1117     /// Constructor.
  1103     /// \param m The undelying map.
  1118     /// \param m The undelying map.
  1104     /// \param v The constant value.
  1119     /// \param v The constant value.
  1105     ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
  1120     ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
  1106     /// \e
  1121     ///\e
  1107     Value operator[](const Key &k) const { return _v*_m[k]; }
  1122     Value operator[](const Key &k) const { return _v*_m[k]; }
  1108   };
  1123   };
  1109 
  1124 
  1110   /// Scales a map with a constant (read-write version).
  1125   /// Scales a map with a constant (read-write version).
  1111 
  1126 
  1122   template<typename M, typename C = typename M::Value>
  1137   template<typename M, typename C = typename M::Value>
  1123   class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1138   class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1124     M &_m;
  1139     M &_m;
  1125     C _v;
  1140     C _v;
  1126   public:
  1141   public:
  1127     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1142     ///\e
  1128     typedef typename Parent::Key Key;
  1143     typedef typename M::Key Key;
  1129     typedef typename Parent::Value Value;
  1144     ///\e
       
  1145     typedef typename M::Value Value;
  1130 
  1146 
  1131     /// Constructor
  1147     /// Constructor
  1132 
  1148 
  1133     /// Constructor.
  1149     /// Constructor.
  1134     /// \param m The undelying map.
  1150     /// \param m The undelying map.
  1135     /// \param v The constant value.
  1151     /// \param v The constant value.
  1136     ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  1152     ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  1137     /// \e
  1153     ///\e
  1138     Value operator[](const Key &k) const { return _v*_m[k]; }
  1154     Value operator[](const Key &k) const { return _v*_m[k]; }
  1139     /// \e
  1155     ///\e
  1140     void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
  1156     void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
  1141   };
  1157   };
  1142 
  1158 
  1143   /// Returns a \c ScaleMap class
  1159   /// Returns a \c ScaleMap class
  1144 
  1160 
  1191   /// \sa NegWriteMap
  1207   /// \sa NegWriteMap
  1192   template<typename M>
  1208   template<typename M>
  1193   class NegMap : public MapBase<typename M::Key, typename M::Value> {
  1209   class NegMap : public MapBase<typename M::Key, typename M::Value> {
  1194     const M& _m;
  1210     const M& _m;
  1195   public:
  1211   public:
  1196     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1212     ///\e
  1197     typedef typename Parent::Key Key;
  1213     typedef typename M::Key Key;
  1198     typedef typename Parent::Value Value;
  1214     ///\e
       
  1215     typedef typename M::Value Value;
  1199 
  1216 
  1200     /// Constructor
  1217     /// Constructor
  1201     NegMap(const M &m) : _m(m) {}
  1218     NegMap(const M &m) : _m(m) {}
  1202     /// \e
  1219     ///\e
  1203     Value operator[](const Key &k) const { return -_m[k]; }
  1220     Value operator[](const Key &k) const { return -_m[k]; }
  1204   };
  1221   };
  1205 
  1222 
  1206   /// Negative of a map (read-write version)
  1223   /// Negative of a map (read-write version)
  1207 
  1224 
  1226   /// \sa NegMap
  1243   /// \sa NegMap
  1227   template<typename M>
  1244   template<typename M>
  1228   class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1245   class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1229     M &_m;
  1246     M &_m;
  1230   public:
  1247   public:
  1231     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1248     ///\e
  1232     typedef typename Parent::Key Key;
  1249     typedef typename M::Key Key;
  1233     typedef typename Parent::Value Value;
  1250     ///\e
       
  1251     typedef typename M::Value Value;
  1234 
  1252 
  1235     /// Constructor
  1253     /// Constructor
  1236     NegWriteMap(M &m) : _m(m) {}
  1254     NegWriteMap(M &m) : _m(m) {}
  1237     /// \e
  1255     ///\e
  1238     Value operator[](const Key &k) const { return -_m[k]; }
  1256     Value operator[](const Key &k) const { return -_m[k]; }
  1239     /// \e
  1257     ///\e
  1240     void set(const Key &k, const Value &v) { _m.set(k, -v); }
  1258     void set(const Key &k, const Value &v) { _m.set(k, -v); }
  1241   };
  1259   };
  1242 
  1260 
  1243   /// Returns a \c NegMap class
  1261   /// Returns a \c NegMap class
  1244 
  1262 
  1280   /// function.
  1298   /// function.
  1281   template<typename M>
  1299   template<typename M>
  1282   class AbsMap : public MapBase<typename M::Key, typename M::Value> {
  1300   class AbsMap : public MapBase<typename M::Key, typename M::Value> {
  1283     const M &_m;
  1301     const M &_m;
  1284   public:
  1302   public:
  1285     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1303     ///\e
  1286     typedef typename Parent::Key Key;
  1304     typedef typename M::Key Key;
  1287     typedef typename Parent::Value Value;
  1305     ///\e
       
  1306     typedef typename M::Value Value;
  1288 
  1307 
  1289     /// Constructor
  1308     /// Constructor
  1290     AbsMap(const M &m) : _m(m) {}
  1309     AbsMap(const M &m) : _m(m) {}
  1291     /// \e
  1310     ///\e
  1292     Value operator[](const Key &k) const {
  1311     Value operator[](const Key &k) const {
  1293       Value tmp = _m[k];
  1312       Value tmp = _m[k];
  1294       return tmp >= 0 ? tmp : -tmp;
  1313       return tmp >= 0 ? tmp : -tmp;
  1295     }
  1314     }
  1296 
  1315 
  1335   /// \sa FalseMap
  1354   /// \sa FalseMap
  1336   /// \sa ConstMap
  1355   /// \sa ConstMap
  1337   template <typename K>
  1356   template <typename K>
  1338   class TrueMap : public MapBase<K, bool> {
  1357   class TrueMap : public MapBase<K, bool> {
  1339   public:
  1358   public:
  1340     typedef MapBase<K, bool> Parent;
  1359     ///\e
  1341     typedef typename Parent::Key Key;
  1360     typedef K Key;
  1342     typedef typename Parent::Value Value;
  1361     ///\e
       
  1362     typedef bool Value;
  1343 
  1363 
  1344     /// Gives back \c true.
  1364     /// Gives back \c true.
  1345     Value operator[](const Key&) const { return true; }
  1365     Value operator[](const Key&) const { return true; }
  1346   };
  1366   };
  1347 
  1367 
  1372   /// \sa TrueMap
  1392   /// \sa TrueMap
  1373   /// \sa ConstMap
  1393   /// \sa ConstMap
  1374   template <typename K>
  1394   template <typename K>
  1375   class FalseMap : public MapBase<K, bool> {
  1395   class FalseMap : public MapBase<K, bool> {
  1376   public:
  1396   public:
  1377     typedef MapBase<K, bool> Parent;
  1397     ///\e
  1378     typedef typename Parent::Key Key;
  1398     typedef K Key;
  1379     typedef typename Parent::Value Value;
  1399     ///\e
       
  1400     typedef bool Value;
  1380 
  1401 
  1381     /// Gives back \c false.
  1402     /// Gives back \c false.
  1382     Value operator[](const Key&) const { return false; }
  1403     Value operator[](const Key&) const { return false; }
  1383   };
  1404   };
  1384 
  1405 
  1417   template<typename M1, typename M2>
  1438   template<typename M1, typename M2>
  1418   class AndMap : public MapBase<typename M1::Key, bool> {
  1439   class AndMap : public MapBase<typename M1::Key, bool> {
  1419     const M1 &_m1;
  1440     const M1 &_m1;
  1420     const M2 &_m2;
  1441     const M2 &_m2;
  1421   public:
  1442   public:
  1422     typedef MapBase<typename M1::Key, bool> Parent;
  1443     ///\e
  1423     typedef typename Parent::Key Key;
  1444     typedef typename M1::Key Key;
  1424     typedef typename Parent::Value Value;
  1445     ///\e
       
  1446     typedef bool Value;
  1425 
  1447 
  1426     /// Constructor
  1448     /// Constructor
  1427     AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1449     AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1428     /// \e
  1450     ///\e
  1429     Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
  1451     Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
  1430   };
  1452   };
  1431 
  1453 
  1432   /// Returns an \c AndMap class
  1454   /// Returns an \c AndMap class
  1433 
  1455 
  1465   template<typename M1, typename M2>
  1487   template<typename M1, typename M2>
  1466   class OrMap : public MapBase<typename M1::Key, bool> {
  1488   class OrMap : public MapBase<typename M1::Key, bool> {
  1467     const M1 &_m1;
  1489     const M1 &_m1;
  1468     const M2 &_m2;
  1490     const M2 &_m2;
  1469   public:
  1491   public:
  1470     typedef MapBase<typename M1::Key, bool> Parent;
  1492     ///\e
  1471     typedef typename Parent::Key Key;
  1493     typedef typename M1::Key Key;
  1472     typedef typename Parent::Value Value;
  1494     ///\e
       
  1495     typedef bool Value;
  1473 
  1496 
  1474     /// Constructor
  1497     /// Constructor
  1475     OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1498     OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1476     /// \e
  1499     ///\e
  1477     Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
  1500     Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
  1478   };
  1501   };
  1479 
  1502 
  1480   /// Returns an \c OrMap class
  1503   /// Returns an \c OrMap class
  1481 
  1504 
  1504   /// \sa NotWriteMap
  1527   /// \sa NotWriteMap
  1505   template <typename M>
  1528   template <typename M>
  1506   class NotMap : public MapBase<typename M::Key, bool> {
  1529   class NotMap : public MapBase<typename M::Key, bool> {
  1507     const M &_m;
  1530     const M &_m;
  1508   public:
  1531   public:
  1509     typedef MapBase<typename M::Key, bool> Parent;
  1532     ///\e
  1510     typedef typename Parent::Key Key;
  1533     typedef typename M::Key Key;
  1511     typedef typename Parent::Value Value;
  1534     ///\e
       
  1535     typedef bool Value;
  1512 
  1536 
  1513     /// Constructor
  1537     /// Constructor
  1514     NotMap(const M &m) : _m(m) {}
  1538     NotMap(const M &m) : _m(m) {}
  1515     /// \e
  1539     ///\e
  1516     Value operator[](const Key &k) const { return !_m[k]; }
  1540     Value operator[](const Key &k) const { return !_m[k]; }
  1517   };
  1541   };
  1518 
  1542 
  1519   /// Logical 'not' of a map (read-write version)
  1543   /// Logical 'not' of a map (read-write version)
  1520 
  1544 
  1530   /// \sa NotMap
  1554   /// \sa NotMap
  1531   template <typename M>
  1555   template <typename M>
  1532   class NotWriteMap : public MapBase<typename M::Key, bool> {
  1556   class NotWriteMap : public MapBase<typename M::Key, bool> {
  1533     M &_m;
  1557     M &_m;
  1534   public:
  1558   public:
  1535     typedef MapBase<typename M::Key, bool> Parent;
  1559     ///\e
  1536     typedef typename Parent::Key Key;
  1560     typedef typename M::Key Key;
  1537     typedef typename Parent::Value Value;
  1561     ///\e
       
  1562     typedef bool Value;
  1538 
  1563 
  1539     /// Constructor
  1564     /// Constructor
  1540     NotWriteMap(M &m) : _m(m) {}
  1565     NotWriteMap(M &m) : _m(m) {}
  1541     /// \e
  1566     ///\e
  1542     Value operator[](const Key &k) const { return !_m[k]; }
  1567     Value operator[](const Key &k) const { return !_m[k]; }
  1543     /// \e
  1568     ///\e
  1544     void set(const Key &k, bool v) { _m.set(k, !v); }
  1569     void set(const Key &k, bool v) { _m.set(k, !v); }
  1545   };
  1570   };
  1546 
  1571 
  1547   /// Returns a \c NotMap class
  1572   /// Returns a \c NotMap class
  1548 
  1573 
  1593   template<typename M1, typename M2>
  1618   template<typename M1, typename M2>
  1594   class EqualMap : public MapBase<typename M1::Key, bool> {
  1619   class EqualMap : public MapBase<typename M1::Key, bool> {
  1595     const M1 &_m1;
  1620     const M1 &_m1;
  1596     const M2 &_m2;
  1621     const M2 &_m2;
  1597   public:
  1622   public:
  1598     typedef MapBase<typename M1::Key, bool> Parent;
  1623     ///\e
  1599     typedef typename Parent::Key Key;
  1624     typedef typename M1::Key Key;
  1600     typedef typename Parent::Value Value;
  1625     ///\e
       
  1626     typedef bool Value;
  1601 
  1627 
  1602     /// Constructor
  1628     /// Constructor
  1603     EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1629     EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1604     /// \e
  1630     ///\e
  1605     Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
  1631     Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
  1606   };
  1632   };
  1607 
  1633 
  1608   /// Returns an \c EqualMap class
  1634   /// Returns an \c EqualMap class
  1609 
  1635 
  1641   template<typename M1, typename M2>
  1667   template<typename M1, typename M2>
  1642   class LessMap : public MapBase<typename M1::Key, bool> {
  1668   class LessMap : public MapBase<typename M1::Key, bool> {
  1643     const M1 &_m1;
  1669     const M1 &_m1;
  1644     const M2 &_m2;
  1670     const M2 &_m2;
  1645   public:
  1671   public:
  1646     typedef MapBase<typename M1::Key, bool> Parent;
  1672     ///\e
  1647     typedef typename Parent::Key Key;
  1673     typedef typename M1::Key Key;
  1648     typedef typename Parent::Value Value;
  1674     ///\e
       
  1675     typedef bool Value;
  1649 
  1676 
  1650     /// Constructor
  1677     /// Constructor
  1651     LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1678     LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1652     /// \e
  1679     ///\e
  1653     Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
  1680     Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
  1654   };
  1681   };
  1655 
  1682 
  1656   /// Returns an \c LessMap class
  1683   /// Returns an \c LessMap class
  1657 
  1684 
  1703   /// easily done with LoggerBoolMap.
  1730   /// easily done with LoggerBoolMap.
  1704   ///
  1731   ///
  1705   /// The simplest way of using this map is through the loggerBoolMap()
  1732   /// The simplest way of using this map is through the loggerBoolMap()
  1706   /// function.
  1733   /// function.
  1707   ///
  1734   ///
  1708   /// \tparam It The type of the iterator.
  1735   /// \tparam IT The type of the iterator.
  1709   /// \tparam Ke The key type of the map. The default value set
  1736   /// \tparam KEY The key type of the map. The default value set
  1710   /// according to the iterator type should work in most cases.
  1737   /// according to the iterator type should work in most cases.
  1711   ///
  1738   ///
  1712   /// \note The container of the iterator must contain enough space
  1739   /// \note The container of the iterator must contain enough space
  1713   /// for the elements or the iterator should be an inserter iterator.
  1740   /// for the elements or the iterator should be an inserter iterator.
  1714 #ifdef DOXYGEN
  1741 #ifdef DOXYGEN
  1715   template <typename It, typename Ke>
  1742   template <typename IT, typename KEY>
  1716 #else
  1743 #else
  1717   template <typename It,
  1744   template <typename IT,
  1718             typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
  1745             typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
  1719 #endif
  1746 #endif
  1720   class LoggerBoolMap {
  1747   class LoggerBoolMap : public MapBase<KEY, bool> {
  1721   public:
  1748   public:
  1722     typedef It Iterator;
  1749 
  1723 
  1750     ///\e
  1724     typedef Ke Key;
  1751     typedef KEY Key;
       
  1752     ///\e
  1725     typedef bool Value;
  1753     typedef bool Value;
       
  1754     ///\e
       
  1755     typedef IT Iterator;
  1726 
  1756 
  1727     /// Constructor
  1757     /// Constructor
  1728     LoggerBoolMap(Iterator it)
  1758     LoggerBoolMap(Iterator it)
  1729       : _begin(it), _end(it) {}
  1759       : _begin(it), _end(it) {}
  1730 
  1760 
  1783   /// @}
  1813   /// @}
  1784 
  1814 
  1785   /// \addtogroup graph_maps
  1815   /// \addtogroup graph_maps
  1786   /// @{
  1816   /// @{
  1787 
  1817 
  1788   /// Provides an immutable and unique id for each item in the graph.
  1818   /// \brief Provides an immutable and unique id for each item in a graph.
  1789 
  1819   ///
  1790   /// The IdMap class provides a unique and immutable id for each item of the
  1820   /// IdMap provides a unique and immutable id for each item of the
  1791   /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
  1821   /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
  1792   /// different items (nodes) get different ids <li>\b immutable: the id of an
  1822   ///  - \b unique: different items get different ids,
  1793   /// item (node) does not change (even if you delete other nodes).  </ul>
  1823   ///  - \b immutable: the id of an item does not change (even if you
  1794   /// Through this map you get access (i.e. can read) the inner id values of
  1824   ///    delete other nodes).
  1795   /// the items stored in the graph. This map can be inverted with its member
  1825   ///
       
  1826   /// Using this map you get access (i.e. can read) the inner id values of
       
  1827   /// the items stored in the graph, which is returned by the \c id()
       
  1828   /// function of the graph. This map can be inverted with its member
  1796   /// class \c InverseMap or with the \c operator() member.
  1829   /// class \c InverseMap or with the \c operator() member.
  1797   ///
  1830   ///
  1798   template <typename _Graph, typename _Item>
  1831   /// \tparam GR The graph type.
  1799   class IdMap {
  1832   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  1800   public:
  1833   /// \c GR::Edge).
  1801     typedef _Graph Graph;
  1834   ///
       
  1835   /// \see DescriptorMap
       
  1836   template <typename GR, typename K>
       
  1837   class IdMap : public MapBase<K, int> {
       
  1838   public:
       
  1839     /// The graph type of IdMap.
       
  1840     typedef GR Graph;
       
  1841     /// The key type of IdMap (\c Node, \c Arc or \c Edge).
       
  1842     typedef K Item;
       
  1843     /// The key type of IdMap (\c Node, \c Arc or \c Edge).
       
  1844     typedef K Key;
       
  1845     /// The value type of IdMap.
  1802     typedef int Value;
  1846     typedef int Value;
  1803     typedef _Item Item;
       
  1804     typedef _Item Key;
       
  1805 
  1847 
  1806     /// \brief Constructor.
  1848     /// \brief Constructor.
  1807     ///
  1849     ///
  1808     /// Constructor of the map.
  1850     /// Constructor of the map.
  1809     explicit IdMap(const Graph& graph) : _graph(&graph) {}
  1851     explicit IdMap(const Graph& graph) : _graph(&graph) {}
  1811     /// \brief Gives back the \e id of the item.
  1853     /// \brief Gives back the \e id of the item.
  1812     ///
  1854     ///
  1813     /// Gives back the immutable and unique \e id of the item.
  1855     /// Gives back the immutable and unique \e id of the item.
  1814     int operator[](const Item& item) const { return _graph->id(item);}
  1856     int operator[](const Item& item) const { return _graph->id(item);}
  1815 
  1857 
  1816     /// \brief Gives back the item by its id.
  1858     /// \brief Gives back the \e item by its id.
  1817     ///
  1859     ///
  1818     /// Gives back the item by its id.
  1860     /// Gives back the \e item by its id.
  1819     Item operator()(int id) { return _graph->fromId(id, Item()); }
  1861     Item operator()(int id) { return _graph->fromId(id, Item()); }
  1820 
  1862 
  1821   private:
  1863   private:
  1822     const Graph* _graph;
  1864     const Graph* _graph;
  1823 
  1865 
  1824   public:
  1866   public:
  1825 
  1867 
  1826     /// \brief The class represents the inverse of its owner (IdMap).
  1868     /// \brief This class represents the inverse of its owner (IdMap).
  1827     ///
  1869     ///
  1828     /// The class represents the inverse of its owner (IdMap).
  1870     /// This class represents the inverse of its owner (IdMap).
  1829     /// \see inverse()
  1871     /// \see inverse()
  1830     class InverseMap {
  1872     class InverseMap {
  1831     public:
  1873     public:
  1832 
  1874 
  1833       /// \brief Constructor.
  1875       /// \brief Constructor.
  1841       explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
  1883       explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
  1842 
  1884 
  1843       /// \brief Gives back the given item from its id.
  1885       /// \brief Gives back the given item from its id.
  1844       ///
  1886       ///
  1845       /// Gives back the given item from its id.
  1887       /// Gives back the given item from its id.
  1846       ///
       
  1847       Item operator[](int id) const { return _graph->fromId(id, Item());}
  1888       Item operator[](int id) const { return _graph->fromId(id, Item());}
  1848 
  1889 
  1849     private:
  1890     private:
  1850       const Graph* _graph;
  1891       const Graph* _graph;
  1851     };
  1892     };
  1852 
  1893 
  1853     /// \brief Gives back the inverse of the map.
  1894     /// \brief Gives back the inverse of the map.
  1854     ///
  1895     ///
  1855     /// Gives back the inverse of the IdMap.
  1896     /// Gives back the inverse of the IdMap.
  1856     InverseMap inverse() const { return InverseMap(*_graph);}
  1897     InverseMap inverse() const { return InverseMap(*_graph);}
  1857 
  1898   };
  1858   };
  1899 
  1859 
  1900 
  1860 
  1901   /// \brief General invertable graph map type.
  1861   /// \brief General invertable graph-map type.
  1902 
  1862 
  1903   /// This class provides simple invertable graph maps.
  1863   /// This type provides simple invertable graph-maps.
  1904   /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
  1864   /// The InvertableMap wraps an arbitrary ReadWriteMap
       
  1865   /// and if a key is set to a new value then store it
  1905   /// and if a key is set to a new value then store it
  1866   /// in the inverse map.
  1906   /// in the inverse map.
  1867   ///
  1907   ///
  1868   /// The values of the map can be accessed
  1908   /// The values of the map can be accessed
  1869   /// with stl compatible forward iterator.
  1909   /// with stl compatible forward iterator.
  1870   ///
  1910   ///
  1871   /// \tparam _Graph The graph type.
  1911   /// \tparam GR The graph type.
  1872   /// \tparam _Item The item type of the graph.
  1912   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  1873   /// \tparam _Value The value type of the map.
  1913   /// \c GR::Edge).
       
  1914   /// \tparam V The value type of the map.
  1874   ///
  1915   ///
  1875   /// \see IterableValueMap
  1916   /// \see IterableValueMap
  1876   template <typename _Graph, typename _Item, typename _Value>
  1917   template <typename GR, typename K, typename V>
  1877   class InvertableMap
  1918   class InvertableMap
  1878     : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
  1919     : protected ItemSetTraits<GR, K>::template Map<V>::Type {
  1879   private:
  1920   private:
  1880 
  1921 
  1881     typedef typename ItemSetTraits<_Graph, _Item>::
  1922     typedef typename ItemSetTraits<GR, K>::
  1882     template Map<_Value>::Type Map;
  1923       template Map<V>::Type Map;
  1883     typedef _Graph Graph;
  1924 
  1884 
  1925     typedef std::map<V, K> Container;
  1885     typedef std::map<_Value, _Item> Container;
       
  1886     Container _inv_map;
  1926     Container _inv_map;
  1887 
  1927 
  1888   public:
  1928   public:
  1889 
  1929 
  1890     /// The key type of InvertableMap (Node, Arc, Edge).
  1930     /// The graph type of InvertableMap.
  1891     typedef typename Map::Key Key;
  1931     typedef GR Graph;
  1892     /// The value type of the InvertableMap.
  1932     /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
  1893     typedef typename Map::Value Value;
  1933     typedef K Item;
       
  1934     /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
       
  1935     typedef K Key;
       
  1936     /// The value type of InvertableMap.
       
  1937     typedef V Value;
  1894 
  1938 
  1895     /// \brief Constructor.
  1939     /// \brief Constructor.
  1896     ///
  1940     ///
  1897     /// Construct a new InvertableMap for the graph.
  1941     /// Construct a new InvertableMap for the given graph.
  1898     ///
       
  1899     explicit InvertableMap(const Graph& graph) : Map(graph) {}
  1942     explicit InvertableMap(const Graph& graph) : Map(graph) {}
  1900 
  1943 
  1901     /// \brief Forward iterator for values.
  1944     /// \brief Forward iterator for values.
  1902     ///
  1945     ///
  1903     /// This iterator is an stl compatible forward
  1946     /// This iterator is an stl compatible forward
  1904     /// iterator on the values of the map. The values can
  1947     /// iterator on the values of the map. The values can
  1905     /// be accessed in the [beginValue, endValue) range.
  1948     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
  1906     ///
       
  1907     class ValueIterator
  1949     class ValueIterator
  1908       : public std::iterator<std::forward_iterator_tag, Value> {
  1950       : public std::iterator<std::forward_iterator_tag, Value> {
  1909       friend class InvertableMap;
  1951       friend class InvertableMap;
  1910     private:
  1952     private:
  1911       ValueIterator(typename Container::const_iterator _it)
  1953       ValueIterator(typename Container::const_iterator _it)
  1933 
  1975 
  1934     /// \brief Returns an iterator to the first value.
  1976     /// \brief Returns an iterator to the first value.
  1935     ///
  1977     ///
  1936     /// Returns an stl compatible iterator to the
  1978     /// Returns an stl compatible iterator to the
  1937     /// first value of the map. The values of the
  1979     /// first value of the map. The values of the
  1938     /// map can be accessed in the [beginValue, endValue)
  1980     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
  1939     /// range.
  1981     /// range.
  1940     ValueIterator beginValue() const {
  1982     ValueIterator beginValue() const {
  1941       return ValueIterator(_inv_map.begin());
  1983       return ValueIterator(_inv_map.begin());
  1942     }
  1984     }
  1943 
  1985 
  1944     /// \brief Returns an iterator after the last value.
  1986     /// \brief Returns an iterator after the last value.
  1945     ///
  1987     ///
  1946     /// Returns an stl compatible iterator after the
  1988     /// Returns an stl compatible iterator after the
  1947     /// last value of the map. The values of the
  1989     /// last value of the map. The values of the
  1948     /// map can be accessed in the [beginValue, endValue)
  1990     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
  1949     /// range.
  1991     /// range.
  1950     ValueIterator endValue() const {
  1992     ValueIterator endValue() const {
  1951       return ValueIterator(_inv_map.end());
  1993       return ValueIterator(_inv_map.end());
  1952     }
  1994     }
  1953 
  1995 
  1954     /// \brief The setter function of the map.
  1996     /// \brief Sets the value associated with the given key.
  1955     ///
  1997     ///
  1956     /// Sets the mapped value.
  1998     /// Sets the value associated with the given key.
  1957     void set(const Key& key, const Value& val) {
  1999     void set(const Key& key, const Value& val) {
  1958       Value oldval = Map::operator[](key);
  2000       Value oldval = Map::operator[](key);
  1959       typename Container::iterator it = _inv_map.find(oldval);
  2001       typename Container::iterator it = _inv_map.find(oldval);
  1960       if (it != _inv_map.end() && it->second == key) {
  2002       if (it != _inv_map.end() && it->second == key) {
  1961         _inv_map.erase(it);
  2003         _inv_map.erase(it);
  1962       }
  2004       }
  1963       _inv_map.insert(make_pair(val, key));
  2005       _inv_map.insert(make_pair(val, key));
  1964       Map::set(key, val);
  2006       Map::set(key, val);
  1965     }
  2007     }
  1966 
  2008 
  1967     /// \brief The getter function of the map.
  2009     /// \brief Returns the value associated with the given key.
  1968     ///
  2010     ///
  1969     /// It gives back the value associated with the key.
  2011     /// Returns the value associated with the given key.
  1970     typename MapTraits<Map>::ConstReturnValue
  2012     typename MapTraits<Map>::ConstReturnValue
  1971     operator[](const Key& key) const {
  2013     operator[](const Key& key) const {
  1972       return Map::operator[](key);
  2014       return Map::operator[](key);
  1973     }
  2015     }
  1974 
  2016 
  1980       return it != _inv_map.end() ? it->second : INVALID;
  2022       return it != _inv_map.end() ? it->second : INVALID;
  1981     }
  2023     }
  1982 
  2024 
  1983   protected:
  2025   protected:
  1984 
  2026 
  1985     /// \brief Erase the key from the map.
  2027     /// \brief Erase the key from the map and the inverse map.
  1986     ///
  2028     ///
  1987     /// Erase the key to the map. It is called by the
  2029     /// Erase the key from the map and the inverse map. It is called by the
  1988     /// \c AlterationNotifier.
  2030     /// \c AlterationNotifier.
  1989     virtual void erase(const Key& key) {
  2031     virtual void erase(const Key& key) {
  1990       Value val = Map::operator[](key);
  2032       Value val = Map::operator[](key);
  1991       typename Container::iterator it = _inv_map.find(val);
  2033       typename Container::iterator it = _inv_map.find(val);
  1992       if (it != _inv_map.end() && it->second == key) {
  2034       if (it != _inv_map.end() && it->second == key) {
  1993         _inv_map.erase(it);
  2035         _inv_map.erase(it);
  1994       }
  2036       }
  1995       Map::erase(key);
  2037       Map::erase(key);
  1996     }
  2038     }
  1997 
  2039 
  1998     /// \brief Erase more keys from the map.
  2040     /// \brief Erase more keys from the map and the inverse map.
  1999     ///
  2041     ///
  2000     /// Erase more keys from the map. It is called by the
  2042     /// Erase more keys from the map and the inverse map. It is called by the
  2001     /// \c AlterationNotifier.
  2043     /// \c AlterationNotifier.
  2002     virtual void erase(const std::vector<Key>& keys) {
  2044     virtual void erase(const std::vector<Key>& keys) {
  2003       for (int i = 0; i < int(keys.size()); ++i) {
  2045       for (int i = 0; i < int(keys.size()); ++i) {
  2004         Value val = Map::operator[](keys[i]);
  2046         Value val = Map::operator[](keys[i]);
  2005         typename Container::iterator it = _inv_map.find(val);
  2047         typename Container::iterator it = _inv_map.find(val);
  2008         }
  2050         }
  2009       }
  2051       }
  2010       Map::erase(keys);
  2052       Map::erase(keys);
  2011     }
  2053     }
  2012 
  2054 
  2013     /// \brief Clear the keys from the map and inverse map.
  2055     /// \brief Clear the keys from the map and the inverse map.
  2014     ///
  2056     ///
  2015     /// Clear the keys from the map and inverse map. It is called by the
  2057     /// Clear the keys from the map and the inverse map. It is called by the
  2016     /// \c AlterationNotifier.
  2058     /// \c AlterationNotifier.
  2017     virtual void clear() {
  2059     virtual void clear() {
  2018       _inv_map.clear();
  2060       _inv_map.clear();
  2019       Map::clear();
  2061       Map::clear();
  2020     }
  2062     }
  2022   public:
  2064   public:
  2023 
  2065 
  2024     /// \brief The inverse map type.
  2066     /// \brief The inverse map type.
  2025     ///
  2067     ///
  2026     /// The inverse of this map. The subscript operator of the map
  2068     /// The inverse of this map. The subscript operator of the map
  2027     /// gives back always the item what was last assigned to the value.
  2069     /// gives back the item that was last assigned to the value.
  2028     class InverseMap {
  2070     class InverseMap {
  2029     public:
  2071     public:
  2030       /// \brief Constructor of the InverseMap.
  2072       /// \brief Constructor
  2031       ///
  2073       ///
  2032       /// Constructor of the InverseMap.
  2074       /// Constructor of the InverseMap.
  2033       explicit InverseMap(const InvertableMap& inverted)
  2075       explicit InverseMap(const InvertableMap& inverted)
  2034         : _inverted(inverted) {}
  2076         : _inverted(inverted) {}
  2035 
  2077 
  2038       /// The key type of the InverseMap.
  2080       /// The key type of the InverseMap.
  2039       typedef typename InvertableMap::Value Key;
  2081       typedef typename InvertableMap::Value Key;
  2040 
  2082 
  2041       /// \brief Subscript operator.
  2083       /// \brief Subscript operator.
  2042       ///
  2084       ///
  2043       /// Subscript operator. It gives back always the item
  2085       /// Subscript operator. It gives back the item
  2044       /// what was last assigned to the value.
  2086       /// that was last assigned to the given value.
  2045       Value operator[](const Key& key) const {
  2087       Value operator[](const Key& key) const {
  2046         return _inverted(key);
  2088         return _inverted(key);
  2047       }
  2089       }
  2048 
  2090 
  2049     private:
  2091     private:
  2050       const InvertableMap& _inverted;
  2092       const InvertableMap& _inverted;
  2051     };
  2093     };
  2052 
  2094 
  2053     /// \brief It gives back the just readable inverse map.
  2095     /// \brief It gives back the read-only inverse map.
  2054     ///
  2096     ///
  2055     /// It gives back the just readable inverse map.
  2097     /// It gives back the read-only inverse map.
  2056     InverseMap inverse() const {
  2098     InverseMap inverse() const {
  2057       return InverseMap(*this);
  2099       return InverseMap(*this);
  2058     }
  2100     }
  2059 
  2101 
  2060   };
  2102   };
  2061 
  2103 
  2062   /// \brief Provides a mutable, continuous and unique descriptor for each
  2104   /// \brief Provides a mutable, continuous and unique descriptor for each
  2063   /// item in the graph.
  2105   /// item in a graph.
  2064   ///
  2106   ///
  2065   /// The DescriptorMap class provides a unique and continuous (but mutable)
  2107   /// DescriptorMap provides a unique and continuous (but mutable)
  2066   /// descriptor (id) for each item of the same type (e.g. node) in the
  2108   /// descriptor (id) for each item of the same type (\c Node, \c Arc or
  2067   /// graph. This id is <ul><li>\b unique: different items (nodes) get
  2109   /// \c Edge) in a graph. This id is
  2068   /// different ids <li>\b continuous: the range of the ids is the set of
  2110   ///  - \b unique: different items get different ids,
  2069   /// integers between 0 and \c n-1, where \c n is the number of the items of
  2111   ///  - \b continuous: the range of the ids is the set of integers
  2070   /// this type (e.g. nodes) (so the id of a node can change if you delete an
  2112   ///    between 0 and \c n-1, where \c n is the number of the items of
  2071   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
  2113   ///    this type (\c Node, \c Arc or \c Edge). So the id of an item can
  2072   /// with its member class \c InverseMap, or with the \c operator() member.
  2114   ///    change if you delete an other item of the same type, i.e. this
  2073   ///
  2115   ///    id is mutable.
  2074   /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
  2116   ///
  2075   /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
  2117   /// Thus this id is not (necessarily) the same as what can get using
  2076   /// Edge.
  2118   /// the \c id() function of the graph or \ref IdMap.
  2077   template <typename _Graph, typename _Item>
  2119   /// This map can be inverted with its member class \c InverseMap,
       
  2120   /// or with the \c operator() member.
       
  2121   ///
       
  2122   /// \tparam GR The graph type.
       
  2123   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
       
  2124   /// \c GR::Edge).
       
  2125   ///
       
  2126   /// \see IdMap
       
  2127   template <typename GR, typename K>
  2078   class DescriptorMap
  2128   class DescriptorMap
  2079     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
  2129     : protected ItemSetTraits<GR, K>::template Map<int>::Type {
  2080 
  2130 
  2081     typedef _Item Item;
  2131     typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
  2082     typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
  2132 
  2083 
  2133   public:
  2084   public:
  2134     /// The graph type of DescriptorMap.
  2085     /// The graph class of DescriptorMap.
  2135     typedef GR Graph;
  2086     typedef _Graph Graph;
  2136     /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
  2087 
  2137     typedef K Item;
  2088     /// The key type of DescriptorMap (Node, Arc, Edge).
  2138     /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
  2089     typedef typename Map::Key Key;
  2139     typedef K Key;
  2090     /// The value type of DescriptorMap.
  2140     /// The value type of DescriptorMap.
  2091     typedef typename Map::Value Value;
  2141     typedef int Value;
  2092 
  2142 
  2093     /// \brief Constructor.
  2143     /// \brief Constructor.
  2094     ///
  2144     ///
  2095     /// Constructor for descriptor map.
  2145     /// Constructor for descriptor map.
  2096     explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
  2146     explicit DescriptorMap(const Graph& gr) : Map(gr) {
  2097       Item it;
  2147       Item it;
  2098       const typename Map::Notifier* nf = Map::notifier();
  2148       const typename Map::Notifier* nf = Map::notifier();
  2099       for (nf->first(it); it != INVALID; nf->next(it)) {
  2149       for (nf->first(it); it != INVALID; nf->next(it)) {
  2100         Map::set(it, _inv_map.size());
  2150         Map::set(it, _inv_map.size());
  2101         _inv_map.push_back(it);
  2151         _inv_map.push_back(it);
  2102       }
  2152       }
  2103     }
  2153     }
  2104 
  2154 
  2105   protected:
  2155   protected:
  2106 
  2156 
  2107     /// \brief Add a new key to the map.
  2157     /// \brief Adds a new key to the map.
  2108     ///
  2158     ///
  2109     /// Add a new key to the map. It is called by the
  2159     /// Add a new key to the map. It is called by the
  2110     /// \c AlterationNotifier.
  2160     /// \c AlterationNotifier.
  2111     virtual void add(const Item& item) {
  2161     virtual void add(const Item& item) {
  2112       Map::add(item);
  2162       Map::add(item);
  2212 
  2262 
  2213     typedef std::vector<Item> Container;
  2263     typedef std::vector<Item> Container;
  2214     Container _inv_map;
  2264     Container _inv_map;
  2215 
  2265 
  2216   public:
  2266   public:
       
  2267 
  2217     /// \brief The inverse map type of DescriptorMap.
  2268     /// \brief The inverse map type of DescriptorMap.
  2218     ///
  2269     ///
  2219     /// The inverse map type of DescriptorMap.
  2270     /// The inverse map type of DescriptorMap.
  2220     class InverseMap {
  2271     class InverseMap {
  2221     public:
  2272     public:
  2222       /// \brief Constructor of the InverseMap.
  2273       /// \brief Constructor
  2223       ///
  2274       ///
  2224       /// Constructor of the InverseMap.
  2275       /// Constructor of the InverseMap.
  2225       explicit InverseMap(const DescriptorMap& inverted)
  2276       explicit InverseMap(const DescriptorMap& inverted)
  2226         : _inverted(inverted) {}
  2277         : _inverted(inverted) {}
  2227 
  2278 
  2232       typedef typename DescriptorMap::Value Key;
  2283       typedef typename DescriptorMap::Value Key;
  2233 
  2284 
  2234       /// \brief Subscript operator.
  2285       /// \brief Subscript operator.
  2235       ///
  2286       ///
  2236       /// Subscript operator. It gives back the item
  2287       /// Subscript operator. It gives back the item
  2237       /// that the descriptor belongs to currently.
  2288       /// that the descriptor currently belongs to.
  2238       Value operator[](const Key& key) const {
  2289       Value operator[](const Key& key) const {
  2239         return _inverted(key);
  2290         return _inverted(key);
  2240       }
  2291       }
  2241 
  2292 
  2242       /// \brief Size of the map.
  2293       /// \brief Size of the map.
  2256     const InverseMap inverse() const {
  2307     const InverseMap inverse() const {
  2257       return InverseMap(*this);
  2308       return InverseMap(*this);
  2258     }
  2309     }
  2259   };
  2310   };
  2260 
  2311 
  2261   /// \brief Returns the source of the given arc.
  2312   /// \brief Map of the source nodes of arcs in a digraph.
  2262   ///
  2313   ///
  2263   /// The SourceMap gives back the source Node of the given arc.
  2314   /// SourceMap provides access for the source node of each arc in a digraph,
       
  2315   /// which is returned by the \c source() function of the digraph.
       
  2316   /// \tparam GR The digraph type.
  2264   /// \see TargetMap
  2317   /// \see TargetMap
  2265   template <typename Digraph>
  2318   template <typename GR>
  2266   class SourceMap {
  2319   class SourceMap {
  2267   public:
  2320   public:
  2268 
  2321 
  2269     typedef typename Digraph::Node Value;
  2322     ///\e
  2270     typedef typename Digraph::Arc Key;
  2323     typedef typename GR::Arc Key;
       
  2324     ///\e
       
  2325     typedef typename GR::Node Value;
  2271 
  2326 
  2272     /// \brief Constructor
  2327     /// \brief Constructor
  2273     ///
  2328     ///
  2274     /// Constructor
  2329     /// Constructor.
  2275     /// \param digraph The digraph that the map belongs to.
  2330     /// \param digraph The digraph that the map belongs to.
  2276     explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
  2331     explicit SourceMap(const GR& digraph) : _graph(digraph) {}
  2277 
  2332 
  2278     /// \brief The subscript operator.
  2333     /// \brief Returns the source node of the given arc.
  2279     ///
  2334     ///
  2280     /// The subscript operator.
  2335     /// Returns the source node of the given arc.
  2281     /// \param arc The arc
       
  2282     /// \return The source of the arc
       
  2283     Value operator[](const Key& arc) const {
  2336     Value operator[](const Key& arc) const {
  2284       return _digraph.source(arc);
  2337       return _graph.source(arc);
  2285     }
  2338     }
  2286 
  2339 
  2287   private:
  2340   private:
  2288     const Digraph& _digraph;
  2341     const GR& _graph;
  2289   };
  2342   };
  2290 
  2343 
  2291   /// \brief Returns a \c SourceMap class.
  2344   /// \brief Returns a \c SourceMap class.
  2292   ///
  2345   ///
  2293   /// This function just returns an \c SourceMap class.
  2346   /// This function just returns an \c SourceMap class.
  2294   /// \relates SourceMap
  2347   /// \relates SourceMap
  2295   template <typename Digraph>
  2348   template <typename GR>
  2296   inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
  2349   inline SourceMap<GR> sourceMap(const GR& graph) {
  2297     return SourceMap<Digraph>(digraph);
  2350     return SourceMap<GR>(graph);
  2298   }
  2351   }
  2299 
  2352 
  2300   /// \brief Returns the target of the given arc.
  2353   /// \brief Map of the target nodes of arcs in a digraph.
  2301   ///
  2354   ///
  2302   /// The TargetMap gives back the target Node of the given arc.
  2355   /// TargetMap provides access for the target node of each arc in a digraph,
       
  2356   /// which is returned by the \c target() function of the digraph.
       
  2357   /// \tparam GR The digraph type.
  2303   /// \see SourceMap
  2358   /// \see SourceMap
  2304   template <typename Digraph>
  2359   template <typename GR>
  2305   class TargetMap {
  2360   class TargetMap {
  2306   public:
  2361   public:
  2307 
  2362 
  2308     typedef typename Digraph::Node Value;
  2363     ///\e
  2309     typedef typename Digraph::Arc Key;
  2364     typedef typename GR::Arc Key;
       
  2365     ///\e
       
  2366     typedef typename GR::Node Value;
  2310 
  2367 
  2311     /// \brief Constructor
  2368     /// \brief Constructor
  2312     ///
  2369     ///
  2313     /// Constructor
  2370     /// Constructor.
  2314     /// \param digraph The digraph that the map belongs to.
  2371     /// \param digraph The digraph that the map belongs to.
  2315     explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
  2372     explicit TargetMap(const GR& digraph) : _graph(digraph) {}
  2316 
  2373 
  2317     /// \brief The subscript operator.
  2374     /// \brief Returns the target node of the given arc.
  2318     ///
  2375     ///
  2319     /// The subscript operator.
  2376     /// Returns the target node of the given arc.
  2320     /// \param e The arc
       
  2321     /// \return The target of the arc
       
  2322     Value operator[](const Key& e) const {
  2377     Value operator[](const Key& e) const {
  2323       return _digraph.target(e);
  2378       return _graph.target(e);
  2324     }
  2379     }
  2325 
  2380 
  2326   private:
  2381   private:
  2327     const Digraph& _digraph;
  2382     const GR& _graph;
  2328   };
  2383   };
  2329 
  2384 
  2330   /// \brief Returns a \c TargetMap class.
  2385   /// \brief Returns a \c TargetMap class.
  2331   ///
  2386   ///
  2332   /// This function just returns a \c TargetMap class.
  2387   /// This function just returns a \c TargetMap class.
  2333   /// \relates TargetMap
  2388   /// \relates TargetMap
  2334   template <typename Digraph>
  2389   template <typename GR>
  2335   inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
  2390   inline TargetMap<GR> targetMap(const GR& graph) {
  2336     return TargetMap<Digraph>(digraph);
  2391     return TargetMap<GR>(graph);
  2337   }
  2392   }
  2338 
  2393 
  2339   /// \brief Returns the "forward" directed arc view of an edge.
  2394   /// \brief Map of the "forward" directed arc view of edges in a graph.
  2340   ///
  2395   ///
  2341   /// Returns the "forward" directed arc view of an edge.
  2396   /// ForwardMap provides access for the "forward" directed arc view of
       
  2397   /// each edge in a graph, which is returned by the \c direct() function
       
  2398   /// of the graph with \c true parameter.
       
  2399   /// \tparam GR The graph type.
  2342   /// \see BackwardMap
  2400   /// \see BackwardMap
  2343   template <typename Graph>
  2401   template <typename GR>
  2344   class ForwardMap {
  2402   class ForwardMap {
  2345   public:
  2403   public:
  2346 
  2404 
  2347     typedef typename Graph::Arc Value;
  2405     typedef typename GR::Arc Value;
  2348     typedef typename Graph::Edge Key;
  2406     typedef typename GR::Edge Key;
  2349 
  2407 
  2350     /// \brief Constructor
  2408     /// \brief Constructor
  2351     ///
  2409     ///
  2352     /// Constructor
  2410     /// Constructor.
  2353     /// \param graph The graph that the map belongs to.
  2411     /// \param graph The graph that the map belongs to.
  2354     explicit ForwardMap(const Graph& graph) : _graph(graph) {}
  2412     explicit ForwardMap(const GR& graph) : _graph(graph) {}
  2355 
  2413 
  2356     /// \brief The subscript operator.
  2414     /// \brief Returns the "forward" directed arc view of the given edge.
  2357     ///
  2415     ///
  2358     /// The subscript operator.
  2416     /// Returns the "forward" directed arc view of the given edge.
  2359     /// \param key An edge
       
  2360     /// \return The "forward" directed arc view of edge
       
  2361     Value operator[](const Key& key) const {
  2417     Value operator[](const Key& key) const {
  2362       return _graph.direct(key, true);
  2418       return _graph.direct(key, true);
  2363     }
  2419     }
  2364 
  2420 
  2365   private:
  2421   private:
  2366     const Graph& _graph;
  2422     const GR& _graph;
  2367   };
  2423   };
  2368 
  2424 
  2369   /// \brief Returns a \c ForwardMap class.
  2425   /// \brief Returns a \c ForwardMap class.
  2370   ///
  2426   ///
  2371   /// This function just returns an \c ForwardMap class.
  2427   /// This function just returns an \c ForwardMap class.
  2372   /// \relates ForwardMap
  2428   /// \relates ForwardMap
  2373   template <typename Graph>
  2429   template <typename GR>
  2374   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
  2430   inline ForwardMap<GR> forwardMap(const GR& graph) {
  2375     return ForwardMap<Graph>(graph);
  2431     return ForwardMap<GR>(graph);
  2376   }
  2432   }
  2377 
  2433 
  2378   /// \brief Returns the "backward" directed arc view of an edge.
  2434   /// \brief Map of the "backward" directed arc view of edges in a graph.
  2379   ///
  2435   ///
  2380   /// Returns the "backward" directed arc view of an edge.
  2436   /// BackwardMap provides access for the "backward" directed arc view of
       
  2437   /// each edge in a graph, which is returned by the \c direct() function
       
  2438   /// of the graph with \c false parameter.
       
  2439   /// \tparam GR The graph type.
  2381   /// \see ForwardMap
  2440   /// \see ForwardMap
  2382   template <typename Graph>
  2441   template <typename GR>
  2383   class BackwardMap {
  2442   class BackwardMap {
  2384   public:
  2443   public:
  2385 
  2444 
  2386     typedef typename Graph::Arc Value;
  2445     typedef typename GR::Arc Value;
  2387     typedef typename Graph::Edge Key;
  2446     typedef typename GR::Edge Key;
  2388 
  2447 
  2389     /// \brief Constructor
  2448     /// \brief Constructor
  2390     ///
  2449     ///
  2391     /// Constructor
  2450     /// Constructor.
  2392     /// \param graph The graph that the map belongs to.
  2451     /// \param graph The graph that the map belongs to.
  2393     explicit BackwardMap(const Graph& graph) : _graph(graph) {}
  2452     explicit BackwardMap(const GR& graph) : _graph(graph) {}
  2394 
  2453 
  2395     /// \brief The subscript operator.
  2454     /// \brief Returns the "backward" directed arc view of the given edge.
  2396     ///
  2455     ///
  2397     /// The subscript operator.
  2456     /// Returns the "backward" directed arc view of the given edge.
  2398     /// \param key An edge
       
  2399     /// \return The "backward" directed arc view of edge
       
  2400     Value operator[](const Key& key) const {
  2457     Value operator[](const Key& key) const {
  2401       return _graph.direct(key, false);
  2458       return _graph.direct(key, false);
  2402     }
  2459     }
  2403 
  2460 
  2404   private:
  2461   private:
  2405     const Graph& _graph;
  2462     const GR& _graph;
  2406   };
  2463   };
  2407 
  2464 
  2408   /// \brief Returns a \c BackwardMap class
  2465   /// \brief Returns a \c BackwardMap class
  2409 
  2466 
  2410   /// This function just returns a \c BackwardMap class.
  2467   /// This function just returns a \c BackwardMap class.
  2411   /// \relates BackwardMap
  2468   /// \relates BackwardMap
  2412   template <typename Graph>
  2469   template <typename GR>
  2413   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
  2470   inline BackwardMap<GR> backwardMap(const GR& graph) {
  2414     return BackwardMap<Graph>(graph);
  2471     return BackwardMap<GR>(graph);
  2415   }
  2472   }
  2416 
  2473 
  2417   /// \brief Potential difference map
  2474   /// \brief Map of the in-degrees of nodes in a digraph.
  2418   ///
       
  2419   /// If there is an potential map on the nodes then we
       
  2420   /// can get an arc map as we get the substraction of the
       
  2421   /// values of the target and source.
       
  2422   template <typename Digraph, typename NodeMap>
       
  2423   class PotentialDifferenceMap {
       
  2424   public:
       
  2425     typedef typename Digraph::Arc Key;
       
  2426     typedef typename NodeMap::Value Value;
       
  2427 
       
  2428     /// \brief Constructor
       
  2429     ///
       
  2430     /// Contructor of the map
       
  2431     explicit PotentialDifferenceMap(const Digraph& digraph,
       
  2432                                     const NodeMap& potential)
       
  2433       : _digraph(digraph), _potential(potential) {}
       
  2434 
       
  2435     /// \brief Const subscription operator
       
  2436     ///
       
  2437     /// Const subscription operator
       
  2438     Value operator[](const Key& arc) const {
       
  2439       return _potential[_digraph.target(arc)] -
       
  2440         _potential[_digraph.source(arc)];
       
  2441     }
       
  2442 
       
  2443   private:
       
  2444     const Digraph& _digraph;
       
  2445     const NodeMap& _potential;
       
  2446   };
       
  2447 
       
  2448   /// \brief Returns a PotentialDifferenceMap.
       
  2449   ///
       
  2450   /// This function just returns a PotentialDifferenceMap.
       
  2451   /// \relates PotentialDifferenceMap
       
  2452   template <typename Digraph, typename NodeMap>
       
  2453   PotentialDifferenceMap<Digraph, NodeMap>
       
  2454   potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
       
  2455     return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
       
  2456   }
       
  2457 
       
  2458   /// \brief Map of the node in-degrees.
       
  2459   ///
  2475   ///
  2460   /// This map returns the in-degree of a node. Once it is constructed,
  2476   /// This map returns the in-degree of a node. Once it is constructed,
  2461   /// the degrees are stored in a standard NodeMap, so each query is done
  2477   /// the degrees are stored in a standard \c NodeMap, so each query is done
  2462   /// in constant time. On the other hand, the values are updated automatically
  2478   /// in constant time. On the other hand, the values are updated automatically
  2463   /// whenever the digraph changes.
  2479   /// whenever the digraph changes.
  2464   ///
  2480   ///
  2465   /// \warning Besides addNode() and addArc(), a digraph structure may provide
  2481   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
  2466   /// alternative ways to modify the digraph. The correct behavior of InDegMap
  2482   /// may provide alternative ways to modify the digraph.
  2467   /// is not guarantied if these additional features are used. For example
  2483   /// The correct behavior of InDegMap is not guarantied if these additional
  2468   /// the functions \ref ListDigraph::changeSource() "changeSource()",
  2484   /// features are used. For example the functions
       
  2485   /// \ref ListDigraph::changeSource() "changeSource()",
  2469   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  2486   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  2470   /// \ref ListDigraph::reverseArc() "reverseArc()"
  2487   /// \ref ListDigraph::reverseArc() "reverseArc()"
  2471   /// of \ref ListDigraph will \e not update the degree values correctly.
  2488   /// of \ref ListDigraph will \e not update the degree values correctly.
  2472   ///
  2489   ///
  2473   /// \sa OutDegMap
  2490   /// \sa OutDegMap
  2474 
  2491   template <typename GR>
  2475   template <typename _Digraph>
       
  2476   class InDegMap
  2492   class InDegMap
  2477     : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
  2493     : protected ItemSetTraits<GR, typename GR::Arc>
  2478       ::ItemNotifier::ObserverBase {
  2494       ::ItemNotifier::ObserverBase {
  2479 
  2495 
  2480   public:
  2496   public:
  2481 
  2497     
  2482     typedef _Digraph Digraph;
  2498     /// The digraph type
       
  2499     typedef GR Digraph;
       
  2500     /// The key type
       
  2501     typedef typename Digraph::Node Key;
       
  2502     /// The value type
  2483     typedef int Value;
  2503     typedef int Value;
  2484     typedef typename Digraph::Node Key;
       
  2485 
  2504 
  2486     typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
  2505     typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
  2487     ::ItemNotifier::ObserverBase Parent;
  2506     ::ItemNotifier::ObserverBase Parent;
  2488 
  2507 
  2489   private:
  2508   private:
  2521 
  2540 
  2522   public:
  2541   public:
  2523 
  2542 
  2524     /// \brief Constructor.
  2543     /// \brief Constructor.
  2525     ///
  2544     ///
  2526     /// Constructor for creating in-degree map.
  2545     /// Constructor for creating an in-degree map.
  2527     explicit InDegMap(const Digraph& digraph)
  2546     explicit InDegMap(const Digraph& graph)
  2528       : _digraph(digraph), _deg(digraph) {
  2547       : _digraph(graph), _deg(graph) {
  2529       Parent::attach(_digraph.notifier(typename Digraph::Arc()));
  2548       Parent::attach(_digraph.notifier(typename Digraph::Arc()));
  2530 
  2549 
  2531       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2550       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2532         _deg[it] = countInArcs(_digraph, it);
  2551         _deg[it] = countInArcs(_digraph, it);
  2533       }
  2552       }
  2534     }
  2553     }
  2535 
  2554 
       
  2555     /// \brief Gives back the in-degree of a Node.
       
  2556     ///
  2536     /// Gives back the in-degree of a Node.
  2557     /// Gives back the in-degree of a Node.
  2537     int operator[](const Key& key) const {
  2558     int operator[](const Key& key) const {
  2538       return _deg[key];
  2559       return _deg[key];
  2539     }
  2560     }
  2540 
  2561 
  2577 
  2598 
  2578     const Digraph& _digraph;
  2599     const Digraph& _digraph;
  2579     AutoNodeMap _deg;
  2600     AutoNodeMap _deg;
  2580   };
  2601   };
  2581 
  2602 
  2582   /// \brief Map of the node out-degrees.
  2603   /// \brief Map of the out-degrees of nodes in a digraph.
  2583   ///
  2604   ///
  2584   /// This map returns the out-degree of a node. Once it is constructed,
  2605   /// This map returns the out-degree of a node. Once it is constructed,
  2585   /// the degrees are stored in a standard NodeMap, so each query is done
  2606   /// the degrees are stored in a standard \c NodeMap, so each query is done
  2586   /// in constant time. On the other hand, the values are updated automatically
  2607   /// in constant time. On the other hand, the values are updated automatically
  2587   /// whenever the digraph changes.
  2608   /// whenever the digraph changes.
  2588   ///
  2609   ///
  2589   /// \warning Besides addNode() and addArc(), a digraph structure may provide
  2610   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
  2590   /// alternative ways to modify the digraph. The correct behavior of OutDegMap
  2611   /// may provide alternative ways to modify the digraph.
  2591   /// is not guarantied if these additional features are used. For example
  2612   /// The correct behavior of OutDegMap is not guarantied if these additional
  2592   /// the functions \ref ListDigraph::changeSource() "changeSource()",
  2613   /// features are used. For example the functions
       
  2614   /// \ref ListDigraph::changeSource() "changeSource()",
  2593   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  2615   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  2594   /// \ref ListDigraph::reverseArc() "reverseArc()"
  2616   /// \ref ListDigraph::reverseArc() "reverseArc()"
  2595   /// of \ref ListDigraph will \e not update the degree values correctly.
  2617   /// of \ref ListDigraph will \e not update the degree values correctly.
  2596   ///
  2618   ///
  2597   /// \sa InDegMap
  2619   /// \sa InDegMap
  2598 
  2620   template <typename GR>
  2599   template <typename _Digraph>
       
  2600   class OutDegMap
  2621   class OutDegMap
  2601     : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
  2622     : protected ItemSetTraits<GR, typename GR::Arc>
  2602       ::ItemNotifier::ObserverBase {
  2623       ::ItemNotifier::ObserverBase {
  2603 
  2624 
  2604   public:
  2625   public:
  2605 
  2626 
  2606     typedef _Digraph Digraph;
  2627     /// The digraph type
       
  2628     typedef GR Digraph;
       
  2629     /// The key type
       
  2630     typedef typename Digraph::Node Key;
       
  2631     /// The value type
  2607     typedef int Value;
  2632     typedef int Value;
  2608     typedef typename Digraph::Node Key;
       
  2609 
  2633 
  2610     typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
  2634     typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
  2611     ::ItemNotifier::ObserverBase Parent;
  2635     ::ItemNotifier::ObserverBase Parent;
  2612 
  2636 
  2613   private:
  2637   private:
  2643 
  2667 
  2644   public:
  2668   public:
  2645 
  2669 
  2646     /// \brief Constructor.
  2670     /// \brief Constructor.
  2647     ///
  2671     ///
  2648     /// Constructor for creating out-degree map.
  2672     /// Constructor for creating an out-degree map.
  2649     explicit OutDegMap(const Digraph& digraph)
  2673     explicit OutDegMap(const Digraph& graph)
  2650       : _digraph(digraph), _deg(digraph) {
  2674       : _digraph(graph), _deg(graph) {
  2651       Parent::attach(_digraph.notifier(typename Digraph::Arc()));
  2675       Parent::attach(_digraph.notifier(typename Digraph::Arc()));
  2652 
  2676 
  2653       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2677       for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
  2654         _deg[it] = countOutArcs(_digraph, it);
  2678         _deg[it] = countOutArcs(_digraph, it);
  2655       }
  2679       }
  2656     }
  2680     }
  2657 
  2681 
       
  2682     /// \brief Gives back the out-degree of a Node.
       
  2683     ///
  2658     /// Gives back the out-degree of a Node.
  2684     /// Gives back the out-degree of a Node.
  2659     int operator[](const Key& key) const {
  2685     int operator[](const Key& key) const {
  2660       return _deg[key];
  2686       return _deg[key];
  2661     }
  2687     }
  2662 
  2688 
  2699 
  2725 
  2700     const Digraph& _digraph;
  2726     const Digraph& _digraph;
  2701     AutoNodeMap _deg;
  2727     AutoNodeMap _deg;
  2702   };
  2728   };
  2703 
  2729 
       
  2730   /// \brief Potential difference map
       
  2731   ///
       
  2732   /// PotentialMap returns the difference between the potentials of the
       
  2733   /// source and target nodes of each arc in a digraph, i.e. it returns
       
  2734   /// \code
       
  2735   ///   potential[gr.target(arc)] - potential[gr.source(arc)].
       
  2736   /// \endcode
       
  2737   /// \tparam GR The digraph type.
       
  2738   /// \tparam POT A node map storing the potentials.
       
  2739   template <typename GR, typename POT>
       
  2740   class PotentialDifferenceMap {
       
  2741   public:
       
  2742     /// Key type
       
  2743     typedef typename GR::Arc Key;
       
  2744     /// Value type
       
  2745     typedef typename POT::Value Value;
       
  2746 
       
  2747     /// \brief Constructor
       
  2748     ///
       
  2749     /// Contructor of the map.
       
  2750     explicit PotentialDifferenceMap(const GR& gr,
       
  2751                                     const POT& potential)
       
  2752       : _digraph(gr), _potential(potential) {}
       
  2753 
       
  2754     /// \brief Returns the potential difference for the given arc.
       
  2755     ///
       
  2756     /// Returns the potential difference for the given arc, i.e.
       
  2757     /// \code
       
  2758     ///   potential[gr.target(arc)] - potential[gr.source(arc)].
       
  2759     /// \endcode
       
  2760     Value operator[](const Key& arc) const {
       
  2761       return _potential[_digraph.target(arc)] -
       
  2762         _potential[_digraph.source(arc)];
       
  2763     }
       
  2764 
       
  2765   private:
       
  2766     const GR& _digraph;
       
  2767     const POT& _potential;
       
  2768   };
       
  2769 
       
  2770   /// \brief Returns a PotentialDifferenceMap.
       
  2771   ///
       
  2772   /// This function just returns a PotentialDifferenceMap.
       
  2773   /// \relates PotentialDifferenceMap
       
  2774   template <typename GR, typename POT>
       
  2775   PotentialDifferenceMap<GR, POT>
       
  2776   potentialDifferenceMap(const GR& gr, const POT& potential) {
       
  2777     return PotentialDifferenceMap<GR, POT>(gr, potential);
       
  2778   }
       
  2779 
  2704   /// @}
  2780   /// @}
  2705 }
  2781 }
  2706 
  2782 
  2707 #endif // LEMON_MAPS_H
  2783 #endif // LEMON_MAPS_H