Changeset 789:8ddb7deabab9 in lemon-main

Timestamp:

11/13/09 12:47:13 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Map utility functions (#320)

Files:

• lemon/maps.h (modified) (1 diff)
• test/maps_test.cc (modified) (6 diffs)

lemon/maps.h

@@ -3765 +3765 @@
   }
 
+
+  /// \brief Copy the values of a graph map to another map.
+  ///
+  /// This function copies the values of a graph map to another graph map.
+  /// \c To::Key must be equal or convertible to \c From::Key and
+  /// \c From::Value must be equal or convertible to \c To::Value.
+  ///
+  /// For example, an edge map of \c int value type can be copied to
+  /// an arc map of \c double value type in an undirected graph, but
+  /// an arc map cannot be copied to an edge map.
+  /// Note that even a \ref ConstMap can be copied to a standard graph map,
+  /// but \ref mapFill() can also be used for this purpose.
+  ///
+  /// \param gr The graph for which the maps are defined.
+  /// \param from The map from which the values have to be copied.
+  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+  /// \param to The map to which the values have to be copied.
+  /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+  template <typename GR, typename From, typename To>
+  void mapCopy(const GR& gr, const From& from, To& to) {
+    typedef typename To::Key Item;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+    
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      to.set(it, from[it]);
+    }
+  }
+
+  /// \brief Compare two graph maps.
+  ///
+  /// This function compares the values of two graph maps. It returns 
+  /// \c true if the maps assign the same value for all items in the graph.
+  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
+  /// and their \c Value types must be comparable using \c %operator==().
+  ///
+  /// \param gr The graph for which the maps are defined.
+  /// \param map1 The first map.
+  /// \param map2 The second map.
+  template <typename GR, typename Map1, typename Map2>
+  bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
+    typedef typename Map2::Key Item;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+    
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (!(map1[it] == map2[it])) return false;
+    }
+    return true;
+  }
+
+  /// \brief Return an item having minimum value of a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// minimum value of the given graph map.
+  /// If the item set is empty, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  template <typename GR, typename Map>
+  typename Map::Key mapMin(const GR& gr, const Map& map) {
+    return mapMin(gr, map, std::less<typename Map::Value>());
+  }
+
+  /// \brief Return an item having minimum value of a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// minimum value of the given graph map.
+  /// If the item set is empty, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param comp Comparison function object.
+  template <typename GR, typename Map, typename Comp>
+  typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
+    typedef typename Map::Key Item;
+    typedef typename Map::Value Value;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+
+    ItemIt min_item(gr);
+    if (min_item == INVALID) return INVALID;
+    Value min = map[min_item];
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (comp(map[it], min)) {
+        min = map[it];
+        min_item = it;
+      }
+    }
+    return min_item;
+  }
+
+  /// \brief Return an item having maximum value of a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// maximum value of the given graph map.
+  /// If the item set is empty, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  template <typename GR, typename Map>
+  typename Map::Key mapMax(const GR& gr, const Map& map) {
+    return mapMax(gr, map, std::less<typename Map::Value>());
+  }
+
+  /// \brief Return an item having maximum value of a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// maximum value of the given graph map.
+  /// If the item set is empty, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param comp Comparison function object.
+  template <typename GR, typename Map, typename Comp>
+  typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
+    typedef typename Map::Key Item;
+    typedef typename Map::Value Value;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+
+    ItemIt max_item(gr);
+    if (max_item == INVALID) return INVALID;
+    Value max = map[max_item];
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (comp(max, map[it])) {
+        max = map[it];
+        max_item = it;
+      }
+    }
+    return max_item;
+  }
+
+  /// \brief Return the minimum value of a graph map.
+  ///
+  /// This function returns the minimum value of the given graph map.
+  /// The corresponding item set of the graph must not be empty.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  template <typename GR, typename Map>
+  typename Map::Value mapMinValue(const GR& gr, const Map& map) {
+    return map[mapMin(gr, map, std::less<typename Map::Value>())];
+  }
+
+  /// \brief Return the minimum value of a graph map.
+  ///
+  /// This function returns the minimum value of the given graph map.
+  /// The corresponding item set of the graph must not be empty.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param comp Comparison function object.
+  template <typename GR, typename Map, typename Comp>
+  typename Map::Value
+  mapMinValue(const GR& gr, const Map& map, const Comp& comp) {
+    return map[mapMin(gr, map, comp)];
+  }
+
+  /// \brief Return the maximum value of a graph map.
+  ///
+  /// This function returns the maximum value of the given graph map.
+  /// The corresponding item set of the graph must not be empty.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  template <typename GR, typename Map>
+  typename Map::Value mapMaxValue(const GR& gr, const Map& map) {
+    return map[mapMax(gr, map, std::less<typename Map::Value>())];
+  }
+
+  /// \brief Return the maximum value of a graph map.
+  ///
+  /// This function returns the maximum value of the given graph map.
+  /// The corresponding item set of the graph must not be empty.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param comp Comparison function object.
+  template <typename GR, typename Map, typename Comp>
+  typename Map::Value
+  mapMaxValue(const GR& gr, const Map& map, const Comp& comp) {
+    return map[mapMax(gr, map, comp)];
+  }
+
+  /// \brief Return an item having a specified value in a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// the specified assigned value in the given graph map.
+  /// If no such item exists, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param val The value that have to be found.
+  template <typename GR, typename Map>
+  typename Map::Key
+  mapFind(const GR& gr, const Map& map, const typename Map::Value& val) {
+    typedef typename Map::Key Item;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (map[it] == val) return it;
+    }
+    return INVALID;
+  }
+
+  /// \brief Return an item having value for which a certain predicate is
+  /// true in a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// such assigned value for which the specified predicate is true
+  /// in the given graph map.
+  /// If no such item exists, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param pred The predicate function object.
+  template <typename GR, typename Map, typename Pred>
+  typename Map::Key
+  mapFindIf(const GR& gr, const Map& map, const Pred& pred) {
+    typedef typename Map::Key Item;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (pred(map[it])) return it;
+    }
+    return INVALID;
+  }
+
+  /// \brief Return the number of items having a specified value in a
+  /// graph map.
+  ///
+  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
+  /// having the specified assigned value in the given graph map.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param val The value that have to be counted.
+  template <typename GR, typename Map>
+  int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) {
+    typedef typename Map::Key Item;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+
+    int cnt = 0;
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (map[it] == val) ++cnt;
+    }
+    return cnt;
+  }
+
+  /// \brief Return the number of items having values for which a certain
+  /// predicate is true in a graph map.
+  ///
+  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
+  /// having such assigned values for which the specified predicate is true
+  /// in the given graph map.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param pred The predicate function object.
+  template <typename GR, typename Map, typename Pred>
+  int mapCountIf(const GR& gr, const Map& map, const Pred& pred) {
+    typedef typename Map::Key Item;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+
+    int cnt = 0;
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (pred(map[it])) ++cnt;
+    }
+    return cnt;
+  }
+
+  /// \brief Fill a graph map with a certain value.
+  ///
+  /// This function sets the specified value for all items (\c Node,
+  /// \c Arc or \c Edge) in the given graph map.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map. It must conform to the
+  /// \ref concepts::WriteMap "WriteMap" concept.
+  /// \param val The value.
+  template <typename GR, typename Map>
+  void mapFill(const GR& gr, Map& map, const typename Map::Value& val) {
+    typedef typename Map::Key Item;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      map.set(it, val);
+    }
+  }
+
   /// @}
 }

