COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r320 r318  
    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    }
    18582259  };
    18592260
Note: See TracChangeset for help on using the changeset viewer.