3762 PotentialDifferenceMap<GR, POT> |
3762 PotentialDifferenceMap<GR, POT> |
3763 potentialDifferenceMap(const GR& gr, const POT& potential) { |
3763 potentialDifferenceMap(const GR& gr, const POT& potential) { |
3764 return PotentialDifferenceMap<GR, POT>(gr, potential); |
3764 return PotentialDifferenceMap<GR, POT>(gr, potential); |
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 } |
3769 |
4056 |
3770 #endif // LEMON_MAPS_H |
4057 #endif // LEMON_MAPS_H |