Changeset 839:a2d5fd4c309a in lemon for lemon/maps.h
 Timestamp:
 11/18/09 14:38:38 (13 years ago)
 Branch:
 default
 Children:
 840:7c0ad6bd6a63, 859:921d5bf41ac2
 Parents:
 835:c92296660262 (diff), 838:4e3484a2e90c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/maps.h
r833 r839 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 } 
lemon/maps.h
r836 r839 231 231 /// This map is essentially a wrapper for \c std::vector. It assigns 232 232 /// values to integer keys from the range <tt>[0..size1]</tt>. 233 /// It can be used with some data structures, for example234 /// \c UnionFind, \c BinHeap, when the used items are small233 /// It can be used together with some data structures, e.g. 234 /// heap types and \c UnionFind, when the used items are small 235 235 /// integers. This map conforms to the \ref concepts::ReferenceMap 236 /// "ReferenceMap" concept. 236 /// "ReferenceMap" concept. 237 237 /// 238 238 /// The simplest way of using this map is through the rangeMap() … … 349 349 /// The name of this type also refers to this important usage. 350 350 /// 351 /// Apart form that this map can be used in many other cases since it351 /// Apart form that, this map can be used in many other cases since it 352 352 /// is based on \c std::map, which is a general associative container. 353 /// However keep in mind that it is usually not as efficient as other353 /// However, keep in mind that it is usually not as efficient as other 354 354 /// maps. 355 355 /// … … 1786 1786 /// The most important usage of it is storing certain nodes or arcs 1787 1787 /// that were marked \c true by an algorithm. 1788 /// For example it makes easier to store the nodes in the processing1788 /// For example, it makes easier to store the nodes in the processing 1789 1789 /// order of Dfs algorithm, as the following examples show. 1790 1790 /// \code … … 1801 1801 /// 1802 1802 /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so 1803 /// it cannot be used when a readable map is needed, for example as1803 /// it cannot be used when a readable map is needed, for example, as 1804 1804 /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms. 1805 1805 /// … … 1923 1923 /// Otherwise consider to use \c IterableValueMap, which is more 1924 1924 /// suitable and more efficient for such cases. It provides iterators 1925 /// to traverse the items with the same associated value, however1925 /// to traverse the items with the same associated value, but 1926 1926 /// it does not have \c InverseMap. 1927 1927 /// … … 3467 3467 /// may provide alternative ways to modify the digraph. 3468 3468 /// The correct behavior of InDegMap is not guarantied if these additional 3469 /// features are used. For example the functions3469 /// features are used. For example, the functions 3470 3470 /// \ref ListDigraph::changeSource() "changeSource()", 3471 3471 /// \ref ListDigraph::changeTarget() "changeTarget()" and … … 3597 3597 /// may provide alternative ways to modify the digraph. 3598 3598 /// The correct behavior of OutDegMap is not guarantied if these additional 3599 /// features are used. For example the functions3599 /// features are used. For example, the functions 3600 3600 /// \ref ListDigraph::changeSource() "changeSource()", 3601 3601 /// \ref ListDigraph::changeTarget() "changeTarget()" and
Note: See TracChangeset
for help on using the changeset viewer.