# Changeset 839:a2d5fd4c309a in lemon

Ignore:
Timestamp:
11/18/09 14:38:38 (11 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
Message:

Merge

Files:
2 edited

Unmodified
Added
Removed
• ## lemon/maps.h

 r833 } /// \brief Copy the values of a graph map to another map. /// /// This function copies the values of a graph map to another graph map. /// \c To::Key must be equal or convertible to \c From::Key and /// \c From::Value must be equal or convertible to \c To::Value. /// /// For example, an edge map of \c int value type can be copied to /// an arc map of \c double value type in an undirected graph, but /// an arc map cannot be copied to an edge map. /// Note that even a \ref ConstMap can be copied to a standard graph map, /// but \ref mapFill() can also be used for this purpose. /// /// \param gr The graph for which the maps are defined. /// \param from The map from which the values have to be copied. /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. /// \param to The map to which the values have to be copied. /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. template void mapCopy(const GR& gr, const From& from, To& to) { typedef typename To::Key Item; typedef typename ItemSetTraits::ItemIt ItemIt; for (ItemIt it(gr); it != INVALID; ++it) { to.set(it, from[it]); } } /// \brief Compare two graph maps. /// /// This function compares the values of two graph maps. It returns /// \c true if the maps assign the same value for all items in the graph. /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal /// and their \c Value types must be comparable using \c %operator==(). /// /// \param gr The graph for which the maps are defined. /// \param map1 The first map. /// \param map2 The second map. template bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) { typedef typename Map2::Key Item; typedef typename ItemSetTraits::ItemIt ItemIt; for (ItemIt it(gr); it != INVALID; ++it) { if (!(map1[it] == map2[it])) return false; } return true; } /// \brief Return an item having minimum value of a graph map. /// /// This function returns an item (\c Node, \c Arc or \c Edge) having /// minimum value of the given graph map. /// If the item set is empty, it returns \c INVALID. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. template typename Map::Key mapMin(const GR& gr, const Map& map) { return mapMin(gr, map, std::less()); } /// \brief Return an item having minimum value of a graph map. /// /// This function returns an item (\c Node, \c Arc or \c Edge) having /// minimum value of the given graph map. /// If the item set is empty, it returns \c INVALID. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. /// \param comp Comparison function object. template typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) { typedef typename Map::Key Item; typedef typename Map::Value Value; typedef typename ItemSetTraits::ItemIt ItemIt; ItemIt min_item(gr); if (min_item == INVALID) return INVALID; Value min = map[min_item]; for (ItemIt it(gr); it != INVALID; ++it) { if (comp(map[it], min)) { min = map[it]; min_item = it; } } return min_item; } /// \brief Return an item having maximum value of a graph map. /// /// This function returns an item (\c Node, \c Arc or \c Edge) having /// maximum value of the given graph map. /// If the item set is empty, it returns \c INVALID. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. template typename Map::Key mapMax(const GR& gr, const Map& map) { return mapMax(gr, map, std::less()); } /// \brief Return an item having maximum value of a graph map. /// /// This function returns an item (\c Node, \c Arc or \c Edge) having /// maximum value of the given graph map. /// If the item set is empty, it returns \c INVALID. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. /// \param comp Comparison function object. template typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) { typedef typename Map::Key Item; typedef typename Map::Value Value; typedef typename ItemSetTraits::ItemIt ItemIt; ItemIt max_item(gr); if (max_item == INVALID) return INVALID; Value max = map[max_item]; for (ItemIt it(gr); it != INVALID; ++it) { if (comp(max, map[it])) { max = map[it]; max_item = it; } } return max_item; } /// \brief Return the minimum value of a graph map. /// /// This function returns the minimum value of the given graph map. /// The corresponding item set of the graph must not be empty. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. template typename Map::Value mapMinValue(const GR& gr, const Map& map) { return map[mapMin(gr, map, std::less())]; } /// \brief Return the minimum value of a graph map. /// /// This function returns the minimum value of the given graph map. /// The corresponding item set of the graph must not be empty. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. /// \param comp Comparison function object. template typename Map::Value mapMinValue(const GR& gr, const Map& map, const Comp& comp) { return map[mapMin(gr, map, comp)]; } /// \brief Return the maximum value of a graph map. /// /// This function returns the maximum value of the given graph map. /// The corresponding item set of the graph must not be empty. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. template typename Map::Value mapMaxValue(const GR& gr, const Map& map) { return map[mapMax(gr, map, std::less())]; } /// \brief Return the maximum value of a graph map. /// /// This function returns the maximum value of the given graph map. /// The corresponding item set of the graph must not be empty. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. /// \param comp Comparison function object. template typename Map::Value mapMaxValue(const GR& gr, const Map& map, const Comp& comp) { return map[mapMax(gr, map, comp)]; } /// \brief Return an item having a specified value in a graph map. /// /// This function returns an item (\c Node, \c Arc or \c Edge) having /// the specified assigned value in the given graph map. /// If no such item exists, it returns \c INVALID. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. /// \param val The value that have to be found. template typename Map::Key mapFind(const GR& gr, const Map& map, const typename Map::Value& val) { typedef typename Map::Key Item; typedef typename ItemSetTraits::ItemIt ItemIt; for (ItemIt it(gr); it != INVALID; ++it) { if (map[it] == val) return it; } return INVALID; } /// \brief Return an item having value for which a certain predicate is /// true in a graph map. /// /// This function returns an item (\c Node, \c Arc or \c Edge) having /// such assigned value for which the specified predicate is true /// in the given graph map. /// If no such item exists, it returns \c INVALID. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. /// \param pred The predicate function object. template typename Map::Key mapFindIf(const GR& gr, const Map& map, const Pred& pred) { typedef typename Map::Key Item; typedef typename ItemSetTraits::ItemIt ItemIt; for (ItemIt it(gr); it != INVALID; ++it) { if (pred(map[it])) return it; } return INVALID; } /// \brief Return the number of items having a specified value in a /// graph map. /// /// This function returns the number of items (\c Node, \c Arc or \c Edge) /// having the specified assigned value in the given graph map. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. /// \param val The value that have to be counted. template int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) { typedef typename Map::Key Item; typedef typename ItemSetTraits::ItemIt ItemIt; int cnt = 0; for (ItemIt it(gr); it != INVALID; ++it) { if (map[it] == val) ++cnt; } return cnt; } /// \brief Return the number of items having values for which a certain /// predicate is true in a graph map. /// /// This function returns the number of items (\c Node, \c Arc or \c Edge) /// having such assigned values for which the specified predicate is true /// in the given graph map. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. /// \param pred The predicate function object. template int mapCountIf(const GR& gr, const Map& map, const Pred& pred) { typedef typename Map::Key Item; typedef typename ItemSetTraits::ItemIt ItemIt; int cnt = 0; for (ItemIt it(gr); it != INVALID; ++it) { if (pred(map[it])) ++cnt; } return cnt; } /// \brief Fill a graph map with a certain value. /// /// This function sets the specified value for all items (\c Node, /// \c Arc or \c Edge) in the given graph map. /// /// \param gr The graph for which the map is defined. /// \param map The graph map. It must conform to the /// \ref concepts::WriteMap "WriteMap" concept. /// \param val The value. template void mapFill(const GR& gr, Map& map, const typename Map::Value& val) { typedef typename Map::Key Item; typedef typename ItemSetTraits::ItemIt ItemIt; for (ItemIt it(gr); it != INVALID; ++it) { map.set(it, val); } } /// @} }
