COIN-OR::LEMON - Graph Library

Changeset 324:fafece417795 in lemon


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

Remove InverseMap? and DescriptorMap?

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r280 r324  
    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 r324  
    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.