Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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/bits/utility.h>
27 #include <lemon/bits/traits.h>
31 ///\brief Miscellaneous property maps
40 /// Base class of maps.
42 /// Base class of maps.
43 /// It provides the necessary <tt>typedef</tt>s required by the map concept.
44 template<typename K, typename T>
53 /// Null map. (a.k.a. DoNothingMap)
55 /// If you have to provide a map only for its type definitions,
56 /// or if you have to provide a writable map, but
57 /// data written to it will sent to <tt>/dev/null</tt>...
58 template<typename K, typename T>
59 class NullMap : public MapBase<K, T> {
61 typedef MapBase<K, T> Parent;
62 typedef typename Parent::Key Key;
63 typedef typename Parent::Value Value;
65 /// Gives back a default constructed element.
66 T operator[](const K&) const { return T(); }
67 /// Absorbs the value.
68 void set(const K&, const T&) {}
71 template <typename K, typename V>
72 NullMap<K, V> nullMap() {
73 return NullMap<K, V>();
79 /// This is a readable map which assigns a specified value to each key.
80 /// In other aspects it is equivalent to the \c NullMap.
81 template<typename K, typename T>
82 class ConstMap : public MapBase<K, T> {
87 typedef MapBase<K, T> Parent;
88 typedef typename Parent::Key Key;
89 typedef typename Parent::Value Value;
91 /// Default constructor
93 /// The value of the map will be uninitialized.
94 /// (More exactly it will be default constructed.)
98 /// \param _v The initial value of the map.
100 ConstMap(const T &_v) : v(_v) {}
103 T operator[](const K&) const { return v; }
106 void setAll(const T &t) {
110 template<typename T1>
112 typedef ConstMap<K, T1> other;
115 template<typename T1>
116 ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
119 ///Returns a \c ConstMap class
121 ///This function just returns a \c ConstMap class.
123 template<typename K, typename V>
124 inline ConstMap<K, V> constMap(const V &v) {
125 return ConstMap<K, V>(v);
129 template<typename T, T v>
132 /// Constant map with inlined constant value.
134 /// This is a readable map which assigns a specified value to each key.
135 /// In other aspects it is equivalent to the \c NullMap.
136 template<typename K, typename V, V v>
137 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
139 typedef MapBase<K, V> Parent;
140 typedef typename Parent::Key Key;
141 typedef typename Parent::Value Value;
145 V operator[](const K&) const { return v; }
147 void set(const K&, const V&) { }
150 ///Returns a \c ConstMap class
152 ///This function just returns a \c ConstMap class with inlined value.
154 template<typename K, typename V, V v>
155 inline ConstMap<K, Const<V, v> > constMap() {
156 return ConstMap<K, Const<V, v> >();
159 ///Map based on std::map
161 ///This is essentially a wrapper for \c std::map. With addition that
162 ///you can specify a default value different from \c Value() .
163 template <typename K, typename T, typename Compare = std::less<K> >
165 template <typename K1, typename T1, typename C1>
169 typedef True ReferenceMapTag;
175 typedef T& Reference;
177 typedef const T& ConstReference;
181 typedef std::map<K, T, Compare> Map;
187 /// Constructor with specified default value
188 StdMap(const T& value = T()) : _value(value) {}
189 /// \brief Constructs the map from an appropriate std::map, and explicitly
190 /// specifies a default value.
191 template <typename T1, typename Comp1>
192 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
193 : _map(map.begin(), map.end()), _value(value) {}
195 /// \brief Constructs a map from an other StdMap.
196 template<typename T1, typename Comp1>
197 StdMap(const StdMap<Key, T1, Comp1> &c)
198 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
202 StdMap& operator=(const StdMap&);
207 Reference operator[](const Key &k) {
208 typename Map::iterator it = _map.lower_bound(k);
209 if (it != _map.end() && !_map.key_comp()(k, it->first))
212 return _map.insert(it, std::make_pair(k, _value))->second;
216 ConstReference operator[](const Key &k) const {
217 typename Map::const_iterator it = _map.find(k);
218 if (it != _map.end())
225 void set(const Key &k, const T &t) {
226 typename Map::iterator it = _map.lower_bound(k);
227 if (it != _map.end() && !_map.key_comp()(k, it->first))
230 _map.insert(it, std::make_pair(k, t));
234 void setAll(const T &t) {
239 template <typename T1, typename C1 = std::less<T1> >
241 typedef StdMap<Key, T1, C1> other;
245 /// \brief Map for storing values for the range \c [0..size-1] range keys
247 /// The current map has the \c [0..size-1] keyset and the values
248 /// are stored in a \c std::vector<T> container. It can be used with
249 /// some data structures, for example \c UnionFind, \c BinHeap, when
250 /// the used items are small integer numbers.
251 template <typename T>
254 template <typename T1>
255 friend class IntegerMap;
259 typedef True ReferenceMapTag;
265 typedef T& Reference;
267 typedef const T& ConstReference;
271 typedef std::vector<T> Vector;
276 /// Constructor with specified default value
277 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
279 /// \brief Constructs the map from an appropriate std::vector.
280 template <typename T1>
281 IntegerMap(const std::vector<T1>& vector)
282 : _vector(vector.begin(), vector.end()) {}
284 /// \brief Constructs a map from an other IntegerMap.
285 template <typename T1>
286 IntegerMap(const IntegerMap<T1> &c)
287 : _vector(c._vector.begin(), c._vector.end()) {}
289 /// \brief Resize the container
290 void resize(int size, const T& value = T()) {
291 _vector.resize(size, value);
296 IntegerMap& operator=(const IntegerMap&);
301 Reference operator[](Key k) {
306 ConstReference operator[](Key k) const {
311 void set(const Key &k, const T& t) {
319 /// \addtogroup map_adaptors
322 /// \brief Identity mapping.
324 /// This mapping gives back the given key as value without any
326 template <typename T>
327 class IdentityMap : public MapBase<T, T> {
329 typedef MapBase<T, T> Parent;
330 typedef typename Parent::Key Key;
331 typedef typename Parent::Value Value;
334 const T& operator[](const T& t) const {
339 ///Returns an \c IdentityMap class
341 ///This function just returns an \c IdentityMap class.
342 ///\relates IdentityMap
344 inline IdentityMap<T> identityMap() {
345 return IdentityMap<T>();
349 ///Convert the \c Value of a map to another type.
351 ///This \c concepts::ReadMap "read only map"
352 ///converts the \c Value of a maps to type \c T.
353 ///Its \c Key is inherited from \c M.
354 template <typename M, typename T>
355 class ConvertMap : public MapBase<typename M::Key, T> {
358 typedef MapBase<typename M::Key, T> Parent;
359 typedef typename Parent::Key Key;
360 typedef typename Parent::Value Value;
365 ///\param _m is the underlying map
366 ConvertMap(const M &_m) : m(_m) {};
368 /// \brief The subscript operator.
370 /// The subscript operator.
372 /// \return The target of the edge
373 Value operator[](const Key& k) const {return m[k];}
376 ///Returns an \c ConvertMap class
378 ///This function just returns an \c ConvertMap class.
379 ///\relates ConvertMap
380 template<typename T, typename M>
381 inline ConvertMap<M, T> convertMap(const M &m) {
382 return ConvertMap<M, T>(m);
385 ///Simple wrapping of the map
387 ///This \c concepts::ReadMap "read only map" returns the simple
388 ///wrapping of the given map. Sometimes the reference maps cannot be
389 ///combined with simple read maps. This map adaptor wraps the given
390 ///map to simple read map.
392 class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
396 typedef MapBase<typename M::Key, typename M::Value> Parent;
397 typedef typename Parent::Key Key;
398 typedef typename Parent::Value Value;
401 SimpleMap(const M &_m) : m(_m) {};
403 Value operator[](Key k) const {return m[k];}
406 ///Simple writeable wrapping of the map
408 ///This \c concepts::ReadMap "read only map" returns the simple
409 ///wrapping of the given map. Sometimes the reference maps cannot be
410 ///combined with simple read-write maps. This map adaptor wraps the
411 ///given map to simple read-write map.
413 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
417 typedef MapBase<typename M::Key, typename M::Value> Parent;
418 typedef typename Parent::Key Key;
419 typedef typename Parent::Value Value;
422 SimpleWriteMap(M &_m) : m(_m) {};
424 Value operator[](Key k) const {return m[k];}
426 void set(Key k, const Value& c) { m.set(k, c); }
431 ///This \c concepts::ReadMap "read only map" returns the sum of the two
432 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
433 ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
435 template<typename M1, typename M2>
436 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
441 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
442 typedef typename Parent::Key Key;
443 typedef typename Parent::Value Value;
446 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
448 Value operator[](Key k) const {return m1[k]+m2[k];}
451 ///Returns an \c AddMap class
453 ///This function just returns an \c AddMap class.
454 ///\todo How to call these type of functions?
457 template<typename M1, typename M2>
458 inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
459 return AddMap<M1, M2>(m1,m2);
462 ///Shift a map with a constant.
464 ///This \c concepts::ReadMap "read only map" returns the sum of the
465 ///given map and a constant value.
466 ///Its \c Key and \c Value is inherited from \c M.
470 /// ShiftMap<X> sh(x,v);
472 ///is equivalent with
474 /// ConstMap<X::Key, X::Value> c_tmp(v);
475 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
477 template<typename M, typename C = typename M::Value>
478 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
482 typedef MapBase<typename M::Key, typename M::Value> Parent;
483 typedef typename Parent::Key Key;
484 typedef typename Parent::Value Value;
489 ///\param _m is the undelying map
490 ///\param _v is the shift value
491 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
493 Value operator[](Key k) const {return m[k] + v;}
496 ///Shift a map with a constant.
498 ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
499 ///given map and a constant value. It makes also possible to write the map.
500 ///Its \c Key and \c Value is inherited from \c M.
504 /// ShiftMap<X> sh(x,v);
506 ///is equivalent with
508 /// ConstMap<X::Key, X::Value> c_tmp(v);
509 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
511 template<typename M, typename C = typename M::Value>
512 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
516 typedef MapBase<typename M::Key, typename M::Value> Parent;
517 typedef typename Parent::Key Key;
518 typedef typename Parent::Value Value;
523 ///\param _m is the undelying map
524 ///\param _v is the shift value
525 ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
527 Value operator[](Key k) const {return m[k] + v;}
529 void set(Key k, const Value& c) { m.set(k, c - v); }
532 ///Returns an \c ShiftMap class
534 ///This function just returns an \c ShiftMap class.
536 template<typename M, typename C>
537 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
538 return ShiftMap<M, C>(m,v);
541 template<typename M, typename C>
542 inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
543 return ShiftWriteMap<M, C>(m,v);
546 ///Difference of two maps
548 ///This \c concepts::ReadMap "read only map" returns the difference
549 ///of the values of the two
550 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
551 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
553 template<typename M1, typename M2>
554 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
558 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
559 typedef typename Parent::Key Key;
560 typedef typename Parent::Value Value;
563 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
565 Value operator[](Key k) const {return m1[k]-m2[k];}
568 ///Returns a \c SubMap class
570 ///This function just returns a \c SubMap class.
573 template<typename M1, typename M2>
574 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
575 return SubMap<M1, M2>(m1, m2);
578 ///Product of two maps
580 ///This \c concepts::ReadMap "read only map" returns the product of the
583 ///maps. Its \c Key and \c Value will be inherited from \c M1.
584 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
586 template<typename M1, typename M2>
587 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
591 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
592 typedef typename Parent::Key Key;
593 typedef typename Parent::Value Value;
596 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
598 Value operator[](Key k) const {return m1[k]*m2[k];}
601 ///Returns a \c MulMap class
603 ///This function just returns a \c MulMap class.
605 template<typename M1, typename M2>
606 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
607 return MulMap<M1, M2>(m1,m2);
610 ///Scales a maps with a constant.
612 ///This \c concepts::ReadMap "read only map" returns the value of the
613 ///given map multiplied from the left side with a constant value.
614 ///Its \c Key and \c Value is inherited from \c M.
618 /// ScaleMap<X> sc(x,v);
620 ///is equivalent with
622 /// ConstMap<X::Key, X::Value> c_tmp(v);
623 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
625 template<typename M, typename C = typename M::Value>
626 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
630 typedef MapBase<typename M::Key, typename M::Value> Parent;
631 typedef typename Parent::Key Key;
632 typedef typename Parent::Value Value;
637 ///\param _m is the undelying map
638 ///\param _v is the scaling value
639 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
641 Value operator[](Key k) const {return v * m[k];}
644 ///Scales a maps with a constant.
646 ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
647 ///given map multiplied from the left side with a constant value. It can
648 ///be used as write map also if the given multiplier is not zero.
649 ///Its \c Key and \c Value is inherited from \c M.
650 template<typename M, typename C = typename M::Value>
651 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
655 typedef MapBase<typename M::Key, typename M::Value> Parent;
656 typedef typename Parent::Key Key;
657 typedef typename Parent::Value Value;
662 ///\param _m is the undelying map
663 ///\param _v is the scaling value
664 ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
666 Value operator[](Key k) const {return v * m[k];}
668 void set(Key k, const Value& c) { m.set(k, c / v);}
671 ///Returns an \c ScaleMap class
673 ///This function just returns an \c ScaleMap class.
675 template<typename M, typename C>
676 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
677 return ScaleMap<M, C>(m,v);
680 template<typename M, typename C>
681 inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
682 return ScaleWriteMap<M, C>(m,v);
685 ///Quotient of two maps
687 ///This \c concepts::ReadMap "read only map" returns the quotient of the
689 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
690 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
692 template<typename M1, typename M2>
693 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
697 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
698 typedef typename Parent::Key Key;
699 typedef typename Parent::Value Value;
702 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
704 Value operator[](Key k) const {return m1[k]/m2[k];}
707 ///Returns a \c DivMap class
709 ///This function just returns a \c DivMap class.
711 template<typename M1, typename M2>
712 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
713 return DivMap<M1, M2>(m1,m2);
716 ///Composition of two maps
718 ///This \c concepts::ReadMap "read only map" returns the composition of
720 ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
724 /// ComposeMap<M1, M2> cm(m1,m2);
726 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
728 ///Its \c Key is inherited from \c M2 and its \c Value is from
730 ///The \c M2::Value must be convertible to \c M1::Key.
731 ///\todo Check the requirements.
732 template <typename M1, typename M2>
733 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
737 typedef MapBase<typename M2::Key, typename M1::Value> Parent;
738 typedef typename Parent::Key Key;
739 typedef typename Parent::Value Value;
742 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
744 typename MapTraits<M1>::ConstReturnValue
746 operator[](Key k) const {return m1[m2[k]];}
748 ///Returns a \c ComposeMap class
750 ///This function just returns a \c ComposeMap class.
752 ///\relates ComposeMap
753 template <typename M1, typename M2>
754 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
755 return ComposeMap<M1, M2>(m1,m2);
758 ///Combines of two maps using an STL (binary) functor.
760 ///Combines of two maps using an STL (binary) functor.
763 ///This \c concepts::ReadMap "read only map" takes two maps and a
764 ///binary functor and returns the composition of
766 ///given maps unsing the functor.
767 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
768 ///and \c f is of \c F,
771 /// CombineMap<M1, M2,F,V> cm(m1,m2,f);
773 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
775 ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
776 ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
777 ///input parameter of \c F and the return type of \c F must be convertible
779 ///\todo Check the requirements.
780 template<typename M1, typename M2, typename F,
781 typename V = typename F::result_type>
782 class CombineMap : public MapBase<typename M1::Key, V> {
787 typedef MapBase<typename M1::Key, V> Parent;
788 typedef typename Parent::Key Key;
789 typedef typename Parent::Value Value;
792 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
793 : m1(_m1), m2(_m2), f(_f) {};
795 Value operator[](Key k) const {return f(m1[k],m2[k]);}
798 ///Returns a \c CombineMap class
800 ///This function just returns a \c CombineMap class.
802 ///For example if \c m1 and \c m2 are both \c double valued maps, then
804 ///combineMap<double>(m1,m2,std::plus<double>())
806 ///is equivalent with
811 ///This function is specialized for adaptable binary function
812 ///classes and c++ functions.
814 ///\relates CombineMap
815 template<typename M1, typename M2, typename F, typename V>
816 inline CombineMap<M1, M2, F, V>
817 combineMap(const M1& m1,const M2& m2, const F& f) {
818 return CombineMap<M1, M2, F, V>(m1,m2,f);
821 template<typename M1, typename M2, typename F>
822 inline CombineMap<M1, M2, F, typename F::result_type>
823 combineMap(const M1& m1, const M2& m2, const F& f) {
824 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
827 template<typename M1, typename M2, typename K1, typename K2, typename V>
828 inline CombineMap<M1, M2, V (*)(K1, K2), V>
829 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
830 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
833 ///Negative value of a map
835 ///This \c concepts::ReadMap "read only map" returns the negative
837 ///value returned by the
838 ///given map. Its \c Key and \c Value will be inherited from \c M.
839 ///The unary \c - operator must be defined for \c Value, of course.
842 class NegMap : public MapBase<typename M::Key, typename M::Value> {
845 typedef MapBase<typename M::Key, typename M::Value> Parent;
846 typedef typename Parent::Key Key;
847 typedef typename Parent::Value Value;
850 NegMap(const M &_m) : m(_m) {};
852 Value operator[](Key k) const {return -m[k];}
855 ///Negative value of a map
857 ///This \c concepts::ReadWriteMap "read-write map" returns the negative
858 ///value of the value returned by the
859 ///given map. Its \c Key and \c Value will be inherited from \c M.
860 ///The unary \c - operator must be defined for \c Value, of course.
863 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
866 typedef MapBase<typename M::Key, typename M::Value> Parent;
867 typedef typename Parent::Key Key;
868 typedef typename Parent::Value Value;
871 NegWriteMap(M &_m) : m(_m) {};
873 Value operator[](Key k) const {return -m[k];}
875 void set(Key k, const Value& v) { m.set(k, -v); }
878 ///Returns a \c NegMap class
880 ///This function just returns a \c NegMap class.
882 template <typename M>
883 inline NegMap<M> negMap(const M &m) {
887 template <typename M>
888 inline NegWriteMap<M> negMap(M &m) {
889 return NegWriteMap<M>(m);
892 ///Absolute value of a map
894 ///This \c concepts::ReadMap "read only map" returns the absolute value
896 ///value returned by the
897 ///given map. Its \c Key and \c Value will be inherited
898 ///from <tt>M</tt>. <tt>Value</tt>
899 ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
900 ///operator must be defined for it, of course.
902 ///\bug We need a unified way to handle the situation below:
904 /// struct _UnConvertible {};
905 /// template<class A> inline A t_abs(A a) {return _UnConvertible();}
906 /// template<> inline int t_abs<>(int n) {return abs(n);}
907 /// template<> inline long int t_abs<>(long int n) {return labs(n);}
908 /// template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
909 /// template<> inline float t_abs<>(float n) {return fabsf(n);}
910 /// template<> inline double t_abs<>(double n) {return fabs(n);}
911 /// template<> inline long double t_abs<>(long double n) {return fabsl(n);}
916 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
919 typedef MapBase<typename M::Key, typename M::Value> Parent;
920 typedef typename Parent::Key Key;
921 typedef typename Parent::Value Value;
924 AbsMap(const M &_m) : m(_m) {};
926 Value operator[](Key k) const {
928 return tmp >= 0 ? tmp : -tmp;
933 ///Returns a \c AbsMap class
935 ///This function just returns a \c AbsMap class.
938 inline AbsMap<M> absMap(const M &m) {
942 ///Converts an STL style functor to a map
944 ///This \c concepts::ReadMap "read only map" returns the value
948 ///Template parameters \c K and \c V will become its
949 ///\c Key and \c Value. They must be given explicitely
950 ///because a functor does not provide such typedefs.
952 ///Parameter \c F is the type of the used functor.
954 typename K = typename F::argument_type,
955 typename V = typename F::result_type>
956 class FunctorMap : public MapBase<K, V> {
959 typedef MapBase<K, V> Parent;
960 typedef typename Parent::Key Key;
961 typedef typename Parent::Value Value;
964 FunctorMap(const F &_f = F()) : f(_f) {}
966 Value operator[](Key k) const { return f(k);}
969 ///Returns a \c FunctorMap class
971 ///This function just returns a \c FunctorMap class.
973 ///It is specialized for adaptable function classes and
975 ///\relates FunctorMap
976 template<typename K, typename V, typename F> inline
977 FunctorMap<F, K, V> functorMap(const F &f) {
978 return FunctorMap<F, K, V>(f);
981 template <typename F> inline
982 FunctorMap<F, typename F::argument_type, typename F::result_type>
983 functorMap(const F &f) {
984 return FunctorMap<F, typename F::argument_type,
985 typename F::result_type>(f);
988 template <typename K, typename V> inline
989 FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
990 return FunctorMap<V (*)(K), K, V>(f);
994 ///Converts a map to an STL style (unary) functor
996 ///This class Converts a map to an STL style (unary) functor.
997 ///that is it provides an <tt>operator()</tt> to read its values.
999 ///For the sake of convenience it also works as
1000 ///a ususal \c concepts::ReadMap "readable map",
1001 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1002 template <typename M>
1003 class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
1006 typedef MapBase<typename M::Key, typename M::Value> Parent;
1007 typedef typename Parent::Key Key;
1008 typedef typename Parent::Value Value;
1010 typedef typename M::Key argument_type;
1011 typedef typename M::Value result_type;
1014 MapFunctor(const M &_m) : m(_m) {};
1016 Value operator()(Key k) const {return m[k];}
1018 Value operator[](Key k) const {return m[k];}
1021 ///Returns a \c MapFunctor class
1023 ///This function just returns a \c MapFunctor class.
1024 ///\relates MapFunctor
1025 template<typename M>
1026 inline MapFunctor<M> mapFunctor(const M &m) {
1027 return MapFunctor<M>(m);
1030 ///Applies all map setting operations to two maps
1032 ///This map has two \c concepts::ReadMap "readable map"
1033 ///parameters and each read request will be passed just to the
1034 ///first map. This class is the just readable map type of the ForkWriteMap.
1036 ///The \c Key and \c Value will be inherited from \c M1.
1037 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1038 template<typename M1, typename M2>
1039 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1043 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1044 typedef typename Parent::Key Key;
1045 typedef typename Parent::Value Value;
1048 ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
1050 Value operator[](Key k) const {return m1[k];}
1054 ///Applies all map setting operations to two maps
1056 ///This map has two \c concepts::WriteMap "writable map"
1057 ///parameters and each write request will be passed to both of them.
1058 ///If \c M1 is also \c concepts::ReadMap "readable",
1059 ///then the read operations will return the
1060 ///corresponding values of \c M1.
1062 ///The \c Key and \c Value will be inherited from \c M1.
1063 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1064 template<typename M1, typename M2>
1065 class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
1069 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1070 typedef typename Parent::Key Key;
1071 typedef typename Parent::Value Value;
1074 ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
1076 Value operator[](Key k) const {return m1[k];}
1078 void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
1081 ///Returns an \c ForkMap class
1083 ///This function just returns an \c ForkMap class.
1086 template <typename M1, typename M2>
1087 inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
1088 return ForkMap<M1, M2>(m1,m2);
1091 template <typename M1, typename M2>
1092 inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
1093 return ForkWriteMap<M1, M2>(m1,m2);
1098 /* ************* BOOL MAPS ******************* */
1100 ///Logical 'not' of a map
1102 ///This bool \c concepts::ReadMap "read only map" returns the
1103 ///logical negation of
1104 ///value returned by the
1105 ///given map. Its \c Key and will be inherited from \c M,
1106 ///its Value is <tt>bool</tt>.
1107 template <typename M>
1108 class NotMap : public MapBase<typename M::Key, bool> {
1111 typedef MapBase<typename M::Key, bool> Parent;
1112 typedef typename Parent::Key Key;
1113 typedef typename Parent::Value Value;
1116 NotMap(const M &_m) : m(_m) {};
1118 Value operator[](Key k) const {return !m[k];}
1121 ///Logical 'not' of a map with writing possibility
1123 ///This bool \c concepts::ReadWriteMap "read-write map" returns the
1124 ///logical negation of value returned by the given map. When it is set,
1125 ///the opposite value is set to the original map.
1126 ///Its \c Key and will be inherited from \c M,
1127 ///its Value is <tt>bool</tt>.
1128 template <typename M>
1129 class NotWriteMap : public MapBase<typename M::Key, bool> {
1132 typedef MapBase<typename M::Key, bool> Parent;
1133 typedef typename Parent::Key Key;
1134 typedef typename Parent::Value Value;
1137 NotWriteMap(M &_m) : m(_m) {};
1139 Value operator[](Key k) const {return !m[k];}
1141 void set(Key k, bool v) { m.set(k, !v); }
1144 ///Returns a \c NotMap class
1146 ///This function just returns a \c NotMap class.
1148 template <typename M>
1149 inline NotMap<M> notMap(const M &m) {
1150 return NotMap<M>(m);
1153 template <typename M>
1154 inline NotWriteMap<M> notMap(M &m) {
1155 return NotWriteMap<M>(m);
1158 namespace _maps_bits {
1160 template <typename Value>
1162 typedef Value argument_type;
1163 typedef Value result_type;
1164 Value operator()(const Value& val) const {
1169 template <typename _Iterator, typename Enable = void>
1170 struct IteratorTraits {
1171 typedef typename std::iterator_traits<_Iterator>::value_type Value;
1174 template <typename _Iterator>
1175 struct IteratorTraits<_Iterator,
1176 typename exists<typename _Iterator::container_type>::type>
1178 typedef typename _Iterator::container_type::value_type Value;
1184 /// \brief Writable bool map for store each true assigned elements.
1186 /// Writable bool map to store each true assigned elements. It will
1187 /// copies all the keys set to true to the given iterator.
1189 /// \note The container of the iterator should contain space
1190 /// for each element.
1192 /// The next example shows how can you write the nodes directly
1193 /// to the standard output.
1195 /// typedef IdMap<UGraph, UEdge> UEdgeIdMap;
1196 /// UEdgeIdMap uedgeId(ugraph);
1198 /// typedef MapFunctor<UEdgeIdMap> UEdgeIdFunctor;
1199 /// UEdgeIdFunctor uedgeIdFunctor(uedgeId);
1201 /// StoreBoolMap<ostream_iterator<int>, UEdgeIdFunctor>
1202 /// writerMap(ostream_iterator<int>(cout, " "), uedgeIdFunctor);
1204 /// prim(ugraph, cost, writerMap);
1206 template <typename _Iterator,
1208 _maps_bits::Identity<typename _maps_bits::
1209 IteratorTraits<_Iterator>::Value> >
1210 class StoreBoolMap {
1212 typedef _Iterator Iterator;
1214 typedef typename _Functor::argument_type Key;
1217 typedef _Functor Functor;
1220 StoreBoolMap(Iterator it, const Functor& functor = Functor())
1221 : _begin(it), _end(it), _functor(functor) {}
1223 /// Gives back the given iterator set for the first time.
1224 Iterator begin() const {
1228 /// Gives back the iterator after the last set operation.
1229 Iterator end() const {
1233 /// Setter function of the map
1234 void set(const Key& key, Value value) const {
1236 *_end++ = _functor(key);
1242 mutable Iterator _end;
1246 /// \brief Writable bool map for store each true assigned elements in
1247 /// a back insertable container.
1249 /// Writable bool map for store each true assigned elements in a back
1250 /// insertable container. It will push back all the keys set to true into
1251 /// the container. It can be used to retrieve the items into a standard
1252 /// container. The next example shows how can you store the undirected
1253 /// edges in a vector with prim algorithm.
1256 /// vector<UEdge> span_tree_uedges;
1257 /// BackInserterBoolMap<vector<UEdge> > inserter_map(span_tree_uedges);
1258 /// prim(ugraph, cost, inserter_map);
1260 template <typename Container,
1262 _maps_bits::Identity<typename Container::value_type> >
1263 class BackInserterBoolMap {
1265 typedef typename Container::value_type Key;
1269 BackInserterBoolMap(Container& _container,
1270 const Functor& _functor = Functor())
1271 : container(_container), functor(_functor) {}
1273 /// Setter function of the map
1274 void set(const Key& key, Value value) {
1276 container.push_back(functor(key));
1281 Container& container;
1285 /// \brief Writable bool map for store each true assigned elements in
1286 /// a front insertable container.
1288 /// Writable bool map for store each true assigned elements in a front
1289 /// insertable container. It will push front all the keys set to \c true into
1290 /// the container. For example see the BackInserterBoolMap.
1291 template <typename Container,
1293 _maps_bits::Identity<typename Container::value_type> >
1294 class FrontInserterBoolMap {
1296 typedef typename Container::value_type Key;
1300 FrontInserterBoolMap(Container& _container,
1301 const Functor& _functor = Functor())
1302 : container(_container), functor(_functor) {}
1304 /// Setter function of the map
1305 void set(const Key& key, Value value) {
1307 container.push_front(key);
1312 Container& container;
1316 /// \brief Writable bool map for store each true assigned elements in
1317 /// an insertable container.
1319 /// Writable bool map for store each true assigned elements in an
1320 /// insertable container. It will insert all the keys set to \c true into
1321 /// the container. If you want to store the cut edges of the strongly
1322 /// connected components in a set you can use the next code:
1325 /// set<Edge> cut_edges;
1326 /// InserterBoolMap<set<Edge> > inserter_map(cut_edges);
1327 /// stronglyConnectedCutEdges(graph, cost, inserter_map);
1329 template <typename Container,
1331 _maps_bits::Identity<typename Container::value_type> >
1332 class InserterBoolMap {
1334 typedef typename Container::value_type Key;
1338 InserterBoolMap(Container& _container, typename Container::iterator _it,
1339 const Functor& _functor = Functor())
1340 : container(_container), it(_it), functor(_functor) {}
1343 InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1344 : container(_container), it(_container.end()), functor(_functor) {}
1346 /// Setter function of the map
1347 void set(const Key& key, Value value) {
1349 it = container.insert(it, key);
1355 Container& container;
1356 typename Container::iterator it;
1360 /// \brief Fill the true set elements with a given value.
1362 /// Writable bool map to fill the elements set to \c true with a given value.
1363 /// The value can set
1366 /// The next code finds the connected components of the undirected graph
1367 /// and stores it in the \c comp map:
1369 /// typedef UGraph::NodeMap<int> ComponentMap;
1370 /// ComponentMap comp(ugraph);
1371 /// typedef FillBoolMap<UGraph::NodeMap<int> > ComponentFillerMap;
1372 /// ComponentFillerMap filler(comp, 0);
1374 /// Dfs<UGraph>::DefProcessedMap<ComponentFillerMap>::Create dfs(ugraph);
1375 /// dfs.processedMap(filler);
1377 /// for (NodeIt it(ugraph); it != INVALID; ++it) {
1378 /// if (!dfs.reached(it)) {
1379 /// dfs.addSource(it);
1381 /// ++filler.fillValue();
1385 template <typename Map>
1388 typedef typename Map::Key Key;
1392 FillBoolMap(Map& _map, const typename Map::Value& _fill)
1393 : map(_map), fill(_fill) {}
1396 FillBoolMap(Map& _map)
1397 : map(_map), fill() {}
1399 /// Gives back the current fill value
1400 const typename Map::Value& fillValue() const {
1404 /// Gives back the current fill value
1405 typename Map::Value& fillValue() {
1409 /// Sets the current fill value
1410 void fillValue(const typename Map::Value& _fill) {
1414 /// Setter function of the map
1415 void set(const Key& key, Value value) {
1423 typename Map::Value fill;
1427 /// \brief Writable bool map which stores for each true assigned elements
1428 /// the setting order number.
1430 /// Writable bool map which stores for each true assigned elements
1431 /// the setting order number. It make easy to calculate the leaving
1432 /// order of the nodes in the \c Dfs algorithm.
1435 /// typedef Graph::NodeMap<int> OrderMap;
1436 /// OrderMap order(graph);
1437 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1438 /// OrderSetterMap setter(order);
1439 /// Dfs<Graph>::DefProcessedMap<OrderSetterMap>::Create dfs(graph);
1440 /// dfs.processedMap(setter);
1442 /// for (NodeIt it(graph); it != INVALID; ++it) {
1443 /// if (!dfs.reached(it)) {
1444 /// dfs.addSource(it);
1450 /// The discovering order can be stored a little harder because the
1451 /// ReachedMap should be readable in the dfs algorithm but the setting
1452 /// order map is not readable. Now we should use the fork map:
1455 /// typedef Graph::NodeMap<int> OrderMap;
1456 /// OrderMap order(graph);
1457 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1458 /// OrderSetterMap setter(order);
1459 /// typedef Graph::NodeMap<bool> StoreMap;
1460 /// StoreMap store(graph);
1462 /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1463 /// ReachedMap reached(store, setter);
1465 /// Dfs<Graph>::DefReachedMap<ReachedMap>::Create dfs(graph);
1466 /// dfs.reachedMap(reached);
1468 /// for (NodeIt it(graph); it != INVALID; ++it) {
1469 /// if (!dfs.reached(it)) {
1470 /// dfs.addSource(it);
1475 template <typename Map>
1476 class SettingOrderBoolMap {
1478 typedef typename Map::Key Key;
1482 SettingOrderBoolMap(Map& _map)
1483 : map(_map), counter(0) {}
1485 /// Number of set operations.
1490 /// Setter function of the map
1491 void set(const Key& key, Value value) {
1493 map.set(key, counter++);
1505 #endif // LEMON_MAPS_H