1778 template<typename Iterator> |
1777 template<typename Iterator> |
1779 inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) { |
1778 inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) { |
1780 return LoggerBoolMap<Iterator>(it); |
1779 return LoggerBoolMap<Iterator>(it); |
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 id-to-item map. |
|
1830 explicit InverseMap(const Graph& graph) : _graph(&graph) {} |
|
1831 |
|
1832 /// \brief Constructor. |
|
1833 /// |
|
1834 /// Constructor for creating an id-to-item 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 graph-map type. |
|
1856 |
|
1857 /// This type provides simple invertable graph-maps. |
|
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 n-1, 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 in-degrees. |
|
2457 /// |
|
2458 /// This map returns the in-degree 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 in-degree 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 in-degree 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 out-degrees. |
|
2581 /// |
|
2582 /// This map returns the out-degree 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 out-degree 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 out-degree 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 } |
1785 |
2704 |
1786 #endif // LEMON_MAPS_H |
2705 #endif // LEMON_MAPS_H |