COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 301:fafece417795 in lemon-1.0


Ignore:
Timestamp:
10/08/08 13:25:57 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.0
Phase:
public
Message:

Remove InverseMap? and DescriptorMap?

Files:
2 edited

Legend:

Unmodified
Added
Removed

  • lemon/maps.h

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

  • test/graph_utils_test.cc

    r220 r301  
    3636  {
    3737    Digraph digraph;
     38    typename Digraph::template NodeMap<int> nodes(digraph);
     39    std::vector<Node> invNodes;
    3840    for (int i = 0; i < 10; ++i) {
    39       digraph.addNode();
    40     }
    41     DescriptorMap<Digraph, Node> nodes(digraph);
    42     typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
     41      invNodes.push_back(digraph.addNode());
     42      nodes[invNodes.back()]=invNodes.size()-1;
     43    }
    4344    for (int i = 0; i < 100; ++i) {
    4445      int src = rnd[invNodes.size()];
    … …  
    4748    }
    4849    typename Digraph::template ArcMap<bool> found(digraph, false);
    49     DescriptorMap<Digraph, Arc> arcs(digraph);
    5050    for (NodeIt src(digraph); src != INVALID; ++src) {
    5151      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
    … …  
    111111  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    112112  Graph graph;
     113  typename Graph::template NodeMap<int> nodes(graph);
     114  std::vector<Node> invNodes;
    113115  for (int i = 0; i < 10; ++i) {
    114     graph.addNode();
    115   }
    116   DescriptorMap<Graph, Node> nodes(graph);
    117   typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
     116    invNodes.push_back(graph.addNode());
     117    nodes[invNodes.back()]=invNodes.size()-1;
     118  }
    118119  for (int i = 0; i < 100; ++i) {
    119120    int src = rnd[invNodes.size()];
    … …  
    122123  }
    123124  typename Graph::template EdgeMap<int> found(graph, 0);
    124   DescriptorMap<Graph, Edge> edges(graph);
    125125  for (NodeIt src(graph); src != INVALID; ++src) {
    126126    for (NodeIt trg(graph); trg != INVALID; ++trg) {
Note: See TracChangeset for help on using the changeset viewer.