diff --git a/lemon/maps.h b/lemon/maps.h --- a/lemon/maps.h +++ b/lemon/maps.h @@ -1847,411 +1847,6 @@ }; - - /// \brief General invertable graph-map type. - - /// This type provides simple invertable graph-maps. - /// The InvertableMap wraps an arbitrary ReadWriteMap - /// and if a key is set to a new value then store it - /// in the inverse map. - /// - /// The values of the map can be accessed - /// with stl compatible forward iterator. - /// - /// \tparam _Graph The graph type. - /// \tparam _Item The item type of the graph. - /// \tparam _Value The value type of the map. - /// - /// \see IterableValueMap - template - class InvertableMap - : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type { - private: - - typedef typename ItemSetTraits<_Graph, _Item>:: - template Map<_Value>::Type Map; - typedef _Graph Graph; - - typedef std::map<_Value, _Item> Container; - Container _inv_map; - - public: - - /// The key type of InvertableMap (Node, Arc, Edge). - typedef typename Map::Key Key; - /// The value type of the InvertableMap. - typedef typename Map::Value Value; - - - - /// \brief Constructor. - /// - /// Construct a new InvertableMap for the graph. - /// - explicit InvertableMap(const Graph& graph) : Map(graph) {} - - /// \brief Forward iterator for values. - /// - /// This iterator is an stl compatible forward - /// iterator on the values of the map. The values can - /// be accessed in the [beginValue, endValue) range. - /// - class ValueIterator - : public std::iterator { - friend class InvertableMap; - private: - ValueIterator(typename Container::const_iterator _it) - : it(_it) {} - public: - - ValueIterator() {} - - ValueIterator& operator++() { ++it; return *this; } - ValueIterator operator++(int) { - ValueIterator tmp(*this); - operator++(); - return tmp; - } - - const Value& operator*() const { return it->first; } - const Value* operator->() const { return &(it->first); } - - bool operator==(ValueIterator jt) const { return it == jt.it; } - bool operator!=(ValueIterator jt) const { return it != jt.it; } - - private: - typename Container::const_iterator it; - }; - - /// \brief Returns an iterator to the first value. - /// - /// Returns an stl compatible iterator to the - /// first value of the map. The values of the - /// map can be accessed in the [beginValue, endValue) - /// range. - ValueIterator beginValue() const { - return ValueIterator(_inv_map.begin()); - } - - /// \brief Returns an iterator after the last value. - /// - /// Returns an stl compatible iterator after the - /// last value of the map. The values of the - /// map can be accessed in the [beginValue, endValue) - /// range. - ValueIterator endValue() const { - return ValueIterator(_inv_map.end()); - } - - /// \brief The setter function of the map. - /// - /// Sets the mapped value. - void set(const Key& key, const Value& val) { - Value oldval = Map::operator[](key); - typename Container::iterator it = _inv_map.find(oldval); - if (it != _inv_map.end() && it->second == key) { - _inv_map.erase(it); - } - _inv_map.insert(make_pair(val, key)); - Map::set(key, val); - } - - /// \brief The getter function of the map. - /// - /// It gives back the value associated with the key. - typename MapTraits::ConstReturnValue - operator[](const Key& key) const { - return Map::operator[](key); - } - - /// \brief Gives back the item by its value. - /// - /// Gives back the item by its value. - Key operator()(const Value& key) const { - typename Container::const_iterator it = _inv_map.find(key); - return it != _inv_map.end() ? it->second : INVALID; - } - - protected: - - /// \brief Erase the key from the map. - /// - /// Erase the key to the map. It is called by the - /// \c AlterationNotifier. - virtual void erase(const Key& key) { - Value val = Map::operator[](key); - typename Container::iterator it = _inv_map.find(val); - if (it != _inv_map.end() && it->second == key) { - _inv_map.erase(it); - } - Map::erase(key); - } - - /// \brief Erase more keys from the map. - /// - /// Erase more keys from the map. It is called by the - /// \c AlterationNotifier. - virtual void erase(const std::vector& keys) { - for (int i = 0; i < int(keys.size()); ++i) { - Value val = Map::operator[](keys[i]); - typename Container::iterator it = _inv_map.find(val); - if (it != _inv_map.end() && it->second == keys[i]) { - _inv_map.erase(it); - } - } - Map::erase(keys); - } - - /// \brief Clear the keys from the map and inverse map. - /// - /// Clear the keys from the map and inverse map. It is called by the - /// \c AlterationNotifier. - virtual void clear() { - _inv_map.clear(); - Map::clear(); - } - - public: - - /// \brief The inverse map type. - /// - /// The inverse of this map. The subscript operator of the map - /// gives back always the item what was last assigned to the value. - class InverseMap { - public: - /// \brief Constructor of the InverseMap. - /// - /// Constructor of the InverseMap. - explicit InverseMap(const InvertableMap& inverted) - : _inverted(inverted) {} - - /// The value type of the InverseMap. - typedef typename InvertableMap::Key Value; - /// The key type of the InverseMap. - typedef typename InvertableMap::Value Key; - - /// \brief Subscript operator. - /// - /// Subscript operator. It gives back always the item - /// what was last assigned to the value. - Value operator[](const Key& key) const { - return _inverted(key); - } - - private: - const InvertableMap& _inverted; - }; - - /// \brief It gives back the just readable inverse map. - /// - /// It gives back the just readable inverse map. - InverseMap inverse() const { - return InverseMap(*this); - } - - - - }; - - /// \brief Provides a mutable, continuous and unique descriptor for each - /// item in the graph. - /// - /// The DescriptorMap class provides a unique and continuous (but mutable) - /// descriptor (id) for each item of the same type (e.g. node) in the - /// graph. This id is
  • \b unique: different items (nodes) get - /// different ids
  • \b continuous: the range of the ids is the set of - /// integers between 0 and \c n-1, where \c n is the number of the items of - /// this type (e.g. nodes) (so the id of a node can change if you delete an - /// other node, i.e. this id is mutable).