• ## lemon/maps.h

 r836 /// This map is essentially a wrapper for \c std::vector. It assigns /// values to integer keys from the range [0..size-1]. /// It can be used with some data structures, for example /// \c UnionFind, \c BinHeap, when the used items are small /// It can be used together with some data structures, e.g. /// heap types and \c UnionFind, when the used items are small /// integers. This map conforms to the \ref concepts::ReferenceMap /// "ReferenceMap" concept. /// "ReferenceMap" concept. /// /// The simplest way of using this map is through the rangeMap() /// The name of this type also refers to this important usage. /// /// Apart form that this map can be used in many other cases since it /// Apart form that, this map can be used in many other cases since it /// is based on \c std::map, which is a general associative container. /// However keep in mind that it is usually not as efficient as other /// However, keep in mind that it is usually not as efficient as other /// maps. /// /// The most important usage of it is storing certain nodes or arcs /// that were marked \c true by an algorithm. /// For example it makes easier to store the nodes in the processing /// For example, it makes easier to store the nodes in the processing /// order of Dfs algorithm, as the following examples show. /// \code /// /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so /// it cannot be used when a readable map is needed, for example as /// it cannot be used when a readable map is needed, for example, as /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms. /// /// Otherwise consider to use \c IterableValueMap, which is more /// suitable and more efficient for such cases. It provides iterators /// to traverse the items with the same associated value, however /// to traverse the items with the same associated value, but /// it does not have \c InverseMap. /// /// may provide alternative ways to modify the digraph. /// The correct behavior of InDegMap is not guarantied if these additional /// features are used. For example the functions /// features are used. For example, the functions /// \ref ListDigraph::changeSource() "changeSource()", /// \ref ListDigraph::changeTarget() "changeTarget()" and /// may provide alternative ways to modify the digraph. /// The correct behavior of OutDegMap is not guarantied if these additional /// features are used. For example the functions /// features are used. For example, the functions /// \ref ListDigraph::changeSource() "changeSource()", /// \ref ListDigraph::changeTarget() "changeTarget()" and
Note: See TracChangeset for help on using the changeset viewer.