COIN-OR::LEMON - Graph Library

Ignore:
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r330 r318  
    4141some graph features like arc/edge or node deletion.
    4242
     43Alteration of standard containers need a very limited number of
     44operations, these together satisfy the everyday requirements.
     45In the case of graph structures, different operations are needed which do
     46not alter the physical graph, but gives another view. If some nodes or
     47arcs have to be hidden or the reverse oriented graph have to be used, then
     48this is the case. It also may happen that in a flow implementation
     49the residual graph can be accessed by another algorithm, or a node-set
     50is to be shrunk for another algorithm.
     51LEMON also provides a variety of graphs for these requirements called
     52\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
     53in conjunction with other graph representations.
     54
    4355You are free to use the graph structure that fit your requirements
    4456the best, most graph algorithms and auxiliary data structures can be used
     
    4658
    4759<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
     60*/
     61
     62/**
     63@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
     64@ingroup graphs
     65\brief Graph types between real graphs and graph adaptors.
     66
     67This group describes some graph types between real graphs and graph adaptors.
     68These classes wrap graphs to give new functionality as the adaptors do it.
     69On the other hand they are not light-weight structures as the adaptors.
    4870*/
    4971
     
    134156
    135157/**
     158@defgroup matrices Matrices
     159@ingroup datas
     160\brief Two dimensional data storages implemented in LEMON.
     161
     162This group describes two dimensional data storages implemented in LEMON.
     163*/
     164
     165/**
    136166@defgroup paths Path Structures
    137167@ingroup datas
     
    185215
    186216/**
     217@defgroup max_flow Maximum Flow Algorithms
     218@ingroup algs
     219\brief Algorithms for finding maximum flows.
     220
     221This group describes the algorithms for finding maximum flows and
     222feasible circulations.
     223
     224The maximum flow problem is to find a flow between a single source and
     225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
     226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     227function and given \f$s, t \in V\f$ source and target node. The
     228maximum flow is the \f$f_a\f$ solution of the next optimization problem:
     229
     230\f[ 0 \le f_a \le c_a \f]
     231\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
     232\qquad \forall u \in V \setminus \{s,t\}\f]
     233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
     234
     235LEMON contains several algorithms for solving maximum flow problems:
     236- \ref lemon::EdmondsKarp "Edmonds-Karp"
     237- \ref lemon::Preflow "Goldberg's Preflow algorithm"
     238- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
     239- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
     240
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
     242fastest method to compute the maximum flow. All impelementations
     243provides functions to query the minimum cut, which is the dual linear
     244programming problem of the maximum flow.
     245*/
     246
     247/**
     248@defgroup min_cost_flow Minimum Cost Flow Algorithms
     249@ingroup algs
     250
     251\brief Algorithms for finding minimum cost flows and circulations.
     252
     253This group describes the algorithms for finding minimum cost flows and
     254circulations.
     255*/
     256
     257/**
     258@defgroup min_cut Minimum Cut Algorithms
     259@ingroup algs
     260
     261\brief Algorithms for finding minimum cut in graphs.
     262
     263This group describes the algorithms for finding minimum cut in graphs.
     264
     265The minimum cut problem is to find a non-empty and non-complete
     266\f$X\f$ subset of the vertices with minimum overall capacity on
     267outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
     268\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     269cut is the \f$X\f$ solution of the next optimization problem:
     270
     271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
     272\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     273
     274LEMON contains several algorithms related to minimum cut problems:
     275
     276- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
     277  in directed graphs
     278- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
     279  calculate minimum cut in undirected graphs
     280- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
     281  pairs minimum cut in undirected graphs
     282
     283If you want to find minimum cut just between two distinict nodes,
     284please see the \ref max_flow "Maximum Flow page".
     285*/
     286
     287/**
     288@defgroup graph_prop Connectivity and Other Graph Properties
     289@ingroup algs
     290\brief Algorithms for discovering the graph properties
     291
     292This group describes the algorithms for discovering the graph properties
     293like connectivity, bipartiteness, euler property, simplicity etc.
     294
     295\image html edge_biconnected_components.png
     296\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
     297*/
     298
     299/**
     300@defgroup planar Planarity Embedding and Drawing
     301@ingroup algs
     302\brief Algorithms for planarity checking, embedding and drawing
     303
     304This group describes the algorithms for planarity checking,
     305embedding and drawing.
     306
     307\image html planar.png
     308\image latex planar.eps "Plane graph" width=\textwidth
     309*/
     310
     311/**
     312@defgroup matching Matching Algorithms
     313@ingroup algs
     314\brief Algorithms for finding matchings in graphs and bipartite graphs.
     315
     316This group contains algorithm objects and functions to calculate
     317matchings in graphs and bipartite graphs. The general matching problem is
     318finding a subset of the arcs which does not shares common endpoints.
     319
     320There are several different algorithms for calculate matchings in
     321graphs.  The matching problems in bipartite graphs are generally
     322easier than in general graphs. The goal of the matching optimization
     323can be the finding maximum cardinality, maximum weight or minimum cost
     324matching. The search can be constrained to find perfect or
     325maximum cardinality matching.
     326
     327LEMON contains the next algorithms:
     328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
     329  augmenting path algorithm for calculate maximum cardinality matching in
     330  bipartite graphs
     331- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
     332  algorithm for calculate maximum cardinality matching in bipartite graphs
     333- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
     334  Successive shortest path algorithm for calculate maximum weighted matching
     335  and maximum weighted bipartite matching in bipartite graph
     336- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
     337  Successive shortest path algorithm for calculate minimum cost maximum
     338  matching in bipartite graph
     339- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
     340  for calculate maximum cardinality matching in general graph
     341- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
     342  shrinking algorithm for calculate maximum weighted matching in general
     343  graph
     344- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
     345  Edmond's blossom shrinking algorithm for calculate maximum weighted
     346  perfect matching in general graph
     347
     348\image html bipartite_matching.png
     349\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
     350*/
     351
     352/**
    187353@defgroup spantree Minimum Spanning Tree Algorithms
    188354@ingroup algs
     
    191357This group describes the algorithms for finding a minimum cost spanning
    192358tree in a graph
     359*/
     360
     361/**
     362@defgroup auxalg Auxiliary Algorithms
     363@ingroup algs
     364\brief Auxiliary algorithms implemented in LEMON.
     365
     366This group describes some algorithms implemented in LEMON
     367in order to make it easier to implement complex algorithms.
     368*/
     369
     370/**
     371@defgroup approx Approximation Algorithms
     372@ingroup algs
     373\brief Approximation algorithms.
     374
     375This group describes the approximation and heuristic algorithms
     376implemented in LEMON.
     377*/
     378
     379/**
     380@defgroup gen_opt_group General Optimization Tools
     381\brief This group describes some general optimization frameworks
     382implemented in LEMON.
     383
     384This group describes some general optimization frameworks
     385implemented in LEMON.
     386*/
     387
     388/**
     389@defgroup lp_group Lp and Mip Solvers
     390@ingroup gen_opt_group
     391\brief Lp and Mip solver interfaces for LEMON.
     392
     393This group describes Lp and Mip solver interfaces for LEMON. The
     394various LP solvers could be used in the same manner with this
     395interface.
     396*/
     397
     398/**
     399@defgroup lp_utils Tools for Lp and Mip Solvers
     400@ingroup lp_group
     401\brief Helper tools to the Lp and Mip solvers.
     402
     403This group adds some helper tools to general optimization framework
     404implemented in LEMON.
     405*/
     406
     407/**
     408@defgroup metah Metaheuristics
     409@ingroup gen_opt_group
     410\brief Metaheuristics for LEMON library.
     411
     412This group describes some metaheuristic optimization tools.
    193413*/
    194414
     
    239459
    240460This group describes the tools for importing and exporting graphs
    241 and graph related data. Now it supports the LEMON format
    242 and the encapsulated postscript (EPS) format.
     461and graph related data. Now it supports the \ref lgf-format
     462"LEMON Graph Format", the \c DIMACS format and the encapsulated
    243463postscript (EPS) format.
    244464*/
     
    304524@ingroup concept
    305525\brief Skeleton and concept checking classes for maps
    306  
     526
    307527This group describes the skeletons and concept checking classes of maps.
    308528*/
     
    319539build the library.
    320540*/
     541
     542/**
     543@defgroup tools Standalone utility applications
     544
     545Some utility applications are listed here.
     546
     547The standard compilation procedure (<tt>./configure;make</tt>) will compile
     548them, as well.
     549*/
     550
  • doc/mainpage.dox

    r332 r314  
    4242\subsection howtoread How to read the documentation
    4343
     44If you want to get a quick start and see the most important features then
     45take a look at our \ref quicktour
     46"Quick Tour to LEMON" which will guide you along.
     47
     48If you already feel like using our library, see the page that tells you
     49\ref getstart "How to start using LEMON".
     50
     51If you
     52want to see how LEMON works, see
     53some \ref demoprograms "demo programs".
     54
    4455If you know what you are looking for then try to find it under the
    4556<a class="el" href="modules.html">Modules</a>
  • lemon/maps.h

    r327 r314  
    18561856    InverseMap inverse() const { return InverseMap(*_graph);}
    18571857
     1858  };
     1859
     1860
     1861  /// \brief General invertable graph-map type.
     1862
     1863  /// This type provides simple invertable graph-maps.
     1864  /// The InvertableMap wraps an arbitrary ReadWriteMap
     1865  /// and if a key is set to a new value then store it
     1866  /// in the inverse map.
     1867  ///
     1868  /// The values of the map can be accessed
     1869  /// with stl compatible forward iterator.
     1870  ///
     1871  /// \tparam _Graph The graph type.
     1872  /// \tparam _Item The item type of the graph.
     1873  /// \tparam _Value The value type of the map.
     1874  ///
     1875  /// \see IterableValueMap
     1876  template <typename _Graph, typename _Item, typename _Value>
     1877  class InvertableMap
     1878    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
     1879  private:
     1880
     1881    typedef typename ItemSetTraits<_Graph, _Item>::
     1882    template Map<_Value>::Type Map;
     1883    typedef _Graph Graph;
     1884
     1885    typedef std::map<_Value, _Item> Container;
     1886    Container _inv_map;
     1887
     1888  public:
     1889
     1890    /// The key type of InvertableMap (Node, Arc, Edge).
     1891    typedef typename Map::Key Key;
     1892    /// The value type of the InvertableMap.
     1893    typedef typename Map::Value Value;
     1894
     1895    /// \brief Constructor.
     1896    ///
     1897    /// Construct a new InvertableMap for the graph.
     1898    ///
     1899    explicit InvertableMap(const Graph& graph) : Map(graph) {}
     1900
     1901    /// \brief Forward iterator for values.
     1902    ///
     1903    /// This iterator is an stl compatible forward
     1904    /// iterator on the values of the map. The values can
     1905    /// be accessed in the [beginValue, endValue) range.
     1906    ///
     1907    class ValueIterator
     1908      : public std::iterator<std::forward_iterator_tag, Value> {
     1909      friend class InvertableMap;
     1910    private:
     1911      ValueIterator(typename Container::const_iterator _it)
     1912        : it(_it) {}
     1913    public:
     1914
     1915      ValueIterator() {}
     1916
     1917      ValueIterator& operator++() { ++it; return *this; }
     1918      ValueIterator operator++(int) {
     1919        ValueIterator tmp(*this);
     1920        operator++();
     1921        return tmp;
     1922      }
     1923
     1924      const Value& operator*() const { return it->first; }
     1925      const Value* operator->() const { return &(it->first); }
     1926
     1927      bool operator==(ValueIterator jt) const { return it == jt.it; }
     1928      bool operator!=(ValueIterator jt) const { return it != jt.it; }
     1929
     1930    private:
     1931      typename Container::const_iterator it;
     1932    };
     1933
     1934    /// \brief Returns an iterator to the first value.
     1935    ///
     1936    /// Returns an stl compatible iterator to the
     1937    /// first value of the map. The values of the
     1938    /// map can be accessed in the [beginValue, endValue)
     1939    /// range.
     1940    ValueIterator beginValue() const {
     1941      return ValueIterator(_inv_map.begin());
     1942    }
     1943
     1944    /// \brief Returns an iterator after the last value.
     1945    ///
     1946    /// Returns an stl compatible iterator after the
     1947    /// last value of the map. The values of the
     1948    /// map can be accessed in the [beginValue, endValue)
     1949    /// range.
     1950    ValueIterator endValue() const {
     1951      return ValueIterator(_inv_map.end());
     1952    }
     1953
     1954    /// \brief The setter function of the map.
     1955    ///
     1956    /// Sets the mapped value.
     1957    void set(const Key& key, const Value& val) {
     1958      Value oldval = Map::operator[](key);
     1959      typename Container::iterator it = _inv_map.find(oldval);
     1960      if (it != _inv_map.end() && it->second == key) {
     1961        _inv_map.erase(it);
     1962      }
     1963      _inv_map.insert(make_pair(val, key));
     1964      Map::set(key, val);
     1965    }
     1966
     1967    /// \brief The getter function of the map.
     1968    ///
     1969    /// It gives back the value associated with the key.
     1970    typename MapTraits<Map>::ConstReturnValue
     1971    operator[](const Key& key) const {
     1972      return Map::operator[](key);
     1973    }
     1974
     1975    /// \brief Gives back the item by its value.
     1976    ///
     1977    /// Gives back the item by its value.
     1978    Key operator()(const Value& key) const {
     1979      typename Container::const_iterator it = _inv_map.find(key);
     1980      return it != _inv_map.end() ? it->second : INVALID;
     1981    }
     1982
     1983  protected:
     1984
     1985    /// \brief Erase the key from the map.
     1986    ///
     1987    /// Erase the key to the map. It is called by the
     1988    /// \c AlterationNotifier.
     1989    virtual void erase(const Key& key) {
     1990      Value val = Map::operator[](key);
     1991      typename Container::iterator it = _inv_map.find(val);
     1992      if (it != _inv_map.end() && it->second == key) {
     1993        _inv_map.erase(it);
     1994      }
     1995      Map::erase(key);
     1996    }
     1997
     1998    /// \brief Erase more keys from the map.
     1999    ///
     2000    /// Erase more keys from the map. It is called by the
     2001    /// \c AlterationNotifier.
     2002    virtual void erase(const std::vector<Key>& keys) {
     2003      for (int i = 0; i < int(keys.size()); ++i) {
     2004        Value val = Map::operator[](keys[i]);
     2005        typename Container::iterator it = _inv_map.find(val);
     2006        if (it != _inv_map.end() && it->second == keys[i]) {
     2007          _inv_map.erase(it);
     2008        }
     2009      }
     2010      Map::erase(keys);
     2011    }
     2012
     2013    /// \brief Clear the keys from the map and inverse map.
     2014    ///
     2015    /// Clear the keys from the map and inverse map. It is called by the
     2016    /// \c AlterationNotifier.
     2017    virtual void clear() {
     2018      _inv_map.clear();
     2019      Map::clear();
     2020    }
     2021
     2022  public:
     2023
     2024    /// \brief The inverse map type.
     2025    ///
     2026    /// The inverse of this map. The subscript operator of the map
     2027    /// gives back always the item what was last assigned to the value.
     2028    class InverseMap {
     2029    public:
     2030      /// \brief Constructor of the InverseMap.
     2031      ///
     2032      /// Constructor of the InverseMap.
     2033      explicit InverseMap(const InvertableMap& inverted)
     2034        : _inverted(inverted) {}
     2035
     2036      /// The value type of the InverseMap.
     2037      typedef typename InvertableMap::Key Value;
     2038      /// The key type of the InverseMap.
     2039      typedef typename InvertableMap::Value Key;
     2040
     2041      /// \brief Subscript operator.
     2042      ///
     2043      /// Subscript operator. It gives back always the item
     2044      /// what was last assigned to the value.
     2045      Value operator[](const Key& key) const {
     2046        return _inverted(key);
     2047      }
     2048
     2049    private:
     2050      const InvertableMap& _inverted;
     2051    };
     2052
     2053    /// \brief It gives back the just readable inverse map.
     2054    ///
     2055    /// It gives back the just readable inverse map.
     2056    InverseMap inverse() const {
     2057      return InverseMap(*this);
     2058    }
     2059
     2060  };
     2061
     2062  /// \brief Provides a mutable, continuous and unique descriptor for each
     2063  /// item in the graph.
     2064  ///
     2065  /// The DescriptorMap class provides a unique and continuous (but mutable)
     2066  /// descriptor (id) for each item of the same type (e.g. node) in the
     2067  /// graph. This id is <ul><li>\b unique: different items (nodes) get
     2068  /// different ids <li>\b continuous: the range of the ids is the set of
     2069  /// integers between 0 and \c n-1, where \c n is the number of the items of
     2070  /// this type (e.g. nodes) (so the id of a node can change if you delete an
     2071  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
     2072  /// with its member class \c InverseMap, or with the \c operator() member.
     2073  ///
     2074  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
     2075  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
     2076  /// Edge.
     2077  template <typename _Graph, typename _Item>
     2078  class DescriptorMap
     2079    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
     2080
     2081    typedef _Item Item;
     2082    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
     2083
     2084  public:
     2085    /// The graph class of DescriptorMap.
     2086    typedef _Graph Graph;
     2087
     2088    /// The key type of DescriptorMap (Node, Arc, Edge).
     2089    typedef typename Map::Key Key;
     2090    /// The value type of DescriptorMap.
     2091    typedef typename Map::Value Value;
     2092
     2093    /// \brief Constructor.
     2094    ///
     2095    /// Constructor for descriptor map.
     2096    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
     2097      Item it;
     2098      const typename Map::Notifier* nf = Map::notifier();
     2099      for (nf->first(it); it != INVALID; nf->next(it)) {
     2100        Map::set(it, _inv_map.size());
     2101        _inv_map.push_back(it);
     2102      }
     2103    }
     2104
     2105  protected:
     2106
     2107    /// \brief Add a new key to the map.
     2108    ///
     2109    /// Add a new key to the map. It is called by the
     2110    /// \c AlterationNotifier.
     2111    virtual void add(const Item& item) {
     2112      Map::add(item);
     2113      Map::set(item, _inv_map.size());
     2114      _inv_map.push_back(item);
     2115    }
     2116
     2117    /// \brief Add more new keys to the map.
     2118    ///
     2119    /// Add more new keys to the map. It is called by the
     2120    /// \c AlterationNotifier.
     2121    virtual void add(const std::vector<Item>& items) {
     2122      Map::add(items);
     2123      for (int i = 0; i < int(items.size()); ++i) {
     2124        Map::set(items[i], _inv_map.size());
     2125        _inv_map.push_back(items[i]);
     2126      }
     2127    }
     2128
     2129    /// \brief Erase the key from the map.
     2130    ///
     2131    /// Erase the key from the map. It is called by the
     2132    /// \c AlterationNotifier.
     2133    virtual void erase(const Item& item) {
     2134      Map::set(_inv_map.back(), Map::operator[](item));
     2135      _inv_map[Map::operator[](item)] = _inv_map.back();
     2136      _inv_map.pop_back();
     2137      Map::erase(item);
     2138    }
     2139
     2140    /// \brief Erase more keys from the map.
     2141    ///
     2142    /// Erase more keys from the map. It is called by the
     2143    /// \c AlterationNotifier.
     2144    virtual void erase(const std::vector<Item>& items) {
     2145      for (int i = 0; i < int(items.size()); ++i) {
     2146        Map::set(_inv_map.back(), Map::operator[](items[i]));
     2147        _inv_map[Map::operator[](items[i])] = _inv_map.back();
     2148        _inv_map.pop_back();
     2149      }
     2150      Map::erase(items);
     2151    }
     2152
     2153    /// \brief Build the unique map.
     2154    ///
     2155    /// Build the unique map. It is called by the
     2156    /// \c AlterationNotifier.
     2157    virtual void build() {
     2158      Map::build();
     2159      Item it;
     2160      const typename Map::Notifier* nf = Map::notifier();
     2161      for (nf->first(it); it != INVALID; nf->next(it)) {
     2162        Map::set(it, _inv_map.size());
     2163        _inv_map.push_back(it);
     2164      }
     2165    }
     2166
     2167    /// \brief Clear the keys from the map.
     2168    ///
     2169    /// Clear the keys from the map. It is called by the
     2170    /// \c AlterationNotifier.
     2171    virtual void clear() {
     2172      _inv_map.clear();
     2173      Map::clear();
     2174    }
     2175
     2176  public:
     2177
     2178    /// \brief Returns the maximal value plus one.
     2179    ///
     2180    /// Returns the maximal value plus one in the map.
     2181    unsigned int size() const {
     2182      return _inv_map.size();
     2183    }
     2184
     2185    /// \brief Swaps the position of the two items in the map.
     2186    ///
     2187    /// Swaps the position of the two items in the map.
     2188    void swap(const Item& p, const Item& q) {
     2189      int pi = Map::operator[](p);
     2190      int qi = Map::operator[](q);
     2191      Map::set(p, qi);
     2192      _inv_map[qi] = p;
     2193      Map::set(q, pi);
     2194      _inv_map[pi] = q;
     2195    }
     2196
     2197    /// \brief Gives back the \e descriptor of the item.
     2198    ///
     2199    /// Gives back the mutable and unique \e descriptor of the map.
     2200    int operator[](const Item& item) const {
     2201      return Map::operator[](item);
     2202    }
     2203
     2204    /// \brief Gives back the item by its descriptor.
     2205    ///
     2206    /// Gives back th item by its descriptor.
     2207    Item operator()(int id) const {
     2208      return _inv_map[id];
     2209    }
     2210
     2211  private:
     2212
     2213    typedef std::vector<Item> Container;
     2214    Container _inv_map;
     2215
     2216  public:
     2217    /// \brief The inverse map type of DescriptorMap.
     2218    ///
     2219    /// The inverse map type of DescriptorMap.
     2220    class InverseMap {
     2221    public:
     2222      /// \brief Constructor of the InverseMap.
     2223      ///
     2224      /// Constructor of the InverseMap.
     2225      explicit InverseMap(const DescriptorMap& inverted)
     2226        : _inverted(inverted) {}
     2227
     2228
     2229      /// The value type of the InverseMap.
     2230      typedef typename DescriptorMap::Key Value;
     2231      /// The key type of the InverseMap.
     2232      typedef typename DescriptorMap::Value Key;
     2233
     2234      /// \brief Subscript operator.
     2235      ///
     2236      /// Subscript operator. It gives back the item
     2237      /// that the descriptor belongs to currently.
     2238      Value operator[](const Key& key) const {
     2239        return _inverted(key);
     2240      }
     2241
     2242      /// \brief Size of the map.
     2243      ///
     2244      /// Returns the size of the map.
     2245      unsigned int size() const {
     2246        return _inverted.size();
     2247      }
     2248
     2249    private:
     2250      const DescriptorMap& _inverted;
     2251    };
     2252
     2253    /// \brief Gives back the inverse of the map.
     2254    ///
     2255    /// Gives back the inverse of the map.
     2256    const InverseMap inverse() const {
     2257      return InverseMap(*this);
     2258    }
    18582259  };
    18592260
  • test/graph_utils_test.cc

    r324 r220  
    3636  {
    3737    Digraph digraph;
    38     typename Digraph::template NodeMap<int> nodes(digraph);
    39     std::vector<Node> invNodes;
    4038    for (int i = 0; i < 10; ++i) {
    41       invNodes.push_back(digraph.addNode());
    42       nodes[invNodes.back()]=invNodes.size()-1;
    43     }
     39      digraph.addNode();
     40    }
     41    DescriptorMap<Digraph, Node> nodes(digraph);
     42    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
    4443    for (int i = 0; i < 100; ++i) {
    4544      int src = rnd[invNodes.size()];
     
    4847    }
    4948    typename Digraph::template ArcMap<bool> found(digraph, false);
     49    DescriptorMap<Digraph, Arc> arcs(digraph);
    5050    for (NodeIt src(digraph); src != INVALID; ++src) {
    5151      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
     
    111111  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    112112  Graph graph;
    113   typename Graph::template NodeMap<int> nodes(graph);
    114   std::vector<Node> invNodes;
    115113  for (int i = 0; i < 10; ++i) {
    116     invNodes.push_back(graph.addNode());
    117     nodes[invNodes.back()]=invNodes.size()-1;
    118   }
     114    graph.addNode();
     115  }
     116  DescriptorMap<Graph, Node> nodes(graph);
     117  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
    119118  for (int i = 0; i < 100; ++i) {
    120119    int src = rnd[invNodes.size()];
     
    123122  }
    124123  typename Graph::template EdgeMap<int> found(graph, 0);
     124  DescriptorMap<Graph, Edge> edges(graph);
    125125  for (NodeIt src(graph); src != INVALID; ++src) {
    126126    for (NodeIt trg(graph); trg != INVALID; ++trg) {
Note: See TracChangeset for help on using the changeset viewer.