COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
3 added
2 deleted
35 edited

Legend:

Unmodified
Added
Removed

  • configure.ac

    r226 r225  
    8989AC_CHECK_FUNCS(gettimeofday times ctime_r)
    9090
    91 dnl Add dependencies on files generated by configure.
    92 AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    93   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in'])
    94 
    9591AC_CONFIG_FILES([
    9692Makefile

  • demo/graph_to_eps_demo.cc

    r220 r211  
    3232
    3333#include<lemon/list_graph.h>
     34#include<lemon/graph_utils.h>
    3435#include<lemon/graph_to_eps.h>
    3536#include<lemon/math.h>

  • doc/Doxyfile.in

    r226 r224  
    146146DISABLE_INDEX          = NO
    147147ENUM_VALUES_PER_LINE   = 4
    148 GENERATE_TREEVIEW      = NO
     148GENERATE_TREEVIEW      = YES
    149149TREEVIEW_WIDTH         = 250
    150150#---------------------------------------------------------------------------

  • lemon/Makefile.am

    r220 r195  
    2525        lemon/concept_check.h \
    2626        lemon/counter.h \
    27         lemon/core.h \
    2827        lemon/dfs.h \
    2928        lemon/dijkstra.h \
    … …  
    3130        lemon/error.h \
    3231        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 \
    5352        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 \
    5758        lemon/bits/vector_map.h
    5859

  • lemon/assert.h

    r218 r212  
    238238
    239239#    if LEMON_ENABLE_DEBUG
    240 #      define LEMON_DEBUG(exp, msg)                                     \
     240#      define LEMON_DEBUG(exp, msg)
    241241         (static_cast<void> (!!(exp) ? 0 : (                            \
    242242           LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                     \

  • lemon/base.cc

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

  • lemon/bfs.h

    r220 r210  
    2525
    2626#include <lemon/list_graph.h>
     27#include <lemon/graph_utils.h>
    2728#include <lemon/bits/path_dump.h>
    28 #include <lemon/core.h>
     29#include <lemon/bits/invalid.h>
    2930#include <lemon/error.h>
    3031#include <lemon/maps.h>

  • lemon/bits/alteration_notifier.h

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

  • lemon/bits/base_extender.h

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

  • lemon/bits/graph_extender.h

    r220 r209  
    2020#define LEMON_BITS_GRAPH_EXTENDER_H
    2121
    22 #include <lemon/core.h>
     22#include <lemon/bits/invalid.h>
     23#include <lemon/bits/utility.h>
    2324
    2425#include <lemon/bits/map_extender.h>

  • lemon/bits/traits.h

    r220 r209  
    2020#define LEMON_BITS_TRAITS_H
    2121
     22#include <lemon/bits/utility.h>
     23
    2224///\file
    2325///\brief Traits for graphs and maps
    2426///
    2527
    26 #include <lemon/bits/enable_if.h>
    27 
    2828namespace lemon {
    29 
    30   struct InvalidType {};
    31 
    3229  template <typename _Graph, typename _Item>
    3330  class ItemSetTraits {};

  • lemon/bits/vector_map.h

    r220 r209  
    2323#include <algorithm>
    2424
    25 #include <lemon/core.h>
     25#include <lemon/bits/traits.h>
     26#include <lemon/bits/utility.h>
     27
    2628#include <lemon/bits/alteration_notifier.h>
    2729

  • lemon/concepts/digraph.h

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

  • lemon/concepts/graph.h

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

  • lemon/concepts/graph_components.h

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

  • lemon/concepts/heap.h

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

  • lemon/concepts/maps.h

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

  • lemon/concepts/path.h

    r220 r212  
    2626#define LEMON_CONCEPT_PATH_H
    2727
    28 #include <lemon/core.h>
     28#include <lemon/bits/invalid.h>
     29#include <lemon/bits/utility.h>
    2930#include <lemon/concept_check.h>
    3031

  • lemon/dfs.h

    r220 r210  
    2525
    2626#include <lemon/list_graph.h>
     27#include <lemon/graph_utils.h>
    2728#include <lemon/bits/path_dump.h>
    28 #include <lemon/core.h>
     29#include <lemon/bits/invalid.h>
    2930#include <lemon/error.h>
    3031#include <lemon/maps.h>

  • lemon/dijkstra.h

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

  • lemon/dim2.h

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

  • lemon/graph_to_eps.h

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

  • lemon/kruskal.h

    r220 r216  
    2323#include <vector>
    2424#include <lemon/unionfind.h>
     25// #include <lemon/graph_utils.h>
    2526#include <lemon/maps.h>
    2627
    27 #include <lemon/core.h>
     28// #include <lemon/radix_sort.h>
     29
     30#include <lemon/bits/utility.h>
    2831#include <lemon/bits/traits.h>
    2932
    … …  
    298301  /// \return The total cost of the found spanning tree.
    299302  ///
    300   /// \note If the input graph is not (weakly) connected, a spanning
     303  /// \note If the input graph is not (weakly) connected, a spanning 
    301304  /// forest is calculated instead of a spanning tree.
    302305

  • lemon/lgf_reader.h

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

  • lemon/lgf_writer.h

    r220 r212  
    3535
    3636#include <lemon/assert.h>
    37 #include <lemon/core.h>
    38 #include <lemon/maps.h>
     37#include <lemon/graph_utils.h>
    3938
    4039namespace lemon {

  • lemon/list_graph.h

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

  • lemon/maps.h

    r220 r209  
    2424#include <vector>
    2525
    26 #include <lemon/core.h>
     26#include <lemon/bits/utility.h>
     27#include <lemon/bits/traits.h>
    2728
    2829///\file
    … …  
    17801781  }
    17811782
    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 
    27021783  /// @}
    27031784}

  • lemon/path.h

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

  • lemon/smart_graph.h

    r220 r209  
    2626#include <vector>
    2727
    28 #include <lemon/core.h>
     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>
    2934#include <lemon/error.h>
     35
    3036#include <lemon/bits/graph_extender.h>
    3137

  • lemon/unionfind.h

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

  • test/bfs_test.cc

    r222 r209  
    9898
    9999
    100   for(ArcIt e(G); e!=INVALID; ++e) {
     100  for(ArcIt e(G); e==INVALID; ++e) {
    101101    Node u=G.source(e);
    102102    Node v=G.target(e);
    103103    check( !bfs_test.reached(u) ||
    104            (bfs_test.dist(v) <= bfs_test.dist(u)+1),
     104           (bfs_test.dist(v) > bfs_test.dist(u)+1),
    105105           "Wrong output.");
    106106  }
    107107
    108   for(NodeIt v(G); v!=INVALID; ++v) {
     108  for(NodeIt v(G); v==INVALID; ++v) {
    109109    check(bfs_test.reached(v),"Each node should be reached.");
    110110    if ( bfs_test.predArc(v)!=INVALID ) {

  • test/dijkstra_test.cc

    r220 r210  
    2020#include <lemon/smart_graph.h>
    2121#include <lemon/list_graph.h>
     22#include <lemon/graph_utils.h>
    2223#include <lemon/dijkstra.h>
    2324#include <lemon/path.h>

  • test/graph_copy_test.cc

    r220 r209  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/lgf_reader.h>
     22#include <lemon/graph_utils.h>
    2223#include <lemon/error.h>
    2324

  • test/graph_test.h

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

  • test/graph_utils_test.cc

    r220 r210  
    2121
    2222#include <lemon/random.h>
     23#include <lemon/graph_utils.h>
    2324#include <lemon/list_graph.h>
    2425#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.