1.1 --- a/lemon/maps.h Wed Oct 08 10:33:42 2008 +0100
1.2 +++ b/lemon/maps.h Wed Oct 08 12:25:57 2008 +0100
1.3 @@ -1847,411 +1847,6 @@
1.4
1.5 };
1.6
1.7 -
1.8 - /// \brief General invertable graph-map type.
1.9 -
1.10 - /// This type provides simple invertable graph-maps.
1.11 - /// The InvertableMap wraps an arbitrary ReadWriteMap
1.12 - /// and if a key is set to a new value then store it
1.13 - /// in the inverse map.
1.14 - ///
1.15 - /// The values of the map can be accessed
1.16 - /// with stl compatible forward iterator.
1.17 - ///
1.18 - /// \tparam _Graph The graph type.
1.19 - /// \tparam _Item The item type of the graph.
1.20 - /// \tparam _Value The value type of the map.
1.21 - ///
1.22 - /// \see IterableValueMap
1.23 - template <typename _Graph, typename _Item, typename _Value>
1.24 - class InvertableMap
1.25 - : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
1.26 - private:
1.27 -
1.28 - typedef typename ItemSetTraits<_Graph, _Item>::
1.29 - template Map<_Value>::Type Map;
1.30 - typedef _Graph Graph;
1.31 -
1.32 - typedef std::map<_Value, _Item> Container;
1.33 - Container _inv_map;
1.34 -
1.35 - public:
1.36 -
1.37 - /// The key type of InvertableMap (Node, Arc, Edge).
1.38 - typedef typename Map::Key Key;
1.39 - /// The value type of the InvertableMap.
1.40 - typedef typename Map::Value Value;
1.41 -
1.42 -
1.43 -
1.44 - /// \brief Constructor.
1.45 - ///
1.46 - /// Construct a new InvertableMap for the graph.
1.47 - ///
1.48 - explicit InvertableMap(const Graph& graph) : Map(graph) {}
1.49 -
1.50 - /// \brief Forward iterator for values.
1.51 - ///
1.52 - /// This iterator is an stl compatible forward
1.53 - /// iterator on the values of the map. The values can
1.54 - /// be accessed in the [beginValue, endValue) range.
1.55 - ///
1.56 - class ValueIterator
1.57 - : public std::iterator<std::forward_iterator_tag, Value> {
1.58 - friend class InvertableMap;
1.59 - private:
1.60 - ValueIterator(typename Container::const_iterator _it)
1.61 - : it(_it) {}
1.62 - public:
1.63 -
1.64 - ValueIterator() {}
1.65 -
1.66 - ValueIterator& operator++() { ++it; return *this; }
1.67 - ValueIterator operator++(int) {
1.68 - ValueIterator tmp(*this);
1.69 - operator++();
1.70 - return tmp;
1.71 - }
1.72 -
1.73 - const Value& operator*() const { return it->first; }
1.74 - const Value* operator->() const { return &(it->first); }
1.75 -
1.76 - bool operator==(ValueIterator jt) const { return it == jt.it; }
1.77 - bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.78 -
1.79 - private:
1.80 - typename Container::const_iterator it;
1.81 - };
1.82 -
1.83 - /// \brief Returns an iterator to the first value.
1.84 - ///
1.85 - /// Returns an stl compatible iterator to the
1.86 - /// first value of the map. The values of the
1.87 - /// map can be accessed in the [beginValue, endValue)
1.88 - /// range.
1.89 - ValueIterator beginValue() const {
1.90 - return ValueIterator(_inv_map.begin());
1.91 - }
1.92 -
1.93 - /// \brief Returns an iterator after the last value.
1.94 - ///
1.95 - /// Returns an stl compatible iterator after the
1.96 - /// last value of the map. The values of the
1.97 - /// map can be accessed in the [beginValue, endValue)
1.98 - /// range.
1.99 - ValueIterator endValue() const {
1.100 - return ValueIterator(_inv_map.end());
1.101 - }
1.102 -
1.103 - /// \brief The setter function of the map.
1.104 - ///
1.105 - /// Sets the mapped value.
1.106 - void set(const Key& key, const Value& val) {
1.107 - Value oldval = Map::operator[](key);
1.108 - typename Container::iterator it = _inv_map.find(oldval);
1.109 - if (it != _inv_map.end() && it->second == key) {
1.110 - _inv_map.erase(it);
1.111 - }
1.112 - _inv_map.insert(make_pair(val, key));
1.113 - Map::set(key, val);
1.114 - }
1.115 -
1.116 - /// \brief The getter function of the map.
1.117 - ///
1.118 - /// It gives back the value associated with the key.
1.119 - typename MapTraits<Map>::ConstReturnValue
1.120 - operator[](const Key& key) const {
1.121 - return Map::operator[](key);
1.122 - }
1.123 -
1.124 - /// \brief Gives back the item by its value.
1.125 - ///
1.126 - /// Gives back the item by its value.
1.127 - Key operator()(const Value& key) const {
1.128 - typename Container::const_iterator it = _inv_map.find(key);
1.129 - return it != _inv_map.end() ? it->second : INVALID;
1.130 - }
1.131 -
1.132 - protected:
1.133 -
1.134 - /// \brief Erase the key from the map.
1.135 - ///
1.136 - /// Erase the key to the map. It is called by the
1.137 - /// \c AlterationNotifier.
1.138 - virtual void erase(const Key& key) {
1.139 - Value val = Map::operator[](key);
1.140 - typename Container::iterator it = _inv_map.find(val);
1.141 - if (it != _inv_map.end() && it->second == key) {
1.142 - _inv_map.erase(it);
1.143 - }
1.144 - Map::erase(key);
1.145 - }
1.146 -
1.147 - /// \brief Erase more keys from the map.
1.148 - ///
1.149 - /// Erase more keys from the map. It is called by the
1.150 - /// \c AlterationNotifier.
1.151 - virtual void erase(const std::vector<Key>& keys) {
1.152 - for (int i = 0; i < int(keys.size()); ++i) {
1.153 - Value val = Map::operator[](keys[i]);
1.154 - typename Container::iterator it = _inv_map.find(val);
1.155 - if (it != _inv_map.end() && it->second == keys[i]) {
1.156 - _inv_map.erase(it);
1.157 - }
1.158 - }
1.159 - Map::erase(keys);
1.160 - }
1.161 -
1.162 - /// \brief Clear the keys from the map and inverse map.
1.163 - ///
1.164 - /// Clear the keys from the map and inverse map. It is called by the
1.165 - /// \c AlterationNotifier.
1.166 - virtual void clear() {
1.167 - _inv_map.clear();
1.168 - Map::clear();
1.169 - }
1.170 -
1.171 - public:
1.172 -
1.173 - /// \brief The inverse map type.
1.174 - ///
1.175 - /// The inverse of this map. The subscript operator of the map
1.176 - /// gives back always the item what was last assigned to the value.
1.177 - class InverseMap {
1.178 - public:
1.179 - /// \brief Constructor of the InverseMap.
1.180 - ///
1.181 - /// Constructor of the InverseMap.
1.182 - explicit InverseMap(const InvertableMap& inverted)
1.183 - : _inverted(inverted) {}
1.184 -
1.185 - /// The value type of the InverseMap.
1.186 - typedef typename InvertableMap::Key Value;
1.187 - /// The key type of the InverseMap.
1.188 - typedef typename InvertableMap::Value Key;
1.189 -
1.190 - /// \brief Subscript operator.
1.191 - ///
1.192 - /// Subscript operator. It gives back always the item
1.193 - /// what was last assigned to the value.
1.194 - Value operator[](const Key& key) const {
1.195 - return _inverted(key);
1.196 - }
1.197 -
1.198 - private:
1.199 - const InvertableMap& _inverted;
1.200 - };
1.201 -
1.202 - /// \brief It gives back the just readable inverse map.
1.203 - ///
1.204 - /// It gives back the just readable inverse map.
1.205 - InverseMap inverse() const {
1.206 - return InverseMap(*this);
1.207 - }
1.208 -
1.209 -
1.210 -
1.211 - };
1.212 -
1.213 - /// \brief Provides a mutable, continuous and unique descriptor for each
1.214 - /// item in the graph.
1.215 - ///
1.216 - /// The DescriptorMap class provides a unique and continuous (but mutable)
1.217 - /// descriptor (id) for each item of the same type (e.g. node) in the
1.218 - /// graph. This id is <ul><li>\b unique: different items (nodes) get
1.219 - /// different ids <li>\b continuous: the range of the ids is the set of
1.220 - /// integers between 0 and \c n-1, where \c n is the number of the items of
1.221 - /// this type (e.g. nodes) (so the id of a node can change if you delete an
1.222 - /// other node, i.e. this id is mutable). </ul> This map can be inverted
1.223 - /// with its member class \c InverseMap, or with the \c operator() member.
1.224 - ///
1.225 - /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
1.226 - /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
1.227 - /// Edge.
1.228 - template <typename _Graph, typename _Item>
1.229 - class DescriptorMap
1.230 - : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
1.231 -
1.232 - typedef _Item Item;
1.233 - typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
1.234 -
1.235 - public:
1.236 - /// The graph class of DescriptorMap.
1.237 - typedef _Graph Graph;
1.238 -
1.239 - /// The key type of DescriptorMap (Node, Arc, Edge).
1.240 - typedef typename Map::Key Key;
1.241 - /// The value type of DescriptorMap.
1.242 - typedef typename Map::Value Value;
1.243 -
1.244 - /// \brief Constructor.
1.245 - ///
1.246 - /// Constructor for descriptor map.
1.247 - explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1.248 - Item it;
1.249 - const typename Map::Notifier* nf = Map::notifier();
1.250 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.251 - Map::set(it, _inv_map.size());
1.252 - _inv_map.push_back(it);
1.253 - }
1.254 - }
1.255 -
1.256 - protected:
1.257 -
1.258 - /// \brief Add a new key to the map.
1.259 - ///
1.260 - /// Add a new key to the map. It is called by the
1.261 - /// \c AlterationNotifier.
1.262 - virtual void add(const Item& item) {
1.263 - Map::add(item);
1.264 - Map::set(item, _inv_map.size());
1.265 - _inv_map.push_back(item);
1.266 - }
1.267 -
1.268 - /// \brief Add more new keys to the map.
1.269 - ///
1.270 - /// Add more new keys to the map. It is called by the
1.271 - /// \c AlterationNotifier.
1.272 - virtual void add(const std::vector<Item>& items) {
1.273 - Map::add(items);
1.274 - for (int i = 0; i < int(items.size()); ++i) {
1.275 - Map::set(items[i], _inv_map.size());
1.276 - _inv_map.push_back(items[i]);
1.277 - }
1.278 - }
1.279 -
1.280 - /// \brief Erase the key from the map.
1.281 - ///
1.282 - /// Erase the key from the map. It is called by the
1.283 - /// \c AlterationNotifier.
1.284 - virtual void erase(const Item& item) {
1.285 - Map::set(_inv_map.back(), Map::operator[](item));
1.286 - _inv_map[Map::operator[](item)] = _inv_map.back();
1.287 - _inv_map.pop_back();
1.288 - Map::erase(item);
1.289 - }
1.290 -
1.291 - /// \brief Erase more keys from the map.
1.292 - ///
1.293 - /// Erase more keys from the map. It is called by the
1.294 - /// \c AlterationNotifier.
1.295 - virtual void erase(const std::vector<Item>& items) {
1.296 - for (int i = 0; i < int(items.size()); ++i) {
1.297 - Map::set(_inv_map.back(), Map::operator[](items[i]));
1.298 - _inv_map[Map::operator[](items[i])] = _inv_map.back();
1.299 - _inv_map.pop_back();
1.300 - }
1.301 - Map::erase(items);
1.302 - }
1.303 -
1.304 - /// \brief Build the unique map.
1.305 - ///
1.306 - /// Build the unique map. It is called by the
1.307 - /// \c AlterationNotifier.
1.308 - virtual void build() {
1.309 - Map::build();
1.310 - Item it;
1.311 - const typename Map::Notifier* nf = Map::notifier();
1.312 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.313 - Map::set(it, _inv_map.size());
1.314 - _inv_map.push_back(it);
1.315 - }
1.316 - }
1.317 -
1.318 - /// \brief Clear the keys from the map.
1.319 - ///
1.320 - /// Clear the keys from the map. It is called by the
1.321 - /// \c AlterationNotifier.
1.322 - virtual void clear() {
1.323 - _inv_map.clear();
1.324 - Map::clear();
1.325 - }
1.326 -
1.327 - public:
1.328 -
1.329 - /// \brief Returns the maximal value plus one.
1.330 - ///
1.331 - /// Returns the maximal value plus one in the map.
1.332 - unsigned int size() const {
1.333 - return _inv_map.size();
1.334 - }
1.335 -
1.336 - /// \brief Swaps the position of the two items in the map.
1.337 - ///
1.338 - /// Swaps the position of the two items in the map.
1.339 - void swap(const Item& p, const Item& q) {
1.340 - int pi = Map::operator[](p);
1.341 - int qi = Map::operator[](q);
1.342 - Map::set(p, qi);
1.343 - _inv_map[qi] = p;
1.344 - Map::set(q, pi);
1.345 - _inv_map[pi] = q;
1.346 - }
1.347 -
1.348 - /// \brief Gives back the \e descriptor of the item.
1.349 - ///
1.350 - /// Gives back the mutable and unique \e descriptor of the map.
1.351 - int operator[](const Item& item) const {
1.352 - return Map::operator[](item);
1.353 - }
1.354 -
1.355 - /// \brief Gives back the item by its descriptor.
1.356 - ///
1.357 - /// Gives back th item by its descriptor.
1.358 - Item operator()(int id) const {
1.359 - return _inv_map[id];
1.360 - }
1.361 -
1.362 - private:
1.363 -
1.364 - typedef std::vector<Item> Container;
1.365 - Container _inv_map;
1.366 -
1.367 - public:
1.368 - /// \brief The inverse map type of DescriptorMap.
1.369 - ///
1.370 - /// The inverse map type of DescriptorMap.
1.371 - class InverseMap {
1.372 - public:
1.373 - /// \brief Constructor of the InverseMap.
1.374 - ///
1.375 - /// Constructor of the InverseMap.
1.376 - explicit InverseMap(const DescriptorMap& inverted)
1.377 - : _inverted(inverted) {}
1.378 -
1.379 -
1.380 - /// The value type of the InverseMap.
1.381 - typedef typename DescriptorMap::Key Value;
1.382 - /// The key type of the InverseMap.
1.383 - typedef typename DescriptorMap::Value Key;
1.384 -
1.385 - /// \brief Subscript operator.
1.386 - ///
1.387 - /// Subscript operator. It gives back the item
1.388 - /// that the descriptor belongs to currently.
1.389 - Value operator[](const Key& key) const {
1.390 - return _inverted(key);
1.391 - }
1.392 -
1.393 - /// \brief Size of the map.
1.394 - ///
1.395 - /// Returns the size of the map.
1.396 - unsigned int size() const {
1.397 - return _inverted.size();
1.398 - }
1.399 -
1.400 - private:
1.401 - const DescriptorMap& _inverted;
1.402 - };
1.403 -
1.404 - /// \brief Gives back the inverse of the map.
1.405 - ///
1.406 - /// Gives back the inverse of the map.
1.407 - const InverseMap inverse() const {
1.408 - return InverseMap(*this);
1.409 - }
1.410 - };
1.411 -
1.412 /// \brief Returns the source of the given arc.
1.413 ///
1.414 /// The SourceMap gives back the source Node of the given arc.
2.1 --- a/test/graph_utils_test.cc Wed Oct 08 10:33:42 2008 +0100
2.2 +++ b/test/graph_utils_test.cc Wed Oct 08 12:25:57 2008 +0100
2.3 @@ -35,18 +35,18 @@
2.4
2.5 {
2.6 Digraph digraph;
2.7 + typename Digraph::template NodeMap<int> nodes(digraph);
2.8 + std::vector<Node> invNodes;
2.9 for (int i = 0; i < 10; ++i) {
2.10 - digraph.addNode();
2.11 + invNodes.push_back(digraph.addNode());
2.12 + nodes[invNodes.back()]=invNodes.size()-1;
2.13 }
2.14 - DescriptorMap<Digraph, Node> nodes(digraph);
2.15 - typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
2.16 for (int i = 0; i < 100; ++i) {
2.17 int src = rnd[invNodes.size()];
2.18 int trg = rnd[invNodes.size()];
2.19 digraph.addArc(invNodes[src], invNodes[trg]);
2.20 }
2.21 typename Digraph::template ArcMap<bool> found(digraph, false);
2.22 - DescriptorMap<Digraph, Arc> arcs(digraph);
2.23 for (NodeIt src(digraph); src != INVALID; ++src) {
2.24 for (NodeIt trg(digraph); trg != INVALID; ++trg) {
2.25 for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
2.26 @@ -110,18 +110,18 @@
2.27 void checkFindEdges() {
2.28 TEMPLATE_GRAPH_TYPEDEFS(Graph);
2.29 Graph graph;
2.30 + typename Graph::template NodeMap<int> nodes(graph);
2.31 + std::vector<Node> invNodes;
2.32 for (int i = 0; i < 10; ++i) {
2.33 - graph.addNode();
2.34 + invNodes.push_back(graph.addNode());
2.35 + nodes[invNodes.back()]=invNodes.size()-1;
2.36 }
2.37 - DescriptorMap<Graph, Node> nodes(graph);
2.38 - typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
2.39 for (int i = 0; i < 100; ++i) {
2.40 int src = rnd[invNodes.size()];
2.41 int trg = rnd[invNodes.size()];
2.42 graph.addEdge(invNodes[src], invNodes[trg]);
2.43 }
2.44 typename Graph::template EdgeMap<int> found(graph, 0);
2.45 - DescriptorMap<Graph, Edge> edges(graph);
2.46 for (NodeIt src(graph); src != INVALID; ++src) {
2.47 for (NodeIt trg(graph); trg != INVALID; ++trg) {
2.48 for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {