1.1 --- a/lemon/maps.h Wed Nov 18 14:38:02 2009 +0100
1.2 +++ b/lemon/maps.h Wed Nov 18 14:38:38 2009 +0100
1.3 @@ -3764,6 +3764,293 @@
1.4 return PotentialDifferenceMap<GR, POT>(gr, potential);
1.5 }
1.6
1.7 +
1.8 + /// \brief Copy the values of a graph map to another map.
1.9 + ///
1.10 + /// This function copies the values of a graph map to another graph map.
1.11 + /// \c To::Key must be equal or convertible to \c From::Key and
1.12 + /// \c From::Value must be equal or convertible to \c To::Value.
1.13 + ///
1.14 + /// For example, an edge map of \c int value type can be copied to
1.15 + /// an arc map of \c double value type in an undirected graph, but
1.16 + /// an arc map cannot be copied to an edge map.
1.17 + /// Note that even a \ref ConstMap can be copied to a standard graph map,
1.18 + /// but \ref mapFill() can also be used for this purpose.
1.19 + ///
1.20 + /// \param gr The graph for which the maps are defined.
1.21 + /// \param from The map from which the values have to be copied.
1.22 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.23 + /// \param to The map to which the values have to be copied.
1.24 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.25 + template <typename GR, typename From, typename To>
1.26 + void mapCopy(const GR& gr, const From& from, To& to) {
1.27 + typedef typename To::Key Item;
1.28 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.29 +
1.30 + for (ItemIt it(gr); it != INVALID; ++it) {
1.31 + to.set(it, from[it]);
1.32 + }
1.33 + }
1.34 +
1.35 + /// \brief Compare two graph maps.
1.36 + ///
1.37 + /// This function compares the values of two graph maps. It returns
1.38 + /// \c true if the maps assign the same value for all items in the graph.
1.39 + /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
1.40 + /// and their \c Value types must be comparable using \c %operator==().
1.41 + ///
1.42 + /// \param gr The graph for which the maps are defined.
1.43 + /// \param map1 The first map.
1.44 + /// \param map2 The second map.
1.45 + template <typename GR, typename Map1, typename Map2>
1.46 + bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
1.47 + typedef typename Map2::Key Item;
1.48 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.49 +
1.50 + for (ItemIt it(gr); it != INVALID; ++it) {
1.51 + if (!(map1[it] == map2[it])) return false;
1.52 + }
1.53 + return true;
1.54 + }
1.55 +
1.56 + /// \brief Return an item having minimum value of a graph map.
1.57 + ///
1.58 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.59 + /// minimum value of the given graph map.
1.60 + /// If the item set is empty, it returns \c INVALID.
1.61 + ///
1.62 + /// \param gr The graph for which the map is defined.
1.63 + /// \param map The graph map.
1.64 + template <typename GR, typename Map>
1.65 + typename Map::Key mapMin(const GR& gr, const Map& map) {
1.66 + return mapMin(gr, map, std::less<typename Map::Value>());
1.67 + }
1.68 +
1.69 + /// \brief Return an item having minimum value of a graph map.
1.70 + ///
1.71 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.72 + /// minimum value of the given graph map.
1.73 + /// If the item set is empty, it returns \c INVALID.
1.74 + ///
1.75 + /// \param gr The graph for which the map is defined.
1.76 + /// \param map The graph map.
1.77 + /// \param comp Comparison function object.
1.78 + template <typename GR, typename Map, typename Comp>
1.79 + typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
1.80 + typedef typename Map::Key Item;
1.81 + typedef typename Map::Value Value;
1.82 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.83 +
1.84 + ItemIt min_item(gr);
1.85 + if (min_item == INVALID) return INVALID;
1.86 + Value min = map[min_item];
1.87 + for (ItemIt it(gr); it != INVALID; ++it) {
1.88 + if (comp(map[it], min)) {
1.89 + min = map[it];
1.90 + min_item = it;
1.91 + }
1.92 + }
1.93 + return min_item;
1.94 + }
1.95 +
1.96 + /// \brief Return an item having maximum value of a graph map.
1.97 + ///
1.98 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.99 + /// maximum value of the given graph map.
1.100 + /// If the item set is empty, it returns \c INVALID.
1.101 + ///
1.102 + /// \param gr The graph for which the map is defined.
1.103 + /// \param map The graph map.
1.104 + template <typename GR, typename Map>
1.105 + typename Map::Key mapMax(const GR& gr, const Map& map) {
1.106 + return mapMax(gr, map, std::less<typename Map::Value>());
1.107 + }
1.108 +
1.109 + /// \brief Return an item having maximum value of a graph map.
1.110 + ///
1.111 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.112 + /// maximum value of the given graph map.
1.113 + /// If the item set is empty, it returns \c INVALID.
1.114 + ///
1.115 + /// \param gr The graph for which the map is defined.
1.116 + /// \param map The graph map.
1.117 + /// \param comp Comparison function object.
1.118 + template <typename GR, typename Map, typename Comp>
1.119 + typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
1.120 + typedef typename Map::Key Item;
1.121 + typedef typename Map::Value Value;
1.122 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.123 +
1.124 + ItemIt max_item(gr);
1.125 + if (max_item == INVALID) return INVALID;
1.126 + Value max = map[max_item];
1.127 + for (ItemIt it(gr); it != INVALID; ++it) {
1.128 + if (comp(max, map[it])) {
1.129 + max = map[it];
1.130 + max_item = it;
1.131 + }
1.132 + }
1.133 + return max_item;
1.134 + }
1.135 +
1.136 + /// \brief Return the minimum value of a graph map.
1.137 + ///
1.138 + /// This function returns the minimum value of the given graph map.
1.139 + /// The corresponding item set of the graph must not be empty.
1.140 + ///
1.141 + /// \param gr The graph for which the map is defined.
1.142 + /// \param map The graph map.
1.143 + template <typename GR, typename Map>
1.144 + typename Map::Value mapMinValue(const GR& gr, const Map& map) {
1.145 + return map[mapMin(gr, map, std::less<typename Map::Value>())];
1.146 + }
1.147 +
1.148 + /// \brief Return the minimum value of a graph map.
1.149 + ///
1.150 + /// This function returns the minimum value of the given graph map.
1.151 + /// The corresponding item set of the graph must not be empty.
1.152 + ///
1.153 + /// \param gr The graph for which the map is defined.
1.154 + /// \param map The graph map.
1.155 + /// \param comp Comparison function object.
1.156 + template <typename GR, typename Map, typename Comp>
1.157 + typename Map::Value
1.158 + mapMinValue(const GR& gr, const Map& map, const Comp& comp) {
1.159 + return map[mapMin(gr, map, comp)];
1.160 + }
1.161 +
1.162 + /// \brief Return the maximum value of a graph map.
1.163 + ///
1.164 + /// This function returns the maximum value of the given graph map.
1.165 + /// The corresponding item set of the graph must not be empty.
1.166 + ///
1.167 + /// \param gr The graph for which the map is defined.
1.168 + /// \param map The graph map.
1.169 + template <typename GR, typename Map>
1.170 + typename Map::Value mapMaxValue(const GR& gr, const Map& map) {
1.171 + return map[mapMax(gr, map, std::less<typename Map::Value>())];
1.172 + }
1.173 +
1.174 + /// \brief Return the maximum value of a graph map.
1.175 + ///
1.176 + /// This function returns the maximum value of the given graph map.
1.177 + /// The corresponding item set of the graph must not be empty.
1.178 + ///
1.179 + /// \param gr The graph for which the map is defined.
1.180 + /// \param map The graph map.
1.181 + /// \param comp Comparison function object.
1.182 + template <typename GR, typename Map, typename Comp>
1.183 + typename Map::Value
1.184 + mapMaxValue(const GR& gr, const Map& map, const Comp& comp) {
1.185 + return map[mapMax(gr, map, comp)];
1.186 + }
1.187 +
1.188 + /// \brief Return an item having a specified value in a graph map.
1.189 + ///
1.190 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.191 + /// the specified assigned value in the given graph map.
1.192 + /// If no such item exists, it returns \c INVALID.
1.193 + ///
1.194 + /// \param gr The graph for which the map is defined.
1.195 + /// \param map The graph map.
1.196 + /// \param val The value that have to be found.
1.197 + template <typename GR, typename Map>
1.198 + typename Map::Key
1.199 + mapFind(const GR& gr, const Map& map, const typename Map::Value& val) {
1.200 + typedef typename Map::Key Item;
1.201 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.202 +
1.203 + for (ItemIt it(gr); it != INVALID; ++it) {
1.204 + if (map[it] == val) return it;
1.205 + }
1.206 + return INVALID;
1.207 + }
1.208 +
1.209 + /// \brief Return an item having value for which a certain predicate is
1.210 + /// true in a graph map.
1.211 + ///
1.212 + /// This function returns an item (\c Node, \c Arc or \c Edge) having
1.213 + /// such assigned value for which the specified predicate is true
1.214 + /// in the given graph map.
1.215 + /// If no such item exists, it returns \c INVALID.
1.216 + ///
1.217 + /// \param gr The graph for which the map is defined.
1.218 + /// \param map The graph map.
1.219 + /// \param pred The predicate function object.
1.220 + template <typename GR, typename Map, typename Pred>
1.221 + typename Map::Key
1.222 + mapFindIf(const GR& gr, const Map& map, const Pred& pred) {
1.223 + typedef typename Map::Key Item;
1.224 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.225 +
1.226 + for (ItemIt it(gr); it != INVALID; ++it) {
1.227 + if (pred(map[it])) return it;
1.228 + }
1.229 + return INVALID;
1.230 + }
1.231 +
1.232 + /// \brief Return the number of items having a specified value in a
1.233 + /// graph map.
1.234 + ///
1.235 + /// This function returns the number of items (\c Node, \c Arc or \c Edge)
1.236 + /// having the specified assigned value in the given graph map.
1.237 + ///
1.238 + /// \param gr The graph for which the map is defined.
1.239 + /// \param map The graph map.
1.240 + /// \param val The value that have to be counted.
1.241 + template <typename GR, typename Map>
1.242 + int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) {
1.243 + typedef typename Map::Key Item;
1.244 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.245 +
1.246 + int cnt = 0;
1.247 + for (ItemIt it(gr); it != INVALID; ++it) {
1.248 + if (map[it] == val) ++cnt;
1.249 + }
1.250 + return cnt;
1.251 + }
1.252 +
1.253 + /// \brief Return the number of items having values for which a certain
1.254 + /// predicate is true in a graph map.
1.255 + ///
1.256 + /// This function returns the number of items (\c Node, \c Arc or \c Edge)
1.257 + /// having such assigned values for which the specified predicate is true
1.258 + /// in the given graph map.
1.259 + ///
1.260 + /// \param gr The graph for which the map is defined.
1.261 + /// \param map The graph map.
1.262 + /// \param pred The predicate function object.
1.263 + template <typename GR, typename Map, typename Pred>
1.264 + int mapCountIf(const GR& gr, const Map& map, const Pred& pred) {
1.265 + typedef typename Map::Key Item;
1.266 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.267 +
1.268 + int cnt = 0;
1.269 + for (ItemIt it(gr); it != INVALID; ++it) {
1.270 + if (pred(map[it])) ++cnt;
1.271 + }
1.272 + return cnt;
1.273 + }
1.274 +
1.275 + /// \brief Fill a graph map with a certain value.
1.276 + ///
1.277 + /// This function sets the specified value for all items (\c Node,
1.278 + /// \c Arc or \c Edge) in the given graph map.
1.279 + ///
1.280 + /// \param gr The graph for which the map is defined.
1.281 + /// \param map The graph map. It must conform to the
1.282 + /// \ref concepts::WriteMap "WriteMap" concept.
1.283 + /// \param val The value.
1.284 + template <typename GR, typename Map>
1.285 + void mapFill(const GR& gr, Map& map, const typename Map::Value& val) {
1.286 + typedef typename Map::Key Item;
1.287 + typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
1.288 +
1.289 + for (ItemIt it(gr); it != INVALID; ++it) {
1.290 + map.set(it, val);
1.291 + }
1.292 + }
1.293 +
1.294 /// @}
1.295 }
1.296