This map can be inverted - /// with its member class \c InverseMap, or with the \c operator() member. - /// - /// \tparam _Graph The graph class the \c DescriptorMap belongs to. - /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or - /// Edge. - template - class DescriptorMap - : protected ItemSetTraits<_Graph, _Item>::template Map::Type { - - typedef _Item Item; - typedef typename ItemSetTraits<_Graph, _Item>::template Map::Type Map; - - public: - /// The graph class of DescriptorMap. - typedef _Graph Graph; - - /// The key type of DescriptorMap (Node, Arc, Edge). - typedef typename Map::Key Key; - /// The value type of DescriptorMap. - typedef typename Map::Value Value; - - /// \brief Constructor. - /// - /// Constructor for descriptor map. - explicit DescriptorMap(const Graph& _graph) : Map(_graph) { - Item it; - const typename Map::Notifier* nf = Map::notifier(); - for (nf->first(it); it != INVALID; nf->next(it)) { - Map::set(it, _inv_map.size()); - _inv_map.push_back(it); - } - } - - protected: - - /// \brief Add a new key to the map. - /// - /// Add a new key to the map. It is called by the - /// \c AlterationNotifier. - virtual void add(const Item& item) { - Map::add(item); - Map::set(item, _inv_map.size()); - _inv_map.push_back(item); - } - - /// \brief Add more new keys to the map. - /// - /// Add more new keys to the map. It is called by the - /// \c AlterationNotifier. - virtual void add(const std::vector& items) { - Map::add(items); - for (int i = 0; i < int(items.size()); ++i) { - Map::set(items[i], _inv_map.size()); - _inv_map.push_back(items[i]); - } - } - - /// \brief Erase the key from the map. - /// - /// Erase the key from the map. It is called by the - /// \c AlterationNotifier. - virtual void erase(const Item& item) { - Map::set(_inv_map.back(), Map::operator[](item)); - _inv_map[Map::operator[](item)] = _inv_map.back(); - _inv_map.pop_back(); - Map::erase(item); - } - - /// \brief Erase more keys from the map. - /// - /// Erase more keys from the map. It is called by the - /// \c AlterationNotifier. - virtual void erase(const std::vector& items) { - for (int i = 0; i < int(items.size()); ++i) { - Map::set(_inv_map.back(), Map::operator[](items[i])); - _inv_map[Map::operator[](items[i])] = _inv_map.back(); - _inv_map.pop_back(); - } - Map::erase(items); - } - - /// \brief Build the unique map. - /// - /// Build the unique map. It is called by the - /// \c AlterationNotifier. - virtual void build() { - Map::build(); - Item it; - const typename Map::Notifier* nf = Map::notifier(); - for (nf->first(it); it != INVALID; nf->next(it)) { - Map::set(it, _inv_map.size()); - _inv_map.push_back(it); - } - } - - /// \brief Clear the keys from the map. - /// - /// Clear the keys from the map. It is called by the - /// \c AlterationNotifier. - virtual void clear() { - _inv_map.clear(); - Map::clear(); - } - - public: - - /// \brief Returns the maximal value plus one. - /// - /// Returns the maximal value plus one in the map. - unsigned int size() const { - return _inv_map.size(); - } - - /// \brief Swaps the position of the two items in the map. - /// - /// Swaps the position of the two items in the map. - void swap(const Item& p, const Item& q) { - int pi = Map::operator[](p); - int qi = Map::operator[](q); - Map::set(p, qi); - _inv_map[qi] = p; - Map::set(q, pi); - _inv_map[pi] = q; - } - - /// \brief Gives back the \e descriptor of the item. - /// - /// Gives back the mutable and unique \e descriptor of the map. - int operator[](const Item& item) const { - return Map::operator[](item); - } - - /// \brief Gives back the item by its descriptor. - /// - /// Gives back th item by its descriptor. - Item operator()(int id) const { - return _inv_map[id]; - } - - private: - - typedef std::vector Container; - Container _inv_map; - - public: - /// \brief The inverse map type of DescriptorMap. - /// - /// The inverse map type of DescriptorMap. - class InverseMap { - public: - /// \brief Constructor of the InverseMap. - /// - /// Constructor of the InverseMap. - explicit InverseMap(const DescriptorMap& inverted) - : _inverted(inverted) {} - - - /// The value type of the InverseMap. - typedef typename DescriptorMap::Key Value; - /// The key type of the InverseMap. - typedef typename DescriptorMap::Value Key; - - /// \brief Subscript operator. - /// - /// Subscript operator. It gives back the item - /// that the descriptor belongs to currently. - Value operator[](const Key& key) const { - return _inverted(key); - } - - /// \brief Size of the map. - /// - /// Returns the size of the map. - unsigned int size() const { - return _inverted.size(); - } - - private: - const DescriptorMap& _inverted; - }; - - /// \brief Gives back the inverse of the map. - /// - /// Gives back the inverse of the map. - const InverseMap inverse() const { - return InverseMap(*this); - } - }; - /// \brief Returns the source of the given arc. /// /// The SourceMap gives back the source Node of the given arc. diff --git a/test/graph_utils_test.cc b/test/graph_utils_test.cc --- a/test/graph_utils_test.cc +++ b/test/graph_utils_test.cc @@ -35,18 +35,18 @@ { Digraph digraph; + typename Digraph::template NodeMap nodes(digraph); + std::vector invNodes; for (int i = 0; i < 10; ++i) { - digraph.addNode(); + invNodes.push_back(digraph.addNode()); + nodes[invNodes.back()]=invNodes.size()-1; } - DescriptorMap nodes(digraph); - typename DescriptorMap::InverseMap invNodes(nodes); for (int i = 0; i < 100; ++i) { int src = rnd[invNodes.size()]; int trg = rnd[invNodes.size()]; digraph.addArc(invNodes[src], invNodes[trg]); } typename Digraph::template ArcMap found(digraph, false); - DescriptorMap arcs(digraph); for (NodeIt src(digraph); src != INVALID; ++src) { for (NodeIt trg(digraph); trg != INVALID; ++trg) { for (ConArcIt con(digraph, src, trg); con != INVALID; ++con) { @@ -110,18 +110,18 @@ void checkFindEdges() { TEMPLATE_GRAPH_TYPEDEFS(Graph); Graph graph; + typename Graph::template NodeMap nodes(graph); + std::vector invNodes; for (int i = 0; i < 10; ++i) { - graph.addNode(); + invNodes.push_back(graph.addNode()); + nodes[invNodes.back()]=invNodes.size()-1; } - DescriptorMap nodes(graph); - typename DescriptorMap::InverseMap invNodes(nodes); for (int i = 0; i < 100; ++i) { int src = rnd[invNodes.size()]; int trg = rnd[invNodes.size()]; graph.addEdge(invNodes[src], invNodes[trg]); } typename Graph::template EdgeMap found(graph, 0); - DescriptorMap edges(graph); for (NodeIt src(graph); src != INVALID; ++src) { for (NodeIt trg(graph); trg != INVALID; ++trg) { for (ConEdgeIt con(graph, src, trg); con != INVALID; ++con) {