COIN-OR::LEMON - Graph Library

Changeset 220:a5d8c039f218 in lemon-1.2


Ignore:
Timestamp:
07/15/08 13:15:39 (16 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Reorganize header files (Ticket #97)

In addition on some places the DefaultMap?<G, K, V> is replaced with
ItemSetTraits?<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.

Files:
2 added
3 deleted
31 edited

Legend:

Unmodified
Added
Removed
  • demo/graph_to_eps_demo.cc

    r211 r220  
    3232
    3333#include<lemon/list_graph.h>
    34 #include<lemon/graph_utils.h>
    3534#include<lemon/graph_to_eps.h>
    3635#include<lemon/math.h>
  • lemon/Makefile.am

    r195 r220  
    2525        lemon/concept_check.h \
    2626        lemon/counter.h \
     27        lemon/core.h \
    2728        lemon/dfs.h \
    2829        lemon/dijkstra.h \
     
    3031        lemon/error.h \
    3132        lemon/graph_to_eps.h \
    32         lemon/graph_utils.h \
    3333        lemon/kruskal.h \
    3434        lemon/lgf_reader.h \
     
    5050        lemon/bits/bezier.h \
    5151        lemon/bits/default_map.h \
     52        lemon/bits/enable_if.h \
    5253        lemon/bits/graph_extender.h \
    53         lemon/bits/invalid.h \
    5454        lemon/bits/map_extender.h \
    5555        lemon/bits/path_dump.h \
    5656        lemon/bits/traits.h \
    57         lemon/bits/utility.h \
    5857        lemon/bits/vector_map.h
    5958
  • lemon/base.cc

    r209 r220  
    2121
    2222#include<lemon/tolerance.h>
    23 #include<lemon/bits/invalid.h>
     23#include<lemon/core.h>
    2424namespace lemon {
    2525
  • lemon/bfs.h

    r210 r220  
    2525
    2626#include <lemon/list_graph.h>
    27 #include <lemon/graph_utils.h>
    2827#include <lemon/bits/path_dump.h>
    29 #include <lemon/bits/invalid.h>
     28#include <lemon/core.h>
    3029#include <lemon/error.h>
    3130#include <lemon/maps.h>
  • lemon/bits/alteration_notifier.h

    r209 r220  
    2323#include <list>
    2424
    25 #include <lemon/bits/utility.h>
     25#include <lemon/core.h>
    2626
    2727///\ingroup graphbits
  • lemon/bits/base_extender.h

    r209 r220  
    2020#define LEMON_BITS_BASE_EXTENDER_H
    2121
    22 #include <lemon/bits/invalid.h>
     22#include <lemon/core.h>
    2323#include <lemon/error.h>
    2424
  • lemon/bits/graph_extender.h

    r209 r220  
    2020#define LEMON_BITS_GRAPH_EXTENDER_H
    2121
    22 #include <lemon/bits/invalid.h>
    23 #include <lemon/bits/utility.h>
     22#include <lemon/core.h>
    2423
    2524#include <lemon/bits/map_extender.h>
  • lemon/bits/traits.h

    r209 r220  
    2020#define LEMON_BITS_TRAITS_H
    2121
    22 #include <lemon/bits/utility.h>
    23 
    2422///\file
    2523///\brief Traits for graphs and maps
    2624///
    2725
     26#include <lemon/bits/enable_if.h>
     27
    2828namespace lemon {
     29
     30  struct InvalidType {};
     31
    2932  template <typename _Graph, typename _Item>
    3033  class ItemSetTraits {};
  • lemon/bits/vector_map.h

    r209 r220  
    2323#include <algorithm>
    2424
    25 #include <lemon/bits/traits.h>
    26 #include <lemon/bits/utility.h>
    27 
     25#include <lemon/core.h>
    2826#include <lemon/bits/alteration_notifier.h>
    2927
  • lemon/concepts/digraph.h

    r209 r220  
    2424///\brief The concept of directed graphs.
    2525
    26 #include <lemon/bits/invalid.h>
    27 #include <lemon/bits/utility.h>
     26#include <lemon/core.h>
    2827#include <lemon/concepts/maps.h>
    2928#include <lemon/concept_check.h>
  • lemon/concepts/graph.h

    r209 r220  
    2626#include <lemon/concepts/graph_components.h>
    2727#include <lemon/concepts/graph.h>
    28 #include <lemon/bits/utility.h>
     28#include <lemon/core.h>
    2929
    3030namespace lemon {
  • lemon/concepts/graph_components.h

    r209 r220  
    2525#define LEMON_CONCEPT_GRAPH_COMPONENTS_H
    2626
    27 #include <lemon/bits/invalid.h>
     27#include <lemon/core.h>
    2828#include <lemon/concepts/maps.h>
    2929
  • lemon/concepts/heap.h

    r209 r220  
    2424#define LEMON_CONCEPT_HEAP_H
    2525
    26 #include <lemon/bits/invalid.h>
     26#include <lemon/core.h>
    2727
    2828namespace lemon {
  • lemon/concepts/maps.h

    r210 r220  
    2020#define LEMON_CONCEPT_MAPS_H
    2121
    22 #include <lemon/bits/utility.h>
     22#include <lemon/core.h>
    2323#include <lemon/concept_check.h>
    2424
  • lemon/concepts/path.h

    r212 r220  
    2626#define LEMON_CONCEPT_PATH_H
    2727
    28 #include <lemon/bits/invalid.h>
    29 #include <lemon/bits/utility.h>
     28#include <lemon/core.h>
    3029#include <lemon/concept_check.h>
    3130
  • lemon/dfs.h

    r210 r220  
    2525
    2626#include <lemon/list_graph.h>
    27 #include <lemon/graph_utils.h>
    2827#include <lemon/bits/path_dump.h>
    29 #include <lemon/bits/invalid.h>
     28#include <lemon/core.h>
    3029#include <lemon/error.h>
    3130#include <lemon/maps.h>
  • lemon/dijkstra.h

    r210 r220  
    2828#include <lemon/bin_heap.h>
    2929#include <lemon/bits/path_dump.h>
    30 #include <lemon/bits/invalid.h>
     30#include <lemon/core.h>
    3131#include <lemon/error.h>
    3232#include <lemon/maps.h>
  • lemon/dim2.h

    r209 r220  
    2121
    2222#include <iostream>
    23 #include <lemon/bits/utility.h>
     23#include <lemon/core.h>
    2424
    2525///\ingroup misc
  • lemon/graph_to_eps.h

    r212 r220  
    3636
    3737#include<lemon/math.h>
    38 #include<lemon/bits/invalid.h>
     38#include<lemon/core.h>
    3939#include<lemon/dim2.h>
    4040#include<lemon/maps.h>
  • lemon/kruskal.h

    r216 r220  
    2323#include <vector>
    2424#include <lemon/unionfind.h>
    25 // #include <lemon/graph_utils.h>
    2625#include <lemon/maps.h>
    2726
    28 // #include <lemon/radix_sort.h>
    29 
    30 #include <lemon/bits/utility.h>
     27#include <lemon/core.h>
    3128#include <lemon/bits/traits.h>
    3229
     
    301298  /// \return The total cost of the found spanning tree.
    302299  ///
    303   /// \note If the input graph is not (weakly) connected, a spanning 
     300  /// \note If the input graph is not (weakly) connected, a spanning
    304301  /// forest is calculated instead of a spanning tree.
    305302
  • lemon/lgf_reader.h

    r212 r220  
    3333
    3434#include <lemon/assert.h>
    35 #include <lemon/graph_utils.h>
     35#include <lemon/core.h>
    3636
    3737#include <lemon/lgf_writer.h>
  • lemon/lgf_writer.h

    r212 r220  
    3535
    3636#include <lemon/assert.h>
    37 #include <lemon/graph_utils.h>
     37#include <lemon/core.h>
     38#include <lemon/maps.h>
    3839
    3940namespace lemon {
  • lemon/list_graph.h

    r212 r220  
    2424///\brief ListDigraph, ListGraph classes.
    2525
     26#include <lemon/core.h>
     27#include <lemon/error.h>
    2628#include <lemon/bits/graph_extender.h>
    2729
  • lemon/maps.h

    r209 r220  
    2424#include <vector>
    2525
    26 #include <lemon/bits/utility.h>
    27 #include <lemon/bits/traits.h>
     26#include <lemon/core.h>
    2827
    2928///\file
     
    17811780  }
    17821781
     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
    17832702  /// @}
    17842703}
  • lemon/path.h

    r209 r220  
    2929
    3030#include <lemon/error.h>
    31 #include <lemon/bits/invalid.h>
     31#include <lemon/core.h>
    3232#include <lemon/concepts/path.h>
    3333
  • lemon/smart_graph.h

    r209 r220  
    2626#include <vector>
    2727
    28 #include <lemon/bits/invalid.h>
    29 
    30 #include <lemon/bits/base_extender.h>
    31 #include <lemon/bits/graph_extender.h>
    32 
    33 #include <lemon/bits/utility.h>
     28#include <lemon/core.h>
    3429#include <lemon/error.h>
    35 
    3630#include <lemon/bits/graph_extender.h>
    3731
  • lemon/unionfind.h

    r209 r220  
    3131#include <functional>
    3232
    33 #include <lemon/bits/invalid.h>
     33#include <lemon/core.h>
    3434
    3535namespace lemon {
  • test/dijkstra_test.cc

    r210 r220  
    2020#include <lemon/smart_graph.h>
    2121#include <lemon/list_graph.h>
    22 #include <lemon/graph_utils.h>
    2322#include <lemon/dijkstra.h>
    2423#include <lemon/path.h>
  • test/graph_copy_test.cc

    r209 r220  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/lgf_reader.h>
    22 #include <lemon/graph_utils.h>
    2322#include <lemon/error.h>
    2423
  • test/graph_test.h

    r209 r220  
    2020#define LEMON_TEST_GRAPH_TEST_H
    2121
    22 #include <lemon/graph_utils.h>
     22#include <lemon/core.h>
    2323#include "test_tools.h"
    2424
  • test/graph_utils_test.cc

    r210 r220  
    2121
    2222#include <lemon/random.h>
    23 #include <lemon/graph_utils.h>
    2423#include <lemon/list_graph.h>
    2524#include <lemon/smart_graph.h>
     25#include <lemon/maps.h>
    2626
    2727#include "graph_test.h"
Note: See TracChangeset for help on using the changeset viewer.