# HG changeset patch # User Peter Kovacs # Date 2009-11-13 12:47:13 # Node ID 8ddb7deabab9433ab2812c66e92356b6b05f47c7 # Parent 1a7fe3bef5144989cc90fe53f4f0a23337fc493f Map utility functions (#320) diff --git a/lemon/maps.h b/lemon/maps.h --- a/lemon/maps.h +++ b/lemon/maps.h @@ -3764,6 +3764,293 @@ return PotentialDifferenceMap(gr, potential); } + + /// \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 + void mapCopy(const GR& gr, const From& from, To& to) { + typedef typename To::Key Item; + typedef typename ItemSetTraits::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 + bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) { + typedef typename Map2::Key Item; + typedef typename ItemSetTraits::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 Map::Key mapMin(const GR& gr, const Map& map) { + return mapMin(gr, map, std::less()); + } + + /// \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 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::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 Map::Key mapMax(const GR& gr, const Map& map) { + return mapMax(gr, map, std::less()); + } + + /// \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 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::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 Map::Value mapMinValue(const GR& gr, const Map& map) { + return map[mapMin(gr, map, std::less())]; + } + + /// \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 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 Map::Value mapMaxValue(const GR& gr, const Map& map) { + return map[mapMax(gr, map, std::less())]; + } + + /// \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 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 Map::Key + mapFind(const GR& gr, const Map& map, const typename Map::Value& val) { + typedef typename Map::Key Item; + typedef typename ItemSetTraits::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 Map::Key + mapFindIf(const GR& gr, const Map& map, const Pred& pred) { + typedef typename Map::Key Item; + typedef typename ItemSetTraits::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 + int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) { + typedef typename Map::Key Item; + typedef typename ItemSetTraits::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 + int mapCountIf(const GR& gr, const Map& map, const Pred& pred) { + typedef typename Map::Key Item; + typedef typename ItemSetTraits::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 + void mapFill(const GR& gr, Map& map, const typename Map::Value& val) { + typedef typename Map::Key Item; + typedef typename ItemSetTraits::ItemIt ItemIt; + + for (ItemIt it(gr); it != INVALID; ++it) { + map.set(it, val); + } + } + /// @} } diff --git a/test/maps_test.cc b/test/maps_test.cc --- a/test/maps_test.cc +++ b/test/maps_test.cc @@ -26,6 +26,7 @@ #include #include #include +#include #include "test_tools.h" @@ -37,9 +38,22 @@ struct B {}; 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 +class Less { + T _t; +public: + Less(T t): _t(t) {} + bool operator()(const T& t) const { return t < _t; } }; class F { @@ -56,6 +70,14 @@ int binc(int a, B) { return a+1; } +template +class Sum { + T& _sum; +public: + Sum(T& sum) : _sum(sum) {} + void operator()(const T& t) { _sum += t; } +}; + typedef ReadMap DoubleMap; typedef ReadWriteMap DoubleWriteMap; typedef ReferenceMap DoubleRefMap; @@ -64,12 +86,6 @@ typedef ReadWriteMap BoolWriteMap; typedef ReferenceMap BoolRefMap; -template -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() { // Map concepts @@ -494,9 +510,10 @@ check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap"); } - compareMap(sourceMap(orienter(gr, constMap(true))), - targetMap(orienter(gr, constMap(false))), - EdgeIt(gr)); + check(mapCompare(gr, + sourceMap(orienter(gr, constMap(true))), + targetMap(orienter(gr, constMap(false)))), + "Wrong SourceMap or TargetMap"); typedef Orienter > Digraph; Digraph dgr(gr, constMap(true)); @@ -800,5 +817,183 @@ check(n == num, "Wrong number"); } + + // 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 map1(g); + SmartDigraph::ArcMap map2(g); + ConstMap cmap1 = A(); + ConstMap 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()) == n3, "Wrong mapMin()"); + check(mapMax(g, map1, std::greater()) == 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()) == a4, "Wrong mapMin()"); + check(mapMax(g, map2, std::greater()) == a2, "Wrong mapMax()"); + check(mapMinValue(g, map2, std::greater()) == 'c', + "Wrong mapMinValue()"); + check(mapMaxValue(g, map2, std::greater()) == '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(7)) == n2, + "Wrong mapFindIf()"); + check(mapFindIf(g, map1, Less(5)) == INVALID, + "Wrong mapFindIf()"); + check(mapFindIf(g, map2, Less('d')) == ArcIt(g), + "Wrong mapFindIf()"); + check(mapFindIf(g, map2, Less('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(11)) == 2, + "Wrong mapCountIf()"); + check(mapCountIf(g, map1, Less(13)) == 3, + "Wrong mapCountIf()"); + check(mapCountIf(g, map1, Less(5)) == 0, + "Wrong mapCountIf()"); + check(mapCountIf(g, map2, Less('d')) == 4, + "Wrong mapCountIf()"); + check(mapCountIf(g, map2, Less('c')) == 3, + "Wrong mapCountIf()"); + check(mapCountIf(g, map2, Less('a')) == 0, + "Wrong mapCountIf()"); + + // MapIt, ConstMapIt +/* +These tests can be used after applying bugfix #330 + typedef SmartDigraph::NodeMap::MapIt MapIt; + typedef SmartDigraph::NodeMap::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(sum)); + check(sum == 27, "Wrong NodeMap<>::MapIt"); + std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum(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 map3(g, 0); + SmartDigraph::ArcMap 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 ug(g); + Undirector::EdgeMap umap1(ug, 'x'); + Undirector::ArcMap 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(2)), "Wrong mapCompare()"); + mapFill(g, map1, 2); + check(mapCompare(g, constMap(2), map1), "Wrong mapFill()"); + + check(!mapCompare(g, map2, constMap('z')), "Wrong mapCompare()"); + mapCopy(g, constMap('z'), map2); + check(mapCompare(g, constMap('z'), map2), "Wrong mapCopy()"); + } + return 0; }