Update INSTALL file.
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
26 #include <lemon/core.h>
30 ///\brief Miscellaneous property maps
39 /// Base class of maps.
41 /// Base class of maps. It provides the necessary type definitions
42 /// required by the map %concepts.
43 template<typename K, typename V>
46 /// \biref The key type of the map.
48 /// \brief The value type of the map.
49 /// (The type of objects associated with the keys).
54 /// Null map. (a.k.a. DoNothingMap)
56 /// This map can be used if you have to provide a map only for
57 /// its type definitions, or if you have to provide a writable map,
58 /// but data written to it is not required (i.e. it will be sent to
59 /// <tt>/dev/null</tt>).
60 /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
63 template<typename K, typename V>
64 class NullMap : public MapBase<K, V> {
66 typedef MapBase<K, V> Parent;
67 typedef typename Parent::Key Key;
68 typedef typename Parent::Value Value;
70 /// Gives back a default constructed element.
71 Value operator[](const Key&) const { return Value(); }
72 /// Absorbs the value.
73 void set(const Key&, const Value&) {}
76 /// Returns a \ref NullMap class
78 /// This function just returns a \ref NullMap class.
80 template <typename K, typename V>
81 NullMap<K, V> nullMap() {
82 return NullMap<K, V>();
88 /// This \ref concepts::ReadMap "readable map" assigns a specified
89 /// value to each key.
91 /// In other aspects it is equivalent to \ref NullMap.
92 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
93 /// concept, but it absorbs the data written to it.
95 /// The simplest way of using this map is through the constMap()
100 template<typename K, typename V>
101 class ConstMap : public MapBase<K, V> {
105 typedef MapBase<K, V> Parent;
106 typedef typename Parent::Key Key;
107 typedef typename Parent::Value Value;
109 /// Default constructor
111 /// Default constructor.
112 /// The value of the map will be default constructed.
115 /// Constructor with specified initial value
117 /// Constructor with specified initial value.
118 /// \param v The initial value of the map.
119 ConstMap(const Value &v) : _value(v) {}
121 /// Gives back the specified value.
122 Value operator[](const Key&) const { return _value; }
124 /// Absorbs the value.
125 void set(const Key&, const Value&) {}
127 /// Sets the value that is assigned to each key.
128 void setAll(const Value &v) {
132 template<typename V1>
133 ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
136 /// Returns a \ref ConstMap class
138 /// This function just returns a \ref ConstMap class.
139 /// \relates ConstMap
140 template<typename K, typename V>
141 inline ConstMap<K, V> constMap(const V &v) {
142 return ConstMap<K, V>(v);
145 template<typename K, typename V>
146 inline ConstMap<K, V> constMap() {
147 return ConstMap<K, V>();
151 template<typename T, T v>
154 /// Constant map with inlined constant value.
156 /// This \ref concepts::ReadMap "readable map" assigns a specified
157 /// value to each key.
159 /// In other aspects it is equivalent to \ref NullMap.
160 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
161 /// concept, but it absorbs the data written to it.
163 /// The simplest way of using this map is through the constMap()
168 template<typename K, typename V, V v>
169 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
171 typedef MapBase<K, V> Parent;
172 typedef typename Parent::Key Key;
173 typedef typename Parent::Value Value;
178 /// Gives back the specified value.
179 Value operator[](const Key&) const { return v; }
181 /// Absorbs the value.
182 void set(const Key&, const Value&) {}
185 /// Returns a \ref ConstMap class with inlined constant value
187 /// This function just returns a \ref ConstMap class with inlined
189 /// \relates ConstMap
190 template<typename K, typename V, V v>
191 inline ConstMap<K, Const<V, v> > constMap() {
192 return ConstMap<K, Const<V, v> >();
198 /// This \ref concepts::ReadMap "read-only map" gives back the given
199 /// key as value without any modification.
202 template <typename T>
203 class IdentityMap : public MapBase<T, T> {
205 typedef MapBase<T, T> Parent;
206 typedef typename Parent::Key Key;
207 typedef typename Parent::Value Value;
209 /// Gives back the given value without any modification.
210 Value operator[](const Key &k) const {
215 /// Returns an \ref IdentityMap class
217 /// This function just returns an \ref IdentityMap class.
218 /// \relates IdentityMap
220 inline IdentityMap<T> identityMap() {
221 return IdentityMap<T>();
225 /// \brief Map for storing values for integer keys from the range
226 /// <tt>[0..size-1]</tt>.
228 /// This map is essentially a wrapper for \c std::vector. It assigns
229 /// values to integer keys from the range <tt>[0..size-1]</tt>.
230 /// It can be used with some data structures, for example
231 /// \ref UnionFind, \ref BinHeap, when the used items are small
232 /// integers. This map conforms the \ref concepts::ReferenceMap
233 /// "ReferenceMap" concept.
235 /// The simplest way of using this map is through the rangeMap()
237 template <typename V>
238 class RangeMap : public MapBase<int, V> {
239 template <typename V1>
240 friend class RangeMap;
243 typedef std::vector<V> Vector;
248 typedef MapBase<int, V> Parent;
250 typedef typename Parent::Key Key;
252 typedef typename Parent::Value Value;
254 typedef typename Vector::reference Reference;
255 /// Const reference type
256 typedef typename Vector::const_reference ConstReference;
258 typedef True ReferenceMapTag;
262 /// Constructor with specified default value.
263 RangeMap(int size = 0, const Value &value = Value())
264 : _vector(size, value) {}
266 /// Constructs the map from an appropriate \c std::vector.
267 template <typename V1>
268 RangeMap(const std::vector<V1>& vector)
269 : _vector(vector.begin(), vector.end()) {}
271 /// Constructs the map from another \ref RangeMap.
272 template <typename V1>
273 RangeMap(const RangeMap<V1> &c)
274 : _vector(c._vector.begin(), c._vector.end()) {}
276 /// Returns the size of the map.
278 return _vector.size();
283 /// Resizes the underlying \c std::vector container, so changes the
284 /// keyset of the map.
285 /// \param size The new size of the map. The new keyset will be the
286 /// range <tt>[0..size-1]</tt>.
287 /// \param value The default value to assign to the new keys.
288 void resize(int size, const Value &value = Value()) {
289 _vector.resize(size, value);
294 RangeMap& operator=(const RangeMap&);
299 Reference operator[](const Key &k) {
304 ConstReference operator[](const Key &k) const {
309 void set(const Key &k, const Value &v) {
314 /// Returns a \ref RangeMap class
316 /// This function just returns a \ref RangeMap class.
317 /// \relates RangeMap
319 inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
320 return RangeMap<V>(size, value);
323 /// \brief Returns a \ref RangeMap class created from an appropriate
326 /// This function just returns a \ref RangeMap class created from an
327 /// appropriate \c std::vector.
328 /// \relates RangeMap
330 inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
331 return RangeMap<V>(vector);
335 /// Map type based on \c std::map
337 /// This map is essentially a wrapper for \c std::map with addition
338 /// that you can specify a default value for the keys that are not
339 /// stored actually. This value can be different from the default
340 /// contructed value (i.e. \c %Value()).
341 /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
344 /// This map is useful if a default value should be assigned to most of
345 /// the keys and different values should be assigned only to a few
346 /// keys (i.e. the map is "sparse").
347 /// The name of this type also refers to this important usage.
349 /// Apart form that this map can be used in many other cases since it
350 /// is based on \c std::map, which is a general associative container.
351 /// However keep in mind that it is usually not as efficient as other
354 /// The simplest way of using this map is through the sparseMap()
356 template <typename K, typename V, typename Compare = std::less<K> >
357 class SparseMap : public MapBase<K, V> {
358 template <typename K1, typename V1, typename C1>
359 friend class SparseMap;
362 typedef MapBase<K, V> Parent;
364 typedef typename Parent::Key Key;
366 typedef typename Parent::Value Value;
368 typedef Value& Reference;
369 /// Const reference type
370 typedef const Value& ConstReference;
372 typedef True ReferenceMapTag;
376 typedef std::map<K, V, Compare> Map;
382 /// \brief Constructor with specified default value.
383 SparseMap(const Value &value = Value()) : _value(value) {}
384 /// \brief Constructs the map from an appropriate \c std::map, and
385 /// explicitly specifies a default value.
386 template <typename V1, typename Comp1>
387 SparseMap(const std::map<Key, V1, Comp1> &map,
388 const Value &value = Value())
389 : _map(map.begin(), map.end()), _value(value) {}
391 /// \brief Constructs the map from another \ref SparseMap.
392 template<typename V1, typename Comp1>
393 SparseMap(const SparseMap<Key, V1, Comp1> &c)
394 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
398 SparseMap& operator=(const SparseMap&);
403 Reference operator[](const Key &k) {
404 typename Map::iterator it = _map.lower_bound(k);
405 if (it != _map.end() && !_map.key_comp()(k, it->first))
408 return _map.insert(it, std::make_pair(k, _value))->second;
412 ConstReference operator[](const Key &k) const {
413 typename Map::const_iterator it = _map.find(k);
414 if (it != _map.end())
421 void set(const Key &k, const Value &v) {
422 typename Map::iterator it = _map.lower_bound(k);
423 if (it != _map.end() && !_map.key_comp()(k, it->first))
426 _map.insert(it, std::make_pair(k, v));
430 void setAll(const Value &v) {
436 /// Returns a \ref SparseMap class
438 /// This function just returns a \ref SparseMap class with specified
440 /// \relates SparseMap
441 template<typename K, typename V, typename Compare>
442 inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
443 return SparseMap<K, V, Compare>(value);
446 template<typename K, typename V>
447 inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
448 return SparseMap<K, V, std::less<K> >(value);
451 /// \brief Returns a \ref SparseMap class created from an appropriate
454 /// This function just returns a \ref SparseMap class created from an
455 /// appropriate \c std::map.
456 /// \relates SparseMap
457 template<typename K, typename V, typename Compare>
458 inline SparseMap<K, V, Compare>
459 sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
461 return SparseMap<K, V, Compare>(map, value);
466 /// \addtogroup map_adaptors
469 /// Composition of two maps
471 /// This \ref concepts::ReadMap "read-only map" returns the
472 /// composition of two given maps. That is to say, if \c m1 is of
473 /// type \c M1 and \c m2 is of \c M2, then for
475 /// ComposeMap<M1, M2> cm(m1,m2);
477 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
479 /// The \c Key type of the map is inherited from \c M2 and the
480 /// \c Value type is from \c M1.
481 /// \c M2::Value must be convertible to \c M1::Key.
483 /// The simplest way of using this map is through the composeMap()
488 /// \todo Check the requirements.
489 template <typename M1, typename M2>
490 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
494 typedef MapBase<typename M2::Key, typename M1::Value> Parent;
495 typedef typename Parent::Key Key;
496 typedef typename Parent::Value Value;
499 ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
502 typename MapTraits<M1>::ConstReturnValue
503 operator[](const Key &k) const { return _m1[_m2[k]]; }
506 /// Returns a \ref ComposeMap class
508 /// This function just returns a \ref ComposeMap class.
510 /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
511 /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
512 /// will be equal to <tt>m1[m2[x]]</tt>.
514 /// \relates ComposeMap
515 template <typename M1, typename M2>
516 inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
517 return ComposeMap<M1, M2>(m1, m2);
521 /// Combination of two maps using an STL (binary) functor.
523 /// This \ref concepts::ReadMap "read-only map" takes two maps and a
524 /// binary functor and returns the combination of the two given maps
525 /// using the functor.
526 /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
527 /// and \c f is of \c F, then for
529 /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
531 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
533 /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
534 /// must be convertible to \c M2::Key) and the \c Value type is \c V.
535 /// \c M2::Value and \c M1::Value must be convertible to the
536 /// corresponding input parameter of \c F and the return type of \c F
537 /// must be convertible to \c V.
539 /// The simplest way of using this map is through the combineMap()
544 /// \todo Check the requirements.
545 template<typename M1, typename M2, typename F,
546 typename V = typename F::result_type>
547 class CombineMap : public MapBase<typename M1::Key, V> {
552 typedef MapBase<typename M1::Key, V> Parent;
553 typedef typename Parent::Key Key;
554 typedef typename Parent::Value Value;
557 CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
558 : _m1(m1), _m2(m2), _f(f) {}
560 Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
563 /// Returns a \ref CombineMap class
565 /// This function just returns a \ref CombineMap class.
567 /// For example, if \c m1 and \c m2 are both maps with \c double
570 /// combineMap(m1,m2,std::plus<double>())
577 /// This function is specialized for adaptable binary function
578 /// classes and C++ functions.
580 /// \relates CombineMap
581 template<typename M1, typename M2, typename F, typename V>
582 inline CombineMap<M1, M2, F, V>
583 combineMap(const M1 &m1, const M2 &m2, const F &f) {
584 return CombineMap<M1, M2, F, V>(m1,m2,f);
587 template<typename M1, typename M2, typename F>
588 inline CombineMap<M1, M2, F, typename F::result_type>
589 combineMap(const M1 &m1, const M2 &m2, const F &f) {
590 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
593 template<typename M1, typename M2, typename K1, typename K2, typename V>
594 inline CombineMap<M1, M2, V (*)(K1, K2), V>
595 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
596 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
600 /// Converts an STL style (unary) functor to a map
602 /// This \ref concepts::ReadMap "read-only map" returns the value
603 /// of a given functor. Actually, it just wraps the functor and
604 /// provides the \c Key and \c Value typedefs.
606 /// Template parameters \c K and \c V will become its \c Key and
607 /// \c Value. In most cases they have to be given explicitly because
608 /// a functor typically does not provide \c argument_type and
609 /// \c result_type typedefs.
610 /// Parameter \c F is the type of the used functor.
612 /// The simplest way of using this map is through the functorToMap()
617 typename K = typename F::argument_type,
618 typename V = typename F::result_type>
619 class FunctorToMap : public MapBase<K, V> {
622 typedef MapBase<K, V> Parent;
623 typedef typename Parent::Key Key;
624 typedef typename Parent::Value Value;
627 FunctorToMap(const F &f = F()) : _f(f) {}
629 Value operator[](const Key &k) const { return _f(k); }
632 /// Returns a \ref FunctorToMap class
634 /// This function just returns a \ref FunctorToMap class.
636 /// This function is specialized for adaptable binary function
637 /// classes and C++ functions.
639 /// \relates FunctorToMap
640 template<typename K, typename V, typename F>
641 inline FunctorToMap<F, K, V> functorToMap(const F &f) {
642 return FunctorToMap<F, K, V>(f);
645 template <typename F>
646 inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
647 functorToMap(const F &f)
649 return FunctorToMap<F, typename F::argument_type,
650 typename F::result_type>(f);
653 template <typename K, typename V>
654 inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
655 return FunctorToMap<V (*)(K), K, V>(f);
659 /// Converts a map to an STL style (unary) functor
661 /// This class converts a map to an STL style (unary) functor.
662 /// That is it provides an <tt>operator()</tt> to read its values.
664 /// For the sake of convenience it also works as a usual
665 /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
666 /// and the \c Key and \c Value typedefs also exist.
668 /// The simplest way of using this map is through the mapToFunctor()
672 template <typename M>
673 class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
676 typedef MapBase<typename M::Key, typename M::Value> Parent;
677 typedef typename Parent::Key Key;
678 typedef typename Parent::Value Value;
680 typedef typename Parent::Key argument_type;
681 typedef typename Parent::Value result_type;
684 MapToFunctor(const M &m) : _m(m) {}
686 Value operator()(const Key &k) const { return _m[k]; }
688 Value operator[](const Key &k) const { return _m[k]; }
691 /// Returns a \ref MapToFunctor class
693 /// This function just returns a \ref MapToFunctor class.
694 /// \relates MapToFunctor
696 inline MapToFunctor<M> mapToFunctor(const M &m) {
697 return MapToFunctor<M>(m);
701 /// \brief Map adaptor to convert the \c Value type of a map to
702 /// another type using the default conversion.
704 /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
705 /// "readable map" to another type using the default conversion.
706 /// The \c Key type of it is inherited from \c M and the \c Value
708 /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
710 /// The simplest way of using this map is through the convertMap()
712 template <typename M, typename V>
713 class ConvertMap : public MapBase<typename M::Key, V> {
716 typedef MapBase<typename M::Key, V> Parent;
717 typedef typename Parent::Key Key;
718 typedef typename Parent::Value Value;
723 /// \param m The underlying map.
724 ConvertMap(const M &m) : _m(m) {}
727 Value operator[](const Key &k) const { return _m[k]; }
730 /// Returns a \ref ConvertMap class
732 /// This function just returns a \ref ConvertMap class.
733 /// \relates ConvertMap
734 template<typename V, typename M>
735 inline ConvertMap<M, V> convertMap(const M &map) {
736 return ConvertMap<M, V>(map);
740 /// Applies all map setting operations to two maps
742 /// This map has two \ref concepts::WriteMap "writable map" parameters
743 /// and each write request will be passed to both of them.
744 /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
745 /// operations will return the corresponding values of \c M1.
747 /// The \c Key and \c Value types are inherited from \c M1.
748 /// The \c Key and \c Value of \c M2 must be convertible from those
751 /// The simplest way of using this map is through the forkMap()
753 template<typename M1, typename M2>
754 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
758 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
759 typedef typename Parent::Key Key;
760 typedef typename Parent::Value Value;
763 ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
764 /// Returns the value associated with the given key in the first map.
765 Value operator[](const Key &k) const { return _m1[k]; }
766 /// Sets the value associated with the given key in both maps.
767 void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
770 /// Returns a \ref ForkMap class
772 /// This function just returns a \ref ForkMap class.
774 template <typename M1, typename M2>
775 inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
776 return ForkMap<M1,M2>(m1,m2);
782 /// This \ref concepts::ReadMap "read-only map" returns the sum
783 /// of the values of the two given maps.
784 /// Its \c Key and \c Value types are inherited from \c M1.
785 /// The \c Key and \c Value of \c M2 must be convertible to those of
788 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
790 /// AddMap<M1,M2> am(m1,m2);
792 /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
794 /// The simplest way of using this map is through the addMap()
797 /// \sa SubMap, MulMap, DivMap
798 /// \sa ShiftMap, ShiftWriteMap
799 template<typename M1, typename M2>
800 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
804 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
805 typedef typename Parent::Key Key;
806 typedef typename Parent::Value Value;
809 AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
811 Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
814 /// Returns an \ref AddMap class
816 /// This function just returns an \ref AddMap class.
818 /// For example, if \c m1 and \c m2 are both maps with \c double
819 /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
820 /// <tt>m1[x]+m2[x]</tt>.
823 template<typename M1, typename M2>
824 inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
825 return AddMap<M1, M2>(m1,m2);
829 /// Difference of two maps
831 /// This \ref concepts::ReadMap "read-only map" returns the difference
832 /// of the values of the two given maps.
833 /// Its \c Key and \c Value types are inherited from \c M1.
834 /// The \c Key and \c Value of \c M2 must be convertible to those of
837 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
839 /// SubMap<M1,M2> sm(m1,m2);
841 /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
843 /// The simplest way of using this map is through the subMap()
846 /// \sa AddMap, MulMap, DivMap
847 template<typename M1, typename M2>
848 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
852 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
853 typedef typename Parent::Key Key;
854 typedef typename Parent::Value Value;
857 SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
859 Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
862 /// Returns a \ref SubMap class
864 /// This function just returns a \ref SubMap class.
866 /// For example, if \c m1 and \c m2 are both maps with \c double
867 /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
868 /// <tt>m1[x]-m2[x]</tt>.
871 template<typename M1, typename M2>
872 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
873 return SubMap<M1, M2>(m1,m2);
877 /// Product of two maps
879 /// This \ref concepts::ReadMap "read-only map" returns the product
880 /// of the values of the two given maps.
881 /// Its \c Key and \c Value types are inherited from \c M1.
882 /// The \c Key and \c Value of \c M2 must be convertible to those of
885 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
887 /// MulMap<M1,M2> mm(m1,m2);
889 /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
891 /// The simplest way of using this map is through the mulMap()
894 /// \sa AddMap, SubMap, DivMap
895 /// \sa ScaleMap, ScaleWriteMap
896 template<typename M1, typename M2>
897 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
901 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
902 typedef typename Parent::Key Key;
903 typedef typename Parent::Value Value;
906 MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
908 Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
911 /// Returns a \ref MulMap class
913 /// This function just returns a \ref MulMap class.
915 /// For example, if \c m1 and \c m2 are both maps with \c double
916 /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
917 /// <tt>m1[x]*m2[x]</tt>.
920 template<typename M1, typename M2>
921 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
922 return MulMap<M1, M2>(m1,m2);
926 /// Quotient of two maps
928 /// This \ref concepts::ReadMap "read-only map" returns the quotient
929 /// of the values of the two given maps.
930 /// Its \c Key and \c Value types are inherited from \c M1.
931 /// The \c Key and \c Value of \c M2 must be convertible to those of
934 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
936 /// DivMap<M1,M2> dm(m1,m2);
938 /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
940 /// The simplest way of using this map is through the divMap()
943 /// \sa AddMap, SubMap, MulMap
944 template<typename M1, typename M2>
945 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
949 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
950 typedef typename Parent::Key Key;
951 typedef typename Parent::Value Value;
954 DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
956 Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
959 /// Returns a \ref DivMap class
961 /// This function just returns a \ref DivMap class.
963 /// For example, if \c m1 and \c m2 are both maps with \c double
964 /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
965 /// <tt>m1[x]/m2[x]</tt>.
968 template<typename M1, typename M2>
969 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
970 return DivMap<M1, M2>(m1,m2);
974 /// Shifts a map with a constant.
976 /// This \ref concepts::ReadMap "read-only map" returns the sum of
977 /// the given map and a constant value (i.e. it shifts the map with
978 /// the constant). Its \c Key and \c Value are inherited from \c M.
982 /// ShiftMap<M> sh(m,v);
986 /// ConstMap<M::Key, M::Value> cm(v);
987 /// AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
990 /// The simplest way of using this map is through the shiftMap()
993 /// \sa ShiftWriteMap
994 template<typename M, typename C = typename M::Value>
995 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
999 typedef MapBase<typename M::Key, typename M::Value> Parent;
1000 typedef typename Parent::Key Key;
1001 typedef typename Parent::Value Value;
1006 /// \param m The undelying map.
1007 /// \param v The constant value.
1008 ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
1010 Value operator[](const Key &k) const { return _m[k]+_v; }
1013 /// Shifts a map with a constant (read-write version).
1015 /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
1016 /// of the given map and a constant value (i.e. it shifts the map with
1017 /// the constant). Its \c Key and \c Value are inherited from \c M.
1018 /// It makes also possible to write the map.
1020 /// The simplest way of using this map is through the shiftWriteMap()
1024 template<typename M, typename C = typename M::Value>
1025 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1029 typedef MapBase<typename M::Key, typename M::Value> Parent;
1030 typedef typename Parent::Key Key;
1031 typedef typename Parent::Value Value;
1036 /// \param m The undelying map.
1037 /// \param v The constant value.
1038 ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1040 Value operator[](const Key &k) const { return _m[k]+_v; }
1042 void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
1045 /// Returns a \ref ShiftMap class
1047 /// This function just returns a \ref ShiftMap class.
1049 /// For example, if \c m is a map with \c double values and \c v is
1050 /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
1051 /// <tt>m[x]+v</tt>.
1053 /// \relates ShiftMap
1054 template<typename M, typename C>
1055 inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
1056 return ShiftMap<M, C>(m,v);
1059 /// Returns a \ref ShiftWriteMap class
1061 /// This function just returns a \ref ShiftWriteMap class.
1063 /// For example, if \c m is a map with \c double values and \c v is
1064 /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
1065 /// <tt>m[x]+v</tt>.
1066 /// Moreover it makes also possible to write the map.
1068 /// \relates ShiftWriteMap
1069 template<typename M, typename C>
1070 inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
1071 return ShiftWriteMap<M, C>(m,v);
1075 /// Scales a map with a constant.
1077 /// This \ref concepts::ReadMap "read-only map" returns the value of
1078 /// the given map multiplied from the left side with a constant value.
1079 /// Its \c Key and \c Value are inherited from \c M.
1083 /// ScaleMap<M> sc(m,v);
1085 /// is equivalent to
1087 /// ConstMap<M::Key, M::Value> cm(v);
1088 /// MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
1091 /// The simplest way of using this map is through the scaleMap()
1094 /// \sa ScaleWriteMap
1095 template<typename M, typename C = typename M::Value>
1096 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1100 typedef MapBase<typename M::Key, typename M::Value> Parent;
1101 typedef typename Parent::Key Key;
1102 typedef typename Parent::Value Value;
1107 /// \param m The undelying map.
1108 /// \param v The constant value.
1109 ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
1111 Value operator[](const Key &k) const { return _v*_m[k]; }
1114 /// Scales a map with a constant (read-write version).
1116 /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
1117 /// the given map multiplied from the left side with a constant value.
1118 /// Its \c Key and \c Value are inherited from \c M.
1119 /// It can also be used as write map if the \c / operator is defined
1120 /// between \c Value and \c C and the given multiplier is not zero.
1122 /// The simplest way of using this map is through the scaleWriteMap()
1126 template<typename M, typename C = typename M::Value>
1127 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1131 typedef MapBase<typename M::Key, typename M::Value> Parent;
1132 typedef typename Parent::Key Key;
1133 typedef typename Parent::Value Value;
1138 /// \param m The undelying map.
1139 /// \param v The constant value.
1140 ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1142 Value operator[](const Key &k) const { return _v*_m[k]; }
1144 void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
1147 /// Returns a \ref ScaleMap class
1149 /// This function just returns a \ref ScaleMap class.
1151 /// For example, if \c m is a map with \c double values and \c v is
1152 /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
1153 /// <tt>v*m[x]</tt>.
1155 /// \relates ScaleMap
1156 template<typename M, typename C>
1157 inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
1158 return ScaleMap<M, C>(m,v);
1161 /// Returns a \ref ScaleWriteMap class
1163 /// This function just returns a \ref ScaleWriteMap class.
1165 /// For example, if \c m is a map with \c double values and \c v is
1166 /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
1167 /// <tt>v*m[x]</tt>.
1168 /// Moreover it makes also possible to write the map.
1170 /// \relates ScaleWriteMap
1171 template<typename M, typename C>
1172 inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
1173 return ScaleWriteMap<M, C>(m,v);
1177 /// Negative of a map
1179 /// This \ref concepts::ReadMap "read-only map" returns the negative
1180 /// of the values of the given map (using the unary \c - operator).
1181 /// Its \c Key and \c Value are inherited from \c M.
1183 /// If M::Value is \c int, \c double etc., then
1185 /// NegMap<M> neg(m);
1187 /// is equivalent to
1189 /// ScaleMap<M> neg(m,-1);
1192 /// The simplest way of using this map is through the negMap()
1196 template<typename M>
1197 class NegMap : public MapBase<typename M::Key, typename M::Value> {
1200 typedef MapBase<typename M::Key, typename M::Value> Parent;
1201 typedef typename Parent::Key Key;
1202 typedef typename Parent::Value Value;
1205 NegMap(const M &m) : _m(m) {}
1207 Value operator[](const Key &k) const { return -_m[k]; }
1210 /// Negative of a map (read-write version)
1212 /// This \ref concepts::ReadWriteMap "read-write map" returns the
1213 /// negative of the values of the given map (using the unary \c -
1215 /// Its \c Key and \c Value are inherited from \c M.
1216 /// It makes also possible to write the map.
1218 /// If M::Value is \c int, \c double etc., then
1220 /// NegWriteMap<M> neg(m);
1222 /// is equivalent to
1224 /// ScaleWriteMap<M> neg(m,-1);
1227 /// The simplest way of using this map is through the negWriteMap()
1231 template<typename M>
1232 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1235 typedef MapBase<typename M::Key, typename M::Value> Parent;
1236 typedef typename Parent::Key Key;
1237 typedef typename Parent::Value Value;
1240 NegWriteMap(M &m) : _m(m) {}
1242 Value operator[](const Key &k) const { return -_m[k]; }
1244 void set(const Key &k, const Value &v) { _m.set(k, -v); }
1247 /// Returns a \ref NegMap class
1249 /// This function just returns a \ref NegMap class.
1251 /// For example, if \c m is a map with \c double values, then
1252 /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1255 template <typename M>
1256 inline NegMap<M> negMap(const M &m) {
1257 return NegMap<M>(m);
1260 /// Returns a \ref NegWriteMap class
1262 /// This function just returns a \ref NegWriteMap class.
1264 /// For example, if \c m is a map with \c double values, then
1265 /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1266 /// Moreover it makes also possible to write the map.
1268 /// \relates NegWriteMap
1269 template <typename M>
1270 inline NegWriteMap<M> negWriteMap(M &m) {
1271 return NegWriteMap<M>(m);
1275 /// Absolute value of a map
1277 /// This \ref concepts::ReadMap "read-only map" returns the absolute
1278 /// value of the values of the given map.
1279 /// Its \c Key and \c Value are inherited from \c M.
1280 /// \c Value must be comparable to \c 0 and the unary \c -
1281 /// operator must be defined for it, of course.
1283 /// The simplest way of using this map is through the absMap()
1285 template<typename M>
1286 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1289 typedef MapBase<typename M::Key, typename M::Value> Parent;
1290 typedef typename Parent::Key Key;
1291 typedef typename Parent::Value Value;
1294 AbsMap(const M &m) : _m(m) {}
1296 Value operator[](const Key &k) const {
1298 return tmp >= 0 ? tmp : -tmp;
1303 /// Returns an \ref AbsMap class
1305 /// This function just returns an \ref AbsMap class.
1307 /// For example, if \c m is a map with \c double values, then
1308 /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
1309 /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
1313 template<typename M>
1314 inline AbsMap<M> absMap(const M &m) {
1315 return AbsMap<M>(m);
1320 // Logical maps and map adaptors:
1322 /// \addtogroup maps
1325 /// Constant \c true map.
1327 /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1334 /// is equivalent to
1336 /// ConstMap<K,bool> tm(true);
1341 template <typename K>
1342 class TrueMap : public MapBase<K, bool> {
1344 typedef MapBase<K, bool> Parent;
1345 typedef typename Parent::Key Key;
1346 typedef typename Parent::Value Value;
1348 /// Gives back \c true.
1349 Value operator[](const Key&) const { return true; }
1352 /// Returns a \ref TrueMap class
1354 /// This function just returns a \ref TrueMap class.
1355 /// \relates TrueMap
1356 template<typename K>
1357 inline TrueMap<K> trueMap() {
1358 return TrueMap<K>();
1362 /// Constant \c false map.
1364 /// This \ref concepts::ReadMap "read-only map" assigns \c false to
1371 /// is equivalent to
1373 /// ConstMap<K,bool> fm(false);
1378 template <typename K>
1379 class FalseMap : public MapBase<K, bool> {
1381 typedef MapBase<K, bool> Parent;
1382 typedef typename Parent::Key Key;
1383 typedef typename Parent::Value Value;
1385 /// Gives back \c false.
1386 Value operator[](const Key&) const { return false; }
1389 /// Returns a \ref FalseMap class
1391 /// This function just returns a \ref FalseMap class.
1392 /// \relates FalseMap
1393 template<typename K>
1394 inline FalseMap<K> falseMap() {
1395 return FalseMap<K>();
1400 /// \addtogroup map_adaptors
1403 /// Logical 'and' of two maps
1405 /// This \ref concepts::ReadMap "read-only map" returns the logical
1406 /// 'and' of the values of the two given maps.
1407 /// Its \c Key type is inherited from \c M1 and its \c Value type is
1408 /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1410 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1412 /// AndMap<M1,M2> am(m1,m2);
1414 /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
1416 /// The simplest way of using this map is through the andMap()
1420 /// \sa NotMap, NotWriteMap
1421 template<typename M1, typename M2>
1422 class AndMap : public MapBase<typename M1::Key, bool> {
1426 typedef MapBase<typename M1::Key, bool> Parent;
1427 typedef typename Parent::Key Key;
1428 typedef typename Parent::Value Value;
1431 AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1433 Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
1436 /// Returns an \ref AndMap class
1438 /// This function just returns an \ref AndMap class.
1440 /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1441 /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
1442 /// <tt>m1[x]&&m2[x]</tt>.
1445 template<typename M1, typename M2>
1446 inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
1447 return AndMap<M1, M2>(m1,m2);
1451 /// Logical 'or' of two maps
1453 /// This \ref concepts::ReadMap "read-only map" returns the logical
1454 /// 'or' of the values of the two given maps.
1455 /// Its \c Key type is inherited from \c M1 and its \c Value type is
1456 /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1458 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1460 /// OrMap<M1,M2> om(m1,m2);
1462 /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
1464 /// The simplest way of using this map is through the orMap()
1468 /// \sa NotMap, NotWriteMap
1469 template<typename M1, typename M2>
1470 class OrMap : public MapBase<typename M1::Key, bool> {
1474 typedef MapBase<typename M1::Key, bool> Parent;
1475 typedef typename Parent::Key Key;
1476 typedef typename Parent::Value Value;
1479 OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1481 Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
1484 /// Returns an \ref OrMap class
1486 /// This function just returns an \ref OrMap class.
1488 /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1489 /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
1490 /// <tt>m1[x]||m2[x]</tt>.
1493 template<typename M1, typename M2>
1494 inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
1495 return OrMap<M1, M2>(m1,m2);
1499 /// Logical 'not' of a map
1501 /// This \ref concepts::ReadMap "read-only map" returns the logical
1502 /// negation of the values of the given map.
1503 /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1505 /// The simplest way of using this map is through the notMap()
1509 template <typename M>
1510 class NotMap : public MapBase<typename M::Key, bool> {
1513 typedef MapBase<typename M::Key, bool> Parent;
1514 typedef typename Parent::Key Key;
1515 typedef typename Parent::Value Value;
1518 NotMap(const M &m) : _m(m) {}
1520 Value operator[](const Key &k) const { return !_m[k]; }
1523 /// Logical 'not' of a map (read-write version)
1525 /// This \ref concepts::ReadWriteMap "read-write map" returns the
1526 /// logical negation of the values of the given map.
1527 /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1528 /// It makes also possible to write the map. When a value is set,
1529 /// the opposite value is set to the original map.
1531 /// The simplest way of using this map is through the notWriteMap()
1535 template <typename M>
1536 class NotWriteMap : public MapBase<typename M::Key, bool> {
1539 typedef MapBase<typename M::Key, bool> Parent;
1540 typedef typename Parent::Key Key;
1541 typedef typename Parent::Value Value;
1544 NotWriteMap(M &m) : _m(m) {}
1546 Value operator[](const Key &k) const { return !_m[k]; }
1548 void set(const Key &k, bool v) { _m.set(k, !v); }
1551 /// Returns a \ref NotMap class
1553 /// This function just returns a \ref NotMap class.
1555 /// For example, if \c m is a map with \c bool values, then
1556 /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1559 template <typename M>
1560 inline NotMap<M> notMap(const M &m) {
1561 return NotMap<M>(m);
1564 /// Returns a \ref NotWriteMap class
1566 /// This function just returns a \ref NotWriteMap class.
1568 /// For example, if \c m is a map with \c bool values, then
1569 /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1570 /// Moreover it makes also possible to write the map.
1572 /// \relates NotWriteMap
1573 template <typename M>
1574 inline NotWriteMap<M> notWriteMap(M &m) {
1575 return NotWriteMap<M>(m);
1579 /// Combination of two maps using the \c == operator
1581 /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1582 /// the keys for which the corresponding values of the two maps are
1584 /// Its \c Key type is inherited from \c M1 and its \c Value type is
1585 /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1587 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1589 /// EqualMap<M1,M2> em(m1,m2);
1591 /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
1593 /// The simplest way of using this map is through the equalMap()
1597 template<typename M1, typename M2>
1598 class EqualMap : public MapBase<typename M1::Key, bool> {
1602 typedef MapBase<typename M1::Key, bool> Parent;
1603 typedef typename Parent::Key Key;
1604 typedef typename Parent::Value Value;
1607 EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1609 Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
1612 /// Returns an \ref EqualMap class
1614 /// This function just returns an \ref EqualMap class.
1616 /// For example, if \c m1 and \c m2 are maps with keys and values of
1617 /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
1618 /// <tt>m1[x]==m2[x]</tt>.
1620 /// \relates EqualMap
1621 template<typename M1, typename M2>
1622 inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
1623 return EqualMap<M1, M2>(m1,m2);
1627 /// Combination of two maps using the \c < operator
1629 /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1630 /// the keys for which the corresponding value of the first map is
1631 /// less then the value of the second map.
1632 /// Its \c Key type is inherited from \c M1 and its \c Value type is
1633 /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1635 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1637 /// LessMap<M1,M2> lm(m1,m2);
1639 /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
1641 /// The simplest way of using this map is through the lessMap()
1645 template<typename M1, typename M2>
1646 class LessMap : public MapBase<typename M1::Key, bool> {
1650 typedef MapBase<typename M1::Key, bool> Parent;
1651 typedef typename Parent::Key Key;
1652 typedef typename Parent::Value Value;
1655 LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1657 Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
1660 /// Returns an \ref LessMap class
1662 /// This function just returns an \ref LessMap class.
1664 /// For example, if \c m1 and \c m2 are maps with keys and values of
1665 /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
1666 /// <tt>m1[x]<m2[x]</tt>.
1668 /// \relates LessMap
1669 template<typename M1, typename M2>
1670 inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
1671 return LessMap<M1, M2>(m1,m2);
1674 namespace _maps_bits {
1676 template <typename _Iterator, typename Enable = void>
1677 struct IteratorTraits {
1678 typedef typename std::iterator_traits<_Iterator>::value_type Value;
1681 template <typename _Iterator>
1682 struct IteratorTraits<_Iterator,
1683 typename exists<typename _Iterator::container_type>::type>
1685 typedef typename _Iterator::container_type::value_type Value;
1690 /// \brief Writable bool map for logging each \c true assigned element
1692 /// A \ref concepts::WriteMap "writable" bool map for logging
1693 /// each \c true assigned element, i.e it copies subsequently each
1694 /// keys set to \c true to the given iterator.
1695 /// The most important usage of it is storing certain nodes or arcs
1696 /// that were marked \c true by an algorithm.
1698 /// There are several algorithms that provide solutions through bool
1699 /// maps and most of them assign \c true at most once for each key.
1700 /// In these cases it is a natural request to store each \c true
1701 /// assigned elements (in order of the assignment), which can be
1702 /// easily done with LoggerBoolMap.
1704 /// The simplest way of using this map is through the loggerBoolMap()
1707 /// \tparam It The type of the iterator.
1708 /// \tparam Ke The key type of the map. The default value set
1709 /// according to the iterator type should work in most cases.
1711 /// \note The container of the iterator must contain enough space
1712 /// for the elements or the iterator should be an inserter iterator.
1714 template <typename It, typename Ke>
1716 template <typename It,
1717 typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
1719 class LoggerBoolMap {
1721 typedef It Iterator;
1727 LoggerBoolMap(Iterator it)
1728 : _begin(it), _end(it) {}
1730 /// Gives back the given iterator set for the first key
1731 Iterator begin() const {
1735 /// Gives back the the 'after the last' iterator
1736 Iterator end() const {
1740 /// The set function of the map
1741 void set(const Key& key, Value value) {
1752 /// Returns a \ref LoggerBoolMap class
1754 /// This function just returns a \ref LoggerBoolMap class.
1756 /// The most important usage of it is storing certain nodes or arcs
1757 /// that were marked \c true by an algorithm.
1758 /// For example it makes easier to store the nodes in the processing
1759 /// order of Dfs algorithm, as the following examples show.
1761 /// std::vector<Node> v;
1762 /// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
1765 /// std::vector<Node> v(countNodes(g));
1766 /// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
1769 /// \note The container of the iterator must contain enough space
1770 /// for the elements or the iterator should be an inserter iterator.
1772 /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
1773 /// it cannot be used when a readable map is needed, for example as
1774 /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
1776 /// \relates LoggerBoolMap
1777 template<typename Iterator>
1778 inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
1779 return LoggerBoolMap<Iterator>(it);
1782 /// Provides an immutable and unique id for each item in the graph.
1784 /// The IdMap class provides a unique and immutable id for each item of the
1785 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1786 /// different items (nodes) get different ids <li>\b immutable: the id of an
1787 /// item (node) does not change (even if you delete other nodes). </ul>
1788 /// Through this map you get access (i.e. can read) the inner id values of
1789 /// the items stored in the graph. This map can be inverted with its member
1790 /// class \c InverseMap or with the \c operator() member.
1792 template <typename _Graph, typename _Item>
1795 typedef _Graph Graph;
1800 /// \brief Constructor.
1802 /// Constructor of the map.
1803 explicit IdMap(const Graph& graph) : _graph(&graph) {}
1805 /// \brief Gives back the \e id of the item.
1807 /// Gives back the immutable and unique \e id of the item.
1808 int operator[](const Item& item) const { return _graph->id(item);}
1810 /// \brief Gives back the item by its id.
1812 /// Gives back the item by its id.
1813 Item operator()(int id) { return _graph->fromId(id, Item()); }
1816 const Graph* _graph;
1820 /// \brief The class represents the inverse of its owner (IdMap).
1822 /// The class represents the inverse of its owner (IdMap).
1827 /// \brief Constructor.
1829 /// Constructor for creating an id-to-item map.
1830 explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1832 /// \brief Constructor.
1834 /// Constructor for creating an id-to-item map.
1835 explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1837 /// \brief Gives back the given item from its id.
1839 /// Gives back the given item from its id.
1841 Item operator[](int id) const { return _graph->fromId(id, Item());}
1844 const Graph* _graph;
1847 /// \brief Gives back the inverse of the map.
1849 /// Gives back the inverse of the IdMap.
1850 InverseMap inverse() const { return InverseMap(*_graph);}
1855 /// \brief General invertable graph-map type.
1857 /// This type provides simple invertable graph-maps.
1858 /// The InvertableMap wraps an arbitrary ReadWriteMap
1859 /// and if a key is set to a new value then store it
1860 /// in the inverse map.
1862 /// The values of the map can be accessed
1863 /// with stl compatible forward iterator.
1865 /// \tparam _Graph The graph type.
1866 /// \tparam _Item The item type of the graph.
1867 /// \tparam _Value The value type of the map.
1869 /// \see IterableValueMap
1870 template <typename _Graph, typename _Item, typename _Value>
1872 : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
1875 typedef typename ItemSetTraits<_Graph, _Item>::
1876 template Map<_Value>::Type Map;
1877 typedef _Graph Graph;
1879 typedef std::map<_Value, _Item> Container;
1884 /// The key type of InvertableMap (Node, Arc, Edge).
1885 typedef typename Map::Key Key;
1886 /// The value type of the InvertableMap.
1887 typedef typename Map::Value Value;
1891 /// \brief Constructor.
1893 /// Construct a new InvertableMap for the graph.
1895 explicit InvertableMap(const Graph& graph) : Map(graph) {}
1897 /// \brief Forward iterator for values.
1899 /// This iterator is an stl compatible forward
1900 /// iterator on the values of the map. The values can
1901 /// be accessed in the [beginValue, endValue) range.
1904 : public std::iterator<std::forward_iterator_tag, Value> {
1905 friend class InvertableMap;
1907 ValueIterator(typename Container::const_iterator _it)
1913 ValueIterator& operator++() { ++it; return *this; }
1914 ValueIterator operator++(int) {
1915 ValueIterator tmp(*this);
1920 const Value& operator*() const { return it->first; }
1921 const Value* operator->() const { return &(it->first); }
1923 bool operator==(ValueIterator jt) const { return it == jt.it; }
1924 bool operator!=(ValueIterator jt) const { return it != jt.it; }
1927 typename Container::const_iterator it;
1930 /// \brief Returns an iterator to the first value.
1932 /// Returns an stl compatible iterator to the
1933 /// first value of the map. The values of the
1934 /// map can be accessed in the [beginValue, endValue)
1936 ValueIterator beginValue() const {
1937 return ValueIterator(_inv_map.begin());
1940 /// \brief Returns an iterator after the last value.
1942 /// Returns an stl compatible iterator after the
1943 /// last value of the map. The values of the
1944 /// map can be accessed in the [beginValue, endValue)
1946 ValueIterator endValue() const {
1947 return ValueIterator(_inv_map.end());
1950 /// \brief The setter function of the map.
1952 /// Sets the mapped value.
1953 void set(const Key& key, const Value& val) {
1954 Value oldval = Map::operator[](key);
1955 typename Container::iterator it = _inv_map.find(oldval);
1956 if (it != _inv_map.end() && it->second == key) {
1959 _inv_map.insert(make_pair(val, key));
1963 /// \brief The getter function of the map.
1965 /// It gives back the value associated with the key.
1966 typename MapTraits<Map>::ConstReturnValue
1967 operator[](const Key& key) const {
1968 return Map::operator[](key);
1971 /// \brief Gives back the item by its value.
1973 /// Gives back the item by its value.
1974 Key operator()(const Value& key) const {
1975 typename Container::const_iterator it = _inv_map.find(key);
1976 return it != _inv_map.end() ? it->second : INVALID;
1981 /// \brief Erase the key from the map.
1983 /// Erase the key to the map. It is called by the
1984 /// \c AlterationNotifier.
1985 virtual void erase(const Key& key) {
1986 Value val = Map::operator[](key);
1987 typename Container::iterator it = _inv_map.find(val);
1988 if (it != _inv_map.end() && it->second == key) {
1994 /// \brief Erase more keys from the map.
1996 /// Erase more keys from the map. It is called by the
1997 /// \c AlterationNotifier.
1998 virtual void erase(const std::vector<Key>& keys) {
1999 for (int i = 0; i < int(keys.size()); ++i) {
2000 Value val = Map::operator[](keys[i]);
2001 typename Container::iterator it = _inv_map.find(val);
2002 if (it != _inv_map.end() && it->second == keys[i]) {
2009 /// \brief Clear the keys from the map and inverse map.
2011 /// Clear the keys from the map and inverse map. It is called by the
2012 /// \c AlterationNotifier.
2013 virtual void clear() {
2020 /// \brief The inverse map type.
2022 /// The inverse of this map. The subscript operator of the map
2023 /// gives back always the item what was last assigned to the value.
2026 /// \brief Constructor of the InverseMap.
2028 /// Constructor of the InverseMap.
2029 explicit InverseMap(const InvertableMap& inverted)
2030 : _inverted(inverted) {}
2032 /// The value type of the InverseMap.
2033 typedef typename InvertableMap::Key Value;
2034 /// The key type of the InverseMap.
2035 typedef typename InvertableMap::Value Key;
2037 /// \brief Subscript operator.
2039 /// Subscript operator. It gives back always the item
2040 /// what was last assigned to the value.
2041 Value operator[](const Key& key) const {
2042 return _inverted(key);
2046 const InvertableMap& _inverted;
2049 /// \brief It gives back the just readable inverse map.
2051 /// It gives back the just readable inverse map.
2052 InverseMap inverse() const {
2053 return InverseMap(*this);
2060 /// \brief Provides a mutable, continuous and unique descriptor for each
2061 /// item in the graph.
2063 /// The DescriptorMap class provides a unique and continuous (but mutable)
2064 /// descriptor (id) for each item of the same type (e.g. node) in the
2065 /// graph. This id is <ul><li>\b unique: different items (nodes) get
2066 /// different ids <li>\b continuous: the range of the ids is the set of
2067 /// integers between 0 and \c n-1, where \c n is the number of the items of
2068 /// this type (e.g. nodes) (so the id of a node can change if you delete an
2069 /// other node, i.e. this id is mutable). </ul> This map can be inverted
2070 /// with its member class \c InverseMap, or with the \c operator() member.
2072 /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
2073 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
2075 template <typename _Graph, typename _Item>
2077 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
2080 typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
2083 /// The graph class of DescriptorMap.
2084 typedef _Graph Graph;
2086 /// The key type of DescriptorMap (Node, Arc, Edge).
2087 typedef typename Map::Key Key;
2088 /// The value type of DescriptorMap.
2089 typedef typename Map::Value Value;
2091 /// \brief Constructor.
2093 /// Constructor for descriptor map.
2094 explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
2096 const typename Map::Notifier* nf = Map::notifier();
2097 for (nf->first(it); it != INVALID; nf->next(it)) {
2098 Map::set(it, _inv_map.size());
2099 _inv_map.push_back(it);
2105 /// \brief Add a new key to the map.
2107 /// Add a new key to the map. It is called by the
2108 /// \c AlterationNotifier.
2109 virtual void add(const Item& item) {
2111 Map::set(item, _inv_map.size());
2112 _inv_map.push_back(item);
2115 /// \brief Add more new keys to the map.
2117 /// Add more new keys to the map. It is called by the
2118 /// \c AlterationNotifier.
2119 virtual void add(const std::vector<Item>& items) {
2121 for (int i = 0; i < int(items.size()); ++i) {
2122 Map::set(items[i], _inv_map.size());
2123 _inv_map.push_back(items[i]);
2127 /// \brief Erase the key from the map.
2129 /// Erase the key from the map. It is called by the
2130 /// \c AlterationNotifier.
2131 virtual void erase(const Item& item) {
2132 Map::set(_inv_map.back(), Map::operator[](item));
2133 _inv_map[Map::operator[](item)] = _inv_map.back();
2134 _inv_map.pop_back();
2138 /// \brief Erase more keys from the map.
2140 /// Erase more keys from the map. It is called by the
2141 /// \c AlterationNotifier.
2142 virtual void erase(const std::vector<Item>& items) {
2143 for (int i = 0; i < int(items.size()); ++i) {
2144 Map::set(_inv_map.back(), Map::operator[](items[i]));
2145 _inv_map[Map::operator[](items[i])] = _inv_map.back();
2146 _inv_map.pop_back();
2151 /// \brief Build the unique map.
2153 /// Build the unique map. It is called by the
2154 /// \c AlterationNotifier.
2155 virtual void build() {
2158 const typename Map::Notifier* nf = Map::notifier();
2159 for (nf->first(it); it != INVALID; nf->next(it)) {
2160 Map::set(it, _inv_map.size());
2161 _inv_map.push_back(it);
2165 /// \brief Clear the keys from the map.
2167 /// Clear the keys from the map. It is called by the
2168 /// \c AlterationNotifier.
2169 virtual void clear() {
2176 /// \brief Returns the maximal value plus one.
2178 /// Returns the maximal value plus one in the map.
2179 unsigned int size() const {
2180 return _inv_map.size();
2183 /// \brief Swaps the position of the two items in the map.
2185 /// Swaps the position of the two items in the map.
2186 void swap(const Item& p, const Item& q) {
2187 int pi = Map::operator[](p);
2188 int qi = Map::operator[](q);
2195 /// \brief Gives back the \e descriptor of the item.
2197 /// Gives back the mutable and unique \e descriptor of the map.
2198 int operator[](const Item& item) const {
2199 return Map::operator[](item);
2202 /// \brief Gives back the item by its descriptor.
2204 /// Gives back th item by its descriptor.
2205 Item operator()(int id) const {
2206 return _inv_map[id];
2211 typedef std::vector<Item> Container;
2215 /// \brief The inverse map type of DescriptorMap.
2217 /// The inverse map type of DescriptorMap.
2220 /// \brief Constructor of the InverseMap.
2222 /// Constructor of the InverseMap.
2223 explicit InverseMap(const DescriptorMap& inverted)
2224 : _inverted(inverted) {}
2227 /// The value type of the InverseMap.
2228 typedef typename DescriptorMap::Key Value;
2229 /// The key type of the InverseMap.
2230 typedef typename DescriptorMap::Value Key;
2232 /// \brief Subscript operator.
2234 /// Subscript operator. It gives back the item
2235 /// that the descriptor belongs to currently.
2236 Value operator[](const Key& key) const {
2237 return _inverted(key);
2240 /// \brief Size of the map.
2242 /// Returns the size of the map.
2243 unsigned int size() const {
2244 return _inverted.size();
2248 const DescriptorMap& _inverted;
2251 /// \brief Gives back the inverse of the map.
2253 /// Gives back the inverse of the map.
2254 const InverseMap inverse() const {
2255 return InverseMap(*this);
2259 /// \brief Returns the source of the given arc.
2261 /// The SourceMap gives back the source Node of the given arc.
2263 template <typename Digraph>
2267 typedef typename Digraph::Node Value;
2268 typedef typename Digraph::Arc Key;
2270 /// \brief Constructor
2273 /// \param _digraph The digraph that the map belongs to.
2274 explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
2276 /// \brief The subscript operator.
2278 /// The subscript operator.
2279 /// \param arc The arc
2280 /// \return The source of the arc
2281 Value operator[](const Key& arc) const {
2282 return _digraph.source(arc);
2286 const Digraph& _digraph;
2289 /// \brief Returns a \ref SourceMap class.
2291 /// This function just returns an \ref SourceMap class.
2292 /// \relates SourceMap
2293 template <typename Digraph>
2294 inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
2295 return SourceMap<Digraph>(digraph);
2298 /// \brief Returns the target of the given arc.
2300 /// The TargetMap gives back the target Node of the given arc.
2302 template <typename Digraph>
2306 typedef typename Digraph::Node Value;
2307 typedef typename Digraph::Arc Key;
2309 /// \brief Constructor
2312 /// \param _digraph The digraph that the map belongs to.
2313 explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
2315 /// \brief The subscript operator.
2317 /// The subscript operator.
2318 /// \param e The arc
2319 /// \return The target of the arc
2320 Value operator[](const Key& e) const {
2321 return _digraph.target(e);
2325 const Digraph& _digraph;
2328 /// \brief Returns a \ref TargetMap class.
2330 /// This function just returns a \ref TargetMap class.
2331 /// \relates TargetMap
2332 template <typename Digraph>
2333 inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
2334 return TargetMap<Digraph>(digraph);
2337 /// \brief Returns the "forward" directed arc view of an edge.
2339 /// Returns the "forward" directed arc view of an edge.
2340 /// \see BackwardMap
2341 template <typename Graph>
2345 typedef typename Graph::Arc Value;
2346 typedef typename Graph::Edge Key;
2348 /// \brief Constructor
2351 /// \param _graph The graph that the map belongs to.
2352 explicit ForwardMap(const Graph& graph) : _graph(graph) {}
2354 /// \brief The subscript operator.
2356 /// The subscript operator.
2357 /// \param key An edge
2358 /// \return The "forward" directed arc view of edge
2359 Value operator[](const Key& key) const {
2360 return _graph.direct(key, true);
2364 const Graph& _graph;
2367 /// \brief Returns a \ref ForwardMap class.
2369 /// This function just returns an \ref ForwardMap class.
2370 /// \relates ForwardMap
2371 template <typename Graph>
2372 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
2373 return ForwardMap<Graph>(graph);
2376 /// \brief Returns the "backward" directed arc view of an edge.
2378 /// Returns the "backward" directed arc view of an edge.
2380 template <typename Graph>
2384 typedef typename Graph::Arc Value;
2385 typedef typename Graph::Edge Key;
2387 /// \brief Constructor
2390 /// \param _graph The graph that the map belongs to.
2391 explicit BackwardMap(const Graph& graph) : _graph(graph) {}
2393 /// \brief The subscript operator.
2395 /// The subscript operator.
2396 /// \param key An edge
2397 /// \return The "backward" directed arc view of edge
2398 Value operator[](const Key& key) const {
2399 return _graph.direct(key, false);
2403 const Graph& _graph;
2406 /// \brief Returns a \ref BackwardMap class
2408 /// This function just returns a \ref BackwardMap class.
2409 /// \relates BackwardMap
2410 template <typename Graph>
2411 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2412 return BackwardMap<Graph>(graph);
2415 /// \brief Potential difference map
2417 /// If there is an potential map on the nodes then we
2418 /// can get an arc map as we get the substraction of the
2419 /// values of the target and source.
2420 template <typename Digraph, typename NodeMap>
2421 class PotentialDifferenceMap {
2423 typedef typename Digraph::Arc Key;
2424 typedef typename NodeMap::Value Value;
2426 /// \brief Constructor
2428 /// Contructor of the map
2429 explicit PotentialDifferenceMap(const Digraph& digraph,
2430 const NodeMap& potential)
2431 : _digraph(digraph), _potential(potential) {}
2433 /// \brief Const subscription operator
2435 /// Const subscription operator
2436 Value operator[](const Key& arc) const {
2437 return _potential[_digraph.target(arc)] -
2438 _potential[_digraph.source(arc)];
2442 const Digraph& _digraph;
2443 const NodeMap& _potential;
2446 /// \brief Returns a PotentialDifferenceMap.
2448 /// This function just returns a PotentialDifferenceMap.
2449 /// \relates PotentialDifferenceMap
2450 template <typename Digraph, typename NodeMap>
2451 PotentialDifferenceMap<Digraph, NodeMap>
2452 potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
2453 return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
2456 /// \brief Map of the node in-degrees.
2458 /// This map returns the in-degree of a node. Once it is constructed,
2459 /// the degrees are stored in a standard NodeMap, so each query is done
2460 /// in constant time. On the other hand, the values are updated automatically
2461 /// whenever the digraph changes.
2463 /// \warning Besides addNode() and addArc(), a digraph structure may provide
2464 /// alternative ways to modify the digraph. The correct behavior of InDegMap
2465 /// is not guarantied if these additional features are used. For example
2466 /// the functions \ref ListDigraph::changeSource() "changeSource()",
2467 /// \ref ListDigraph::changeTarget() "changeTarget()" and
2468 /// \ref ListDigraph::reverseArc() "reverseArc()"
2469 /// of \ref ListDigraph will \e not update the degree values correctly.
2473 template <typename _Digraph>
2475 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2476 ::ItemNotifier::ObserverBase {
2480 typedef _Digraph Digraph;
2482 typedef typename Digraph::Node Key;
2484 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2485 ::ItemNotifier::ObserverBase Parent;
2490 : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2493 typedef typename ItemSetTraits<Digraph, Key>::
2494 template Map<int>::Type Parent;
2496 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2498 virtual void add(const Key& key) {
2500 Parent::set(key, 0);
2503 virtual void add(const std::vector<Key>& keys) {
2505 for (int i = 0; i < int(keys.size()); ++i) {
2506 Parent::set(keys[i], 0);
2510 virtual void build() {
2513 typename Parent::Notifier* nf = Parent::notifier();
2514 for (nf->first(it); it != INVALID; nf->next(it)) {
2522 /// \brief Constructor.
2524 /// Constructor for creating in-degree map.
2525 explicit InDegMap(const Digraph& digraph)
2526 : _digraph(digraph), _deg(digraph) {
2527 Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2529 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2530 _deg[it] = countInArcs(_digraph, it);
2534 /// Gives back the in-degree of a Node.
2535 int operator[](const Key& key) const {
2541 typedef typename Digraph::Arc Arc;
2543 virtual void add(const Arc& arc) {
2544 ++_deg[_digraph.target(arc)];
2547 virtual void add(const std::vector<Arc>& arcs) {
2548 for (int i = 0; i < int(arcs.size()); ++i) {
2549 ++_deg[_digraph.target(arcs[i])];
2553 virtual void erase(const Arc& arc) {
2554 --_deg[_digraph.target(arc)];
2557 virtual void erase(const std::vector<Arc>& arcs) {
2558 for (int i = 0; i < int(arcs.size()); ++i) {
2559 --_deg[_digraph.target(arcs[i])];
2563 virtual void build() {
2564 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2565 _deg[it] = countInArcs(_digraph, it);
2569 virtual void clear() {
2570 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2576 const Digraph& _digraph;
2580 /// \brief Map of the node out-degrees.
2582 /// This map returns the out-degree of a node. Once it is constructed,
2583 /// the degrees are stored in a standard NodeMap, so each query is done
2584 /// in constant time. On the other hand, the values are updated automatically
2585 /// whenever the digraph changes.
2587 /// \warning Besides addNode() and addArc(), a digraph structure may provide
2588 /// alternative ways to modify the digraph. The correct behavior of OutDegMap
2589 /// is not guarantied if these additional features are used. For example
2590 /// the functions \ref ListDigraph::changeSource() "changeSource()",
2591 /// \ref ListDigraph::changeTarget() "changeTarget()" and
2592 /// \ref ListDigraph::reverseArc() "reverseArc()"
2593 /// of \ref ListDigraph will \e not update the degree values correctly.
2597 template <typename _Digraph>
2599 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2600 ::ItemNotifier::ObserverBase {
2604 typedef _Digraph Digraph;
2606 typedef typename Digraph::Node Key;
2608 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2609 ::ItemNotifier::ObserverBase Parent;
2614 : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2617 typedef typename ItemSetTraits<Digraph, Key>::
2618 template Map<int>::Type Parent;
2620 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2622 virtual void add(const Key& key) {
2624 Parent::set(key, 0);
2626 virtual void add(const std::vector<Key>& keys) {
2628 for (int i = 0; i < int(keys.size()); ++i) {
2629 Parent::set(keys[i], 0);
2632 virtual void build() {
2635 typename Parent::Notifier* nf = Parent::notifier();
2636 for (nf->first(it); it != INVALID; nf->next(it)) {
2644 /// \brief Constructor.
2646 /// Constructor for creating out-degree map.
2647 explicit OutDegMap(const Digraph& digraph)
2648 : _digraph(digraph), _deg(digraph) {
2649 Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2651 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2652 _deg[it] = countOutArcs(_digraph, it);
2656 /// Gives back the out-degree of a Node.
2657 int operator[](const Key& key) const {
2663 typedef typename Digraph::Arc Arc;
2665 virtual void add(const Arc& arc) {
2666 ++_deg[_digraph.source(arc)];
2669 virtual void add(const std::vector<Arc>& arcs) {
2670 for (int i = 0; i < int(arcs.size()); ++i) {
2671 ++_deg[_digraph.source(arcs[i])];
2675 virtual void erase(const Arc& arc) {
2676 --_deg[_digraph.source(arc)];
2679 virtual void erase(const std::vector<Arc>& arcs) {
2680 for (int i = 0; i < int(arcs.size()); ++i) {
2681 --_deg[_digraph.source(arcs[i])];
2685 virtual void build() {
2686 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2687 _deg[it] = countOutArcs(_digraph, it);
2691 virtual void clear() {
2692 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2698 const Digraph& _digraph;
2705 #endif // LEMON_MAPS_H