Changeset 836:8ddb7deabab9 in lemon for lemon/maps.h
- Timestamp:
- 11/13/09 12:47:13 (14 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r773 r836 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 }
Note: See TracChangeset
for help on using the changeset viewer.