test/maps_test.cc

@@ -27 +27 @@
 #include <lemon/adaptors.h>
 #include <lemon/dfs.h>
+#include <algorithm>
 
 #include "test_tools.h"
@@ -38 +39 @@
 
 class C {
-  int x;
+  int _x;
 public:
-  C(int _x) : x(_x) {}
+  C(int x) : _x(x) {}
+  int get() const { return _x; }
+};
+inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }
+inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }
+
+C createC(int x) { return C(x); }
+
+template <typename T>
+class Less {
+  T _t;
+public:
+  Less(T t): _t(t) {}
+  bool operator()(const T& t) const { return t < _t; }
 };
 
@@ -57 +71 @@
 int binc(int a, B) { return a+1; }
 
+template <typename T>
+class Sum {
+  T& _sum;
+public:
+  Sum(T& sum) : _sum(sum) {}
+  void operator()(const T& t) { _sum += t; }
+};
+
 typedef ReadMap<A, double> DoubleMap;
 typedef ReadWriteMap<A, double> DoubleWriteMap;
@@ -64 +86 @@
 typedef ReadWriteMap<A, bool> BoolWriteMap;
 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
-
-template<typename Map1, typename Map2, typename ItemIt>
-void compareMap(const Map1& map1, const Map2& map2, ItemIt it) {
-  for (; it != INVALID; ++it)
-    check(map1[it] == map2[it], "The maps are not equal");
-}
 
 int main()
@@ -495 +511 @@
     }
     
-    compareMap(sourceMap(orienter(gr, constMap<Edge, bool>(true))),
-               targetMap(orienter(gr, constMap<Edge, bool>(false))),
-               EdgeIt(gr));
+    check(mapCompare(gr,
+          sourceMap(orienter(gr, constMap<Edge, bool>(true))),
+          targetMap(orienter(gr, constMap<Edge, bool>(false)))),
+          "Wrong SourceMap or TargetMap");
 
     typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
@@ -801 +818 @@
 
   }
