COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/maps.h

    r664 r773  
    2323#include <functional>
    2424#include <vector>
     25#include <map>
    2526
    2627#include <lemon/core.h>
    … …  
    2930///\ingroup maps
    3031///\brief Miscellaneous property maps
    31 
    32 #include <map>
    3332
    3433namespace lemon {
    … …  
    5857  /// but data written to it is not required (i.e. it will be sent to
    5958  /// <tt>/dev/null</tt>).
    60   /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     59  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    6160  ///
    6261  /// \sa ConstMap
    … …  
    9190  ///
    9291  /// In other aspects it is equivalent to \c NullMap.
    93   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
     92  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
    9493  /// concept, but it absorbs the data written to it.
    9594  ///
    … …  
    160159  ///
    161160  /// In other aspects it is equivalent to \c NullMap.
    162   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
     161  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
    163162  /// concept, but it absorbs the data written to it.
    164163  ///
    … …  
    234233  /// It can be used with some data structures, for example
    235234  /// \c UnionFind, \c BinHeap, when the used items are small
    236   /// integers. This map conforms the \ref concepts::ReferenceMap
     235  /// integers. This map conforms to the \ref concepts::ReferenceMap
    237236  /// "ReferenceMap" concept.
    238237  ///
    … …  
    342341  /// stored actually. This value can be different from the default
    343342  /// contructed value (i.e. \c %Value()).
    344   /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
     343  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
    345344  /// concept.
    346345  ///
    … …  
    708707  /// The \c Key type of it is inherited from \c M and the \c Value
    709708  /// type is \c V.
    710   /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
     709  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
    711710  ///
    712711  /// The simplest way of using this map is through the convertMap()
    … …  
    17911790  /// \code
    17921791  ///   std::vector<Node> v;
    1793   ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
     1792  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
    17941793  /// \endcode
    17951794  /// \code
    17961795  ///   std::vector<Node> v(countNodes(g));
    1797   ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
     1796  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
    17981797  /// \endcode
    17991798  ///
    … …  
    18191818  ///
    18201819  /// IdMap provides a unique and immutable id for each item of the
    1821   /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
     1820  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
    18221821  ///  - \b unique: different items get different ids,
    18231822  ///  - \b immutable: the id of an item does not change (even if you
    … …  
    18271826  /// the items stored in the graph, which is returned by the \c id()
    18281827  /// function of the graph. This map can be inverted with its member
    1829   /// class \c InverseMap or with the \c operator() member.
     1828  /// class \c InverseMap or with the \c operator()() member.
    18301829  ///
    18311830  /// \tparam GR The graph type.
    … …  
    18671866  public:
    18681867
    1869     /// \brief This class represents the inverse of its owner (IdMap).
    1870     ///
    1871     /// This class represents the inverse of its owner (IdMap).
     1868    /// \brief The inverse map type of IdMap.
     1869    ///
     1870    /// The inverse map type of IdMap. The subscript operator gives back
     1871    /// an item by its id.
     1872    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
    18721873    /// \see inverse()
    18731874    class InverseMap {
    … …  
    18841885      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
    18851886
    1886       /// \brief Gives back the given item from its id.
     1887      /// \brief Gives back an item by its id.
    18871888      ///
    1888       /// Gives back the given item from its id.
     1889      /// Gives back an item by its id.
    18891890      Item operator[](int id) const { return _graph->fromId(id, Item());}
    18901891
    … …  
    18991900  };
    19001901
     1902  /// \brief Returns an \c IdMap class.
     1903  ///
     1904  /// This function just returns an \c IdMap class.
     1905  /// \relates IdMap
     1906  template <typename K, typename GR>
     1907  inline IdMap<GR, K> idMap(const GR& graph) {
     1908    return IdMap<GR, K>(graph);
     1909  }
    19011910
    19021911  /// \brief General cross reference graph map type.
    19031912
    19041913  /// This class provides simple invertable graph maps.
    1905   /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
    1906   /// and if a key is set to a new value then store it
    1907   /// in the inverse map.
    1908   ///
    1909   /// The values of the map can be accessed
    1910   /// with stl compatible forward iterator.
     1914  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
     1915  /// and if a key is set to a new value, then stores it in the inverse map.
     1916  /// The graph items can be accessed by their values either using
     1917  /// \c InverseMap or \c operator()(), and the values of the map can be
     1918  /// accessed with an STL compatible forward iterator (\c ValueIt).
     1919  ///
     1920  /// This map is intended to be used when all associated values are
     1921  /// different (the map is actually invertable) or there are only a few
     1922  /// items with the same value.
     1923  /// Otherwise consider to use \c IterableValueMap, which is more
     1924  /// suitable and more efficient for such cases. It provides iterators
     1925  /// to traverse the items with the same associated value, however
     1926  /// it does not have \c InverseMap.
     1927  ///
     1928  /// This type is not reference map, so it cannot be modified with
     1929  /// the subscript operator.
    19111930  ///
    19121931  /// \tparam GR The graph type.
    … …  
    19241943      template Map<V>::Type Map;
    19251944
    1926     typedef std::map<V, K> Container;
     1945    typedef std::multimap<V, K> Container;
    19271946    Container _inv_map;
    19281947
    … …  
    19461965    /// \brief Forward iterator for values.
    19471966    ///
    1948     /// This iterator is an stl compatible forward
     1967    /// This iterator is an STL compatible forward
    19491968    /// iterator on the values of the map. The values can
    19501969    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
    1951     class ValueIterator
     1970    /// They are considered with multiplicity, so each value is
     1971    /// traversed for each item it is assigned to.
     1972    class ValueIt
    19521973      : public std::iterator<std::forward_iterator_tag, Value> {
    19531974      friend class CrossRefMap;
    19541975    private:
    1955       ValueIterator(typename Container::const_iterator _it)
     1976      ValueIt(typename Container::const_iterator _it)
    19561977        : it(_it) {}
    19571978    public:
    19581979
    1959       ValueIterator() {}
    1960 
    1961       ValueIterator& operator++() { ++it; return *this; }
    1962       ValueIterator operator++(int) {
    1963         ValueIterator tmp(*this);
     1980      /// Constructor
     1981      ValueIt() {}
     1982
     1983      /// \e
     1984      ValueIt& operator++() { ++it; return *this; }
     1985      /// \e
     1986      ValueIt operator++(int) {
     1987        ValueIt tmp(*this);
    19641988        operator++();
    19651989        return tmp;
    19661990      }
    19671991
     1992      /// \e
    19681993      const Value& operator*() const { return it->first; }
     1994      /// \e
    19691995      const Value* operator->() const { return &(it->first); }
    19701996
    1971       bool operator==(ValueIterator jt) const { return it == jt.it; }
    1972       bool operator!=(ValueIterator jt) const { return it != jt.it; }
     1997      /// \e
     1998      bool operator==(ValueIt jt) const { return it == jt.it; }
     1999      /// \e
     2000      bool operator!=(ValueIt jt) const { return it != jt.it; }
    19732001
    19742002    private:
    19752003      typename Container::const_iterator it;
    19762004    };
     2005   
     2006    /// Alias for \c ValueIt
     2007    typedef ValueIt ValueIterator;
    19772008
    19782009    /// \brief Returns an iterator to the first value.
    19792010    ///
    1980     /// Returns an stl compatible iterator to the
     2011    /// Returns an STL compatible iterator to the
    19812012    /// first value of the map. The values of the
    19822013    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    19832014    /// range.
    1984     ValueIterator beginValue() const {
    1985       return ValueIterator(_inv_map.begin());
     2015    ValueIt beginValue() const {
     2016      return ValueIt(_inv_map.begin());
    19862017    }
    19872018
    19882019    /// \brief Returns an iterator after the last value.
    19892020    ///
    1990     /// Returns an stl compatible iterator after the
     2021    /// Returns an STL compatible iterator after the
    19912022    /// last value of the map. The values of the
    19922023    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    19932024    /// range.
    1994     ValueIterator endValue() const {
    1995       return ValueIterator(_inv_map.end());
     2025    ValueIt endValue() const {
     2026      return ValueIt(_inv_map.end());
    19962027    }
    19972028
    … …  
    20012032    void set(const Key& key, const Value& val) {
    20022033      Value oldval = Map::operator[](key);
    2003       typename Container::iterator it = _inv_map.find(oldval);
    2004       if (it != _inv_map.end() && it->second == key) {
    2005         _inv_map.erase(it);
    2006       }
    2007       _inv_map.insert(make_pair(val, key));
     2034      typename Container::iterator it;
     2035      for (it = _inv_map.equal_range(oldval).first;
     2036           it != _inv_map.equal_range(oldval).second; ++it) {
     2037        if (it->second == key) {
     2038          _inv_map.erase(it);
     2039          break;
     2040        }
     2041      }
     2042      _inv_map.insert(std::make_pair(val, key));
    20082043      Map::set(key, val);
    20092044    }
    … …  
    20172052    }
    20182053
    2019     /// \brief Gives back the item by its value.
    2020     ///
    2021     /// Gives back the item by its value.
    2022     Key operator()(const Value& key) const {
    2023       typename Container::const_iterator it = _inv_map.find(key);
     2054    /// \brief Gives back an item by its value.
     2055    ///
     2056    /// This function gives back an item that is assigned to
     2057    /// the given value or \c INVALID if no such item exists.
     2058    /// If there are more items with the same associated value,
     2059    /// only one of them is returned.
     2060    Key operator()(const Value& val) const {
     2061      typename Container::const_iterator it = _inv_map.find(val);
    20242062      return it != _inv_map.end() ? it->second : INVALID;
     2063    }
     2064   
     2065    /// \brief Returns the number of items with the given value.
     2066    ///
     2067    /// This function returns the number of items with the given value
     2068    /// associated with it.
     2069    int count(const Value &val) const {
     2070      return _inv_map.count(val);
    20252071    }
    20262072
    … …  
    20332079    virtual void erase(const Key& key) {
    20342080      Value val = Map::operator[](key);
    2035       typename Container::iterator it = _inv_map.find(val);
    2036       if (it != _inv_map.end() && it->second == key) {
    2037         _inv_map.erase(it);
     2081      typename Container::iterator it;
     2082      for (it = _inv_map.equal_range(val).first;
     2083           it != _inv_map.equal_range(val).second; ++it) {
     2084        if (it->second == key) {
     2085          _inv_map.erase(it);
     2086          break;
     2087        }
    20382088      }
    20392089      Map::erase(key);
    … …  
    20472097      for (int i = 0; i < int(keys.size()); ++i) {
    20482098        Value val = Map::operator[](keys[i]);
    2049         typename Container::iterator it = _inv_map.find(val);
    2050         if (it != _inv_map.end() && it->second == keys[i]) {
    2051           _inv_map.erase(it);
     2099        typename Container::iterator it;
     2100        for (it = _inv_map.equal_range(val).first;
     2101             it != _inv_map.equal_range(val).second; ++it) {
     2102          if (it->second == keys[i]) {
     2103            _inv_map.erase(it);
     2104            break;
     2105          }
    20522106        }
    20532107      }
    … …  
    20662120  public:
    20672121
    2068     /// \brief The inverse map type.
    2069     ///
    2070     /// The inverse of this map. The subscript operator of the map
    2071     /// gives back the item that was last assigned to the value.
     2122    /// \brief The inverse map type of CrossRefMap.
     2123    ///
     2124    /// The inverse map type of CrossRefMap. The subscript operator gives
     2125    /// back an item by its value.
     2126    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
     2127    /// \see inverse()
    20722128    class InverseMap {
    20732129    public:
    … …  
    20852141      /// \brief Subscript operator.
    20862142      ///
    2087       /// Subscript operator. It gives back the item
    2088       /// that was last assigned to the given value.
     2143      /// Subscript operator. It gives back an item
     2144      /// that is assigned to the given value or \c INVALID
     2145      /// if no such item exists.
    20892146      Value operator[](const Key& key) const {
    20902147        return _inverted(key);
    … …  
    20952152    };
    20962153
    2097     /// \brief It gives back the read-only inverse map.
    2098     ///
    2099     /// It gives back the read-only inverse map.
     2154    /// \brief Gives back the inverse of the map.
     2155    ///
     2156    /// Gives back the inverse of the CrossRefMap.
    21002157    InverseMap inverse() const {
    21012158      return InverseMap(*this);
    … …  
    21042161  };
    21052162
    2106   /// \brief Provides continuous and unique ID for the
     2163  /// \brief Provides continuous and unique id for the
    21072164  /// items of a graph.
    21082165  ///
    21092166  /// RangeIdMap provides a unique and continuous
    2110   /// ID for each item of a given type (\c Node, \c Arc or
     2167  /// id for each item of a given type (\c Node, \c Arc or
    21112168  /// \c Edge) in a graph. This id is
    21122169  ///  - \b unique: different items get different ids,
    … …  
    21192176  /// the \c id() function of the graph or \ref IdMap.
    21202177  /// This map can be inverted with its member class \c InverseMap,
    2121   /// or with the \c operator() member.
     2178  /// or with the \c operator()() member.
    21222179  ///
    21232180  /// \tparam GR The graph type.
    … …  
    22472304    }
    22482305
    2249     /// \brief Gives back the \e RangeId of the item
    2250     ///
    2251     /// Gives back the \e RangeId of the item.
     2306    /// \brief Gives back the \e range \e id of the item
     2307    ///
     2308    /// Gives back the \e range \e id of the item.
    22522309    int operator[](const Item& item) const {
    22532310      return Map::operator[](item);
    22542311    }
    22552312
    2256     /// \brief Gives back the item belonging to a \e RangeId
    2257     /// 
    2258     /// Gives back the item belonging to a \e RangeId.
     2313    /// \brief Gives back the item belonging to a \e range \e id
     2314    ///
     2315    /// Gives back the item belonging to the given \e range \e id.
    22592316    Item operator()(int id) const {
    22602317      return _inv_map[id];
    … …  
    22702327    /// \brief The inverse map type of RangeIdMap.
    22712328    ///
    2272     /// The inverse map type of RangeIdMap.
     2329    /// The inverse map type of RangeIdMap. The subscript operator gives
     2330    /// back an item by its \e range \e id.
     2331    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
    22732332    class InverseMap {
    22742333    public:
    … …  
    22882347      ///
    22892348      /// Subscript operator. It gives back the item
    2290       /// that the descriptor currently belongs to.
     2349      /// that the given \e range \e id currently belongs to.
    22912350      Value operator[](const Key& key) const {
    22922351        return _inverted(key);
    … …  
    23062365    /// \brief Gives back the inverse of the map.
    23072366    ///
    2308     /// Gives back the inverse of the map.
     2367    /// Gives back the inverse of the RangeIdMap.
    23092368    const InverseMap inverse() const {
    23102369      return InverseMap(*this);
    23112370    }
     2371  };
     2372
     2373  /// \brief Returns a \c RangeIdMap class.
     2374  ///
     2375  /// This function just returns an \c RangeIdMap class.
     2376  /// \relates RangeIdMap
     2377  template <typename K, typename GR>
     2378  inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
     2379    return RangeIdMap<GR, K>(graph);
     2380  }
     2381 
     2382  /// \brief Dynamic iterable \c bool map.
     2383  ///
     2384  /// This class provides a special graph map type which can store a
     2385  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
     2386  /// For both \c true and \c false values it is possible to iterate on
     2387  /// the keys mapped to the value.
     2388  ///
     2389  /// This type is a reference map, so it can be modified with the
     2390  /// subscript operator.
     2391  ///
     2392  /// \tparam GR The graph type.
     2393  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2394  /// \c GR::Edge).
     2395  ///
     2396  /// \see IterableIntMap, IterableValueMap
     2397  /// \see CrossRefMap
     2398  template <typename GR, typename K>
     2399  class IterableBoolMap
     2400    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
     2401  private:
     2402    typedef GR Graph;
     2403
     2404    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
     2405    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
     2406
     2407    std::vector<K> _array;
     2408    int _sep;
     2409
     2410  public:
     2411
     2412    /// Indicates that the map is reference map.
     2413    typedef True ReferenceMapTag;
     2414
     2415    /// The key type
     2416    typedef K Key;
     2417    /// The value type
     2418    typedef bool Value;
     2419    /// The const reference type.
     2420    typedef const Value& ConstReference;
     2421
     2422  private:
     2423
     2424    int position(const Key& key) const {
     2425      return Parent::operator[](key);
     2426    }
     2427
     2428  public:
     2429
     2430    /// \brief Reference to the value of the map.
     2431    ///
     2432    /// This class is similar to the \c bool type. It can be converted to
     2433    /// \c bool and it provides the same operators.
     2434    class Reference {
     2435      friend class IterableBoolMap;
     2436    private:
     2437      Reference(IterableBoolMap& map, const Key& key)
     2438        : _key(key), _map(map) {}
     2439    public:
     2440
     2441      Reference& operator=(const Reference& value) {
     2442        _map.set(_key, static_cast<bool>(value));
     2443         return *this;
     2444      }
     2445
     2446      operator bool() const {
     2447        return static_cast<const IterableBoolMap&>(_map)[_key];
     2448      }
     2449
     2450      Reference& operator=(bool value) {
     2451        _map.set(_key, value);
     2452        return *this;
     2453      }
     2454      Reference& operator&=(bool value) {
     2455        _map.set(_key, _map[_key] & value);
     2456        return *this;
     2457      }
     2458      Reference& operator|=(bool value) {
     2459        _map.set(_key, _map[_key] | value);
     2460        return *this;
     2461      }
     2462      Reference& operator^=(bool value) {
     2463        _map.set(_key, _map[_key] ^ value);
     2464        return *this;
     2465      }
     2466    private:
     2467      Key _key;
     2468      IterableBoolMap& _map;
     2469    };
     2470
     2471    /// \brief Constructor of the map with a default value.
     2472    ///
     2473    /// Constructor of the map with a default value.
     2474    explicit IterableBoolMap(const Graph& graph, bool def = false)
     2475      : Parent(graph) {
     2476      typename Parent::Notifier* nf = Parent::notifier();
     2477      Key it;
     2478      for (nf->first(it); it != INVALID; nf->next(it)) {
     2479        Parent::set(it, _array.size());
     2480        _array.push_back(it);
     2481      }
     2482      _sep = (def ? _array.size() : 0);
     2483    }
     2484
     2485    /// \brief Const subscript operator of the map.
     2486    ///
     2487    /// Const subscript operator of the map.
     2488    bool operator[](const Key& key) const {
     2489      return position(key) < _sep;
     2490    }
     2491
     2492    /// \brief Subscript operator of the map.
     2493    ///
     2494    /// Subscript operator of the map.
     2495    Reference operator[](const Key& key) {
     2496      return Reference(*this, key);
     2497    }
     2498
     2499    /// \brief Set operation of the map.
     2500    ///
     2501    /// Set operation of the map.
     2502    void set(const Key& key, bool value) {
     2503      int pos = position(key);
     2504      if (value) {
     2505        if (pos < _sep) return;
     2506        Key tmp = _array[_sep];
     2507        _array[_sep] = key;
     2508        Parent::set(key, _sep);
     2509        _array[pos] = tmp;
     2510        Parent::set(tmp, pos);
     2511        ++_sep;
     2512      } else {
     2513        if (pos >= _sep) return;
     2514        --_sep;
     2515        Key tmp = _array[_sep];
     2516        _array[_sep] = key;
     2517        Parent::set(key, _sep);
     2518        _array[pos] = tmp;
     2519        Parent::set(tmp, pos);
     2520      }
     2521    }
     2522
     2523    /// \brief Set all items.
     2524    ///
     2525    /// Set all items in the map.
     2526    /// \note Constant time operation.
     2527    void setAll(bool value) {
     2528      _sep = (value ? _array.size() : 0);
     2529    }
     2530
     2531    /// \brief Returns the number of the keys mapped to \c true.
     2532    ///
     2533    /// Returns the number of the keys mapped to \c true.
     2534    int trueNum() const {
     2535      return _sep;
     2536    }
     2537
     2538    /// \brief Returns the number of the keys mapped to \c false.
     2539    ///
     2540    /// Returns the number of the keys mapped to \c false.
     2541    int falseNum() const {
     2542      return _array.size() - _sep;
     2543    }
     2544
     2545    /// \brief Iterator for the keys mapped to \c true.
     2546    ///
     2547    /// Iterator for the keys mapped to \c true. It works
     2548    /// like a graph item iterator, it can be converted to
     2549    /// the key type of the map, incremented with \c ++ operator, and
     2550    /// if the iterator leaves the last valid key, it will be equal to
     2551    /// \c INVALID.
     2552    class TrueIt : public Key {
     2553    public:
     2554      typedef Key Parent;
     2555
     2556      /// \brief Creates an iterator.
     2557      ///
     2558      /// Creates an iterator. It iterates on the
     2559      /// keys mapped to \c true.
     2560      /// \param map The IterableBoolMap.
     2561      explicit TrueIt(const IterableBoolMap& map)
     2562        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
     2563          _map(&map) {}
     2564
     2565      /// \brief Invalid constructor \& conversion.
     2566      ///
     2567      /// This constructor initializes the iterator to be invalid.
     2568      /// \sa Invalid for more details.
     2569      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
     2570
     2571      /// \brief Increment operator.
     2572      ///
     2573      /// Increment operator.
     2574      TrueIt& operator++() {
     2575        int pos = _map->position(*this);
     2576        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
     2577        return *this;
     2578      }
     2579
     2580    private:
     2581      const IterableBoolMap* _map;
     2582    };
     2583
     2584    /// \brief Iterator for the keys mapped to \c false.
     2585    ///
     2586    /// Iterator for the keys mapped to \c false. It works
     2587    /// like a graph item iterator, it can be converted to
     2588    /// the key type of the map, incremented with \c ++ operator, and
     2589    /// if the iterator leaves the last valid key, it will be equal to
     2590    /// \c INVALID.
     2591    class FalseIt : public Key {
     2592    public:
     2593      typedef Key Parent;
     2594
     2595      /// \brief Creates an iterator.
     2596      ///
     2597      /// Creates an iterator. It iterates on the
     2598      /// keys mapped to \c false.
     2599      /// \param map The IterableBoolMap.
     2600      explicit FalseIt(const IterableBoolMap& map)
     2601        : Parent(map._sep < int(map._array.size()) ?
     2602                 map._array.back() : INVALID), _map(&map) {}
     2603
     2604      /// \brief Invalid constructor \& conversion.
     2605      ///
     2606      /// This constructor initializes the iterator to be invalid.
     2607      /// \sa Invalid for more details.
     2608      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
     2609
     2610      /// \brief Increment operator.
     2611      ///
     2612      /// Increment operator.
     2613      FalseIt& operator++() {
     2614        int pos = _map->position(*this);
     2615        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
     2616        return *this;
     2617      }
     2618
     2619    private:
     2620      const IterableBoolMap* _map;
     2621    };
     2622
     2623    /// \brief Iterator for the keys mapped to a given value.
     2624    ///
     2625    /// Iterator for the keys mapped to a given value. It works
     2626    /// like a graph item iterator, it can be converted to
     2627    /// the key type of the map, incremented with \c ++ operator, and
     2628    /// if the iterator leaves the last valid key, it will be equal to
     2629    /// \c INVALID.
     2630    class ItemIt : public Key {
     2631    public:
     2632      typedef Key Parent;
     2633
     2634      /// \brief Creates an iterator with a value.
     2635      ///
     2636      /// Creates an iterator with a value. It iterates on the
     2637      /// keys mapped to the given value.
     2638      /// \param map The IterableBoolMap.
     2639      /// \param value The value.
     2640      ItemIt(const IterableBoolMap& map, bool value)
     2641        : Parent(value ?
     2642                 (map._sep > 0 ?
     2643                  map._array[map._sep - 1] : INVALID) :
     2644                 (map._sep < int(map._array.size()) ?
     2645                  map._array.back() : INVALID)), _map(&map) {}
     2646
     2647      /// \brief Invalid constructor \& conversion.
     2648      ///
     2649      /// This constructor initializes the iterator to be invalid.
     2650      /// \sa Invalid for more details.
     2651      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2652
     2653      /// \brief Increment operator.
     2654      ///
     2655      /// Increment operator.
     2656      ItemIt& operator++() {
     2657        int pos = _map->position(*this);
     2658        int _sep = pos >= _map->_sep ? _map->_sep : 0;
     2659        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
     2660        return *this;
     2661      }
     2662
     2663    private:
     2664      const IterableBoolMap* _map;
     2665    };
     2666
     2667  protected:
     2668
     2669    virtual void add(const Key& key) {
     2670      Parent::add(key);
     2671      Parent::set(key, _array.size());
     2672      _array.push_back(key);
     2673    }
     2674
     2675    virtual void add(const std::vector<Key>& keys) {
     2676      Parent::add(keys);
     2677      for (int i = 0; i < int(keys.size()); ++i) {
     2678        Parent::set(keys[i], _array.size());
     2679        _array.push_back(keys[i]);
     2680      }
     2681    }
     2682
     2683    virtual void erase(const Key& key) {
     2684      int pos = position(key);
     2685      if (pos < _sep) {
     2686        --_sep;
     2687        Parent::set(_array[_sep], pos);
     2688        _array[pos] = _array[_sep];
     2689        Parent::set(_array.back(), _sep);
     2690        _array[_sep] = _array.back();
     2691        _array.pop_back();
     2692      } else {
     2693        Parent::set(_array.back(), pos);
     2694        _array[pos] = _array.back();
     2695        _array.pop_back();
     2696      }
     2697      Parent::erase(key);
     2698    }
     2699
     2700    virtual void erase(const std::vector<Key>& keys) {
     2701      for (int i = 0; i < int(keys.size()); ++i) {
     2702        int pos = position(keys[i]);
     2703        if (pos < _sep) {
     2704          --_sep;
     2705          Parent::set(_array[_sep], pos);
     2706          _array[pos] = _array[_sep];
     2707          Parent::set(_array.back(), _sep);
     2708          _array[_sep] = _array.back();
     2709          _array.pop_back();
     2710        } else {
     2711          Parent::set(_array.back(), pos);
     2712          _array[pos] = _array.back();
     2713          _array.pop_back();
     2714        }
     2715      }
     2716      Parent::erase(keys);
     2717    }
     2718
     2719    virtual void build() {
     2720      Parent::build();
     2721      typename Parent::Notifier* nf = Parent::notifier();
     2722      Key it;
     2723      for (nf->first(it); it != INVALID; nf->next(it)) {
     2724        Parent::set(it, _array.size());
     2725        _array.push_back(it);
     2726      }
     2727      _sep = 0;
     2728    }
     2729
     2730    virtual void clear() {
     2731      _array.clear();
     2732      _sep = 0;
     2733      Parent::clear();
     2734    }
     2735
     2736  };
     2737
     2738
     2739  namespace _maps_bits {
     2740    template <typename Item>
     2741    struct IterableIntMapNode {
     2742      IterableIntMapNode() : value(-1) {}
     2743      IterableIntMapNode(int _value) : value(_value) {}
     2744      Item prev, next;
     2745      int value;
     2746    };
     2747  }
     2748
     2749  /// \brief Dynamic iterable integer map.
     2750  ///
     2751  /// This class provides a special graph map type which can store an
     2752  /// integer value for graph items (\c Node, \c Arc or \c Edge).
     2753  /// For each non-negative value it is possible to iterate on the keys
     2754  /// mapped to the value.
     2755  ///
     2756  /// This map is intended to be used with small integer values, for which
     2757  /// it is efficient, and supports iteration only for non-negative values.
     2758  /// If you need large values and/or iteration for negative integers,
     2759  /// consider to use \ref IterableValueMap instead.
     2760  ///
     2761  /// This type is a reference map, so it can be modified with the
     2762  /// subscript operator.
     2763  ///
     2764  /// \note The size of the data structure depends on the largest
     2765  /// value in the map.
     2766  ///
     2767  /// \tparam GR The graph type.
     2768  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2769  /// \c GR::Edge).
     2770  ///
     2771  /// \see IterableBoolMap, IterableValueMap
     2772  /// \see CrossRefMap
     2773  template <typename GR, typename K>
     2774  class IterableIntMap
     2775    : protected ItemSetTraits<GR, K>::
     2776        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
     2777  public:
     2778    typedef typename ItemSetTraits<GR, K>::
     2779      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
     2780
     2781    /// The key type
     2782    typedef K Key;
     2783    /// The value type
     2784    typedef int Value;
     2785    /// The graph type
     2786    typedef GR Graph;
     2787
     2788    /// \brief Constructor of the map.
     2789    ///
     2790    /// Constructor of the map. It sets all values to -1.
     2791    explicit IterableIntMap(const Graph& graph)
     2792      : Parent(graph) {}
     2793
     2794    /// \brief Constructor of the map with a given value.
     2795    ///
     2796    /// Constructor of the map with a given value.
     2797    explicit IterableIntMap(const Graph& graph, int value)
     2798      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
     2799      if (value >= 0) {
     2800        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     2801          lace(it);
     2802        }
     2803      }
     2804    }
     2805
     2806  private:
     2807
     2808    void unlace(const Key& key) {
     2809      typename Parent::Value& node = Parent::operator[](key);
     2810      if (node.value < 0) return;
     2811      if (node.prev != INVALID) {
     2812        Parent::operator[](node.prev).next = node.next;
     2813      } else {
     2814        _first[node.value] = node.next;
     2815      }
     2816      if (node.next != INVALID) {
     2817        Parent::operator[](node.next).prev = node.prev;
     2818      }
     2819      while (!_first.empty() && _first.back() == INVALID) {
     2820        _first.pop_back();
     2821      }
     2822    }
     2823
     2824    void lace(const Key& key) {
     2825      typename Parent::Value& node = Parent::operator[](key);
     2826      if (node.value < 0) return;
     2827      if (node.value >= int(_first.size())) {
     2828        _first.resize(node.value + 1, INVALID);
     2829      }
     2830      node.prev = INVALID;
     2831      node.next = _first[node.value];
     2832      if (node.next != INVALID) {
     2833        Parent::operator[](node.next).prev = key;
     2834      }
     2835      _first[node.value] = key;
     2836    }
     2837
     2838  public:
     2839
     2840    /// Indicates that the map is reference map.
     2841    typedef True ReferenceMapTag;
     2842
     2843    /// \brief Reference to the value of the map.
     2844    ///
     2845    /// This class is similar to the \c int type. It can
     2846    /// be converted to \c int and it has the same operators.
     2847    class Reference {
     2848      friend class IterableIntMap;
     2849    private:
     2850      Reference(IterableIntMap& map, const Key& key)
     2851        : _key(key), _map(map) {}
     2852    public:
     2853
     2854      Reference& operator=(const Reference& value) {
     2855        _map.set(_key, static_cast<const int&>(value));
     2856         return *this;
     2857      }
     2858
     2859      operator const int&() const {
     2860        return static_cast<const IterableIntMap&>(_map)[_key];
     2861      }
     2862
     2863      Reference& operator=(int value) {
     2864        _map.set(_key, value);
     2865        return *this;
     2866      }
     2867      Reference& operator++() {
     2868        _map.set(_key, _map[_key] + 1);
     2869        return *this;
     2870      }
     2871      int operator++(int) {
     2872        int value = _map[_key];
     2873        _map.set(_key, value + 1);
     2874        return value;
     2875      }
     2876      Reference& operator--() {
     2877        _map.set(_key, _map[_key] - 1);
     2878        return *this;
     2879      }
     2880      int operator--(int) {
     2881        int value = _map[_key];
     2882        _map.set(_key, value - 1);
     2883        return value;
     2884      }
     2885      Reference& operator+=(int value) {
     2886        _map.set(_key, _map[_key] + value);
     2887        return *this;
     2888      }
     2889      Reference& operator-=(int value) {
     2890        _map.set(_key, _map[_key] - value);
     2891        return *this;
     2892      }
     2893      Reference& operator*=(int value) {
     2894        _map.set(_key, _map[_key] * value);
     2895        return *this;
     2896      }
     2897      Reference& operator/=(int value) {
     2898        _map.set(_key, _map[_key] / value);
     2899        return *this;
     2900      }
     2901      Reference& operator%=(int value) {
     2902        _map.set(_key, _map[_key] % value);
     2903        return *this;
     2904      }
     2905      Reference& operator&=(int value) {
     2906        _map.set(_key, _map[_key] & value);
     2907        return *this;
     2908      }
     2909      Reference& operator|=(int value) {
     2910        _map.set(_key, _map[_key] | value);
     2911        return *this;
     2912      }
     2913      Reference& operator^=(int value) {
     2914        _map.set(_key, _map[_key] ^ value);
     2915        return *this;
     2916      }
     2917      Reference& operator<<=(int value) {
     2918        _map.set(_key, _map[_key] << value);
     2919        return *this;
     2920      }
     2921      Reference& operator>>=(int value) {
     2922        _map.set(_key, _map[_key] >> value);
     2923        return *this;
     2924      }
     2925
     2926    private:
     2927      Key _key;
     2928      IterableIntMap& _map;
     2929    };
     2930
     2931    /// The const reference type.
     2932    typedef const Value& ConstReference;
     2933
     2934    /// \brief Gives back the maximal value plus one.
     2935    ///
     2936    /// Gives back the maximal value plus one.
     2937    int size() const {
     2938      return _first.size();
     2939    }
     2940
     2941    /// \brief Set operation of the map.
     2942    ///
     2943    /// Set operation of the map.
     2944    void set(const Key& key, const Value& value) {
     2945      unlace(key);
     2946      Parent::operator[](key).value = value;
     2947      lace(key);
     2948    }
     2949
     2950    /// \brief Const subscript operator of the map.
     2951    ///
     2952    /// Const subscript operator of the map.
     2953    const Value& operator[](const Key& key) const {
     2954      return Parent::operator[](key).value;
     2955    }
     2956
     2957    /// \brief Subscript operator of the map.
     2958    ///
     2959    /// Subscript operator of the map.
     2960    Reference operator[](const Key& key) {
     2961      return Reference(*this, key);
     2962    }
     2963
     2964    /// \brief Iterator for the keys with the same value.
     2965    ///
     2966    /// Iterator for the keys with the same value. It works
     2967    /// like a graph item iterator, it can be converted to
     2968    /// the item type of the map, incremented with \c ++ operator, and
     2969    /// if the iterator leaves the last valid item, it will be equal to
     2970    /// \c INVALID.
     2971    class ItemIt : public Key {
     2972    public:
     2973      typedef Key Parent;
     2974
     2975      /// \brief Invalid constructor \& conversion.
     2976      ///
     2977      /// This constructor initializes the iterator to be invalid.
     2978      /// \sa Invalid for more details.
     2979      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2980
     2981      /// \brief Creates an iterator with a value.
     2982      ///
     2983      /// Creates an iterator with a value. It iterates on the
     2984      /// keys mapped to the given value.
     2985      /// \param map The IterableIntMap.
     2986      /// \param value The value.
     2987      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
     2988        if (value < 0 || value >= int(_map->_first.size())) {
     2989          Parent::operator=(INVALID);
     2990        } else {
     2991          Parent::operator=(_map->_first[value]);
     2992        }
     2993      }
     2994
     2995      /// \brief Increment operator.
     2996      ///
     2997      /// Increment operator.
     2998      ItemIt& operator++() {
     2999        Parent::operator=(_map->IterableIntMap::Parent::
     3000                          operator[](static_cast<Parent&>(*this)).next);
     3001        return *this;
     3002      }
     3003
     3004    private:
     3005      const IterableIntMap* _map;
     3006    };
     3007
     3008  protected:
     3009
     3010    virtual void erase(const Key& key) {
     3011      unlace(key);
     3012      Parent::erase(key);
     3013    }
     3014
     3015    virtual void erase(const std::vector<Key>& keys) {
     3016      for (int i = 0; i < int(keys.size()); ++i) {
     3017        unlace(keys[i]);
     3018      }
     3019      Parent::erase(keys);
     3020    }
     3021
     3022    virtual void clear() {
     3023      _first.clear();
     3024      Parent::clear();
     3025    }
     3026
     3027  private:
     3028    std::vector<Key> _first;
     3029  };
     3030
     3031  namespace _maps_bits {
     3032    template <typename Item, typename Value>
     3033    struct IterableValueMapNode {
     3034      IterableValueMapNode(Value _value = Value()) : value(_value) {}
     3035      Item prev, next;
     3036      Value value;
     3037    };
     3038  }
     3039
     3040  /// \brief Dynamic iterable map for comparable values.
     3041  ///
     3042  /// This class provides a special graph map type which can store a
     3043  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
     3044  /// For each value it is possible to iterate on the keys mapped to
     3045  /// the value (\c ItemIt), and the values of the map can be accessed
     3046  /// with an STL compatible forward iterator (\c ValueIt).
     3047  /// The map stores a linked list for each value, which contains
     3048  /// the items mapped to the value, and the used values are stored
     3049  /// in balanced binary tree (\c std::map).
     3050  ///
     3051  /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
     3052  /// specialized for \c bool and \c int values, respectively.
     3053  ///
     3054  /// This type is not reference map, so it cannot be modified with
     3055  /// the subscript operator.
     3056  ///
     3057  /// \tparam GR The graph type.
     3058  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     3059  /// \c GR::Edge).
     3060  /// \tparam V The value type of the map. It can be any comparable
     3061  /// value type.
     3062  ///
     3063  /// \see IterableBoolMap, IterableIntMap
     3064  /// \see CrossRefMap
     3065  template <typename GR, typename K, typename V>
     3066  class IterableValueMap
     3067    : protected ItemSetTraits<GR, K>::
     3068        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
     3069  public:
     3070    typedef typename ItemSetTraits<GR, K>::
     3071      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
     3072
     3073    /// The key type
     3074    typedef K Key;
     3075    /// The value type
     3076    typedef V Value;
     3077    /// The graph type
     3078    typedef GR Graph;
     3079
     3080  public:
     3081
     3082    /// \brief Constructor of the map with a given value.
     3083    ///
     3084    /// Constructor of the map with a given value.
     3085    explicit IterableValueMap(const Graph& graph,
     3086                              const Value& value = Value())
     3087      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
     3088      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3089        lace(it);
     3090      }
     3091    }
     3092
     3093  protected:
     3094
     3095    void unlace(const Key& key) {
     3096      typename Parent::Value& node = Parent::operator[](key);
     3097      if (node.prev != INVALID) {
     3098        Parent::operator[](node.prev).next = node.next;
     3099      } else {
     3100        if (node.next != INVALID) {
     3101          _first[node.value] = node.next;
     3102        } else {
     3103          _first.erase(node.value);
     3104        }
     3105      }
     3106      if (node.next != INVALID) {
     3107        Parent::operator[](node.next).prev = node.prev;
     3108      }
     3109    }
     3110
     3111    void lace(const Key& key) {
     3112      typename Parent::Value& node = Parent::operator[](key);
     3113      typename std::map<Value, Key>::iterator it = _first.find(node.value);
     3114      if (it == _first.end()) {
     3115        node.prev = node.next = INVALID;
     3116        _first.insert(std::make_pair(node.value, key));
     3117      } else {
     3118        node.prev = INVALID;
     3119        node.next = it->second;
     3120        if (node.next != INVALID) {
     3121          Parent::operator[](node.next).prev = key;
     3122        }
     3123        it->second = key;
     3124      }
     3125    }
     3126
     3127  public:
     3128
     3129    /// \brief Forward iterator for values.
     3130    ///
     3131    /// This iterator is an STL compatible forward
     3132    /// iterator on the values of the map. The values can
     3133    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     3134    class ValueIt
     3135      : public std::iterator<std::forward_iterator_tag, Value> {
     3136      friend class IterableValueMap;
     3137    private:
     3138      ValueIt(typename std::map<Value, Key>::const_iterator _it)
     3139        : it(_it) {}
     3140    public:
     3141
     3142      /// Constructor
     3143      ValueIt() {}
     3144
     3145      /// \e
     3146      ValueIt& operator++() { ++it; return *this; }
     3147      /// \e
     3148      ValueIt operator++(int) {
     3149        ValueIt tmp(*this);
     3150        operator++();
     3151        return tmp;
     3152      }
     3153
     3154      /// \e
     3155      const Value& operator*() const { return it->first; }
     3156      /// \e
     3157      const Value* operator->() const { return &(it->first); }
     3158
     3159      /// \e
     3160      bool operator==(ValueIt jt) const { return it == jt.it; }
     3161      /// \e
     3162      bool operator!=(ValueIt jt) const { return it != jt.it; }
     3163
     3164    private:
     3165      typename std::map<Value, Key>::const_iterator it;
     3166    };
     3167
     3168    /// \brief Returns an iterator to the first value.
     3169    ///
     3170    /// Returns an STL compatible iterator to the
     3171    /// first value of the map. The values of the
     3172    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3173    /// range.
     3174    ValueIt beginValue() const {
     3175      return ValueIt(_first.begin());
     3176    }
     3177
     3178    /// \brief Returns an iterator after the last value.
     3179    ///
     3180    /// Returns an STL compatible iterator after the
     3181    /// last value of the map. The values of the
     3182    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3183    /// range.
     3184    ValueIt endValue() const {
     3185      return ValueIt(_first.end());
     3186    }
     3187
     3188    /// \brief Set operation of the map.
     3189    ///
     3190    /// Set operation of the map.
     3191    void set(const Key& key, const Value& value) {
     3192      unlace(key);
     3193      Parent::operator[](key).value = value;
     3194      lace(key);
     3195    }
     3196
     3197    /// \brief Const subscript operator of the map.
     3198    ///
     3199    /// Const subscript operator of the map.
     3200    const Value& operator[](const Key& key) const {
     3201      return Parent::operator[](key).value;
     3202    }
     3203
     3204    /// \brief Iterator for the keys with the same value.
     3205    ///
     3206    /// Iterator for the keys with the same value. It works
     3207    /// like a graph item iterator, it can be converted to
     3208    /// the item type of the map, incremented with \c ++ operator, and
     3209    /// if the iterator leaves the last valid item, it will be equal to
     3210    /// \c INVALID.
     3211    class ItemIt : public Key {
     3212    public:
     3213      typedef Key Parent;
     3214
     3215      /// \brief Invalid constructor \& conversion.
     3216      ///
     3217      /// This constructor initializes the iterator to be invalid.
     3218      /// \sa Invalid for more details.
     3219      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     3220
     3221      /// \brief Creates an iterator with a value.
     3222      ///
     3223      /// Creates an iterator with a value. It iterates on the
     3224      /// keys which have the given value.
     3225      /// \param map The IterableValueMap
     3226      /// \param value The value
     3227      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
     3228        typename std::map<Value, Key>::const_iterator it =
     3229          map._first.find(value);
     3230        if (it == map._first.end()) {
     3231          Parent::operator=(INVALID);
     3232        } else {
     3233          Parent::operator=(it->second);
     3234        }
     3235      }
     3236
     3237      /// \brief Increment operator.
     3238      ///
     3239      /// Increment Operator.
     3240      ItemIt& operator++() {
     3241        Parent::operator=(_map->IterableValueMap::Parent::
     3242                          operator[](static_cast<Parent&>(*this)).next);
     3243        return *this;
     3244      }
     3245
     3246
     3247    private:
     3248      const IterableValueMap* _map;
     3249    };
     3250
     3251  protected:
     3252
     3253    virtual void add(const Key& key) {
     3254      Parent::add(key);
     3255      unlace(key);
     3256    }
     3257
     3258    virtual void add(const std::vector<Key>& keys) {
     3259      Parent::add(keys);
     3260      for (int i = 0; i < int(keys.size()); ++i) {
     3261        lace(keys[i]);
     3262      }
     3263    }
     3264
     3265    virtual void erase(const Key& key) {
     3266      unlace(key);
     3267      Parent::erase(key);
     3268    }
     3269
     3270    virtual void erase(const std::vector<Key>& keys) {
     3271      for (int i = 0; i < int(keys.size()); ++i) {
     3272        unlace(keys[i]);
     3273      }
     3274      Parent::erase(keys);
     3275    }
     3276
     3277    virtual void build() {
     3278      Parent::build();
     3279      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3280        lace(it);
     3281      }
     3282    }
     3283
     3284    virtual void clear() {
     3285      _first.clear();
     3286      Parent::clear();
     3287    }
     3288
     3289  private:
     3290    std::map<Value, Key> _first;
    23123291  };
    23133292
    … …  
    23223301  public:
    23233302
    2324     ///\e
     3303    /// The key type (the \c Arc type of the digraph).
    23253304    typedef typename GR::Arc Key;
    2326     ///\e
     3305    /// The value type (the \c Node type of the digraph).
    23273306    typedef typename GR::Node Value;
    23283307
    … …  
    23633342  public:
    23643343
    2365     ///\e
     3344    /// The key type (the \c Arc type of the digraph).
    23663345    typedef typename GR::Arc Key;
    2367     ///\e
     3346    /// The value type (the \c Node type of the digraph).
    23683347    typedef typename GR::Node Value;
    23693348
    … …  
    24053384  public:
    24063385
     3386    /// The key type (the \c Edge type of the digraph).
     3387    typedef typename GR::Edge Key;
     3388    /// The value type (the \c Arc type of the digraph).
    24073389    typedef typename GR::Arc Value;
    2408     typedef typename GR::Edge Key;
    24093390
    24103391    /// \brief Constructor
    … …  
    24453426  public:
    24463427
     3428    /// The key type (the \c Edge type of the digraph).
     3429    typedef typename GR::Edge Key;
     3430    /// The value type (the \c Arc type of the digraph).
    24473431    typedef typename GR::Arc Value;
    2448     typedef typename GR::Edge Key;
    24493432
    24503433    /// \brief Constructor
    … …  
    24813464  /// whenever the digraph changes.
    24823465  ///
    2483   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3466  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    24843467  /// may provide alternative ways to modify the digraph.
    24853468  /// The correct behavior of InDegMap is not guarantied if these additional
    … …  
    24973480
    24983481  public:
    2499    
     3482
    25003483    /// The graph type of InDegMap
    25013484    typedef GR Graph;
    … …  
    26113594  /// whenever the digraph changes.
    26123595  ///
    2613   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3596  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    26143597  /// may provide alternative ways to modify the digraph.
    26153598  /// The correct behavior of OutDegMap is not guarantied if these additional
Note: See TracChangeset for help on using the changeset viewer.