diff -r 94387da47f79 -r c5fd2d996909 lemon/maps.h --- a/lemon/maps.h Thu Mar 05 10:13:20 2009 +0000 +++ b/lemon/maps.h Sun Mar 29 23:08:20 2009 +0200 @@ -63,9 +63,10 @@ template class NullMap : public MapBase { public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef K Key; + ///\e + typedef V Value; /// Gives back a default constructed element. Value operator[](const Key&) const { return Value(); } @@ -102,9 +103,10 @@ private: V _value; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef K Key; + ///\e + typedef V Value; /// Default constructor @@ -168,9 +170,10 @@ template class ConstMap > : public MapBase { public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef K Key; + ///\e + typedef V Value; /// Constructor. ConstMap() {} @@ -202,9 +205,10 @@ template class IdentityMap : public MapBase { public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef T Key; + ///\e + typedef T Value; /// Gives back the given value without any modification. Value operator[](const Key &k) const { @@ -245,11 +249,10 @@ public: - typedef MapBase Parent; /// Key type - typedef typename Parent::Key Key; + typedef int Key; /// Value type - typedef typename Parent::Value Value; + typedef V Value; /// Reference type typedef typename Vector::reference Reference; /// Const reference type @@ -353,17 +356,16 @@ /// /// The simplest way of using this map is through the sparseMap() /// function. - template > + template > class SparseMap : public MapBase { template friend class SparseMap; public: - typedef MapBase Parent; /// Key type - typedef typename Parent::Key Key; + typedef K Key; /// Value type - typedef typename Parent::Value Value; + typedef V Value; /// Reference type typedef Value& Reference; /// Const reference type @@ -373,7 +375,7 @@ private: - typedef std::map Map; + typedef std::map Map; Map _map; Value _value; @@ -489,14 +491,15 @@ const M1 &_m1; const M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M2::Key Key; + ///\e + typedef typename M1::Value Value; /// Constructor ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} - /// \e + ///\e typename MapTraits::ConstReturnValue operator[](const Key &k) const { return _m1[_m2[k]]; } }; @@ -545,14 +548,15 @@ const M2 &_m2; F _f; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef V Value; /// Constructor CombineMap(const M1 &m1, const M2 &m2, const F &f = F()) : _m1(m1), _m2(m2), _f(f) {} - /// \e + ///\e Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); } }; @@ -615,13 +619,14 @@ class FunctorToMap : public MapBase { F _f; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef K Key; + ///\e + typedef V Value; /// Constructor FunctorToMap(const F &f = F()) : _f(f) {} - /// \e + ///\e Value operator[](const Key &k) const { return _f(k); } }; @@ -669,18 +674,19 @@ class MapToFunctor : public MapBase { const M &_m; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; - - typedef typename Parent::Key argument_type; - typedef typename Parent::Value result_type; + ///\e + typedef typename M::Key Key; + ///\e + typedef typename M::Value Value; + + typedef typename M::Key argument_type; + typedef typename M::Value result_type; /// Constructor MapToFunctor(const M &m) : _m(m) {} - /// \e + ///\e Value operator()(const Key &k) const { return _m[k]; } - /// \e + ///\e Value operator[](const Key &k) const { return _m[k]; } }; @@ -709,9 +715,10 @@ class ConvertMap : public MapBase { const M &_m; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef V Value; /// Constructor @@ -719,7 +726,7 @@ /// \param m The underlying map. ConvertMap(const M &m) : _m(m) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m[k]; } }; @@ -751,9 +758,10 @@ M1 &_m1; M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef typename M1::Value Value; /// Constructor ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {} @@ -797,13 +805,14 @@ const M1 &_m1; const M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef typename M1::Value Value; /// Constructor AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m1[k]+_m2[k]; } }; @@ -845,13 +854,14 @@ const M1 &_m1; const M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef typename M1::Value Value; /// Constructor SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m1[k]-_m2[k]; } }; @@ -894,13 +904,14 @@ const M1 &_m1; const M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef typename M1::Value Value; /// Constructor MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m1[k]*_m2[k]; } }; @@ -942,13 +953,14 @@ const M1 &_m1; const M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef typename M1::Value Value; /// Constructor DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m1[k]/_m2[k]; } }; @@ -992,9 +1004,10 @@ const M &_m; C _v; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef typename M::Value Value; /// Constructor @@ -1002,7 +1015,7 @@ /// \param m The undelying map. /// \param v The constant value. ShiftMap(const M &m, const C &v) : _m(m), _v(v) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m[k]+_v; } }; @@ -1022,9 +1035,10 @@ M &_m; C _v; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef typename M::Value Value; /// Constructor @@ -1032,9 +1046,9 @@ /// \param m The undelying map. /// \param v The constant value. ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m[k]+_v; } - /// \e + ///\e void set(const Key &k, const Value &v) { _m.set(k, v-_v); } }; @@ -1093,9 +1107,10 @@ const M &_m; C _v; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef typename M::Value Value; /// Constructor @@ -1103,7 +1118,7 @@ /// \param m The undelying map. /// \param v The constant value. ScaleMap(const M &m, const C &v) : _m(m), _v(v) {} - /// \e + ///\e Value operator[](const Key &k) const { return _v*_m[k]; } }; @@ -1124,9 +1139,10 @@ M &_m; C _v; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef typename M::Value Value; /// Constructor @@ -1134,9 +1150,9 @@ /// \param m The undelying map. /// \param v The constant value. ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {} - /// \e + ///\e Value operator[](const Key &k) const { return _v*_m[k]; } - /// \e + ///\e void set(const Key &k, const Value &v) { _m.set(k, v/_v); } }; @@ -1193,13 +1209,14 @@ class NegMap : public MapBase { const M& _m; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef typename M::Value Value; /// Constructor NegMap(const M &m) : _m(m) {} - /// \e + ///\e Value operator[](const Key &k) const { return -_m[k]; } }; @@ -1228,15 +1245,16 @@ class NegWriteMap : public MapBase { M &_m; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef typename M::Value Value; /// Constructor NegWriteMap(M &m) : _m(m) {} - /// \e + ///\e Value operator[](const Key &k) const { return -_m[k]; } - /// \e + ///\e void set(const Key &k, const Value &v) { _m.set(k, -v); } }; @@ -1282,13 +1300,14 @@ class AbsMap : public MapBase { const M &_m; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef typename M::Value Value; /// Constructor AbsMap(const M &m) : _m(m) {} - /// \e + ///\e Value operator[](const Key &k) const { Value tmp = _m[k]; return tmp >= 0 ? tmp : -tmp; @@ -1337,9 +1356,10 @@ template class TrueMap : public MapBase { public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef K Key; + ///\e + typedef bool Value; /// Gives back \c true. Value operator[](const Key&) const { return true; } @@ -1374,9 +1394,10 @@ template class FalseMap : public MapBase { public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef K Key; + ///\e + typedef bool Value; /// Gives back \c false. Value operator[](const Key&) const { return false; } @@ -1419,13 +1440,14 @@ const M1 &_m1; const M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef bool Value; /// Constructor AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; } }; @@ -1467,13 +1489,14 @@ const M1 &_m1; const M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef bool Value; /// Constructor OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m1[k]||_m2[k]; } }; @@ -1506,13 +1529,14 @@ class NotMap : public MapBase { const M &_m; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef bool Value; /// Constructor NotMap(const M &m) : _m(m) {} - /// \e + ///\e Value operator[](const Key &k) const { return !_m[k]; } }; @@ -1532,15 +1556,16 @@ class NotWriteMap : public MapBase { M &_m; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M::Key Key; + ///\e + typedef bool Value; /// Constructor NotWriteMap(M &m) : _m(m) {} - /// \e + ///\e Value operator[](const Key &k) const { return !_m[k]; } - /// \e + ///\e void set(const Key &k, bool v) { _m.set(k, !v); } }; @@ -1595,13 +1620,14 @@ const M1 &_m1; const M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef bool Value; /// Constructor EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m1[k]==_m2[k]; } }; @@ -1643,13 +1669,14 @@ const M1 &_m1; const M2 &_m2; public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; + ///\e + typedef typename M1::Key Key; + ///\e + typedef bool Value; /// Constructor LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} - /// \e + ///\e Value operator[](const Key &k) const { return _m1[k]<_m2[k]; } }; @@ -1705,24 +1732,27 @@ /// The simplest way of using this map is through the loggerBoolMap() /// function. /// - /// \tparam It The type of the iterator. - /// \tparam Ke The key type of the map. The default value set + /// \tparam IT The type of the iterator. + /// \tparam KEY The key type of the map. The default value set /// according to the iterator type should work in most cases. /// /// \note The container of the iterator must contain enough space /// for the elements or the iterator should be an inserter iterator. #ifdef DOXYGEN - template + template #else - template ::Value> + template ::Value> #endif - class LoggerBoolMap { + class LoggerBoolMap : public MapBase { public: - typedef It Iterator; - - typedef Ke Key; + + ///\e + typedef KEY Key; + ///\e typedef bool Value; + ///\e + typedef IT Iterator; /// Constructor LoggerBoolMap(Iterator it) @@ -1785,23 +1815,35 @@ /// \addtogroup graph_maps /// @{ - /// Provides an immutable and unique id for each item in the graph. - - /// The IdMap class provides a unique and immutable id for each item of the - /// same type (e.g. node) in the graph. This id is
  • \b unique: - /// different items (nodes) get different ids
  • \b immutable: the id of an - /// item (node) does not change (even if you delete other nodes).
- /// Through this map you get access (i.e. can read) the inner id values of - /// the items stored in the graph. This map can be inverted with its member + /// \brief Provides an immutable and unique id for each item in a graph. + /// + /// IdMap provides a unique and immutable id for each item of the + /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is + /// - \b unique: different items get different ids, + /// - \b immutable: the id of an item does not change (even if you + /// delete other nodes). + /// + /// Using this map you get access (i.e. can read) the inner id values of + /// the items stored in the graph, which is returned by the \c id() + /// function of the graph. This map can be inverted with its member /// class \c InverseMap or with the \c operator() member. /// - template - class IdMap { + /// \tparam GR The graph type. + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or + /// \c GR::Edge). + /// + /// \see DescriptorMap + template + class IdMap : public MapBase { public: - typedef _Graph Graph; + /// The graph type of IdMap. + typedef GR Graph; + /// The key type of IdMap (\c Node, \c Arc or \c Edge). + typedef K Item; + /// The key type of IdMap (\c Node, \c Arc or \c Edge). + typedef K Key; + /// The value type of IdMap. typedef int Value; - typedef _Item Item; - typedef _Item Key; /// \brief Constructor. /// @@ -1813,9 +1855,9 @@ /// Gives back the immutable and unique \e id of the item. int operator[](const Item& item) const { return _graph->id(item);} - /// \brief Gives back the item by its id. + /// \brief Gives back the \e item by its id. /// - /// Gives back the item by its id. + /// Gives back the \e item by its id. Item operator()(int id) { return _graph->fromId(id, Item()); } private: @@ -1823,9 +1865,9 @@ public: - /// \brief The class represents the inverse of its owner (IdMap). + /// \brief This class represents the inverse of its owner (IdMap). /// - /// The class represents the inverse of its owner (IdMap). + /// This class represents the inverse of its owner (IdMap). /// \see inverse() class InverseMap { public: @@ -1843,7 +1885,6 @@ /// \brief Gives back the given item from its id. /// /// Gives back the given item from its id. - /// Item operator[](int id) const { return _graph->fromId(id, Item());} private: @@ -1854,56 +1895,57 @@ /// /// Gives back the inverse of the IdMap. InverseMap inverse() const { return InverseMap(*_graph);} - }; - /// \brief General invertable graph-map type. - - /// This type provides simple invertable graph-maps. - /// The InvertableMap wraps an arbitrary ReadWriteMap + /// \brief General invertable graph map type. + + /// This class provides simple invertable graph maps. + /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap" /// and if a key is set to a new value then store it /// in the inverse map. /// /// The values of the map can be accessed /// with stl compatible forward iterator. /// - /// \tparam _Graph The graph type. - /// \tparam _Item The item type of the graph. - /// \tparam _Value The value type of the map. + /// \tparam GR The graph type. + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or + /// \c GR::Edge). + /// \tparam V The value type of the map. /// /// \see IterableValueMap - template + template class InvertableMap - : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type { + : protected ItemSetTraits::template Map::Type { private: - typedef typename ItemSetTraits<_Graph, _Item>:: - template Map<_Value>::Type Map; - typedef _Graph Graph; - - typedef std::map<_Value, _Item> Container; + typedef typename ItemSetTraits:: + template Map::Type Map; + + typedef std::map Container; Container _inv_map; public: - /// The key type of InvertableMap (Node, Arc, Edge). - typedef typename Map::Key Key; - /// The value type of the InvertableMap. - typedef typename Map::Value Value; + /// The graph type of InvertableMap. + typedef GR Graph; + /// The key type of InvertableMap (\c Node, \c Arc or \c Edge). + typedef K Item; + /// The key type of InvertableMap (\c Node, \c Arc or \c Edge). + typedef K Key; + /// The value type of InvertableMap. + typedef V Value; /// \brief Constructor. /// - /// Construct a new InvertableMap for the graph. - /// + /// Construct a new InvertableMap for the given graph. explicit InvertableMap(const Graph& graph) : Map(graph) {} /// \brief Forward iterator for values. /// /// This iterator is an stl compatible forward /// iterator on the values of the map. The values can - /// be accessed in the [beginValue, endValue) range. - /// + /// be accessed in the [beginValue, endValue) range. class ValueIterator : public std::iterator { friend class InvertableMap; @@ -1935,7 +1977,7 @@ /// /// Returns an stl compatible iterator to the /// first value of the map. The values of the - /// map can be accessed in the [beginValue, endValue) + /// map can be accessed in the [beginValue, endValue) /// range. ValueIterator beginValue() const { return ValueIterator(_inv_map.begin()); @@ -1945,15 +1987,15 @@ /// /// Returns an stl compatible iterator after the /// last value of the map. The values of the - /// map can be accessed in the [beginValue, endValue) + /// map can be accessed in the [beginValue, endValue) /// range. ValueIterator endValue() const { return ValueIterator(_inv_map.end()); } - /// \brief The setter function of the map. + /// \brief Sets the value associated with the given key. /// - /// Sets the mapped value. + /// Sets the value associated with the given key. void set(const Key& key, const Value& val) { Value oldval = Map::operator[](key); typename Container::iterator it = _inv_map.find(oldval); @@ -1964,9 +2006,9 @@ Map::set(key, val); } - /// \brief The getter function of the map. + /// \brief Returns the value associated with the given key. /// - /// It gives back the value associated with the key. + /// Returns the value associated with the given key. typename MapTraits::ConstReturnValue operator[](const Key& key) const { return Map::operator[](key); @@ -1982,9 +2024,9 @@ protected: - /// \brief Erase the key from the map. + /// \brief Erase the key from the map and the inverse map. /// - /// Erase the key to the map. It is called by the + /// Erase the key from the map and the inverse map. It is called by the /// \c AlterationNotifier. virtual void erase(const Key& key) { Value val = Map::operator[](key); @@ -1995,9 +2037,9 @@ Map::erase(key); } - /// \brief Erase more keys from the map. + /// \brief Erase more keys from the map and the inverse map. /// - /// Erase more keys from the map. It is called by the + /// Erase more keys from the map and the inverse map. It is called by the /// \c AlterationNotifier. virtual void erase(const std::vector& keys) { for (int i = 0; i < int(keys.size()); ++i) { @@ -2010,9 +2052,9 @@ Map::erase(keys); } - /// \brief Clear the keys from the map and inverse map. + /// \brief Clear the keys from the map and the inverse map. /// - /// Clear the keys from the map and inverse map. It is called by the + /// Clear the keys from the map and the inverse map. It is called by the /// \c AlterationNotifier. virtual void clear() { _inv_map.clear(); @@ -2024,10 +2066,10 @@ /// \brief The inverse map type. /// /// The inverse of this map. The subscript operator of the map - /// gives back always the item what was last assigned to the value. + /// gives back the item that was last assigned to the value. class InverseMap { public: - /// \brief Constructor of the InverseMap. + /// \brief Constructor /// /// Constructor of the InverseMap. explicit InverseMap(const InvertableMap& inverted) @@ -2040,8 +2082,8 @@ /// \brief Subscript operator. /// - /// Subscript operator. It gives back always the item - /// what was last assigned to the value. + /// Subscript operator. It gives back the item + /// that was last assigned to the given value. Value operator[](const Key& key) const { return _inverted(key); } @@ -2050,9 +2092,9 @@ const InvertableMap& _inverted; }; - /// \brief It gives back the just readable inverse map. + /// \brief It gives back the read-only inverse map. /// - /// It gives back the just readable inverse map. + /// It gives back the read-only inverse map. InverseMap inverse() const { return InverseMap(*this); } @@ -2060,40 +2102,48 @@ }; /// \brief Provides a mutable, continuous and unique descriptor for each - /// item in the graph. + /// item in a graph. /// - /// The DescriptorMap class provides a unique and continuous (but mutable) - /// descriptor (id) for each item of the same type (e.g. node) in the - /// graph. This id is
  • \b unique: different items (nodes) get - /// different ids
  • \b continuous: the range of the ids is the set of - /// integers between 0 and \c n-1, where \c n is the number of the items of - /// this type (e.g. nodes) (so the id of a node can change if you delete an - /// other node, i.e. this id is mutable).
This map can be inverted - /// with its member class \c InverseMap, or with the \c operator() member. + /// DescriptorMap provides a unique and continuous (but mutable) + /// descriptor (id) for each item of the same type (\c Node, \c Arc or + /// \c Edge) in a graph. This id is + /// - \b unique: different items get different ids, + /// - \b continuous: the range of the ids is the set of integers + /// between 0 and \c n-1, where \c n is the number of the items of + /// this type (\c Node, \c Arc or \c Edge). So the id of an item can + /// change if you delete an other item of the same type, i.e. this + /// id is mutable. /// - /// \tparam _Graph The graph class the \c DescriptorMap belongs to. - /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or - /// Edge. - template + /// Thus this id is not (necessarily) the same as what can get using + /// the \c id() function of the graph or \ref IdMap. + /// This map can be inverted with its member class \c InverseMap, + /// or with the \c operator() member. + /// + /// \tparam GR The graph type. + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or + /// \c GR::Edge). + /// + /// \see IdMap + template class DescriptorMap - : protected ItemSetTraits<_Graph, _Item>::template Map::Type { - - typedef _Item Item; - typedef typename ItemSetTraits<_Graph, _Item>::template Map::Type Map; + : protected ItemSetTraits::template Map::Type { + + typedef typename ItemSetTraits::template Map::Type Map; public: - /// The graph class of DescriptorMap. - typedef _Graph Graph; - - /// The key type of DescriptorMap (Node, Arc, Edge). - typedef typename Map::Key Key; + /// The graph type of DescriptorMap. + typedef GR Graph; + /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge). + typedef K Item; + /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge). + typedef K Key; /// The value type of DescriptorMap. - typedef typename Map::Value Value; + typedef int Value; /// \brief Constructor. /// /// Constructor for descriptor map. - explicit DescriptorMap(const Graph& _graph) : Map(_graph) { + explicit DescriptorMap(const Graph& gr) : Map(gr) { Item it; const typename Map::Notifier* nf = Map::notifier(); for (nf->first(it); it != INVALID; nf->next(it)) { @@ -2104,7 +2154,7 @@ protected: - /// \brief Add a new key to the map. + /// \brief Adds a new key to the map. /// /// Add a new key to the map. It is called by the /// \c AlterationNotifier. @@ -2214,12 +2264,13 @@ Container _inv_map; public: + /// \brief The inverse map type of DescriptorMap. /// /// The inverse map type of DescriptorMap. class InverseMap { public: - /// \brief Constructor of the InverseMap. + /// \brief Constructor /// /// Constructor of the InverseMap. explicit InverseMap(const DescriptorMap& inverted) @@ -2234,7 +2285,7 @@ /// \brief Subscript operator. /// /// Subscript operator. It gives back the item - /// that the descriptor belongs to currently. + /// that the descriptor currently belongs to. Value operator[](const Key& key) const { return _inverted(key); } @@ -2258,230 +2309,198 @@ } }; - /// \brief Returns the source of the given arc. + /// \brief Map of the source nodes of arcs in a digraph. /// - /// The SourceMap gives back the source Node of the given arc. + /// SourceMap provides access for the source node of each arc in a digraph, + /// which is returned by the \c source() function of the digraph. + /// \tparam GR The digraph type. /// \see TargetMap - template + template class SourceMap { public: - typedef typename Digraph::Node Value; - typedef typename Digraph::Arc Key; + ///\e + typedef typename GR::Arc Key; + ///\e + typedef typename GR::Node Value; /// \brief Constructor /// - /// Constructor + /// Constructor. /// \param digraph The digraph that the map belongs to. - explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {} - - /// \brief The subscript operator. + explicit SourceMap(const GR& digraph) : _graph(digraph) {} + + /// \brief Returns the source node of the given arc. /// - /// The subscript operator. - /// \param arc The arc - /// \return The source of the arc + /// Returns the source node of the given arc. Value operator[](const Key& arc) const { - return _digraph.source(arc); + return _graph.source(arc); } private: - const Digraph& _digraph; + const GR& _graph; }; /// \brief Returns a \c SourceMap class. /// /// This function just returns an \c SourceMap class. /// \relates SourceMap - template - inline SourceMap sourceMap(const Digraph& digraph) { - return SourceMap(digraph); + template + inline SourceMap sourceMap(const GR& graph) { + return SourceMap(graph); } - /// \brief Returns the target of the given arc. + /// \brief Map of the target nodes of arcs in a digraph. /// - /// The TargetMap gives back the target Node of the given arc. + /// TargetMap provides access for the target node of each arc in a digraph, + /// which is returned by the \c target() function of the digraph. + /// \tparam GR The digraph type. /// \see SourceMap - template + template class TargetMap { public: - typedef typename Digraph::Node Value; - typedef typename Digraph::Arc Key; + ///\e + typedef typename GR::Arc Key; + ///\e + typedef typename GR::Node Value; /// \brief Constructor /// - /// Constructor + /// Constructor. /// \param digraph The digraph that the map belongs to. - explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {} - - /// \brief The subscript operator. + explicit TargetMap(const GR& digraph) : _graph(digraph) {} + + /// \brief Returns the target node of the given arc. /// - /// The subscript operator. - /// \param e The arc - /// \return The target of the arc + /// Returns the target node of the given arc. Value operator[](const Key& e) const { - return _digraph.target(e); + return _graph.target(e); } private: - const Digraph& _digraph; + const GR& _graph; }; /// \brief Returns a \c TargetMap class. /// /// This function just returns a \c TargetMap class. /// \relates TargetMap - template - inline TargetMap targetMap(const Digraph& digraph) { - return TargetMap(digraph); + template + inline TargetMap targetMap(const GR& graph) { + return TargetMap(graph); } - /// \brief Returns the "forward" directed arc view of an edge. + /// \brief Map of the "forward" directed arc view of edges in a graph. /// - /// Returns the "forward" directed arc view of an edge. + /// ForwardMap provides access for the "forward" directed arc view of + /// each edge in a graph, which is returned by the \c direct() function + /// of the graph with \c true parameter. + /// \tparam GR The graph type. /// \see BackwardMap - template + template class ForwardMap { public: - typedef typename Graph::Arc Value; - typedef typename Graph::Edge Key; + typedef typename GR::Arc Value; + typedef typename GR::Edge Key; /// \brief Constructor /// - /// Constructor + /// Constructor. /// \param graph The graph that the map belongs to. - explicit ForwardMap(const Graph& graph) : _graph(graph) {} - - /// \brief The subscript operator. + explicit ForwardMap(const GR& graph) : _graph(graph) {} + + /// \brief Returns the "forward" directed arc view of the given edge. /// - /// The subscript operator. - /// \param key An edge - /// \return The "forward" directed arc view of edge + /// Returns the "forward" directed arc view of the given edge. Value operator[](const Key& key) const { return _graph.direct(key, true); } private: - const Graph& _graph; + const GR& _graph; }; /// \brief Returns a \c ForwardMap class. /// /// This function just returns an \c ForwardMap class. /// \relates ForwardMap - template - inline ForwardMap forwardMap(const Graph& graph) { - return ForwardMap(graph); + template + inline ForwardMap forwardMap(const GR& graph) { + return ForwardMap(graph); } - /// \brief Returns the "backward" directed arc view of an edge. + /// \brief Map of the "backward" directed arc view of edges in a graph. /// - /// Returns the "backward" directed arc view of an edge. + /// BackwardMap provides access for the "backward" directed arc view of + /// each edge in a graph, which is returned by the \c direct() function + /// of the graph with \c false parameter. + /// \tparam GR The graph type. /// \see ForwardMap - template + template class BackwardMap { public: - typedef typename Graph::Arc Value; - typedef typename Graph::Edge Key; + typedef typename GR::Arc Value; + typedef typename GR::Edge Key; /// \brief Constructor /// - /// Constructor + /// Constructor. /// \param graph The graph that the map belongs to. - explicit BackwardMap(const Graph& graph) : _graph(graph) {} - - /// \brief The subscript operator. + explicit BackwardMap(const GR& graph) : _graph(graph) {} + + /// \brief Returns the "backward" directed arc view of the given edge. /// - /// The subscript operator. - /// \param key An edge - /// \return The "backward" directed arc view of edge + /// Returns the "backward" directed arc view of the given edge. Value operator[](const Key& key) const { return _graph.direct(key, false); } private: - const Graph& _graph; + const GR& _graph; }; /// \brief Returns a \c BackwardMap class /// This function just returns a \c BackwardMap class. /// \relates BackwardMap - template - inline BackwardMap backwardMap(const Graph& graph) { - return BackwardMap(graph); + template + inline BackwardMap backwardMap(const GR& graph) { + return BackwardMap(graph); } - /// \brief Potential difference map - /// - /// If there is an potential map on the nodes then we - /// can get an arc map as we get the substraction of the - /// values of the target and source. - template - class PotentialDifferenceMap { - public: - typedef typename Digraph::Arc Key; - typedef typename NodeMap::Value Value; - - /// \brief Constructor - /// - /// Contructor of the map - explicit PotentialDifferenceMap(const Digraph& digraph, - const NodeMap& potential) - : _digraph(digraph), _potential(potential) {} - - /// \brief Const subscription operator - /// - /// Const subscription operator - Value operator[](const Key& arc) const { - return _potential[_digraph.target(arc)] - - _potential[_digraph.source(arc)]; - } - - private: - const Digraph& _digraph; - const NodeMap& _potential; - }; - - /// \brief Returns a PotentialDifferenceMap. - /// - /// This function just returns a PotentialDifferenceMap. - /// \relates PotentialDifferenceMap - template - PotentialDifferenceMap - potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) { - return PotentialDifferenceMap(digraph, potential); - } - - /// \brief Map of the node in-degrees. + /// \brief Map of the in-degrees of nodes in a digraph. /// /// This map returns the in-degree of a node. Once it is constructed, - /// the degrees are stored in a standard NodeMap, so each query is done + /// the degrees are stored in a standard \c NodeMap, so each query is done /// in constant time. On the other hand, the values are updated automatically /// whenever the digraph changes. /// - /// \warning Besides addNode() and addArc(), a digraph structure may provide - /// alternative ways to modify the digraph. The correct behavior of InDegMap - /// is not guarantied if these additional features are used. For example - /// the functions \ref ListDigraph::changeSource() "changeSource()", + /// \warning Besides \c addNode() and \c addArc(), a digraph structure + /// may provide alternative ways to modify the digraph. + /// The correct behavior of InDegMap is not guarantied if these additional + /// features are used. For example the functions + /// \ref ListDigraph::changeSource() "changeSource()", /// \ref ListDigraph::changeTarget() "changeTarget()" and /// \ref ListDigraph::reverseArc() "reverseArc()" /// of \ref ListDigraph will \e not update the degree values correctly. /// /// \sa OutDegMap - - template + template class InDegMap - : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> + : protected ItemSetTraits ::ItemNotifier::ObserverBase { public: - - typedef _Digraph Digraph; + + /// The digraph type + typedef GR Digraph; + /// The key type + typedef typename Digraph::Node Key; + /// The value type typedef int Value; - typedef typename Digraph::Node Key; typedef typename ItemSetTraits ::ItemNotifier::ObserverBase Parent; @@ -2523,9 +2542,9 @@ /// \brief Constructor. /// - /// Constructor for creating in-degree map. - explicit InDegMap(const Digraph& digraph) - : _digraph(digraph), _deg(digraph) { + /// Constructor for creating an in-degree map. + explicit InDegMap(const Digraph& graph) + : _digraph(graph), _deg(graph) { Parent::attach(_digraph.notifier(typename Digraph::Arc())); for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { @@ -2533,6 +2552,8 @@ } } + /// \brief Gives back the in-degree of a Node. + /// /// Gives back the in-degree of a Node. int operator[](const Key& key) const { return _deg[key]; @@ -2579,33 +2600,36 @@ AutoNodeMap _deg; }; - /// \brief Map of the node out-degrees. + /// \brief Map of the out-degrees of nodes in a digraph. /// /// This map returns the out-degree of a node. Once it is constructed, - /// the degrees are stored in a standard NodeMap, so each query is done + /// the degrees are stored in a standard \c NodeMap, so each query is done /// in constant time. On the other hand, the values are updated automatically /// whenever the digraph changes. /// - /// \warning Besides addNode() and addArc(), a digraph structure may provide - /// alternative ways to modify the digraph. The correct behavior of OutDegMap - /// is not guarantied if these additional features are used. For example - /// the functions \ref ListDigraph::changeSource() "changeSource()", + /// \warning Besides \c addNode() and \c addArc(), a digraph structure + /// may provide alternative ways to modify the digraph. + /// The correct behavior of OutDegMap is not guarantied if these additional + /// features are used. For example the functions + /// \ref ListDigraph::changeSource() "changeSource()", /// \ref ListDigraph::changeTarget() "changeTarget()" and /// \ref ListDigraph::reverseArc() "reverseArc()" /// of \ref ListDigraph will \e not update the degree values correctly. /// /// \sa InDegMap - - template + template class OutDegMap - : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> + : protected ItemSetTraits ::ItemNotifier::ObserverBase { public: - typedef _Digraph Digraph; + /// The digraph type + typedef GR Digraph; + /// The key type + typedef typename Digraph::Node Key; + /// The value type typedef int Value; - typedef typename Digraph::Node Key; typedef typename ItemSetTraits ::ItemNotifier::ObserverBase Parent; @@ -2645,9 +2669,9 @@ /// \brief Constructor. /// - /// Constructor for creating out-degree map. - explicit OutDegMap(const Digraph& digraph) - : _digraph(digraph), _deg(digraph) { + /// Constructor for creating an out-degree map. + explicit OutDegMap(const Digraph& graph) + : _digraph(graph), _deg(graph) { Parent::attach(_digraph.notifier(typename Digraph::Arc())); for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { @@ -2655,6 +2679,8 @@ } } + /// \brief Gives back the out-degree of a Node. + /// /// Gives back the out-degree of a Node. int operator[](const Key& key) const { return _deg[key]; @@ -2701,6 +2727,56 @@ AutoNodeMap _deg; }; + /// \brief Potential difference map + /// + /// PotentialMap returns the difference between the potentials of the + /// source and target nodes of each arc in a digraph, i.e. it returns + /// \code + /// potential[gr.target(arc)] - potential[gr.source(arc)]. + /// \endcode + /// \tparam GR The digraph type. + /// \tparam POT A node map storing the potentials. + template + class PotentialDifferenceMap { + public: + /// Key type + typedef typename GR::Arc Key; + /// Value type + typedef typename POT::Value Value; + + /// \brief Constructor + /// + /// Contructor of the map. + explicit PotentialDifferenceMap(const GR& gr, + const POT& potential) + : _digraph(gr), _potential(potential) {} + + /// \brief Returns the potential difference for the given arc. + /// + /// Returns the potential difference for the given arc, i.e. + /// \code + /// potential[gr.target(arc)] - potential[gr.source(arc)]. + /// \endcode + Value operator[](const Key& arc) const { + return _potential[_digraph.target(arc)] - + _potential[_digraph.source(arc)]; + } + + private: + const GR& _digraph; + const POT& _potential; + }; + + /// \brief Returns a PotentialDifferenceMap. + /// + /// This function just returns a PotentialDifferenceMap. + /// \relates PotentialDifferenceMap + template + PotentialDifferenceMap + potentialDifferenceMap(const GR& gr, const POT& potential) { + return PotentialDifferenceMap(gr, potential); + } + /// @} }