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:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r318 r330  
    4141some graph features like arc/edge or node deletion.
    4242
    43 Alteration of standard containers need a very limited number of
    44 operations, these together satisfy the everyday requirements.
    45 In the case of graph structures, different operations are needed which do
    46 not alter the physical graph, but gives another view. If some nodes or
    47 arcs have to be hidden or the reverse oriented graph have to be used, then
    48 this is the case. It also may happen that in a flow implementation
    49 the residual graph can be accessed by another algorithm, or a node-set
    50 is to be shrunk for another algorithm.
    51 LEMON also provides a variety of graphs for these requirements called
    52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
    53 in conjunction with other graph representations.
    54 
    5543You are free to use the graph structure that fit your requirements
    5644the best, most graph algorithms and auxiliary data structures can be used
    … …  
    5846
    5947<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 
    67 This group describes some graph types between real graphs and graph adaptors.
    68 These classes wrap graphs to give new functionality as the adaptors do it.
    69 On the other hand they are not light-weight structures as the adaptors.
    7048*/
    7149
    … …  
    156134
    157135/**
    158 @defgroup matrices Matrices
    159 @ingroup datas
    160 \brief Two dimensional data storages implemented in LEMON.
    161 
    162 This group describes two dimensional data storages implemented in LEMON.
    163 */
    164 
    165 /**
    166136@defgroup paths Path Structures
    167137@ingroup datas
    … …  
    215185
    216186/**
    217 @defgroup max_flow Maximum Flow Algorithms
    218 @ingroup algs
    219 \brief Algorithms for finding maximum flows.
    220 
    221 This group describes the algorithms for finding maximum flows and
    222 feasible circulations.
    223 
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum 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 
    235 LEMON 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 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming 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 
    253 This group describes the algorithms for finding minimum cost flows and
    254 circulations.
    255 */
    256 
    257 /**
    258 @defgroup min_cut Minimum Cut Algorithms
    259 @ingroup algs
    260 
    261 \brief Algorithms for finding minimum cut in graphs.
    262 
    263 This group describes the algorithms for finding minimum cut in graphs.
    264 
    265 The 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
    267 outgoing 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
    269 cut 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 
    274 LEMON 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 
    283 If you want to find minimum cut just between two distinict nodes,
    284 please 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 
    292 This group describes the algorithms for discovering the graph properties
    293 like 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 
    304 This group describes the algorithms for planarity checking,
    305 embedding 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 
    316 This group contains algorithm objects and functions to calculate
    317 matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the arcs which does not shares common endpoints.
    319 
    320 There are several different algorithms for calculate matchings in
    321 graphs.  The matching problems in bipartite graphs are generally
    322 easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
    324 matching. The search can be constrained to find perfect or
    325 maximum cardinality matching.
    326 
    327 LEMON 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 /**
    353187@defgroup spantree Minimum Spanning Tree Algorithms
    354188@ingroup algs
    … …  
    360194
    361195/**
    362 @defgroup auxalg Auxiliary Algorithms
    363 @ingroup algs
    364 \brief Auxiliary algorithms implemented in LEMON.
    365 
    366 This group describes some algorithms implemented in LEMON
    367 in 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 
    375 This group describes the approximation and heuristic algorithms
    376 implemented in LEMON.
    377 */
    378 
    379 /**
    380 @defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
    382 implemented in LEMON.
    383 
    384 This group describes some general optimization frameworks
    385 implemented 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 
    393 This group describes Lp and Mip solver interfaces for LEMON. The
    394 various LP solvers could be used in the same manner with this
    395 interface.
    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 
    403 This group adds some helper tools to general optimization framework
    404 implemented in LEMON.
    405 */
    406 
    407 /**
    408 @defgroup metah Metaheuristics
    409 @ingroup gen_opt_group
    410 \brief Metaheuristics for LEMON library.
    411 
    412 This group describes some metaheuristic optimization tools.
    413 */
    414 
    415 /**
    416196@defgroup utils Tools and Utilities
    417197\brief Tools and utilities for programming in LEMON
    … …  
    459239
    460240This group describes the tools for importing and exporting graphs
    461 and graph related data. Now it supports the \ref lgf-format
    462 "LEMON Graph Format", the \c DIMACS format and the encapsulated
     241and graph related data. Now it supports the LEMON format
     242and the encapsulated postscript (EPS) format.
    463243postscript (EPS) format.
    464244*/
    … …  
    524304@ingroup concept
    525305\brief Skeleton and concept checking classes for maps
    526 
     306 
    527307This group describes the skeletons and concept checking classes of maps.
    528308*/
    … …  
    539319build the library.
    540320*/
    541 
    542 /**
    543 @defgroup tools Standalone utility applications
    544 
    545 Some utility applications are listed here.
    546 
    547 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    548 them, as well.
    549 */
    550 

  • doc/mainpage.dox

    r314 r327  
    4242\subsection howtoread How to read the documentation
    4343
    44 If you want to get a quick start and see the most important features then
    45 take a look at our \ref quicktour
    46 "Quick Tour to LEMON" which will guide you along.
    47 
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
    50 
    5144If you
    5245want to see how LEMON works, see

  • lemon/maps.h

    r314 r327  
    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     }
    22591858  };
    22601859

  • test/graph_utils_test.cc

    r220 r324  
    3636  {
    3737    Digraph digraph;
     38    typename Digraph::template NodeMap<int> nodes(digraph);
     39    std::vector<Node> invNodes;
    3840    for (int i = 0; i < 10; ++i) {
    39       digraph.addNode();
    40     }
    41     DescriptorMap<Digraph, Node> nodes(digraph);
    42     typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
     41      invNodes.push_back(digraph.addNode());
     42      nodes[invNodes.back()]=invNodes.size()-1;
     43    }
    4344    for (int i = 0; i < 100; ++i) {
    4445      int src = rnd[invNodes.size()];
    … …  
    4748    }
    4849    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;
    113115  for (int i = 0; i < 10; ++i) {
    114     graph.addNode();
    115   }
    116   DescriptorMap<Graph, Node> nodes(graph);
    117   typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
     116    invNodes.push_back(graph.addNode());
     117    nodes[invNodes.back()]=invNodes.size()-1;
     118  }
    118119  for (int i = 0; i < 100; ++i) {
    119120    int src = rnd[invNodes.size()];
    … …  
    122123  }
    123124  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.