Changeset 789:8ddb7deabab9 in lemon1.2
 Timestamp:
 11/13/09 12:47:13 (10 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/maps.h
r726 r789 3765 3765 } 3766 3766 3767 3768 /// \brief Copy the values of a graph map to another map. 3769 /// 3770 /// This function copies the values of a graph map to another graph map. 3771 /// \c To::Key must be equal or convertible to \c From::Key and 3772 /// \c From::Value must be equal or convertible to \c To::Value. 3773 /// 3774 /// For example, an edge map of \c int value type can be copied to 3775 /// an arc map of \c double value type in an undirected graph, but 3776 /// an arc map cannot be copied to an edge map. 3777 /// Note that even a \ref ConstMap can be copied to a standard graph map, 3778 /// but \ref mapFill() can also be used for this purpose. 3779 /// 3780 /// \param gr The graph for which the maps are defined. 3781 /// \param from The map from which the values have to be copied. 3782 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. 3783 /// \param to The map to which the values have to be copied. 3784 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 3785 template <typename GR, typename From, typename To> 3786 void mapCopy(const GR& gr, const From& from, To& to) { 3787 typedef typename To::Key Item; 3788 typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; 3789 3790 for (ItemIt it(gr); it != INVALID; ++it) { 3791 to.set(it, from[it]); 3792 } 3793 } 3794 3795 /// \brief Compare two graph maps. 3796 /// 3797 /// This function compares the values of two graph maps. It returns 3798 /// \c true if the maps assign the same value for all items in the graph. 3799 /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal 3800 /// and their \c Value types must be comparable using \c %operator==(). 3801 /// 3802 /// \param gr The graph for which the maps are defined. 3803 /// \param map1 The first map. 3804 /// \param map2 The second map. 3805 template <typename GR, typename Map1, typename Map2> 3806 bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) { 3807 typedef typename Map2::Key Item; 3808 typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; 3809 3810 for (ItemIt it(gr); it != INVALID; ++it) { 3811 if (!(map1[it] == map2[it])) return false; 3812 } 3813 return true; 3814 } 3815 3816 /// \brief Return an item having minimum value of a graph map. 3817 /// 3818 /// This function returns an item (\c Node, \c Arc or \c Edge) having 3819 /// minimum value of the given graph map. 3820 /// If the item set is empty, it returns \c INVALID. 3821 /// 3822 /// \param gr The graph for which the map is defined. 3823 /// \param map The graph map. 3824 template <typename GR, typename Map> 3825 typename Map::Key mapMin(const GR& gr, const Map& map) { 3826 return mapMin(gr, map, std::less<typename Map::Value>()); 3827 } 3828 3829 /// \brief Return an item having minimum value of a graph map. 3830 /// 3831 /// This function returns an item (\c Node, \c Arc or \c Edge) having 3832 /// minimum value of the given graph map. 3833 /// If the item set is empty, it returns \c INVALID. 3834 /// 3835 /// \param gr The graph for which the map is defined. 3836 /// \param map The graph map. 3837 /// \param comp Comparison function object. 3838 template <typename GR, typename Map, typename Comp> 3839 typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) { 3840 typedef typename Map::Key Item; 3841 typedef typename Map::Value Value; 3842 typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; 3843 3844 ItemIt min_item(gr); 3845 if (min_item == INVALID) return INVALID; 3846 Value min = map[min_item]; 3847 for (ItemIt it(gr); it != INVALID; ++it) { 3848 if (comp(map[it], min)) { 3849 min = map[it]; 3850 min_item = it; 3851 } 3852 } 3853 return min_item; 3854 } 3855 3856 /// \brief Return an item having maximum value of a graph map. 3857 /// 3858 /// This function returns an item (\c Node, \c Arc or \c Edge) having 3859 /// maximum value of the given graph map. 3860 /// If the item set is empty, it returns \c INVALID. 3861 /// 3862 /// \param gr The graph for which the map is defined. 3863 /// \param map The graph map. 3864 template <typename GR, typename Map> 3865 typename Map::Key mapMax(const GR& gr, const Map& map) { 3866 return mapMax(gr, map, std::less<typename Map::Value>()); 3867 } 3868 3869 /// \brief Return an item having maximum value of a graph map. 3870 /// 3871 /// This function returns an item (\c Node, \c Arc or \c Edge) having 3872 /// maximum value of the given graph map. 3873 /// If the item set is empty, it returns \c INVALID. 3874 /// 3875 /// \param gr The graph for which the map is defined. 3876 /// \param map The graph map. 3877 /// \param comp Comparison function object. 3878 template <typename GR, typename Map, typename Comp> 3879 typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) { 3880 typedef typename Map::Key Item; 3881 typedef typename Map::Value Value; 3882 typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; 3883 3884 ItemIt max_item(gr); 3885 if (max_item == INVALID) return INVALID; 3886 Value max = map[max_item]; 3887 for (ItemIt it(gr); it != INVALID; ++it) { 3888 if (comp(max, map[it])) { 3889 max = map[it]; 3890 max_item = it; 3891 } 3892 } 3893 return max_item; 3894 } 3895 3896 /// \brief Return the minimum value of a graph map. 3897 /// 3898 /// This function returns the minimum value of the given graph map. 3899 /// The corresponding item set of the graph must not be empty. 3900 /// 3901 /// \param gr The graph for which the map is defined. 3902 /// \param map The graph map. 3903 template <typename GR, typename Map> 3904 typename Map::Value mapMinValue(const GR& gr, const Map& map) { 3905 return map[mapMin(gr, map, std::less<typename Map::Value>())]; 3906 } 3907 3908 /// \brief Return the minimum value of a graph map. 3909 /// 3910 /// This function returns the minimum value of the given graph map. 3911 /// The corresponding item set of the graph must not be empty. 3912 /// 3913 /// \param gr The graph for which the map is defined. 3914 /// \param map The graph map. 3915 /// \param comp Comparison function object. 3916 template <typename GR, typename Map, typename Comp> 3917 typename Map::Value 3918 mapMinValue(const GR& gr, const Map& map, const Comp& comp) { 3919 return map[mapMin(gr, map, comp)]; 3920 } 3921 3922 /// \brief Return the maximum value of a graph map. 3923 /// 3924 /// This function returns the maximum value of the given graph map. 3925 /// The corresponding item set of the graph must not be empty. 3926 /// 3927 /// \param gr The graph for which the map is defined. 3928 /// \param map The graph map. 3929 template <typename GR, typename Map> 3930 typename Map::Value mapMaxValue(const GR& gr, const Map& map) { 3931 return map[mapMax(gr, map, std::less<typename Map::Value>())]; 3932 } 3933 3934 /// \brief Return the maximum value of a graph map. 3935 /// 3936 /// This function returns the maximum value of the given graph map. 3937 /// The corresponding item set of the graph must not be empty. 3938 /// 3939 /// \param gr The graph for which the map is defined. 3940 /// \param map The graph map. 3941 /// \param comp Comparison function object. 3942 template <typename GR, typename Map, typename Comp> 3943 typename Map::Value 3944 mapMaxValue(const GR& gr, const Map& map, const Comp& comp) { 3945 return map[mapMax(gr, map, comp)]; 3946 } 3947 3948 /// \brief Return an item having a specified value in a graph map. 3949 /// 3950 /// This function returns an item (\c Node, \c Arc or \c Edge) having 3951 /// the specified assigned value in the given graph map. 3952 /// If no such item exists, it returns \c INVALID. 3953 /// 3954 /// \param gr The graph for which the map is defined. 3955 /// \param map The graph map. 3956 /// \param val The value that have to be found. 3957 template <typename GR, typename Map> 3958 typename Map::Key 3959 mapFind(const GR& gr, const Map& map, const typename Map::Value& val) { 3960 typedef typename Map::Key Item; 3961 typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; 3962 3963 for (ItemIt it(gr); it != INVALID; ++it) { 3964 if (map[it] == val) return it; 3965 } 3966 return INVALID; 3967 } 3968 3969 /// \brief Return an item having value for which a certain predicate is 3970 /// true in a graph map. 3971 /// 3972 /// This function returns an item (\c Node, \c Arc or \c Edge) having 3973 /// such assigned value for which the specified predicate is true 3974 /// in the given graph map. 3975 /// If no such item exists, it returns \c INVALID. 3976 /// 3977 /// \param gr The graph for which the map is defined. 3978 /// \param map The graph map. 3979 /// \param pred The predicate function object. 3980 template <typename GR, typename Map, typename Pred> 3981 typename Map::Key 3982 mapFindIf(const GR& gr, const Map& map, const Pred& pred) { 3983 typedef typename Map::Key Item; 3984 typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; 3985 3986 for (ItemIt it(gr); it != INVALID; ++it) { 3987 if (pred(map[it])) return it; 3988 } 3989 return INVALID; 3990 } 3991 3992 /// \brief Return the number of items having a specified value in a 3993 /// graph map. 3994 /// 3995 /// This function returns the number of items (\c Node, \c Arc or \c Edge) 3996 /// having the specified assigned value in the given graph map. 3997 /// 3998 /// \param gr The graph for which the map is defined. 3999 /// \param map The graph map. 4000 /// \param val The value that have to be counted. 4001 template <typename GR, typename Map> 4002 int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) { 4003 typedef typename Map::Key Item; 4004 typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; 4005 4006 int cnt = 0; 4007 for (ItemIt it(gr); it != INVALID; ++it) { 4008 if (map[it] == val) ++cnt; 4009 } 4010 return cnt; 4011 } 4012 4013 /// \brief Return the number of items having values for which a certain 4014 /// predicate is true in a graph map. 4015 /// 4016 /// This function returns the number of items (\c Node, \c Arc or \c Edge) 4017 /// having such assigned values for which the specified predicate is true 4018 /// in the given graph map. 4019 /// 4020 /// \param gr The graph for which the map is defined. 4021 /// \param map The graph map. 4022 /// \param pred The predicate function object. 4023 template <typename GR, typename Map, typename Pred> 4024 int mapCountIf(const GR& gr, const Map& map, const Pred& pred) { 4025 typedef typename Map::Key Item; 4026 typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; 4027 4028 int cnt = 0; 4029 for (ItemIt it(gr); it != INVALID; ++it) { 4030 if (pred(map[it])) ++cnt; 4031 } 4032 return cnt; 4033 } 4034 4035 /// \brief Fill a graph map with a certain value. 4036 /// 4037 /// This function sets the specified value for all items (\c Node, 4038 /// \c Arc or \c Edge) in the given graph map. 4039 /// 4040 /// \param gr The graph for which the map is defined. 4041 /// \param map The graph map. It must conform to the 4042 /// \ref concepts::WriteMap "WriteMap" concept. 4043 /// \param val The value. 4044 template <typename GR, typename Map> 4045 void mapFill(const GR& gr, Map& map, const typename Map::Value& val) { 4046 typedef typename Map::Key Item; 4047 typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; 4048 4049 for (ItemIt it(gr); it != INVALID; ++it) { 4050 map.set(it, val); 4051 } 4052 } 4053 3767 4054 /// @} 3768 4055 } 
test/maps_test.cc
r726 r789 27 27 #include <lemon/adaptors.h> 28 28 #include <lemon/dfs.h> 29 #include <algorithm> 29 30 30 31 #include "test_tools.h" … … 38 39 39 40 class C { 40 int x;41 int _x; 41 42 public: 42 C(int _x) : x(_x) {} 43 C(int x) : _x(x) {} 44 int get() const { return _x; } 45 }; 46 inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); } 47 inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); } 48 49 C createC(int x) { return C(x); } 50 51 template <typename T> 52 class Less { 53 T _t; 54 public: 55 Less(T t): _t(t) {} 56 bool operator()(const T& t) const { return t < _t; } 43 57 }; 44 58 … … 57 71 int binc(int a, B) { return a+1; } 58 72 73 template <typename T> 74 class Sum { 75 T& _sum; 76 public: 77 Sum(T& sum) : _sum(sum) {} 78 void operator()(const T& t) { _sum += t; } 79 }; 80 59 81 typedef ReadMap<A, double> DoubleMap; 60 82 typedef ReadWriteMap<A, double> DoubleWriteMap; … … 64 86 typedef ReadWriteMap<A, bool> BoolWriteMap; 65 87 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap; 66 67 template<typename Map1, typename Map2, typename ItemIt>68 void compareMap(const Map1& map1, const Map2& map2, ItemIt it) {69 for (; it != INVALID; ++it)70 check(map1[it] == map2[it], "The maps are not equal");71 }72 88 73 89 int main() … … 495 511 } 496 512 497 compareMap(sourceMap(orienter(gr, constMap<Edge, bool>(true))), 498 targetMap(orienter(gr, constMap<Edge, bool>(false))), 499 EdgeIt(gr)); 513 check(mapCompare(gr, 514 sourceMap(orienter(gr, constMap<Edge, bool>(true))), 515 targetMap(orienter(gr, constMap<Edge, bool>(false)))), 516 "Wrong SourceMap or TargetMap"); 500 517 501 518 typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph; … … 801 818 802 819 } 820 821 // Graph map utilities: 822 // mapMin(), mapMax(), mapMinValue(), mapMaxValue() 823 // mapFind(), mapFindIf(), mapCount(), mapCountIf() 824 // mapCopy(), mapCompare(), mapFill() 825 { 826 DIGRAPH_TYPEDEFS(SmartDigraph); 827 828 SmartDigraph g; 829 Node n1 = g.addNode(); 830 Node n2 = g.addNode(); 831 Node n3 = g.addNode(); 832 833 SmartDigraph::NodeMap<int> map1(g); 834 SmartDigraph::ArcMap<char> map2(g); 835 ConstMap<Node, A> cmap1 = A(); 836 ConstMap<Arc, C> cmap2 = C(0); 837 838 map1[n1] = 10; 839 map1[n2] = 5; 840 map1[n3] = 12; 841 842 // mapMin(), mapMax(), mapMinValue(), mapMaxValue() 843 check(mapMin(g, map1) == n2, "Wrong mapMin()"); 844 check(mapMax(g, map1) == n3, "Wrong mapMax()"); 845 check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()"); 846 check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()"); 847 check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()"); 848 check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()"); 849 850 check(mapMin(g, map2) == INVALID, "Wrong mapMin()"); 851 check(mapMax(g, map2) == INVALID, "Wrong mapMax()"); 852 853 check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()"); 854 check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()"); 855 856 Arc a1 = g.addArc(n1, n2); 857 Arc a2 = g.addArc(n1, n3); 858 Arc a3 = g.addArc(n2, n3); 859 Arc a4 = g.addArc(n3, n1); 860 861 map2[a1] = 'b'; 862 map2[a2] = 'a'; 863 map2[a3] = 'b'; 864 map2[a4] = 'c'; 865 866 // mapMin(), mapMax(), mapMinValue(), mapMaxValue() 867 check(mapMin(g, map2) == a2, "Wrong mapMin()"); 868 check(mapMax(g, map2) == a4, "Wrong mapMax()"); 869 check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()"); 870 check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()"); 871 check(mapMinValue(g, map2, std::greater<int>()) == 'c', 872 "Wrong mapMinValue()"); 873 check(mapMaxValue(g, map2, std::greater<int>()) == 'a', 874 "Wrong mapMaxValue()"); 875 876 check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()"); 877 check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()"); 878 check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()"); 879 880 check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2, 881 "Wrong mapMin()"); 882 check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4, 883 "Wrong mapMax()"); 884 check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'), 885 "Wrong mapMinValue()"); 886 check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'), 887 "Wrong mapMaxValue()"); 888 889 // mapFind(), mapFindIf() 890 check(mapFind(g, map1, 5) == n2, "Wrong mapFind()"); 891 check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()"); 892 check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()"); 893 check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()"); 894 check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()"); 895 check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()"); 896 897 check(mapFindIf(g, map1, Less<int>(7)) == n2, 898 "Wrong mapFindIf()"); 899 check(mapFindIf(g, map1, Less<int>(5)) == INVALID, 900 "Wrong mapFindIf()"); 901 check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g), 902 "Wrong mapFindIf()"); 903 check(mapFindIf(g, map2, Less<char>('a')) == INVALID, 904 "Wrong mapFindIf()"); 905 906 // mapCount(), mapCountIf() 907 check(mapCount(g, map1, 5) == 1, "Wrong mapCount()"); 908 check(mapCount(g, map1, 6) == 0, "Wrong mapCount()"); 909 check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()"); 910 check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()"); 911 check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()"); 912 check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()"); 913 check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()"); 914 915 check(mapCountIf(g, map1, Less<int>(11)) == 2, 916 "Wrong mapCountIf()"); 917 check(mapCountIf(g, map1, Less<int>(13)) == 3, 918 "Wrong mapCountIf()"); 919 check(mapCountIf(g, map1, Less<int>(5)) == 0, 920 "Wrong mapCountIf()"); 921 check(mapCountIf(g, map2, Less<char>('d')) == 4, 922 "Wrong mapCountIf()"); 923 check(mapCountIf(g, map2, Less<char>('c')) == 3, 924 "Wrong mapCountIf()"); 925 check(mapCountIf(g, map2, Less<char>('a')) == 0, 926 "Wrong mapCountIf()"); 927 928 // MapIt, ConstMapIt 929 /* 930 These tests can be used after applying bugfix #330 931 typedef SmartDigraph::NodeMap<int>::MapIt MapIt; 932 typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt; 933 check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5, 934 "Wrong NodeMap<>::MapIt"); 935 check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12, 936 "Wrong NodeMap<>::MapIt"); 937 938 int sum = 0; 939 std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum)); 940 check(sum == 27, "Wrong NodeMap<>::MapIt"); 941 std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum)); 942 check(sum == 54, "Wrong NodeMap<>::ConstMapIt"); 943 */ 944 945 // mapCopy(), mapCompare(), mapFill() 946 check(mapCompare(g, map1, map1), "Wrong mapCompare()"); 947 check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()"); 948 check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()"); 949 check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()"); 950 check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()"); 951 952 SmartDigraph::NodeMap<int> map3(g, 0); 953 SmartDigraph::ArcMap<char> map4(g, 'a'); 954 955 check(!mapCompare(g, map1, map3), "Wrong mapCompare()"); 956 check(!mapCompare(g, map2, map4), "Wrong mapCompare()"); 957 958 mapCopy(g, map1, map3); 959 mapCopy(g, map2, map4); 960 961 check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()"); 962 check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()"); 963 964 Undirector<SmartDigraph> ug(g); 965 Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x'); 966 Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14); 967 968 check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()"); 969 check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()"); 970 check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()"); 971 check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()"); 972 973 mapCopy(g, map2, umap1); 974 975 check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()"); 976 check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()"); 977 check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()"); 978 check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()"); 979 980 mapCopy(g, map2, umap1); 981 mapCopy(g, umap1, map2); 982 mapCopy(ug, map2, umap1); 983 mapCopy(ug, umap1, map2); 984 985 check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()"); 986 mapCopy(ug, umap1, umap2); 987 check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()"); 988 989 check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()"); 990 mapFill(g, map1, 2); 991 check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()"); 992 993 check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()"); 994 mapCopy(g, constMap<Arc>('z'), map2); 995 check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()"); 996 } 997 803 998 return 0; 804 999 }
Note: See TracChangeset
for help on using the changeset viewer.