+  
+  // Graph map utilities:
+  // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
+  // mapFind(), mapFindIf(), mapCount(), mapCountIf()
+  // mapCopy(), mapCompare(), mapFill()
+  {
+    DIGRAPH_TYPEDEFS(SmartDigraph);
+
+    SmartDigraph g;
+    Node n1 = g.addNode();
+    Node n2 = g.addNode();
+    Node n3 = g.addNode();
+    
+    SmartDigraph::NodeMap<int> map1(g);
+    SmartDigraph::ArcMap<char> map2(g);
+    ConstMap<Node, A> cmap1 = A();
+    ConstMap<Arc, C> cmap2 = C(0);
+    
+    map1[n1] = 10;
+    map1[n2] = 5;
+    map1[n3] = 12;
+    
+    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
+    check(mapMin(g, map1) == n2, "Wrong mapMin()");
+    check(mapMax(g, map1) == n3, "Wrong mapMax()");
+    check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");
+    check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");
+    check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");
+    check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");
+
+    check(mapMin(g, map2) == INVALID, "Wrong mapMin()");
+    check(mapMax(g, map2) == INVALID, "Wrong mapMax()");
+
+    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
+    check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");
+
+    Arc a1 = g.addArc(n1, n2);
+    Arc a2 = g.addArc(n1, n3);
+    Arc a3 = g.addArc(n2, n3);
+    Arc a4 = g.addArc(n3, n1);
+    
+    map2[a1] = 'b';
+    map2[a2] = 'a';
+    map2[a3] = 'b';
+    map2[a4] = 'c';
+
+    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
+    check(mapMin(g, map2) == a2, "Wrong mapMin()");
+    check(mapMax(g, map2) == a4, "Wrong mapMax()");
+    check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");
+    check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");
+    check(mapMinValue(g, map2, std::greater<int>()) == 'c',
+          "Wrong mapMinValue()");
+    check(mapMaxValue(g, map2, std::greater<int>()) == 'a',
+          "Wrong mapMaxValue()");
+
+    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
+    check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");
+    check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");
+
+    check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,
+          "Wrong mapMin()");
+    check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,
+          "Wrong mapMax()");
+    check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),
+          "Wrong mapMinValue()");
+    check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),
+          "Wrong mapMaxValue()");
+
+    // mapFind(), mapFindIf()
+    check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");
+    check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");
+    check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");
+    check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");
+    check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");
+    check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");
+
+    check(mapFindIf(g, map1, Less<int>(7)) == n2,
+          "Wrong mapFindIf()");
+    check(mapFindIf(g, map1, Less<int>(5)) == INVALID,
+          "Wrong mapFindIf()");
+    check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),
+          "Wrong mapFindIf()");
+    check(mapFindIf(g, map2, Less<char>('a')) == INVALID,
+          "Wrong mapFindIf()");
+
+    // mapCount(), mapCountIf()
+    check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");
+    check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");
+    check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");
+    check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");
+    check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");
+    check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");
+    check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");
+
+    check(mapCountIf(g, map1, Less<int>(11)) == 2,
+          "Wrong mapCountIf()");
+    check(mapCountIf(g, map1, Less<int>(13)) == 3,
+          "Wrong mapCountIf()");
+    check(mapCountIf(g, map1, Less<int>(5)) == 0,
+          "Wrong mapCountIf()");
+    check(mapCountIf(g, map2, Less<char>('d')) == 4,
+          "Wrong mapCountIf()");
+    check(mapCountIf(g, map2, Less<char>('c')) == 3,
+          "Wrong mapCountIf()");
+    check(mapCountIf(g, map2, Less<char>('a')) == 0,
+          "Wrong mapCountIf()");
+     
+    // MapIt, ConstMapIt
+/*
+These tests can be used after applying bugfix #330
+    typedef SmartDigraph::NodeMap<int>::MapIt MapIt;
+    typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;
+    check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,
+          "Wrong NodeMap<>::MapIt");
+    check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,
+          "Wrong NodeMap<>::MapIt");
+    
+    int sum = 0;
+    std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));
+    check(sum == 27, "Wrong NodeMap<>::MapIt");
+    std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));
+    check(sum == 54, "Wrong NodeMap<>::ConstMapIt");
+*/
+
+    // mapCopy(), mapCompare(), mapFill()
+    check(mapCompare(g, map1, map1), "Wrong mapCompare()");
+    check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");
+    check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");
+    check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");
+    check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");
+
+    SmartDigraph::NodeMap<int> map3(g, 0);
+    SmartDigraph::ArcMap<char> map4(g, 'a');
+    
+    check(!mapCompare(g, map1, map3), "Wrong mapCompare()");
+    check(!mapCompare(g, map2, map4), "Wrong mapCompare()");    
+    
+    mapCopy(g, map1, map3);
+    mapCopy(g, map2, map4);
+
+    check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");
+    check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");    
+    
+    Undirector<SmartDigraph> ug(g);
+    Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');
+    Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);
+    
+    check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
+    check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
+    check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
+    check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
+    
+    mapCopy(g, map2, umap1);
+
+    check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
+    check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
+    check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
+    check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
+    
+    mapCopy(g, map2, umap1);
+    mapCopy(g, umap1, map2);
+    mapCopy(ug, map2, umap1);
+    mapCopy(ug, umap1, map2);
+    
+    check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
+    mapCopy(ug, umap1, umap2);
+    check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
+    
+    check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");
+    mapFill(g, map1, 2);
+    check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()");
+
+    check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()");
+    mapCopy(g, constMap<Arc>('z'), map2);
+    check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");
+  }
+  
   return 0;
 }