lemon/maps.h
changeset 222 f9a18c21dba8
parent 209 765619b7cbb2
child 280 e7f8647ce760
equal deleted inserted replaced
22:13fae95f3777 23:f3873b65f677
    21 
    21 
    22 #include <iterator>
    22 #include <iterator>
    23 #include <functional>
    23 #include <functional>
    24 #include <vector>
    24 #include <vector>
    25 
    25 
    26 #include <lemon/bits/utility.h>
    26 #include <lemon/core.h>
    27 #include <lemon/bits/traits.h>
       
    28 
    27 
    29 ///\file
    28 ///\file
    30 ///\ingroup maps
    29 ///\ingroup maps
    31 ///\brief Miscellaneous property maps
    30 ///\brief Miscellaneous property maps
    32 
    31 
  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