Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Wed, 18 Nov 2009 14:38:38 +0100
changeset 792a2d5fd4c309a
parent 788 c92296660262
parent 791 4e3484a2e90c
child 793 7c0ad6bd6a63
child 795 921d5bf41ac2
Merge
lemon/maps.h
     1.1 --- a/lemon/maps.h	Wed Nov 18 14:38:02 2009 +0100
     1.2 +++ b/lemon/maps.h	Wed Nov 18 14:38:38 2009 +0100
     1.3 @@ -3764,6 +3764,293 @@
     1.4      return PotentialDifferenceMap<GR, POT>(gr, potential);
     1.5    }
     1.6  
     1.7 +
     1.8 +  /// \brief Copy the values of a graph map to another map.
     1.9 +  ///
    1.10 +  /// This function copies the values of a graph map to another graph map.
    1.11 +  /// \c To::Key must be equal or convertible to \c From::Key and
    1.12 +  /// \c From::Value must be equal or convertible to \c To::Value.
    1.13 +  ///
    1.14 +  /// For example, an edge map of \c int value type can be copied to
    1.15 +  /// an arc map of \c double value type in an undirected graph, but
    1.16 +  /// an arc map cannot be copied to an edge map.
    1.17 +  /// Note that even a \ref ConstMap can be copied to a standard graph map,
    1.18 +  /// but \ref mapFill() can also be used for this purpose.
    1.19 +  ///
    1.20 +  /// \param gr The graph for which the maps are defined.
    1.21 +  /// \param from The map from which the values have to be copied.
    1.22 +  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    1.23 +  /// \param to The map to which the values have to be copied.
    1.24 +  /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.25 +  template <typename GR, typename From, typename To>
    1.26 +  void mapCopy(const GR& gr, const From& from, To& to) {
    1.27 +    typedef typename To::Key Item;
    1.28 +    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
    1.29 +    
    1.30 +    for (ItemIt it(gr); it != INVALID; ++it) {
    1.31 +      to.set(it, from[it]);
    1.32 +    }
    1.33 +  }
    1.34 +
    1.35 +  /// \brief Compare two graph maps.
    1.36 +  ///
    1.37 +  /// This function compares the values of two graph maps. It returns 
    1.38 +  /// \c true if the maps assign the same value for all items in the graph.
    1.39 +  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
    1.40 +  /// and their \c Value types must be comparable using \c %operator==().
    1.41 +  ///
    1.42 +  /// \param gr The graph for which the maps are defined.
    1.43 +  /// \param map1 The first map.
    1.44 +  /// \param map2 The second map.
    1.45 +  template <typename GR, typename Map1, typename Map2>
    1.46 +  bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
    1.47 +    typedef typename Map2::Key Item;
    1.48 +    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
    1.49 +    
    1.50 +    for (ItemIt it(gr); it != INVALID; ++it) {
    1.51 +      if (!(map1[it] == map2[it])) return false;
    1.52 +    }
    1.53 +    return true;
    1.54 +  }
    1.55 +
    1.56 +  /// \brief Return an item having minimum value of a graph map.
    1.57 +  ///
    1.58 +  /// This function returns an item (\c Node, \c Arc or \c Edge) having
    1.59 +  /// minimum value of the given graph map.
    1.60 +  /// If the item set is empty, it returns \c INVALID.
    1.61 +  ///
    1.62 +  /// \param gr The graph for which the map is defined.
    1.63 +  /// \param map The graph map.
    1.64 +  template <typename GR, typename Map>
    1.65 +  typename Map::Key mapMin(const GR& gr, const Map& map) {
    1.66 +    return mapMin(gr, map, std::less<typename Map::Value>());
    1.67 +  }
    1.68 +
    1.69 +  /// \brief Return an item having minimum value of a graph map.
    1.70 +  ///
    1.71 +  /// This function returns an item (\c Node, \c Arc or \c Edge) having
    1.72 +  /// minimum value of the given graph map.
    1.73 +  /// If the item set is empty, it returns \c INVALID.
    1.74 +  ///
    1.75 +  /// \param gr The graph for which the map is defined.
    1.76 +  /// \param map The graph map.
    1.77 +  /// \param comp Comparison function object.
    1.78 +  template <typename GR, typename Map, typename Comp>
    1.79 +  typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
    1.80 +    typedef typename Map::Key Item;
    1.81 +    typedef typename Map::Value Value;
    1.82 +    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
    1.83 +
    1.84 +    ItemIt min_item(gr);
    1.85 +    if (min_item == INVALID) return INVALID;
    1.86 +    Value min = map[min_item];
    1.87 +    for (ItemIt it(gr); it != INVALID; ++it) {
    1.88 +      if (comp(map[it], min)) {
    1.89 +        min = map[it];
    1.90 +        min_item = it;
    1.91 +      }
    1.92 +    }
    1.93 +    return min_item;
    1.94 +  }
    1.95 +
    1.96 +  /// \brief Return an item having maximum value of a graph map.
    1.97 +  ///
    1.98 +  /// This function returns an item (\c Node, \c Arc or \c Edge) having
    1.99 +  /// maximum value of the given graph map.
   1.100 +  /// If the item set is empty, it returns \c INVALID.
   1.101 +  ///
   1.102 +  /// \param gr The graph for which the map is defined.
   1.103 +  /// \param map The graph map.
   1.104 +  template <typename GR, typename Map>
   1.105 +  typename Map::Key mapMax(const GR& gr, const Map& map) {
   1.106 +    return mapMax(gr, map, std::less<typename Map::Value>());
   1.107 +  }
   1.108 +
   1.109 +  /// \brief Return an item having maximum value of a graph map.
   1.110 +  ///
   1.111 +  /// This function returns an item (\c Node, \c Arc or \c Edge) having
   1.112 +  /// maximum value of the given graph map.
   1.113 +  /// If the item set is empty, it returns \c INVALID.
   1.114 +  ///
   1.115 +  /// \param gr The graph for which the map is defined.
   1.116 +  /// \param map The graph map.
   1.117 +  /// \param comp Comparison function object.
   1.118 +  template <typename GR, typename Map, typename Comp>
   1.119 +  typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
   1.120 +    typedef typename Map::Key Item;
   1.121 +    typedef typename Map::Value Value;
   1.122 +    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
   1.123 +
   1.124 +    ItemIt max_item(gr);
   1.125 +    if (max_item == INVALID) return INVALID;
   1.126 +    Value max = map[max_item];
   1.127 +    for (ItemIt it(gr); it != INVALID; ++it) {
   1.128 +      if (comp(max, map[it])) {
   1.129 +        max = map[it];
   1.130 +        max_item = it;
   1.131 +      }
   1.132 +    }
   1.133 +    return max_item;
   1.134 +  }
   1.135 +
   1.136 +  /// \brief Return the minimum value of a graph map.
   1.137 +  ///
   1.138 +  /// This function returns the minimum value of the given graph map.
   1.139 +  /// The corresponding item set of the graph must not be empty.
   1.140 +  ///
   1.141 +  /// \param gr The graph for which the map is defined.
   1.142 +  /// \param map The graph map.
   1.143 +  template <typename GR, typename Map>
   1.144 +  typename Map::Value mapMinValue(const GR& gr, const Map& map) {
   1.145 +    return map[mapMin(gr, map, std::less<typename Map::Value>())];
   1.146 +  }
   1.147 +
   1.148 +  /// \brief Return the minimum value of a graph map.
   1.149 +  ///
   1.150 +  /// This function returns the minimum value of the given graph map.
   1.151 +  /// The corresponding item set of the graph must not be empty.
   1.152 +  ///
   1.153 +  /// \param gr The graph for which the map is defined.
   1.154 +  /// \param map The graph map.
   1.155 +  /// \param comp Comparison function object.
   1.156 +  template <typename GR, typename Map, typename Comp>
   1.157 +  typename Map::Value
   1.158 +  mapMinValue(const GR& gr, const Map& map, const Comp& comp) {
   1.159 +    return map[mapMin(gr, map, comp)];
   1.160 +  }
   1.161 +
   1.162 +  /// \brief Return the maximum value of a graph map.
   1.163 +  ///
   1.164 +  /// This function returns the maximum value of the given graph map.
   1.165 +  /// The corresponding item set of the graph must not be empty.
   1.166 +  ///
   1.167 +  /// \param gr The graph for which the map is defined.
   1.168 +  /// \param map The graph map.
   1.169 +  template <typename GR, typename Map>
   1.170 +  typename Map::Value mapMaxValue(const GR& gr, const Map& map) {
   1.171 +    return map[mapMax(gr, map, std::less<typename Map::Value>())];
   1.172 +  }
   1.173 +
   1.174 +  /// \brief Return the maximum value of a graph map.
   1.175 +  ///
   1.176 +  /// This function returns the maximum value of the given graph map.
   1.177 +  /// The corresponding item set of the graph must not be empty.
   1.178 +  ///
   1.179 +  /// \param gr The graph for which the map is defined.
   1.180 +  /// \param map The graph map.
   1.181 +  /// \param comp Comparison function object.
   1.182 +  template <typename GR, typename Map, typename Comp>
   1.183 +  typename Map::Value
   1.184 +  mapMaxValue(const GR& gr, const Map& map, const Comp& comp) {
   1.185 +    return map[mapMax(gr, map, comp)];
   1.186 +  }
   1.187 +
   1.188 +  /// \brief Return an item having a specified value in a graph map.
   1.189 +  ///
   1.190 +  /// This function returns an item (\c Node, \c Arc or \c Edge) having
   1.191 +  /// the specified assigned value in the given graph map.
   1.192 +  /// If no such item exists, it returns \c INVALID.
   1.193 +  ///
   1.194 +  /// \param gr The graph for which the map is defined.
   1.195 +  /// \param map The graph map.
   1.196 +  /// \param val The value that have to be found.
   1.197 +  template <typename GR, typename Map>
   1.198 +  typename Map::Key
   1.199 +  mapFind(const GR& gr, const Map& map, const typename Map::Value& val) {
   1.200 +    typedef typename Map::Key Item;
   1.201 +    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
   1.202 +
   1.203 +    for (ItemIt it(gr); it != INVALID; ++it) {
   1.204 +      if (map[it] == val) return it;
   1.205 +    }
   1.206 +    return INVALID;
   1.207 +  }
   1.208 +
   1.209 +  /// \brief Return an item having value for which a certain predicate is
   1.210 +  /// true in a graph map.
   1.211 +  ///
   1.212 +  /// This function returns an item (\c Node, \c Arc or \c Edge) having
   1.213 +  /// such assigned value for which the specified predicate is true
   1.214 +  /// in the given graph map.
   1.215 +  /// If no such item exists, it returns \c INVALID.
   1.216 +  ///
   1.217 +  /// \param gr The graph for which the map is defined.
   1.218 +  /// \param map The graph map.
   1.219 +  /// \param pred The predicate function object.
   1.220 +  template <typename GR, typename Map, typename Pred>
   1.221 +  typename Map::Key
   1.222 +  mapFindIf(const GR& gr, const Map& map, const Pred& pred) {
   1.223 +    typedef typename Map::Key Item;
   1.224 +    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
   1.225 +
   1.226 +    for (ItemIt it(gr); it != INVALID; ++it) {
   1.227 +      if (pred(map[it])) return it;
   1.228 +    }
   1.229 +    return INVALID;
   1.230 +  }
   1.231 +
   1.232 +  /// \brief Return the number of items having a specified value in a
   1.233 +  /// graph map.
   1.234 +  ///
   1.235 +  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
   1.236 +  /// having the specified assigned value in the given graph map.
   1.237 +  ///
   1.238 +  /// \param gr The graph for which the map is defined.
   1.239 +  /// \param map The graph map.
   1.240 +  /// \param val The value that have to be counted.
   1.241 +  template <typename GR, typename Map>
   1.242 +  int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) {
   1.243 +    typedef typename Map::Key Item;
   1.244 +    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
   1.245 +
   1.246 +    int cnt = 0;
   1.247 +    for (ItemIt it(gr); it != INVALID; ++it) {
   1.248 +      if (map[it] == val) ++cnt;
   1.249 +    }
   1.250 +    return cnt;
   1.251 +  }
   1.252 +
   1.253 +  /// \brief Return the number of items having values for which a certain
   1.254 +  /// predicate is true in a graph map.
   1.255 +  ///
   1.256 +  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
   1.257 +  /// having such assigned values for which the specified predicate is true
   1.258 +  /// in the given graph map.
   1.259 +  ///
   1.260 +  /// \param gr The graph for which the map is defined.
   1.261 +  /// \param map The graph map.
   1.262 +  /// \param pred The predicate function object.
   1.263 +  template <typename GR, typename Map, typename Pred>
   1.264 +  int mapCountIf(const GR& gr, const Map& map, const Pred& pred) {
   1.265 +    typedef typename Map::Key Item;
   1.266 +    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
   1.267 +
   1.268 +    int cnt = 0;
   1.269 +    for (ItemIt it(gr); it != INVALID; ++it) {
   1.270 +      if (pred(map[it])) ++cnt;
   1.271 +    }
   1.272 +    return cnt;
   1.273 +  }
   1.274 +
   1.275 +  /// \brief Fill a graph map with a certain value.
   1.276 +  ///
   1.277 +  /// This function sets the specified value for all items (\c Node,
   1.278 +  /// \c Arc or \c Edge) in the given graph map.
   1.279 +  ///
   1.280 +  /// \param gr The graph for which the map is defined.
   1.281 +  /// \param map The graph map. It must conform to the
   1.282 +  /// \ref concepts::WriteMap "WriteMap" concept.
   1.283 +  /// \param val The value.
   1.284 +  template <typename GR, typename Map>
   1.285 +  void mapFill(const GR& gr, Map& map, const typename Map::Value& val) {
   1.286 +    typedef typename Map::Key Item;
   1.287 +    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
   1.288 +
   1.289 +    for (ItemIt it(gr); it != INVALID; ++it) {
   1.290 +      map.set(it, val);
   1.291 +    }
   1.292 +  }
   1.293 +
   1.294    /// @}
   1.295  }
   1.296  
     2.1 --- a/test/bellman_ford_test.cc	Wed Nov 18 14:38:02 2009 +0100
     2.2 +++ b/test/bellman_ford_test.cc	Wed Nov 18 14:38:38 2009 +0100
     2.3 @@ -65,7 +65,7 @@
     2.4    Node s, t, n;
     2.5    Arc e;
     2.6    Value l;
     2.7 -  int k;
     2.8 +  int k=3;
     2.9    bool b;
    2.10    BF::DistMap d(gr);
    2.11    BF::PredMap p(gr);
     3.1 --- a/test/maps_test.cc	Wed Nov 18 14:38:02 2009 +0100
     3.2 +++ b/test/maps_test.cc	Wed Nov 18 14:38:38 2009 +0100
     3.3 @@ -26,6 +26,7 @@
     3.4  #include <lemon/smart_graph.h>
     3.5  #include <lemon/adaptors.h>
     3.6  #include <lemon/dfs.h>
     3.7 +#include <algorithm>
     3.8  
     3.9  #include "test_tools.h"
    3.10  
    3.11 @@ -37,9 +38,22 @@
    3.12  struct B {};
    3.13  
    3.14  class C {
    3.15 -  int x;
    3.16 +  int _x;
    3.17  public:
    3.18 -  C(int _x) : x(_x) {}
    3.19 +  C(int x) : _x(x) {}
    3.20 +  int get() const { return _x; }
    3.21 +};
    3.22 +inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }
    3.23 +inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }
    3.24 +
    3.25 +C createC(int x) { return C(x); }
    3.26 +
    3.27 +template <typename T>
    3.28 +class Less {
    3.29 +  T _t;
    3.30 +public:
    3.31 +  Less(T t): _t(t) {}
    3.32 +  bool operator()(const T& t) const { return t < _t; }
    3.33  };
    3.34  
    3.35  class F {
    3.36 @@ -56,6 +70,14 @@
    3.37  
    3.38  int binc(int a, B) { return a+1; }
    3.39  
    3.40 +template <typename T>
    3.41 +class Sum {
    3.42 +  T& _sum;
    3.43 +public:
    3.44 +  Sum(T& sum) : _sum(sum) {}
    3.45 +  void operator()(const T& t) { _sum += t; }
    3.46 +};
    3.47 +
    3.48  typedef ReadMap<A, double> DoubleMap;
    3.49  typedef ReadWriteMap<A, double> DoubleWriteMap;
    3.50  typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
    3.51 @@ -64,12 +86,6 @@
    3.52  typedef ReadWriteMap<A, bool> BoolWriteMap;
    3.53  typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
    3.54  
    3.55 -template<typename Map1, typename Map2, typename ItemIt>
    3.56 -void compareMap(const Map1& map1, const Map2& map2, ItemIt it) {
    3.57 -  for (; it != INVALID; ++it)
    3.58 -    check(map1[it] == map2[it], "The maps are not equal");
    3.59 -}
    3.60 -
    3.61  int main()
    3.62  {
    3.63    // Map concepts
    3.64 @@ -494,9 +510,10 @@
    3.65        check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
    3.66      }
    3.67      
    3.68 -    compareMap(sourceMap(orienter(gr, constMap<Edge, bool>(true))),
    3.69 -               targetMap(orienter(gr, constMap<Edge, bool>(false))),
    3.70 -               EdgeIt(gr));
    3.71 +    check(mapCompare(gr,
    3.72 +          sourceMap(orienter(gr, constMap<Edge, bool>(true))),
    3.73 +          targetMap(orienter(gr, constMap<Edge, bool>(false)))),
    3.74 +          "Wrong SourceMap or TargetMap");
    3.75  
    3.76      typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
    3.77      Digraph dgr(gr, constMap<Edge, bool>(true));
    3.78 @@ -800,5 +817,183 @@
    3.79      check(n == num, "Wrong number");
    3.80  
    3.81    }
    3.82 +  
    3.83 +  // Graph map utilities:
    3.84 +  // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
    3.85 +  // mapFind(), mapFindIf(), mapCount(), mapCountIf()
    3.86 +  // mapCopy(), mapCompare(), mapFill()
    3.87 +  {
    3.88 +    DIGRAPH_TYPEDEFS(SmartDigraph);
    3.89 +
    3.90 +    SmartDigraph g;
    3.91 +    Node n1 = g.addNode();
    3.92 +    Node n2 = g.addNode();
    3.93 +    Node n3 = g.addNode();
    3.94 +    
    3.95 +    SmartDigraph::NodeMap<int> map1(g);
    3.96 +    SmartDigraph::ArcMap<char> map2(g);
    3.97 +    ConstMap<Node, A> cmap1 = A();
    3.98 +    ConstMap<Arc, C> cmap2 = C(0);
    3.99 +    
   3.100 +    map1[n1] = 10;
   3.101 +    map1[n2] = 5;
   3.102 +    map1[n3] = 12;
   3.103 +    
   3.104 +    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
   3.105 +    check(mapMin(g, map1) == n2, "Wrong mapMin()");
   3.106 +    check(mapMax(g, map1) == n3, "Wrong mapMax()");
   3.107 +    check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");
   3.108 +    check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");
   3.109 +    check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");
   3.110 +    check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");
   3.111 +
   3.112 +    check(mapMin(g, map2) == INVALID, "Wrong mapMin()");
   3.113 +    check(mapMax(g, map2) == INVALID, "Wrong mapMax()");
   3.114 +
   3.115 +    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
   3.116 +    check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");
   3.117 +
   3.118 +    Arc a1 = g.addArc(n1, n2);
   3.119 +    Arc a2 = g.addArc(n1, n3);
   3.120 +    Arc a3 = g.addArc(n2, n3);
   3.121 +    Arc a4 = g.addArc(n3, n1);
   3.122 +    
   3.123 +    map2[a1] = 'b';
   3.124 +    map2[a2] = 'a';
   3.125 +    map2[a3] = 'b';
   3.126 +    map2[a4] = 'c';
   3.127 +
   3.128 +    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
   3.129 +    check(mapMin(g, map2) == a2, "Wrong mapMin()");
   3.130 +    check(mapMax(g, map2) == a4, "Wrong mapMax()");
   3.131 +    check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");
   3.132 +    check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");
   3.133 +    check(mapMinValue(g, map2, std::greater<int>()) == 'c',
   3.134 +          "Wrong mapMinValue()");
   3.135 +    check(mapMaxValue(g, map2, std::greater<int>()) == 'a',
   3.136 +          "Wrong mapMaxValue()");
   3.137 +
   3.138 +    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
   3.139 +    check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");
   3.140 +    check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");
   3.141 +
   3.142 +    check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,
   3.143 +          "Wrong mapMin()");
   3.144 +    check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,
   3.145 +          "Wrong mapMax()");
   3.146 +    check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),
   3.147 +          "Wrong mapMinValue()");
   3.148 +    check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),
   3.149 +          "Wrong mapMaxValue()");
   3.150 +
   3.151 +    // mapFind(), mapFindIf()
   3.152 +    check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");
   3.153 +    check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");
   3.154 +    check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");
   3.155 +    check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");
   3.156 +    check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");
   3.157 +    check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");
   3.158 +
   3.159 +    check(mapFindIf(g, map1, Less<int>(7)) == n2,
   3.160 +          "Wrong mapFindIf()");
   3.161 +    check(mapFindIf(g, map1, Less<int>(5)) == INVALID,
   3.162 +          "Wrong mapFindIf()");
   3.163 +    check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),
   3.164 +          "Wrong mapFindIf()");
   3.165 +    check(mapFindIf(g, map2, Less<char>('a')) == INVALID,
   3.166 +          "Wrong mapFindIf()");
   3.167 +
   3.168 +    // mapCount(), mapCountIf()
   3.169 +    check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");
   3.170 +    check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");
   3.171 +    check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");
   3.172 +    check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");
   3.173 +    check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");
   3.174 +    check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");
   3.175 +    check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");
   3.176 +
   3.177 +    check(mapCountIf(g, map1, Less<int>(11)) == 2,
   3.178 +          "Wrong mapCountIf()");
   3.179 +    check(mapCountIf(g, map1, Less<int>(13)) == 3,
   3.180 +          "Wrong mapCountIf()");
   3.181 +    check(mapCountIf(g, map1, Less<int>(5)) == 0,
   3.182 +          "Wrong mapCountIf()");
   3.183 +    check(mapCountIf(g, map2, Less<char>('d')) == 4,
   3.184 +          "Wrong mapCountIf()");
   3.185 +    check(mapCountIf(g, map2, Less<char>('c')) == 3,
   3.186 +          "Wrong mapCountIf()");
   3.187 +    check(mapCountIf(g, map2, Less<char>('a')) == 0,
   3.188 +          "Wrong mapCountIf()");
   3.189 +     
   3.190 +    // MapIt, ConstMapIt
   3.191 +/*
   3.192 +These tests can be used after applying bugfix #330
   3.193 +    typedef SmartDigraph::NodeMap<int>::MapIt MapIt;
   3.194 +    typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;
   3.195 +    check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,
   3.196 +          "Wrong NodeMap<>::MapIt");
   3.197 +    check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,
   3.198 +          "Wrong NodeMap<>::MapIt");
   3.199 +    
   3.200 +    int sum = 0;
   3.201 +    std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));
   3.202 +    check(sum == 27, "Wrong NodeMap<>::MapIt");
   3.203 +    std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));
   3.204 +    check(sum == 54, "Wrong NodeMap<>::ConstMapIt");
   3.205 +*/
   3.206 +
   3.207 +    // mapCopy(), mapCompare(), mapFill()
   3.208 +    check(mapCompare(g, map1, map1), "Wrong mapCompare()");
   3.209 +    check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");
   3.210 +    check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");
   3.211 +    check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");
   3.212 +    check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");
   3.213 +
   3.214 +    SmartDigraph::NodeMap<int> map3(g, 0);
   3.215 +    SmartDigraph::ArcMap<char> map4(g, 'a');
   3.216 +    
   3.217 +    check(!mapCompare(g, map1, map3), "Wrong mapCompare()");
   3.218 +    check(!mapCompare(g, map2, map4), "Wrong mapCompare()");    
   3.219 +    
   3.220 +    mapCopy(g, map1, map3);
   3.221 +    mapCopy(g, map2, map4);
   3.222 +
   3.223 +    check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");
   3.224 +    check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");    
   3.225 +    
   3.226 +    Undirector<SmartDigraph> ug(g);
   3.227 +    Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');
   3.228 +    Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);
   3.229 +    
   3.230 +    check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
   3.231 +    check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
   3.232 +    check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
   3.233 +    check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
   3.234 +    
   3.235 +    mapCopy(g, map2, umap1);
   3.236 +
   3.237 +    check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
   3.238 +    check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
   3.239 +    check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
   3.240 +    check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
   3.241 +    
   3.242 +    mapCopy(g, map2, umap1);
   3.243 +    mapCopy(g, umap1, map2);
   3.244 +    mapCopy(ug, map2, umap1);
   3.245 +    mapCopy(ug, umap1, map2);
   3.246 +    
   3.247 +    check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
   3.248 +    mapCopy(ug, umap1, umap2);
   3.249 +    check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
   3.250 +    
   3.251 +    check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");
   3.252 +    mapFill(g, map1, 2);
   3.253 +    check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()");
   3.254 +
   3.255 +    check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()");
   3.256 +    mapCopy(g, constMap<Arc>('z'), map2);
   3.257 +    check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");
   3.258 +  }
   3.259 +  
   3.260    return 0;
   3.261  }