lemon/maps.h
changeset 221 64613d8fae28
parent 209 765619b7cbb2
child 280 e7f8647ce760
     1.1 --- a/lemon/maps.h	Tue Jul 15 18:43:41 2008 +0100
     1.2 +++ b/lemon/maps.h	Tue Jul 15 18:49:30 2008 +0100
     1.3 @@ -23,8 +23,7 @@
     1.4  #include <functional>
     1.5  #include <vector>
     1.6  
     1.7 -#include <lemon/bits/utility.h>
     1.8 -#include <lemon/bits/traits.h>
     1.9 +#include <lemon/core.h>
    1.10  
    1.11  ///\file
    1.12  ///\ingroup maps
    1.13 @@ -1780,6 +1779,926 @@
    1.14      return LoggerBoolMap<Iterator>(it);
    1.15    }
    1.16  
    1.17 +  /// Provides an immutable and unique id for each item in the graph.
    1.18 +
    1.19 +  /// The IdMap class provides a unique and immutable id for each item of the
    1.20 +  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
    1.21 +  /// different items (nodes) get different ids <li>\b immutable: the id of an
    1.22 +  /// item (node) does not change (even if you delete other nodes).  </ul>
    1.23 +  /// Through this map you get access (i.e. can read) the inner id values of
    1.24 +  /// the items stored in the graph. This map can be inverted with its member
    1.25 +  /// class \c InverseMap or with the \c operator() member.
    1.26 +  ///
    1.27 +  template <typename _Graph, typename _Item>
    1.28 +  class IdMap {
    1.29 +  public:
    1.30 +    typedef _Graph Graph;
    1.31 +    typedef int Value;
    1.32 +    typedef _Item Item;
    1.33 +    typedef _Item Key;
    1.34 +
    1.35 +    /// \brief Constructor.
    1.36 +    ///
    1.37 +    /// Constructor of the map.
    1.38 +    explicit IdMap(const Graph& graph) : _graph(&graph) {}
    1.39 +
    1.40 +    /// \brief Gives back the \e id of the item.
    1.41 +    ///
    1.42 +    /// Gives back the immutable and unique \e id of the item.
    1.43 +    int operator[](const Item& item) const { return _graph->id(item);}
    1.44 +
    1.45 +    /// \brief Gives back the item by its id.
    1.46 +    ///
    1.47 +    /// Gives back the item by its id.
    1.48 +    Item operator()(int id) { return _graph->fromId(id, Item()); }
    1.49 +
    1.50 +  private:
    1.51 +    const Graph* _graph;
    1.52 +
    1.53 +  public:
    1.54 +
    1.55 +    /// \brief The class represents the inverse of its owner (IdMap).
    1.56 +    ///
    1.57 +    /// The class represents the inverse of its owner (IdMap).
    1.58 +    /// \see inverse()
    1.59 +    class InverseMap {
    1.60 +    public:
    1.61 +
    1.62 +      /// \brief Constructor.
    1.63 +      ///
    1.64 +      /// Constructor for creating an id-to-item map.
    1.65 +      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
    1.66 +
    1.67 +      /// \brief Constructor.
    1.68 +      ///
    1.69 +      /// Constructor for creating an id-to-item map.
    1.70 +      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
    1.71 +
    1.72 +      /// \brief Gives back the given item from its id.
    1.73 +      ///
    1.74 +      /// Gives back the given item from its id.
    1.75 +      ///
    1.76 +      Item operator[](int id) const { return _graph->fromId(id, Item());}
    1.77 +
    1.78 +    private:
    1.79 +      const Graph* _graph;
    1.80 +    };
    1.81 +
    1.82 +    /// \brief Gives back the inverse of the map.
    1.83 +    ///
    1.84 +    /// Gives back the inverse of the IdMap.
    1.85 +    InverseMap inverse() const { return InverseMap(*_graph);}
    1.86 +
    1.87 +  };
    1.88 +
    1.89 +
    1.90 +  /// \brief General invertable graph-map type.
    1.91 +
    1.92 +  /// This type provides simple invertable graph-maps.
    1.93 +  /// The InvertableMap wraps an arbitrary ReadWriteMap
    1.94 +  /// and if a key is set to a new value then store it
    1.95 +  /// in the inverse map.
    1.96 +  ///
    1.97 +  /// The values of the map can be accessed
    1.98 +  /// with stl compatible forward iterator.
    1.99 +  ///
   1.100 +  /// \tparam _Graph The graph type.
   1.101 +  /// \tparam _Item The item type of the graph.
   1.102 +  /// \tparam _Value The value type of the map.
   1.103 +  ///
   1.104 +  /// \see IterableValueMap
   1.105 +  template <typename _Graph, typename _Item, typename _Value>
   1.106 +  class InvertableMap
   1.107 +    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
   1.108 +  private:
   1.109 +
   1.110 +    typedef typename ItemSetTraits<_Graph, _Item>::
   1.111 +    template Map<_Value>::Type Map;
   1.112 +    typedef _Graph Graph;
   1.113 +
   1.114 +    typedef std::map<_Value, _Item> Container;
   1.115 +    Container _inv_map;
   1.116 +
   1.117 +  public:
   1.118 +
   1.119 +    /// The key type of InvertableMap (Node, Arc, Edge).
   1.120 +    typedef typename Map::Key Key;
   1.121 +    /// The value type of the InvertableMap.
   1.122 +    typedef typename Map::Value Value;
   1.123 +
   1.124 +
   1.125 +
   1.126 +    /// \brief Constructor.
   1.127 +    ///
   1.128 +    /// Construct a new InvertableMap for the graph.
   1.129 +    ///
   1.130 +    explicit InvertableMap(const Graph& graph) : Map(graph) {}
   1.131 +
   1.132 +    /// \brief Forward iterator for values.
   1.133 +    ///
   1.134 +    /// This iterator is an stl compatible forward
   1.135 +    /// iterator on the values of the map. The values can
   1.136 +    /// be accessed in the [beginValue, endValue) range.
   1.137 +    ///
   1.138 +    class ValueIterator
   1.139 +      : public std::iterator<std::forward_iterator_tag, Value> {
   1.140 +      friend class InvertableMap;
   1.141 +    private:
   1.142 +      ValueIterator(typename Container::const_iterator _it)
   1.143 +        : it(_it) {}
   1.144 +    public:
   1.145 +
   1.146 +      ValueIterator() {}
   1.147 +
   1.148 +      ValueIterator& operator++() { ++it; return *this; }
   1.149 +      ValueIterator operator++(int) {
   1.150 +        ValueIterator tmp(*this);
   1.151 +        operator++();
   1.152 +        return tmp;
   1.153 +      }
   1.154 +
   1.155 +      const Value& operator*() const { return it->first; }
   1.156 +      const Value* operator->() const { return &(it->first); }
   1.157 +
   1.158 +      bool operator==(ValueIterator jt) const { return it == jt.it; }
   1.159 +      bool operator!=(ValueIterator jt) const { return it != jt.it; }
   1.160 +
   1.161 +    private:
   1.162 +      typename Container::const_iterator it;
   1.163 +    };
   1.164 +
   1.165 +    /// \brief Returns an iterator to the first value.
   1.166 +    ///
   1.167 +    /// Returns an stl compatible iterator to the
   1.168 +    /// first value of the map. The values of the
   1.169 +    /// map can be accessed in the [beginValue, endValue)
   1.170 +    /// range.
   1.171 +    ValueIterator beginValue() const {
   1.172 +      return ValueIterator(_inv_map.begin());
   1.173 +    }
   1.174 +
   1.175 +    /// \brief Returns an iterator after the last value.
   1.176 +    ///
   1.177 +    /// Returns an stl compatible iterator after the
   1.178 +    /// last value of the map. The values of the
   1.179 +    /// map can be accessed in the [beginValue, endValue)
   1.180 +    /// range.
   1.181 +    ValueIterator endValue() const {
   1.182 +      return ValueIterator(_inv_map.end());
   1.183 +    }
   1.184 +
   1.185 +    /// \brief The setter function of the map.
   1.186 +    ///
   1.187 +    /// Sets the mapped value.
   1.188 +    void set(const Key& key, const Value& val) {
   1.189 +      Value oldval = Map::operator[](key);
   1.190 +      typename Container::iterator it = _inv_map.find(oldval);
   1.191 +      if (it != _inv_map.end() && it->second == key) {
   1.192 +        _inv_map.erase(it);
   1.193 +      }
   1.194 +      _inv_map.insert(make_pair(val, key));
   1.195 +      Map::set(key, val);
   1.196 +    }
   1.197 +
   1.198 +    /// \brief The getter function of the map.
   1.199 +    ///
   1.200 +    /// It gives back the value associated with the key.
   1.201 +    typename MapTraits<Map>::ConstReturnValue
   1.202 +    operator[](const Key& key) const {
   1.203 +      return Map::operator[](key);
   1.204 +    }
   1.205 +
   1.206 +    /// \brief Gives back the item by its value.
   1.207 +    ///
   1.208 +    /// Gives back the item by its value.
   1.209 +    Key operator()(const Value& key) const {
   1.210 +      typename Container::const_iterator it = _inv_map.find(key);
   1.211 +      return it != _inv_map.end() ? it->second : INVALID;
   1.212 +    }
   1.213 +
   1.214 +  protected:
   1.215 +
   1.216 +    /// \brief Erase the key from the map.
   1.217 +    ///
   1.218 +    /// Erase the key to the map. It is called by the
   1.219 +    /// \c AlterationNotifier.
   1.220 +    virtual void erase(const Key& key) {
   1.221 +      Value val = Map::operator[](key);
   1.222 +      typename Container::iterator it = _inv_map.find(val);
   1.223 +      if (it != _inv_map.end() && it->second == key) {
   1.224 +        _inv_map.erase(it);
   1.225 +      }
   1.226 +      Map::erase(key);
   1.227 +    }
   1.228 +
   1.229 +    /// \brief Erase more keys from the map.
   1.230 +    ///
   1.231 +    /// Erase more keys from the map. It is called by the
   1.232 +    /// \c AlterationNotifier.
   1.233 +    virtual void erase(const std::vector<Key>& keys) {
   1.234 +      for (int i = 0; i < int(keys.size()); ++i) {
   1.235 +        Value val = Map::operator[](keys[i]);
   1.236 +        typename Container::iterator it = _inv_map.find(val);
   1.237 +        if (it != _inv_map.end() && it->second == keys[i]) {
   1.238 +          _inv_map.erase(it);
   1.239 +        }
   1.240 +      }
   1.241 +      Map::erase(keys);
   1.242 +    }
   1.243 +
   1.244 +    /// \brief Clear the keys from the map and inverse map.
   1.245 +    ///
   1.246 +    /// Clear the keys from the map and inverse map. It is called by the
   1.247 +    /// \c AlterationNotifier.
   1.248 +    virtual void clear() {
   1.249 +      _inv_map.clear();
   1.250 +      Map::clear();
   1.251 +    }
   1.252 +
   1.253 +  public:
   1.254 +
   1.255 +    /// \brief The inverse map type.
   1.256 +    ///
   1.257 +    /// The inverse of this map. The subscript operator of the map
   1.258 +    /// gives back always the item what was last assigned to the value.
   1.259 +    class InverseMap {
   1.260 +    public:
   1.261 +      /// \brief Constructor of the InverseMap.
   1.262 +      ///
   1.263 +      /// Constructor of the InverseMap.
   1.264 +      explicit InverseMap(const InvertableMap& inverted)
   1.265 +        : _inverted(inverted) {}
   1.266 +
   1.267 +      /// The value type of the InverseMap.
   1.268 +      typedef typename InvertableMap::Key Value;
   1.269 +      /// The key type of the InverseMap.
   1.270 +      typedef typename InvertableMap::Value Key;
   1.271 +
   1.272 +      /// \brief Subscript operator.
   1.273 +      ///
   1.274 +      /// Subscript operator. It gives back always the item
   1.275 +      /// what was last assigned to the value.
   1.276 +      Value operator[](const Key& key) const {
   1.277 +        return _inverted(key);
   1.278 +      }
   1.279 +
   1.280 +    private:
   1.281 +      const InvertableMap& _inverted;
   1.282 +    };
   1.283 +
   1.284 +    /// \brief It gives back the just readable inverse map.
   1.285 +    ///
   1.286 +    /// It gives back the just readable inverse map.
   1.287 +    InverseMap inverse() const {
   1.288 +      return InverseMap(*this);
   1.289 +    }
   1.290 +
   1.291 +
   1.292 +
   1.293 +  };
   1.294 +
   1.295 +  /// \brief Provides a mutable, continuous and unique descriptor for each
   1.296 +  /// item in the graph.
   1.297 +  ///
   1.298 +  /// The DescriptorMap class provides a unique and continuous (but mutable)
   1.299 +  /// descriptor (id) for each item of the same type (e.g. node) in the
   1.300 +  /// graph. This id is <ul><li>\b unique: different items (nodes) get
   1.301 +  /// different ids <li>\b continuous: the range of the ids is the set of
   1.302 +  /// integers between 0 and \c n-1, where \c n is the number of the items of
   1.303 +  /// this type (e.g. nodes) (so the id of a node can change if you delete an
   1.304 +  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
   1.305 +  /// with its member class \c InverseMap, or with the \c operator() member.
   1.306 +  ///
   1.307 +  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
   1.308 +  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
   1.309 +  /// Edge.
   1.310 +  template <typename _Graph, typename _Item>
   1.311 +  class DescriptorMap
   1.312 +    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
   1.313 +
   1.314 +    typedef _Item Item;
   1.315 +    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
   1.316 +
   1.317 +  public:
   1.318 +    /// The graph class of DescriptorMap.
   1.319 +    typedef _Graph Graph;
   1.320 +
   1.321 +    /// The key type of DescriptorMap (Node, Arc, Edge).
   1.322 +    typedef typename Map::Key Key;
   1.323 +    /// The value type of DescriptorMap.
   1.324 +    typedef typename Map::Value Value;
   1.325 +
   1.326 +    /// \brief Constructor.
   1.327 +    ///
   1.328 +    /// Constructor for descriptor map.
   1.329 +    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
   1.330 +      Item it;
   1.331 +      const typename Map::Notifier* nf = Map::notifier();
   1.332 +      for (nf->first(it); it != INVALID; nf->next(it)) {
   1.333 +        Map::set(it, _inv_map.size());
   1.334 +        _inv_map.push_back(it);
   1.335 +      }
   1.336 +    }
   1.337 +
   1.338 +  protected:
   1.339 +
   1.340 +    /// \brief Add a new key to the map.
   1.341 +    ///
   1.342 +    /// Add a new key to the map. It is called by the
   1.343 +    /// \c AlterationNotifier.
   1.344 +    virtual void add(const Item& item) {
   1.345 +      Map::add(item);
   1.346 +      Map::set(item, _inv_map.size());
   1.347 +      _inv_map.push_back(item);
   1.348 +    }
   1.349 +
   1.350 +    /// \brief Add more new keys to the map.
   1.351 +    ///
   1.352 +    /// Add more new keys to the map. It is called by the
   1.353 +    /// \c AlterationNotifier.
   1.354 +    virtual void add(const std::vector<Item>& items) {
   1.355 +      Map::add(items);
   1.356 +      for (int i = 0; i < int(items.size()); ++i) {
   1.357 +        Map::set(items[i], _inv_map.size());
   1.358 +        _inv_map.push_back(items[i]);
   1.359 +      }
   1.360 +    }
   1.361 +
   1.362 +    /// \brief Erase the key from the map.
   1.363 +    ///
   1.364 +    /// Erase the key from the map. It is called by the
   1.365 +    /// \c AlterationNotifier.
   1.366 +    virtual void erase(const Item& item) {
   1.367 +      Map::set(_inv_map.back(), Map::operator[](item));
   1.368 +      _inv_map[Map::operator[](item)] = _inv_map.back();
   1.369 +      _inv_map.pop_back();
   1.370 +      Map::erase(item);
   1.371 +    }
   1.372 +
   1.373 +    /// \brief Erase more keys from the map.
   1.374 +    ///
   1.375 +    /// Erase more keys from the map. It is called by the
   1.376 +    /// \c AlterationNotifier.
   1.377 +    virtual void erase(const std::vector<Item>& items) {
   1.378 +      for (int i = 0; i < int(items.size()); ++i) {
   1.379 +        Map::set(_inv_map.back(), Map::operator[](items[i]));
   1.380 +        _inv_map[Map::operator[](items[i])] = _inv_map.back();
   1.381 +        _inv_map.pop_back();
   1.382 +      }
   1.383 +      Map::erase(items);
   1.384 +    }
   1.385 +
   1.386 +    /// \brief Build the unique map.
   1.387 +    ///
   1.388 +    /// Build the unique map. It is called by the
   1.389 +    /// \c AlterationNotifier.
   1.390 +    virtual void build() {
   1.391 +      Map::build();
   1.392 +      Item it;
   1.393 +      const typename Map::Notifier* nf = Map::notifier();
   1.394 +      for (nf->first(it); it != INVALID; nf->next(it)) {
   1.395 +        Map::set(it, _inv_map.size());
   1.396 +        _inv_map.push_back(it);
   1.397 +      }
   1.398 +    }
   1.399 +
   1.400 +    /// \brief Clear the keys from the map.
   1.401 +    ///
   1.402 +    /// Clear the keys from the map. It is called by the
   1.403 +    /// \c AlterationNotifier.
   1.404 +    virtual void clear() {
   1.405 +      _inv_map.clear();
   1.406 +      Map::clear();
   1.407 +    }
   1.408 +
   1.409 +  public:
   1.410 +
   1.411 +    /// \brief Returns the maximal value plus one.
   1.412 +    ///
   1.413 +    /// Returns the maximal value plus one in the map.
   1.414 +    unsigned int size() const {
   1.415 +      return _inv_map.size();
   1.416 +    }
   1.417 +
   1.418 +    /// \brief Swaps the position of the two items in the map.
   1.419 +    ///
   1.420 +    /// Swaps the position of the two items in the map.
   1.421 +    void swap(const Item& p, const Item& q) {
   1.422 +      int pi = Map::operator[](p);
   1.423 +      int qi = Map::operator[](q);
   1.424 +      Map::set(p, qi);
   1.425 +      _inv_map[qi] = p;
   1.426 +      Map::set(q, pi);
   1.427 +      _inv_map[pi] = q;
   1.428 +    }
   1.429 +
   1.430 +    /// \brief Gives back the \e descriptor of the item.
   1.431 +    ///
   1.432 +    /// Gives back the mutable and unique \e descriptor of the map.
   1.433 +    int operator[](const Item& item) const {
   1.434 +      return Map::operator[](item);
   1.435 +    }
   1.436 +
   1.437 +    /// \brief Gives back the item by its descriptor.
   1.438 +    ///
   1.439 +    /// Gives back th item by its descriptor.
   1.440 +    Item operator()(int id) const {
   1.441 +      return _inv_map[id];
   1.442 +    }
   1.443 +
   1.444 +  private:
   1.445 +
   1.446 +    typedef std::vector<Item> Container;
   1.447 +    Container _inv_map;
   1.448 +
   1.449 +  public:
   1.450 +    /// \brief The inverse map type of DescriptorMap.
   1.451 +    ///
   1.452 +    /// The inverse map type of DescriptorMap.
   1.453 +    class InverseMap {
   1.454 +    public:
   1.455 +      /// \brief Constructor of the InverseMap.
   1.456 +      ///
   1.457 +      /// Constructor of the InverseMap.
   1.458 +      explicit InverseMap(const DescriptorMap& inverted)
   1.459 +        : _inverted(inverted) {}
   1.460 +
   1.461 +
   1.462 +      /// The value type of the InverseMap.
   1.463 +      typedef typename DescriptorMap::Key Value;
   1.464 +      /// The key type of the InverseMap.
   1.465 +      typedef typename DescriptorMap::Value Key;
   1.466 +
   1.467 +      /// \brief Subscript operator.
   1.468 +      ///
   1.469 +      /// Subscript operator. It gives back the item
   1.470 +      /// that the descriptor belongs to currently.
   1.471 +      Value operator[](const Key& key) const {
   1.472 +        return _inverted(key);
   1.473 +      }
   1.474 +
   1.475 +      /// \brief Size of the map.
   1.476 +      ///
   1.477 +      /// Returns the size of the map.
   1.478 +      unsigned int size() const {
   1.479 +        return _inverted.size();
   1.480 +      }
   1.481 +
   1.482 +    private:
   1.483 +      const DescriptorMap& _inverted;
   1.484 +    };
   1.485 +
   1.486 +    /// \brief Gives back the inverse of the map.
   1.487 +    ///
   1.488 +    /// Gives back the inverse of the map.
   1.489 +    const InverseMap inverse() const {
   1.490 +      return InverseMap(*this);
   1.491 +    }
   1.492 +  };
   1.493 +
   1.494 +  /// \brief Returns the source of the given arc.
   1.495 +  ///
   1.496 +  /// The SourceMap gives back the source Node of the given arc.
   1.497 +  /// \see TargetMap
   1.498 +  template <typename Digraph>
   1.499 +  class SourceMap {
   1.500 +  public:
   1.501 +
   1.502 +    typedef typename Digraph::Node Value;
   1.503 +    typedef typename Digraph::Arc Key;
   1.504 +
   1.505 +    /// \brief Constructor
   1.506 +    ///
   1.507 +    /// Constructor
   1.508 +    /// \param _digraph The digraph that the map belongs to.
   1.509 +    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
   1.510 +
   1.511 +    /// \brief The subscript operator.
   1.512 +    ///
   1.513 +    /// The subscript operator.
   1.514 +    /// \param arc The arc
   1.515 +    /// \return The source of the arc
   1.516 +    Value operator[](const Key& arc) const {
   1.517 +      return _digraph.source(arc);
   1.518 +    }
   1.519 +
   1.520 +  private:
   1.521 +    const Digraph& _digraph;
   1.522 +  };
   1.523 +
   1.524 +  /// \brief Returns a \ref SourceMap class.
   1.525 +  ///
   1.526 +  /// This function just returns an \ref SourceMap class.
   1.527 +  /// \relates SourceMap
   1.528 +  template <typename Digraph>
   1.529 +  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
   1.530 +    return SourceMap<Digraph>(digraph);
   1.531 +  }
   1.532 +
   1.533 +  /// \brief Returns the target of the given arc.
   1.534 +  ///
   1.535 +  /// The TargetMap gives back the target Node of the given arc.
   1.536 +  /// \see SourceMap
   1.537 +  template <typename Digraph>
   1.538 +  class TargetMap {
   1.539 +  public:
   1.540 +
   1.541 +    typedef typename Digraph::Node Value;
   1.542 +    typedef typename Digraph::Arc Key;
   1.543 +
   1.544 +    /// \brief Constructor
   1.545 +    ///
   1.546 +    /// Constructor
   1.547 +    /// \param _digraph The digraph that the map belongs to.
   1.548 +    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
   1.549 +
   1.550 +    /// \brief The subscript operator.
   1.551 +    ///
   1.552 +    /// The subscript operator.
   1.553 +    /// \param e The arc
   1.554 +    /// \return The target of the arc
   1.555 +    Value operator[](const Key& e) const {
   1.556 +      return _digraph.target(e);
   1.557 +    }
   1.558 +
   1.559 +  private:
   1.560 +    const Digraph& _digraph;
   1.561 +  };
   1.562 +
   1.563 +  /// \brief Returns a \ref TargetMap class.
   1.564 +  ///
   1.565 +  /// This function just returns a \ref TargetMap class.
   1.566 +  /// \relates TargetMap
   1.567 +  template <typename Digraph>
   1.568 +  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
   1.569 +    return TargetMap<Digraph>(digraph);
   1.570 +  }
   1.571 +
   1.572 +  /// \brief Returns the "forward" directed arc view of an edge.
   1.573 +  ///
   1.574 +  /// Returns the "forward" directed arc view of an edge.
   1.575 +  /// \see BackwardMap
   1.576 +  template <typename Graph>
   1.577 +  class ForwardMap {
   1.578 +  public:
   1.579 +
   1.580 +    typedef typename Graph::Arc Value;
   1.581 +    typedef typename Graph::Edge Key;
   1.582 +
   1.583 +    /// \brief Constructor
   1.584 +    ///
   1.585 +    /// Constructor
   1.586 +    /// \param _graph The graph that the map belongs to.
   1.587 +    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
   1.588 +
   1.589 +    /// \brief The subscript operator.
   1.590 +    ///
   1.591 +    /// The subscript operator.
   1.592 +    /// \param key An edge
   1.593 +    /// \return The "forward" directed arc view of edge
   1.594 +    Value operator[](const Key& key) const {
   1.595 +      return _graph.direct(key, true);
   1.596 +    }
   1.597 +
   1.598 +  private:
   1.599 +    const Graph& _graph;
   1.600 +  };
   1.601 +
   1.602 +  /// \brief Returns a \ref ForwardMap class.
   1.603 +  ///
   1.604 +  /// This function just returns an \ref ForwardMap class.
   1.605 +  /// \relates ForwardMap
   1.606 +  template <typename Graph>
   1.607 +  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
   1.608 +    return ForwardMap<Graph>(graph);
   1.609 +  }
   1.610 +
   1.611 +  /// \brief Returns the "backward" directed arc view of an edge.
   1.612 +  ///
   1.613 +  /// Returns the "backward" directed arc view of an edge.
   1.614 +  /// \see ForwardMap
   1.615 +  template <typename Graph>
   1.616 +  class BackwardMap {
   1.617 +  public:
   1.618 +
   1.619 +    typedef typename Graph::Arc Value;
   1.620 +    typedef typename Graph::Edge Key;
   1.621 +
   1.622 +    /// \brief Constructor
   1.623 +    ///
   1.624 +    /// Constructor
   1.625 +    /// \param _graph The graph that the map belongs to.
   1.626 +    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
   1.627 +
   1.628 +    /// \brief The subscript operator.
   1.629 +    ///
   1.630 +    /// The subscript operator.
   1.631 +    /// \param key An edge
   1.632 +    /// \return The "backward" directed arc view of edge
   1.633 +    Value operator[](const Key& key) const {
   1.634 +      return _graph.direct(key, false);
   1.635 +    }
   1.636 +
   1.637 +  private:
   1.638 +    const Graph& _graph;
   1.639 +  };
   1.640 +
   1.641 +  /// \brief Returns a \ref BackwardMap class
   1.642 +
   1.643 +  /// This function just returns a \ref BackwardMap class.
   1.644 +  /// \relates BackwardMap
   1.645 +  template <typename Graph>
   1.646 +  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
   1.647 +    return BackwardMap<Graph>(graph);
   1.648 +  }
   1.649 +
   1.650 +  /// \brief Potential difference map
   1.651 +  ///
   1.652 +  /// If there is an potential map on the nodes then we
   1.653 +  /// can get an arc map as we get the substraction of the
   1.654 +  /// values of the target and source.
   1.655 +  template <typename Digraph, typename NodeMap>
   1.656 +  class PotentialDifferenceMap {
   1.657 +  public:
   1.658 +    typedef typename Digraph::Arc Key;
   1.659 +    typedef typename NodeMap::Value Value;
   1.660 +
   1.661 +    /// \brief Constructor
   1.662 +    ///
   1.663 +    /// Contructor of the map
   1.664 +    explicit PotentialDifferenceMap(const Digraph& digraph,
   1.665 +                                    const NodeMap& potential)
   1.666 +      : _digraph(digraph), _potential(potential) {}
   1.667 +
   1.668 +    /// \brief Const subscription operator
   1.669 +    ///
   1.670 +    /// Const subscription operator
   1.671 +    Value operator[](const Key& arc) const {
   1.672 +      return _potential[_digraph.target(arc)] -
   1.673 +        _potential[_digraph.source(arc)];
   1.674 +    }
   1.675 +
   1.676 +  private:
   1.677 +    const Digraph& _digraph;
   1.678 +    const NodeMap& _potential;
   1.679 +  };
   1.680 +
   1.681 +  /// \brief Returns a PotentialDifferenceMap.
   1.682 +  ///
   1.683 +  /// This function just returns a PotentialDifferenceMap.
   1.684 +  /// \relates PotentialDifferenceMap
   1.685 +  template <typename Digraph, typename NodeMap>
   1.686 +  PotentialDifferenceMap<Digraph, NodeMap>
   1.687 +  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
   1.688 +    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
   1.689 +  }
   1.690 +
   1.691 +  /// \brief Map of the node in-degrees.
   1.692 +  ///
   1.693 +  /// This map returns the in-degree of a node. Once it is constructed,
   1.694 +  /// the degrees are stored in a standard NodeMap, so each query is done
   1.695 +  /// in constant time. On the other hand, the values are updated automatically
   1.696 +  /// whenever the digraph changes.
   1.697 +  ///
   1.698 +  /// \warning Besides addNode() and addArc(), a digraph structure may provide
   1.699 +  /// alternative ways to modify the digraph. The correct behavior of InDegMap
   1.700 +  /// is not guarantied if these additional features are used. For example
   1.701 +  /// the functions \ref ListDigraph::changeSource() "changeSource()",
   1.702 +  /// \ref ListDigraph::changeTarget() "changeTarget()" and
   1.703 +  /// \ref ListDigraph::reverseArc() "reverseArc()"
   1.704 +  /// of \ref ListDigraph will \e not update the degree values correctly.
   1.705 +  ///
   1.706 +  /// \sa OutDegMap
   1.707 +
   1.708 +  template <typename _Digraph>
   1.709 +  class InDegMap
   1.710 +    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
   1.711 +      ::ItemNotifier::ObserverBase {
   1.712 +
   1.713 +  public:
   1.714 +
   1.715 +    typedef _Digraph Digraph;
   1.716 +    typedef int Value;
   1.717 +    typedef typename Digraph::Node Key;
   1.718 +
   1.719 +    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
   1.720 +    ::ItemNotifier::ObserverBase Parent;
   1.721 +
   1.722 +  private:
   1.723 +
   1.724 +    class AutoNodeMap
   1.725 +      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
   1.726 +    public:
   1.727 +
   1.728 +      typedef typename ItemSetTraits<Digraph, Key>::
   1.729 +      template Map<int>::Type Parent;
   1.730 +
   1.731 +      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
   1.732 +
   1.733 +      virtual void add(const Key& key) {
   1.734 +        Parent::add(key);
   1.735 +        Parent::set(key, 0);
   1.736 +      }
   1.737 +
   1.738 +      virtual void add(const std::vector<Key>& keys) {
   1.739 +        Parent::add(keys);
   1.740 +        for (int i = 0; i < int(keys.size()); ++i) {
   1.741 +          Parent::set(keys[i], 0);
   1.742 +        }
   1.743 +      }
   1.744 +
   1.745 +      virtual void build() {
   1.746 +        Parent::build();
   1.747 +        Key it;
   1.748 +        typename Parent::Notifier* nf = Parent::notifier();
   1.749 +        for (nf->first(it); it != INVALID; nf->next(it)) {
   1.750 +          Parent::set(it, 0);
   1.751 +        }
   1.752 +      }
   1.753 +    };
   1.754 +
   1.755 +  public:
   1.756 +
   1.757 +    /// \brief Constructor.
   1.758 +    ///
   1.759 +    /// Constructor for creating in-degree map.
   1.760 +    explicit InDegMap(const Digraph& digraph)
   1.761 +      : _digraph(digraph), _deg(digraph) {
   1.762 +      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
   1.763 +
   1.764 +      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
   1.765 +        _deg[it] = countInArcs(_digraph, it);
   1.766 +      }
   1.767 +    }
   1.768 +
   1.769 +    /// Gives back the in-degree of a Node.
   1.770 +    int operator[](const Key& key) const {
   1.771 +      return _deg[key];
   1.772 +    }
   1.773 +
   1.774 +  protected:
   1.775 +
   1.776 +    typedef typename Digraph::Arc Arc;
   1.777 +
   1.778 +    virtual void add(const Arc& arc) {
   1.779 +      ++_deg[_digraph.target(arc)];
   1.780 +    }
   1.781 +
   1.782 +    virtual void add(const std::vector<Arc>& arcs) {
   1.783 +      for (int i = 0; i < int(arcs.size()); ++i) {
   1.784 +        ++_deg[_digraph.target(arcs[i])];
   1.785 +      }
   1.786 +    }
   1.787 +
   1.788 +    virtual void erase(const Arc& arc) {
   1.789 +      --_deg[_digraph.target(arc)];
   1.790 +    }
   1.791 +
   1.792 +    virtual void erase(const std::vector<Arc>& arcs) {
   1.793 +      for (int i = 0; i < int(arcs.size()); ++i) {
   1.794 +        --_deg[_digraph.target(arcs[i])];
   1.795 +      }
   1.796 +    }
   1.797 +
   1.798 +    virtual void build() {
   1.799 +      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
   1.800 +        _deg[it] = countInArcs(_digraph, it);
   1.801 +      }
   1.802 +    }
   1.803 +
   1.804 +    virtual void clear() {
   1.805 +      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
   1.806 +        _deg[it] = 0;
   1.807 +      }
   1.808 +    }
   1.809 +  private:
   1.810 +
   1.811 +    const Digraph& _digraph;
   1.812 +    AutoNodeMap _deg;
   1.813 +  };
   1.814 +
   1.815 +  /// \brief Map of the node out-degrees.
   1.816 +  ///
   1.817 +  /// This map returns the out-degree of a node. Once it is constructed,
   1.818 +  /// the degrees are stored in a standard NodeMap, so each query is done
   1.819 +  /// in constant time. On the other hand, the values are updated automatically
   1.820 +  /// whenever the digraph changes.
   1.821 +  ///
   1.822 +  /// \warning Besides addNode() and addArc(), a digraph structure may provide
   1.823 +  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
   1.824 +  /// is not guarantied if these additional features are used. For example
   1.825 +  /// the functions \ref ListDigraph::changeSource() "changeSource()",
   1.826 +  /// \ref ListDigraph::changeTarget() "changeTarget()" and
   1.827 +  /// \ref ListDigraph::reverseArc() "reverseArc()"
   1.828 +  /// of \ref ListDigraph will \e not update the degree values correctly.
   1.829 +  ///
   1.830 +  /// \sa InDegMap
   1.831 +
   1.832 +  template <typename _Digraph>
   1.833 +  class OutDegMap
   1.834 +    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
   1.835 +      ::ItemNotifier::ObserverBase {
   1.836 +
   1.837 +  public:
   1.838 +
   1.839 +    typedef _Digraph Digraph;
   1.840 +    typedef int Value;
   1.841 +    typedef typename Digraph::Node Key;
   1.842 +
   1.843 +    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
   1.844 +    ::ItemNotifier::ObserverBase Parent;
   1.845 +
   1.846 +  private:
   1.847 +
   1.848 +    class AutoNodeMap
   1.849 +      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
   1.850 +    public:
   1.851 +
   1.852 +      typedef typename ItemSetTraits<Digraph, Key>::
   1.853 +      template Map<int>::Type Parent;
   1.854 +
   1.855 +      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
   1.856 +
   1.857 +      virtual void add(const Key& key) {
   1.858 +        Parent::add(key);
   1.859 +        Parent::set(key, 0);
   1.860 +      }
   1.861 +      virtual void add(const std::vector<Key>& keys) {
   1.862 +        Parent::add(keys);
   1.863 +        for (int i = 0; i < int(keys.size()); ++i) {
   1.864 +          Parent::set(keys[i], 0);
   1.865 +        }
   1.866 +      }
   1.867 +      virtual void build() {
   1.868 +        Parent::build();
   1.869 +        Key it;
   1.870 +        typename Parent::Notifier* nf = Parent::notifier();
   1.871 +        for (nf->first(it); it != INVALID; nf->next(it)) {
   1.872 +          Parent::set(it, 0);
   1.873 +        }
   1.874 +      }
   1.875 +    };
   1.876 +
   1.877 +  public:
   1.878 +
   1.879 +    /// \brief Constructor.
   1.880 +    ///
   1.881 +    /// Constructor for creating out-degree map.
   1.882 +    explicit OutDegMap(const Digraph& digraph)
   1.883 +      : _digraph(digraph), _deg(digraph) {
   1.884 +      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
   1.885 +
   1.886 +      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
   1.887 +        _deg[it] = countOutArcs(_digraph, it);
   1.888 +      }
   1.889 +    }
   1.890 +
   1.891 +    /// Gives back the out-degree of a Node.
   1.892 +    int operator[](const Key& key) const {
   1.893 +      return _deg[key];
   1.894 +    }
   1.895 +
   1.896 +  protected:
   1.897 +
   1.898 +    typedef typename Digraph::Arc Arc;
   1.899 +
   1.900 +    virtual void add(const Arc& arc) {
   1.901 +      ++_deg[_digraph.source(arc)];
   1.902 +    }
   1.903 +
   1.904 +    virtual void add(const std::vector<Arc>& arcs) {
   1.905 +      for (int i = 0; i < int(arcs.size()); ++i) {
   1.906 +        ++_deg[_digraph.source(arcs[i])];
   1.907 +      }
   1.908 +    }
   1.909 +
   1.910 +    virtual void erase(const Arc& arc) {
   1.911 +      --_deg[_digraph.source(arc)];
   1.912 +    }
   1.913 +
   1.914 +    virtual void erase(const std::vector<Arc>& arcs) {
   1.915 +      for (int i = 0; i < int(arcs.size()); ++i) {
   1.916 +        --_deg[_digraph.source(arcs[i])];
   1.917 +      }
   1.918 +    }
   1.919 +
   1.920 +    virtual void build() {
   1.921 +      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
   1.922 +        _deg[it] = countOutArcs(_digraph, it);
   1.923 +      }
   1.924 +    }
   1.925 +
   1.926 +    virtual void clear() {
   1.927 +      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
   1.928 +        _deg[it] = 0;
   1.929 +      }
   1.930 +    }
   1.931 +  private:
   1.932 +
   1.933 +    const Digraph& _digraph;
   1.934 +    AutoNodeMap _deg;
   1.935 +  };
   1.936 +
   1.937    /// @}
   1.938  }
   1.939