Changeset 220:a5d8c039f218 in lemon1.0 for lemon/maps.h
 Timestamp:
 07/15/08 13:15:39 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/maps.h
r209 r220 24 24 #include <vector> 25 25 26 #include <lemon/bits/utility.h> 27 #include <lemon/bits/traits.h> 26 #include <lemon/core.h> 28 27 29 28 ///\file … … 1781 1780 } 1782 1781 1782 /// Provides an immutable and unique id for each item in the graph. 1783 1784 /// The IdMap class provides a unique and immutable id for each item of the 1785 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique: 1786 /// different items (nodes) get different ids <li>\b immutable: the id of an 1787 /// item (node) does not change (even if you delete other nodes). </ul> 1788 /// Through this map you get access (i.e. can read) the inner id values of 1789 /// the items stored in the graph. This map can be inverted with its member 1790 /// class \c InverseMap or with the \c operator() member. 1791 /// 1792 template <typename _Graph, typename _Item> 1793 class IdMap { 1794 public: 1795 typedef _Graph Graph; 1796 typedef int Value; 1797 typedef _Item Item; 1798 typedef _Item Key; 1799 1800 /// \brief Constructor. 1801 /// 1802 /// Constructor of the map. 1803 explicit IdMap(const Graph& graph) : _graph(&graph) {} 1804 1805 /// \brief Gives back the \e id of the item. 1806 /// 1807 /// Gives back the immutable and unique \e id of the item. 1808 int operator[](const Item& item) const { return _graph>id(item);} 1809 1810 /// \brief Gives back the item by its id. 1811 /// 1812 /// Gives back the item by its id. 1813 Item operator()(int id) { return _graph>fromId(id, Item()); } 1814 1815 private: 1816 const Graph* _graph; 1817 1818 public: 1819 1820 /// \brief The class represents the inverse of its owner (IdMap). 1821 /// 1822 /// The class represents the inverse of its owner (IdMap). 1823 /// \see inverse() 1824 class InverseMap { 1825 public: 1826 1827 /// \brief Constructor. 1828 /// 1829 /// Constructor for creating an idtoitem map. 1830 explicit InverseMap(const Graph& graph) : _graph(&graph) {} 1831 1832 /// \brief Constructor. 1833 /// 1834 /// Constructor for creating an idtoitem map. 1835 explicit InverseMap(const IdMap& map) : _graph(map._graph) {} 1836 1837 /// \brief Gives back the given item from its id. 1838 /// 1839 /// Gives back the given item from its id. 1840 /// 1841 Item operator[](int id) const { return _graph>fromId(id, Item());} 1842 1843 private: 1844 const Graph* _graph; 1845 }; 1846 1847 /// \brief Gives back the inverse of the map. 1848 /// 1849 /// Gives back the inverse of the IdMap. 1850 InverseMap inverse() const { return InverseMap(*_graph);} 1851 1852 }; 1853 1854 1855 /// \brief General invertable graphmap type. 1856 1857 /// This type provides simple invertable graphmaps. 1858 /// The InvertableMap wraps an arbitrary ReadWriteMap 1859 /// and if a key is set to a new value then store it 1860 /// in the inverse map. 1861 /// 1862 /// The values of the map can be accessed 1863 /// with stl compatible forward iterator. 1864 /// 1865 /// \tparam _Graph The graph type. 1866 /// \tparam _Item The item type of the graph. 1867 /// \tparam _Value The value type of the map. 1868 /// 1869 /// \see IterableValueMap 1870 template <typename _Graph, typename _Item, typename _Value> 1871 class InvertableMap 1872 : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type { 1873 private: 1874 1875 typedef typename ItemSetTraits<_Graph, _Item>:: 1876 template Map<_Value>::Type Map; 1877 typedef _Graph Graph; 1878 1879 typedef std::map<_Value, _Item> Container; 1880 Container _inv_map; 1881 1882 public: 1883 1884 /// The key type of InvertableMap (Node, Arc, Edge). 1885 typedef typename Map::Key Key; 1886 /// The value type of the InvertableMap. 1887 typedef typename Map::Value Value; 1888 1889 1890 1891 /// \brief Constructor. 1892 /// 1893 /// Construct a new InvertableMap for the graph. 1894 /// 1895 explicit InvertableMap(const Graph& graph) : Map(graph) {} 1896 1897 /// \brief Forward iterator for values. 1898 /// 1899 /// This iterator is an stl compatible forward 1900 /// iterator on the values of the map. The values can 1901 /// be accessed in the [beginValue, endValue) range. 1902 /// 1903 class ValueIterator 1904 : public std::iterator<std::forward_iterator_tag, Value> { 1905 friend class InvertableMap; 1906 private: 1907 ValueIterator(typename Container::const_iterator _it) 1908 : it(_it) {} 1909 public: 1910 1911 ValueIterator() {} 1912 1913 ValueIterator& operator++() { ++it; return *this; } 1914 ValueIterator operator++(int) { 1915 ValueIterator tmp(*this); 1916 operator++(); 1917 return tmp; 1918 } 1919 1920 const Value& operator*() const { return it>first; } 1921 const Value* operator>() const { return &(it>first); } 1922 1923 bool operator==(ValueIterator jt) const { return it == jt.it; } 1924 bool operator!=(ValueIterator jt) const { return it != jt.it; } 1925 1926 private: 1927 typename Container::const_iterator it; 1928 }; 1929 1930 /// \brief Returns an iterator to the first value. 1931 /// 1932 /// Returns an stl compatible iterator to the 1933 /// first value of the map. The values of the 1934 /// map can be accessed in the [beginValue, endValue) 1935 /// range. 1936 ValueIterator beginValue() const { 1937 return ValueIterator(_inv_map.begin()); 1938 } 1939 1940 /// \brief Returns an iterator after the last value. 1941 /// 1942 /// Returns an stl compatible iterator after the 1943 /// last value of the map. The values of the 1944 /// map can be accessed in the [beginValue, endValue) 1945 /// range. 1946 ValueIterator endValue() const { 1947 return ValueIterator(_inv_map.end()); 1948 } 1949 1950 /// \brief The setter function of the map. 1951 /// 1952 /// Sets the mapped value. 1953 void set(const Key& key, const Value& val) { 1954 Value oldval = Map::operator[](key); 1955 typename Container::iterator it = _inv_map.find(oldval); 1956 if (it != _inv_map.end() && it>second == key) { 1957 _inv_map.erase(it); 1958 } 1959 _inv_map.insert(make_pair(val, key)); 1960 Map::set(key, val); 1961 } 1962 1963 /// \brief The getter function of the map. 1964 /// 1965 /// It gives back the value associated with the key. 1966 typename MapTraits<Map>::ConstReturnValue 1967 operator[](const Key& key) const { 1968 return Map::operator[](key); 1969 } 1970 1971 /// \brief Gives back the item by its value. 1972 /// 1973 /// Gives back the item by its value. 1974 Key operator()(const Value& key) const { 1975 typename Container::const_iterator it = _inv_map.find(key); 1976 return it != _inv_map.end() ? it>second : INVALID; 1977 } 1978 1979 protected: 1980 1981 /// \brief Erase the key from the map. 1982 /// 1983 /// Erase the key to the map. It is called by the 1984 /// \c AlterationNotifier. 1985 virtual void erase(const Key& key) { 1986 Value val = Map::operator[](key); 1987 typename Container::iterator it = _inv_map.find(val); 1988 if (it != _inv_map.end() && it>second == key) { 1989 _inv_map.erase(it); 1990 } 1991 Map::erase(key); 1992 } 1993 1994 /// \brief Erase more keys from the map. 1995 /// 1996 /// Erase more keys from the map. It is called by the 1997 /// \c AlterationNotifier. 1998 virtual void erase(const std::vector<Key>& keys) { 1999 for (int i = 0; i < int(keys.size()); ++i) { 2000 Value val = Map::operator[](keys[i]); 2001 typename Container::iterator it = _inv_map.find(val); 2002 if (it != _inv_map.end() && it>second == keys[i]) { 2003 _inv_map.erase(it); 2004 } 2005 } 2006 Map::erase(keys); 2007 } 2008 2009 /// \brief Clear the keys from the map and inverse map. 2010 /// 2011 /// Clear the keys from the map and inverse map. It is called by the 2012 /// \c AlterationNotifier. 2013 virtual void clear() { 2014 _inv_map.clear(); 2015 Map::clear(); 2016 } 2017 2018 public: 2019 2020 /// \brief The inverse map type. 2021 /// 2022 /// The inverse of this map. The subscript operator of the map 2023 /// gives back always the item what was last assigned to the value. 2024 class InverseMap { 2025 public: 2026 /// \brief Constructor of the InverseMap. 2027 /// 2028 /// Constructor of the InverseMap. 2029 explicit InverseMap(const InvertableMap& inverted) 2030 : _inverted(inverted) {} 2031 2032 /// The value type of the InverseMap. 2033 typedef typename InvertableMap::Key Value; 2034 /// The key type of the InverseMap. 2035 typedef typename InvertableMap::Value Key; 2036 2037 /// \brief Subscript operator. 2038 /// 2039 /// Subscript operator. It gives back always the item 2040 /// what was last assigned to the value. 2041 Value operator[](const Key& key) const { 2042 return _inverted(key); 2043 } 2044 2045 private: 2046 const InvertableMap& _inverted; 2047 }; 2048 2049 /// \brief It gives back the just readable inverse map. 2050 /// 2051 /// It gives back the just readable inverse map. 2052 InverseMap inverse() const { 2053 return InverseMap(*this); 2054 } 2055 2056 2057 2058 }; 2059 2060 /// \brief Provides a mutable, continuous and unique descriptor for each 2061 /// item in the graph. 2062 /// 2063 /// The DescriptorMap class provides a unique and continuous (but mutable) 2064 /// descriptor (id) for each item of the same type (e.g. node) in the 2065 /// graph. This id is <ul><li>\b unique: different items (nodes) get 2066 /// different ids <li>\b continuous: the range of the ids is the set of 2067 /// integers between 0 and \c n1, where \c n is the number of the items of 2068 /// this type (e.g. nodes) (so the id of a node can change if you delete an 2069 /// other node, i.e. this id is mutable). </ul> This map can be inverted 2070 /// with its member class \c InverseMap, or with the \c operator() member. 2071 /// 2072 /// \tparam _Graph The graph class the \c DescriptorMap belongs to. 2073 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or 2074 /// Edge. 2075 template <typename _Graph, typename _Item> 2076 class DescriptorMap 2077 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type { 2078 2079 typedef _Item Item; 2080 typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map; 2081 2082 public: 2083 /// The graph class of DescriptorMap. 2084 typedef _Graph Graph; 2085 2086 /// The key type of DescriptorMap (Node, Arc, Edge). 2087 typedef typename Map::Key Key; 2088 /// The value type of DescriptorMap. 2089 typedef typename Map::Value Value; 2090 2091 /// \brief Constructor. 2092 /// 2093 /// Constructor for descriptor map. 2094 explicit DescriptorMap(const Graph& _graph) : Map(_graph) { 2095 Item it; 2096 const typename Map::Notifier* nf = Map::notifier(); 2097 for (nf>first(it); it != INVALID; nf>next(it)) { 2098 Map::set(it, _inv_map.size()); 2099 _inv_map.push_back(it); 2100 } 2101 } 2102 2103 protected: 2104 2105 /// \brief Add a new key to the map. 2106 /// 2107 /// Add a new key to the map. It is called by the 2108 /// \c AlterationNotifier. 2109 virtual void add(const Item& item) { 2110 Map::add(item); 2111 Map::set(item, _inv_map.size()); 2112 _inv_map.push_back(item); 2113 } 2114 2115 /// \brief Add more new keys to the map. 2116 /// 2117 /// Add more new keys to the map. It is called by the 2118 /// \c AlterationNotifier. 2119 virtual void add(const std::vector<Item>& items) { 2120 Map::add(items); 2121 for (int i = 0; i < int(items.size()); ++i) { 2122 Map::set(items[i], _inv_map.size()); 2123 _inv_map.push_back(items[i]); 2124 } 2125 } 2126 2127 /// \brief Erase the key from the map. 2128 /// 2129 /// Erase the key from the map. It is called by the 2130 /// \c AlterationNotifier. 2131 virtual void erase(const Item& item) { 2132 Map::set(_inv_map.back(), Map::operator[](item)); 2133 _inv_map[Map::operator[](item)] = _inv_map.back(); 2134 _inv_map.pop_back(); 2135 Map::erase(item); 2136 } 2137 2138 /// \brief Erase more keys from the map. 2139 /// 2140 /// Erase more keys from the map. It is called by the 2141 /// \c AlterationNotifier. 2142 virtual void erase(const std::vector<Item>& items) { 2143 for (int i = 0; i < int(items.size()); ++i) { 2144 Map::set(_inv_map.back(), Map::operator[](items[i])); 2145 _inv_map[Map::operator[](items[i])] = _inv_map.back(); 2146 _inv_map.pop_back(); 2147 } 2148 Map::erase(items); 2149 } 2150 2151 /// \brief Build the unique map. 2152 /// 2153 /// Build the unique map. It is called by the 2154 /// \c AlterationNotifier. 2155 virtual void build() { 2156 Map::build(); 2157 Item it; 2158 const typename Map::Notifier* nf = Map::notifier(); 2159 for (nf>first(it); it != INVALID; nf>next(it)) { 2160 Map::set(it, _inv_map.size()); 2161 _inv_map.push_back(it); 2162 } 2163 } 2164 2165 /// \brief Clear the keys from the map. 2166 /// 2167 /// Clear the keys from the map. It is called by the 2168 /// \c AlterationNotifier. 2169 virtual void clear() { 2170 _inv_map.clear(); 2171 Map::clear(); 2172 } 2173 2174 public: 2175 2176 /// \brief Returns the maximal value plus one. 2177 /// 2178 /// Returns the maximal value plus one in the map. 2179 unsigned int size() const { 2180 return _inv_map.size(); 2181 } 2182 2183 /// \brief Swaps the position of the two items in the map. 2184 /// 2185 /// Swaps the position of the two items in the map. 2186 void swap(const Item& p, const Item& q) { 2187 int pi = Map::operator[](p); 2188 int qi = Map::operator[](q); 2189 Map::set(p, qi); 2190 _inv_map[qi] = p; 2191 Map::set(q, pi); 2192 _inv_map[pi] = q; 2193 } 2194 2195 /// \brief Gives back the \e descriptor of the item. 2196 /// 2197 /// Gives back the mutable and unique \e descriptor of the map. 2198 int operator[](const Item& item) const { 2199 return Map::operator[](item); 2200 } 2201 2202 /// \brief Gives back the item by its descriptor. 2203 /// 2204 /// Gives back th item by its descriptor. 2205 Item operator()(int id) const { 2206 return _inv_map[id]; 2207 } 2208 2209 private: 2210 2211 typedef std::vector<Item> Container; 2212 Container _inv_map; 2213 2214 public: 2215 /// \brief The inverse map type of DescriptorMap. 2216 /// 2217 /// The inverse map type of DescriptorMap. 2218 class InverseMap { 2219 public: 2220 /// \brief Constructor of the InverseMap. 2221 /// 2222 /// Constructor of the InverseMap. 2223 explicit InverseMap(const DescriptorMap& inverted) 2224 : _inverted(inverted) {} 2225 2226 2227 /// The value type of the InverseMap. 2228 typedef typename DescriptorMap::Key Value; 2229 /// The key type of the InverseMap. 2230 typedef typename DescriptorMap::Value Key; 2231 2232 /// \brief Subscript operator. 2233 /// 2234 /// Subscript operator. It gives back the item 2235 /// that the descriptor belongs to currently. 2236 Value operator[](const Key& key) const { 2237 return _inverted(key); 2238 } 2239 2240 /// \brief Size of the map. 2241 /// 2242 /// Returns the size of the map. 2243 unsigned int size() const { 2244 return _inverted.size(); 2245 } 2246 2247 private: 2248 const DescriptorMap& _inverted; 2249 }; 2250 2251 /// \brief Gives back the inverse of the map. 2252 /// 2253 /// Gives back the inverse of the map. 2254 const InverseMap inverse() const { 2255 return InverseMap(*this); 2256 } 2257 }; 2258 2259 /// \brief Returns the source of the given arc. 2260 /// 2261 /// The SourceMap gives back the source Node of the given arc. 2262 /// \see TargetMap 2263 template <typename Digraph> 2264 class SourceMap { 2265 public: 2266 2267 typedef typename Digraph::Node Value; 2268 typedef typename Digraph::Arc Key; 2269 2270 /// \brief Constructor 2271 /// 2272 /// Constructor 2273 /// \param _digraph The digraph that the map belongs to. 2274 explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {} 2275 2276 /// \brief The subscript operator. 2277 /// 2278 /// The subscript operator. 2279 /// \param arc The arc 2280 /// \return The source of the arc 2281 Value operator[](const Key& arc) const { 2282 return _digraph.source(arc); 2283 } 2284 2285 private: 2286 const Digraph& _digraph; 2287 }; 2288 2289 /// \brief Returns a \ref SourceMap class. 2290 /// 2291 /// This function just returns an \ref SourceMap class. 2292 /// \relates SourceMap 2293 template <typename Digraph> 2294 inline SourceMap<Digraph> sourceMap(const Digraph& digraph) { 2295 return SourceMap<Digraph>(digraph); 2296 } 2297 2298 /// \brief Returns the target of the given arc. 2299 /// 2300 /// The TargetMap gives back the target Node of the given arc. 2301 /// \see SourceMap 2302 template <typename Digraph> 2303 class TargetMap { 2304 public: 2305 2306 typedef typename Digraph::Node Value; 2307 typedef typename Digraph::Arc Key; 2308 2309 /// \brief Constructor 2310 /// 2311 /// Constructor 2312 /// \param _digraph The digraph that the map belongs to. 2313 explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {} 2314 2315 /// \brief The subscript operator. 2316 /// 2317 /// The subscript operator. 2318 /// \param e The arc 2319 /// \return The target of the arc 2320 Value operator[](const Key& e) const { 2321 return _digraph.target(e); 2322 } 2323 2324 private: 2325 const Digraph& _digraph; 2326 }; 2327 2328 /// \brief Returns a \ref TargetMap class. 2329 /// 2330 /// This function just returns a \ref TargetMap class. 2331 /// \relates TargetMap 2332 template <typename Digraph> 2333 inline TargetMap<Digraph> targetMap(const Digraph& digraph) { 2334 return TargetMap<Digraph>(digraph); 2335 } 2336 2337 /// \brief Returns the "forward" directed arc view of an edge. 2338 /// 2339 /// Returns the "forward" directed arc view of an edge. 2340 /// \see BackwardMap 2341 template <typename Graph> 2342 class ForwardMap { 2343 public: 2344 2345 typedef typename Graph::Arc Value; 2346 typedef typename Graph::Edge Key; 2347 2348 /// \brief Constructor 2349 /// 2350 /// Constructor 2351 /// \param _graph The graph that the map belongs to. 2352 explicit ForwardMap(const Graph& graph) : _graph(graph) {} 2353 2354 /// \brief The subscript operator. 2355 /// 2356 /// The subscript operator. 2357 /// \param key An edge 2358 /// \return The "forward" directed arc view of edge 2359 Value operator[](const Key& key) const { 2360 return _graph.direct(key, true); 2361 } 2362 2363 private: 2364 const Graph& _graph; 2365 }; 2366 2367 /// \brief Returns a \ref ForwardMap class. 2368 /// 2369 /// This function just returns an \ref ForwardMap class. 2370 /// \relates ForwardMap 2371 template <typename Graph> 2372 inline ForwardMap<Graph> forwardMap(const Graph& graph) { 2373 return ForwardMap<Graph>(graph); 2374 } 2375 2376 /// \brief Returns the "backward" directed arc view of an edge. 2377 /// 2378 /// Returns the "backward" directed arc view of an edge. 2379 /// \see ForwardMap 2380 template <typename Graph> 2381 class BackwardMap { 2382 public: 2383 2384 typedef typename Graph::Arc Value; 2385 typedef typename Graph::Edge Key; 2386 2387 /// \brief Constructor 2388 /// 2389 /// Constructor 2390 /// \param _graph The graph that the map belongs to. 2391 explicit BackwardMap(const Graph& graph) : _graph(graph) {} 2392 2393 /// \brief The subscript operator. 2394 /// 2395 /// The subscript operator. 2396 /// \param key An edge 2397 /// \return The "backward" directed arc view of edge 2398 Value operator[](const Key& key) const { 2399 return _graph.direct(key, false); 2400 } 2401 2402 private: 2403 const Graph& _graph; 2404 }; 2405 2406 /// \brief Returns a \ref BackwardMap class 2407 2408 /// This function just returns a \ref BackwardMap class. 2409 /// \relates BackwardMap 2410 template <typename Graph> 2411 inline BackwardMap<Graph> backwardMap(const Graph& graph) { 2412 return BackwardMap<Graph>(graph); 2413 } 2414 2415 /// \brief Potential difference map 2416 /// 2417 /// If there is an potential map on the nodes then we 2418 /// can get an arc map as we get the substraction of the 2419 /// values of the target and source. 2420 template <typename Digraph, typename NodeMap> 2421 class PotentialDifferenceMap { 2422 public: 2423 typedef typename Digraph::Arc Key; 2424 typedef typename NodeMap::Value Value; 2425 2426 /// \brief Constructor 2427 /// 2428 /// Contructor of the map 2429 explicit PotentialDifferenceMap(const Digraph& digraph, 2430 const NodeMap& potential) 2431 : _digraph(digraph), _potential(potential) {} 2432 2433 /// \brief Const subscription operator 2434 /// 2435 /// Const subscription operator 2436 Value operator[](const Key& arc) const { 2437 return _potential[_digraph.target(arc)]  2438 _potential[_digraph.source(arc)]; 2439 } 2440 2441 private: 2442 const Digraph& _digraph; 2443 const NodeMap& _potential; 2444 }; 2445 2446 /// \brief Returns a PotentialDifferenceMap. 2447 /// 2448 /// This function just returns a PotentialDifferenceMap. 2449 /// \relates PotentialDifferenceMap 2450 template <typename Digraph, typename NodeMap> 2451 PotentialDifferenceMap<Digraph, NodeMap> 2452 potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) { 2453 return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential); 2454 } 2455 2456 /// \brief Map of the node indegrees. 2457 /// 2458 /// This map returns the indegree of a node. Once it is constructed, 2459 /// the degrees are stored in a standard NodeMap, so each query is done 2460 /// in constant time. On the other hand, the values are updated automatically 2461 /// whenever the digraph changes. 2462 /// 2463 /// \warning Besides addNode() and addArc(), a digraph structure may provide 2464 /// alternative ways to modify the digraph. The correct behavior of InDegMap 2465 /// is not guarantied if these additional features are used. For example 2466 /// the functions \ref ListDigraph::changeSource() "changeSource()", 2467 /// \ref ListDigraph::changeTarget() "changeTarget()" and 2468 /// \ref ListDigraph::reverseArc() "reverseArc()" 2469 /// of \ref ListDigraph will \e not update the degree values correctly. 2470 /// 2471 /// \sa OutDegMap 2472 2473 template <typename _Digraph> 2474 class InDegMap 2475 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> 2476 ::ItemNotifier::ObserverBase { 2477 2478 public: 2479 2480 typedef _Digraph Digraph; 2481 typedef int Value; 2482 typedef typename Digraph::Node Key; 2483 2484 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> 2485 ::ItemNotifier::ObserverBase Parent; 2486 2487 private: 2488 2489 class AutoNodeMap 2490 : public ItemSetTraits<Digraph, Key>::template Map<int>::Type { 2491 public: 2492 2493 typedef typename ItemSetTraits<Digraph, Key>:: 2494 template Map<int>::Type Parent; 2495 2496 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} 2497 2498 virtual void add(const Key& key) { 2499 Parent::add(key); 2500 Parent::set(key, 0); 2501 } 2502 2503 virtual void add(const std::vector<Key>& keys) { 2504 Parent::add(keys); 2505 for (int i = 0; i < int(keys.size()); ++i) { 2506 Parent::set(keys[i], 0); 2507 } 2508 } 2509 2510 virtual void build() { 2511 Parent::build(); 2512 Key it; 2513 typename Parent::Notifier* nf = Parent::notifier(); 2514 for (nf>first(it); it != INVALID; nf>next(it)) { 2515 Parent::set(it, 0); 2516 } 2517 } 2518 }; 2519 2520 public: 2521 2522 /// \brief Constructor. 2523 /// 2524 /// Constructor for creating indegree map. 2525 explicit InDegMap(const Digraph& digraph) 2526 : _digraph(digraph), _deg(digraph) { 2527 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 2528 2529 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2530 _deg[it] = countInArcs(_digraph, it); 2531 } 2532 } 2533 2534 /// Gives back the indegree of a Node. 2535 int operator[](const Key& key) const { 2536 return _deg[key]; 2537 } 2538 2539 protected: 2540 2541 typedef typename Digraph::Arc Arc; 2542 2543 virtual void add(const Arc& arc) { 2544 ++_deg[_digraph.target(arc)]; 2545 } 2546 2547 virtual void add(const std::vector<Arc>& arcs) { 2548 for (int i = 0; i < int(arcs.size()); ++i) { 2549 ++_deg[_digraph.target(arcs[i])]; 2550 } 2551 } 2552 2553 virtual void erase(const Arc& arc) { 2554 _deg[_digraph.target(arc)]; 2555 } 2556 2557 virtual void erase(const std::vector<Arc>& arcs) { 2558 for (int i = 0; i < int(arcs.size()); ++i) { 2559 _deg[_digraph.target(arcs[i])]; 2560 } 2561 } 2562 2563 virtual void build() { 2564 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2565 _deg[it] = countInArcs(_digraph, it); 2566 } 2567 } 2568 2569 virtual void clear() { 2570 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2571 _deg[it] = 0; 2572 } 2573 } 2574 private: 2575 2576 const Digraph& _digraph; 2577 AutoNodeMap _deg; 2578 }; 2579 2580 /// \brief Map of the node outdegrees. 2581 /// 2582 /// This map returns the outdegree of a node. Once it is constructed, 2583 /// the degrees are stored in a standard NodeMap, so each query is done 2584 /// in constant time. On the other hand, the values are updated automatically 2585 /// whenever the digraph changes. 2586 /// 2587 /// \warning Besides addNode() and addArc(), a digraph structure may provide 2588 /// alternative ways to modify the digraph. The correct behavior of OutDegMap 2589 /// is not guarantied if these additional features are used. For example 2590 /// the functions \ref ListDigraph::changeSource() "changeSource()", 2591 /// \ref ListDigraph::changeTarget() "changeTarget()" and 2592 /// \ref ListDigraph::reverseArc() "reverseArc()" 2593 /// of \ref ListDigraph will \e not update the degree values correctly. 2594 /// 2595 /// \sa InDegMap 2596 2597 template <typename _Digraph> 2598 class OutDegMap 2599 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> 2600 ::ItemNotifier::ObserverBase { 2601 2602 public: 2603 2604 typedef _Digraph Digraph; 2605 typedef int Value; 2606 typedef typename Digraph::Node Key; 2607 2608 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> 2609 ::ItemNotifier::ObserverBase Parent; 2610 2611 private: 2612 2613 class AutoNodeMap 2614 : public ItemSetTraits<Digraph, Key>::template Map<int>::Type { 2615 public: 2616 2617 typedef typename ItemSetTraits<Digraph, Key>:: 2618 template Map<int>::Type Parent; 2619 2620 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} 2621 2622 virtual void add(const Key& key) { 2623 Parent::add(key); 2624 Parent::set(key, 0); 2625 } 2626 virtual void add(const std::vector<Key>& keys) { 2627 Parent::add(keys); 2628 for (int i = 0; i < int(keys.size()); ++i) { 2629 Parent::set(keys[i], 0); 2630 } 2631 } 2632 virtual void build() { 2633 Parent::build(); 2634 Key it; 2635 typename Parent::Notifier* nf = Parent::notifier(); 2636 for (nf>first(it); it != INVALID; nf>next(it)) { 2637 Parent::set(it, 0); 2638 } 2639 } 2640 }; 2641 2642 public: 2643 2644 /// \brief Constructor. 2645 /// 2646 /// Constructor for creating outdegree map. 2647 explicit OutDegMap(const Digraph& digraph) 2648 : _digraph(digraph), _deg(digraph) { 2649 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 2650 2651 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2652 _deg[it] = countOutArcs(_digraph, it); 2653 } 2654 } 2655 2656 /// Gives back the outdegree of a Node. 2657 int operator[](const Key& key) const { 2658 return _deg[key]; 2659 } 2660 2661 protected: 2662 2663 typedef typename Digraph::Arc Arc; 2664 2665 virtual void add(const Arc& arc) { 2666 ++_deg[_digraph.source(arc)]; 2667 } 2668 2669 virtual void add(const std::vector<Arc>& arcs) { 2670 for (int i = 0; i < int(arcs.size()); ++i) { 2671 ++_deg[_digraph.source(arcs[i])]; 2672 } 2673 } 2674 2675 virtual void erase(const Arc& arc) { 2676 _deg[_digraph.source(arc)]; 2677 } 2678 2679 virtual void erase(const std::vector<Arc>& arcs) { 2680 for (int i = 0; i < int(arcs.size()); ++i) { 2681 _deg[_digraph.source(arcs[i])]; 2682 } 2683 } 2684 2685 virtual void build() { 2686 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2687 _deg[it] = countOutArcs(_digraph, it); 2688 } 2689 } 2690 2691 virtual void clear() { 2692 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2693 _deg[it] = 0; 2694 } 2695 } 2696 private: 2697 2698 const Digraph& _digraph; 2699 AutoNodeMap _deg; 2700 }; 2701 1783 2702 /// @} 1784 2703 }
Note: See TracChangeset
for help on using the changeset viewer.