COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/maps.h

    r318 r320  
    18561856    InverseMap inverse() const { return InverseMap(*_graph);}
    18571857
    1858   };
    1859 
    1860 
    1861   /// \brief General invertable graph-map type.
    1862 
    1863   /// This type provides simple invertable graph-maps.
    1864   /// The InvertableMap wraps an arbitrary ReadWriteMap
    1865   /// and if a key is set to a new value then store it
    1866   /// in the inverse map.
    1867   ///
    1868   /// The values of the map can be accessed
    1869   /// with stl compatible forward iterator.
    1870   ///
    1871   /// \tparam _Graph The graph type.
    1872   /// \tparam _Item The item type of the graph.
    1873   /// \tparam _Value The value type of the map.
    1874   ///
    1875   /// \see IterableValueMap
    1876   template <typename _Graph, typename _Item, typename _Value>
    1877   class InvertableMap
    1878     : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
    1879   private:
    1880 
    1881     typedef typename ItemSetTraits<_Graph, _Item>::
    1882     template Map<_Value>::Type Map;
    1883     typedef _Graph Graph;
    1884 
    1885     typedef std::map<_Value, _Item> Container;
    1886     Container _inv_map;
    1887 
    1888   public:
    1889 
    1890     /// The key type of InvertableMap (Node, Arc, Edge).
    1891     typedef typename Map::Key Key;
    1892     /// The value type of the InvertableMap.
    1893     typedef typename Map::Value Value;
    1894 
    1895     /// \brief Constructor.
    1896     ///
    1897     /// Construct a new InvertableMap for the graph.
    1898     ///
    1899     explicit InvertableMap(const Graph& graph) : Map(graph) {}
    1900 
    1901     /// \brief Forward iterator for values.
    1902     ///
    1903     /// This iterator is an stl compatible forward
    1904     /// iterator on the values of the map. The values can
    1905     /// be accessed in the [beginValue, endValue) range.
    1906     ///
    1907     class ValueIterator
    1908       : public std::iterator<std::forward_iterator_tag, Value> {
    1909       friend class InvertableMap;
    1910     private:
    1911       ValueIterator(typename Container::const_iterator _it)
    1912         : it(_it) {}
    1913     public:
    1914 
    1915       ValueIterator() {}
    1916 
    1917       ValueIterator& operator++() { ++it; return *this; }
    1918       ValueIterator operator++(int) {
    1919         ValueIterator tmp(*this);
    1920         operator++();
    1921         return tmp;
    1922       }
    1923 
    1924       const Value& operator*() const { return it->first; }
    1925       const Value* operator->() const { return &(it->first); }
    1926 
    1927       bool operator==(ValueIterator jt) const { return it == jt.it; }
    1928       bool operator!=(ValueIterator jt) const { return it != jt.it; }
    1929 
    1930     private:
    1931       typename Container::const_iterator it;
    1932     };
    1933 
    1934     /// \brief Returns an iterator to the first value.
    1935     ///
    1936     /// Returns an stl compatible iterator to the
    1937     /// first value of the map. The values of the
    1938     /// map can be accessed in the [beginValue, endValue)
    1939     /// range.
    1940     ValueIterator beginValue() const {
    1941       return ValueIterator(_inv_map.begin());
    1942     }
    1943 
    1944     /// \brief Returns an iterator after the last value.
    1945     ///
    1946     /// Returns an stl compatible iterator after the
    1947     /// last value of the map. The values of the
    1948     /// map can be accessed in the [beginValue, endValue)
    1949     /// range.
    1950     ValueIterator endValue() const {
    1951       return ValueIterator(_inv_map.end());
    1952     }
    1953 
    1954     /// \brief The setter function of the map.
    1955     ///
    1956     /// Sets the mapped value.
    1957     void set(const Key& key, const Value& val) {
    1958       Value oldval = Map::operator[](key);
    1959       typename Container::iterator it = _inv_map.find(oldval);
    1960       if (it != _inv_map.end() && it->second == key) {
    1961         _inv_map.erase(it);
    1962       }
    1963       _inv_map.insert(make_pair(val, key));
    1964       Map::set(key, val);
    1965     }
    1966 
    1967     /// \brief The getter function of the map.
    1968     ///
    1969     /// It gives back the value associated with the key.
    1970     typename MapTraits<Map>::ConstReturnValue
    1971     operator[](const Key& key) const {
    1972       return Map::operator[](key);
    1973     }
    1974 
    1975     /// \brief Gives back the item by its value.
    1976     ///
    1977     /// Gives back the item by its value.
    1978     Key operator()(const Value& key) const {
    1979       typename Container::const_iterator it = _inv_map.find(key);
    1980       return it != _inv_map.end() ? it->second : INVALID;
    1981     }
    1982 
    1983   protected:
    1984 
    1985     /// \brief Erase the key from the map.
    1986     ///
    1987     /// Erase the key to the map. It is called by the
    1988     /// \c AlterationNotifier.
    1989     virtual void erase(const Key& key) {
    1990       Value val = Map::operator[](key);
    1991       typename Container::iterator it = _inv_map.find(val);
    1992       if (it != _inv_map.end() && it->second == key) {
    1993         _inv_map.erase(it);
    1994       }
    1995       Map::erase(key);
    1996     }
    1997 
    1998     /// \brief Erase more keys from the map.
    1999     ///
    2000     /// Erase more keys from the map. It is called by the
    2001     /// \c AlterationNotifier.
    2002     virtual void erase(const std::vector<Key>& keys) {
    2003       for (int i = 0; i < int(keys.size()); ++i) {
    2004         Value val = Map::operator[](keys[i]);
    2005         typename Container::iterator it = _inv_map.find(val);
    2006         if (it != _inv_map.end() && it->second == keys[i]) {
    2007           _inv_map.erase(it);
    2008         }
    2009       }
    2010       Map::erase(keys);
    2011     }
    2012 
    2013     /// \brief Clear the keys from the map and inverse map.
    2014     ///
    2015     /// Clear the keys from the map and inverse map. It is called by the
    2016     /// \c AlterationNotifier.
    2017     virtual void clear() {
    2018       _inv_map.clear();
    2019       Map::clear();
    2020     }
    2021 
    2022   public:
    2023 
    2024     /// \brief The inverse map type.
    2025     ///
    2026     /// The inverse of this map. The subscript operator of the map
    2027     /// gives back always the item what was last assigned to the value.
    2028     class InverseMap {
    2029     public:
    2030       /// \brief Constructor of the InverseMap.
    2031       ///
    2032       /// Constructor of the InverseMap.
    2033       explicit InverseMap(const InvertableMap& inverted)
    2034         : _inverted(inverted) {}
    2035 
    2036       /// The value type of the InverseMap.
    2037       typedef typename InvertableMap::Key Value;
    2038       /// The key type of the InverseMap.
    2039       typedef typename InvertableMap::Value Key;
    2040 
    2041       /// \brief Subscript operator.
    2042       ///
    2043       /// Subscript operator. It gives back always the item
    2044       /// what was last assigned to the value.
    2045       Value operator[](const Key& key) const {
    2046         return _inverted(key);
    2047       }
    2048 
    2049     private:
    2050       const InvertableMap& _inverted;
    2051     };
    2052 
    2053     /// \brief It gives back the just readable inverse map.
    2054     ///
    2055     /// It gives back the just readable inverse map.
    2056     InverseMap inverse() const {
    2057       return InverseMap(*this);
    2058     }
    2059 
    2060   };
    2061 
    2062   /// \brief Provides a mutable, continuous and unique descriptor for each
    2063   /// item in the graph.
    2064   ///
    2065   /// The DescriptorMap class provides a unique and continuous (but mutable)
    2066   /// descriptor (id) for each item of the same type (e.g. node) in the
    2067   /// graph. This id is <ul><li>\b unique: different items (nodes) get
    2068   /// different ids <li>\b continuous: the range of the ids is the set of
    2069   /// integers between 0 and \c n-1, where \c n is the number of the items of
    2070   /// this type (e.g. nodes) (so the id of a node can change if you delete an
    2071   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
    2072   /// with its member class \c InverseMap, or with the \c operator() member.
    2073   ///
    2074   /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
    2075   /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
    2076   /// Edge.
    2077   template <typename _Graph, typename _Item>
    2078   class DescriptorMap
    2079     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
    2080 
    2081     typedef _Item Item;
    2082     typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
    2083 
    2084   public:
    2085     /// The graph class of DescriptorMap.
    2086     typedef _Graph Graph;
    2087 
    2088     /// The key type of DescriptorMap (Node, Arc, Edge).
    2089     typedef typename Map::Key Key;
    2090     /// The value type of DescriptorMap.
    2091     typedef typename Map::Value Value;
    2092 
    2093     /// \brief Constructor.
    2094     ///
    2095     /// Constructor for descriptor map.
    2096     explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
    2097       Item it;
    2098       const typename Map::Notifier* nf = Map::notifier();
    2099       for (nf->first(it); it != INVALID; nf->next(it)) {
    2100         Map::set(it, _inv_map.size());
    2101         _inv_map.push_back(it);
    2102       }
    2103     }
    2104 
    2105   protected:
    2106 
    2107     /// \brief Add a new key to the map.
    2108     ///
    2109     /// Add a new key to the map. It is called by the
    2110     /// \c AlterationNotifier.
    2111     virtual void add(const Item& item) {
    2112       Map::add(item);
    2113       Map::set(item, _inv_map.size());
    2114       _inv_map.push_back(item);
    2115     }
    2116 
    2117     /// \brief Add more new keys to the map.
    2118     ///
    2119     /// Add more new keys to the map. It is called by the
    2120     /// \c AlterationNotifier.
    2121     virtual void add(const std::vector<Item>& items) {
    2122       Map::add(items);
    2123       for (int i = 0; i < int(items.size()); ++i) {
    2124         Map::set(items[i], _inv_map.size());
    2125         _inv_map.push_back(items[i]);
    2126       }
    2127     }
    2128 
    2129     /// \brief Erase the key from the map.
    2130     ///
    2131     /// Erase the key from the map. It is called by the
    2132     /// \c AlterationNotifier.
    2133     virtual void erase(const Item& item) {
    2134       Map::set(_inv_map.back(), Map::operator[](item));
    2135       _inv_map[Map::operator[](item)] = _inv_map.back();
    2136       _inv_map.pop_back();
    2137       Map::erase(item);
    2138     }
    2139 
    2140     /// \brief Erase more keys from the map.
    2141     ///
    2142     /// Erase more keys from the map. It is called by the
    2143     /// \c AlterationNotifier.
    2144     virtual void erase(const std::vector<Item>& items) {
    2145       for (int i = 0; i < int(items.size()); ++i) {
    2146         Map::set(_inv_map.back(), Map::operator[](items[i]));
    2147         _inv_map[Map::operator[](items[i])] = _inv_map.back();
    2148         _inv_map.pop_back();
    2149       }
    2150       Map::erase(items);
    2151     }
    2152 
    2153     /// \brief Build the unique map.
    2154     ///
    2155     /// Build the unique map. It is called by the
    2156     /// \c AlterationNotifier.
    2157     virtual void build() {
    2158       Map::build();
    2159       Item it;
    2160       const typename Map::Notifier* nf = Map::notifier();
    2161       for (nf->first(it); it != INVALID; nf->next(it)) {
    2162         Map::set(it, _inv_map.size());
    2163         _inv_map.push_back(it);
    2164       }
    2165     }
    2166 
    2167     /// \brief Clear the keys from the map.
    2168     ///
    2169     /// Clear the keys from the map. It is called by the
    2170     /// \c AlterationNotifier.
    2171     virtual void clear() {
    2172       _inv_map.clear();
    2173       Map::clear();
    2174     }
    2175 
    2176   public:
    2177 
    2178     /// \brief Returns the maximal value plus one.
    2179     ///
    2180     /// Returns the maximal value plus one in the map.
    2181     unsigned int size() const {
    2182       return _inv_map.size();
    2183     }
    2184 
    2185     /// \brief Swaps the position of the two items in the map.
    2186     ///
    2187     /// Swaps the position of the two items in the map.
    2188     void swap(const Item& p, const Item& q) {
    2189       int pi = Map::operator[](p);
    2190       int qi = Map::operator[](q);
    2191       Map::set(p, qi);
    2192       _inv_map[qi] = p;
    2193       Map::set(q, pi);
    2194       _inv_map[pi] = q;
    2195     }
    2196 
    2197     /// \brief Gives back the \e descriptor of the item.
    2198     ///
    2199     /// Gives back the mutable and unique \e descriptor of the map.
    2200     int operator[](const Item& item) const {
    2201       return Map::operator[](item);
    2202     }
    2203 
    2204     /// \brief Gives back the item by its descriptor.
    2205     ///
    2206     /// Gives back th item by its descriptor.
    2207     Item operator()(int id) const {
    2208       return _inv_map[id];
    2209     }
    2210 
    2211   private:
    2212 
    2213     typedef std::vector<Item> Container;
    2214     Container _inv_map;
    2215 
    2216   public:
    2217     /// \brief The inverse map type of DescriptorMap.
    2218     ///
    2219     /// The inverse map type of DescriptorMap.
    2220     class InverseMap {
    2221     public:
    2222       /// \brief Constructor of the InverseMap.
    2223       ///
    2224       /// Constructor of the InverseMap.
    2225       explicit InverseMap(const DescriptorMap& inverted)
    2226         : _inverted(inverted) {}
    2227 
    2228 
    2229       /// The value type of the InverseMap.
    2230       typedef typename DescriptorMap::Key Value;
    2231       /// The key type of the InverseMap.
    2232       typedef typename DescriptorMap::Value Key;
    2233 
    2234       /// \brief Subscript operator.
    2235       ///
    2236       /// Subscript operator. It gives back the item
    2237       /// that the descriptor belongs to currently.
    2238       Value operator[](const Key& key) const {
    2239         return _inverted(key);
    2240       }
    2241 
    2242       /// \brief Size of the map.
    2243       ///
    2244       /// Returns the size of the map.
    2245       unsigned int size() const {
    2246         return _inverted.size();
    2247       }
    2248 
    2249     private:
    2250       const DescriptorMap& _inverted;
    2251     };
    2252 
    2253     /// \brief Gives back the inverse of the map.
    2254     ///
    2255     /// Gives back the inverse of the map.
    2256     const InverseMap inverse() const {
    2257       return InverseMap(*this);
    2258     }
    22591858  };
    22601859
Note: See TracChangeset for help on using the changeset viewer.