RhodeCode

      IterableIntMapNode(int _value) : value(_value) {}

      Item prev, next;

      int value;

    };

  }

  /// \brief Dynamic iterable integer map.

  ///

  /// This class provides a special graph map type which can store an

  /// integer value for graph items (\c Node, \c Arc or \c Edge).

  /// For each non-negative value it is possible to iterate on the keys

  /// mapped to the value.

  ///

  /// This map is intended to be used with small integer values, for which

  /// it is efficient, and supports iteration only for non-negative values.

  /// If you need large values and/or iteration for negative integers,

  /// consider to use \ref IterableValueMap instead.

  ///

  /// This type is a reference map, so it can be modified with the

  /// subscript operator.

  ///

  /// \note The size of the data structure depends on the largest

  /// value in the map.

  ///

  /// \tparam GR The graph type.

  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or

  /// \c GR::Edge).

  ///

  /// \see IterableBoolMap, IterableValueMap

  /// \see CrossRefMap

  template <typename GR, typename K>

  class IterableIntMap

    : protected ItemSetTraits<GR, K>::

        template Map<_maps_bits::IterableIntMapNode<K> >::Type {

  public:

    typedef typename ItemSetTraits<GR, K>::

      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;

    /// The key type

    typedef K Key;

    /// The value type

    typedef int Value;

    /// The graph type

    typedef GR Graph;

    /// \brief Constructor of the map.

    ///

    /// Constructor of the map. It sets all values to -1.

    explicit IterableIntMap(const Graph& graph)

      : Parent(graph) {}

    /// \brief Constructor of the map with a given value.

    ///

    /// Constructor of the map with a given value.

    explicit IterableIntMap(const Graph& graph, int value)

      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {

      if (value >= 0) {

        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {

          lace(it);

        }

      }

    }

  private:

    void unlace(const Key& key) {

      typename Parent::Value& node = Parent::operator[](key);

      if (node.value < 0) return;

      if (node.prev != INVALID) {

        Parent::operator[](node.prev).next = node.next;

      } else {

        _first[node.value] = node.next;

      }

      if (node.next != INVALID) {

        Parent::operator[](node.next).prev = node.prev;

      }

      while (!_first.empty() && _first.back() == INVALID) {

        _first.pop_back();

      }

    }

    void lace(const Key& key) {

      typename Parent::Value& node = Parent::operator[](key);

      if (node.value < 0) return;

      if (node.value >= int(_first.size())) {

        _first.resize(node.value + 1, INVALID);

      }

      node.prev = INVALID;

      node.next = _first[node.value];

      if (node.next != INVALID) {

        Parent::operator[](node.next).prev = key;

      }

      _first[node.value] = key;

    }

  public:

    /// Indicates that the map is reference map.

    typedef True ReferenceMapTag;

    /// \brief Reference to the value of the map.

    ///

    /// This class is similar to the \c int type. It can

    /// be converted to \c int and it has the same operators.

    class Reference {

      friend class IterableIntMap;

    private:

      Reference(IterableIntMap& map, const Key& key)

        : _key(key), _map(map) {}

    public:

      Reference& operator=(const Reference& value) {

        _map.set(_key, static_cast<const int&>(value));

         return *this;

      }

      operator const int&() const {

        return static_cast<const IterableIntMap&>(_map)[_key];

      }

      Reference& operator=(int value) {

        _map.set(_key, value);

        return *this;

      }

      Reference& operator++() {

        _map.set(_key, _map[_key] + 1);

        return *this;

      }

      int operator++(int) {

        int value = _map[_key];

        _map.set(_key, value + 1);

        return value;

      }

      Reference& operator--() {

        _map.set(_key, _map[_key] - 1);

        return *this;

      }

      int operator--(int) {

        int value = _map[_key];

        _map.set(_key, value - 1);

        return value;

      }

      Reference& operator+=(int value) {

        _map.set(_key, _map[_key] + value);

        return *this;

      }

      Reference& operator-=(int value) {

        _map.set(_key, _map[_key] - value);

        return *this;

      }

      Reference& operator*=(int value) {

        _map.set(_key, _map[_key] * value);

        return *this;

      }

      Reference& operator/=(int value) {

        _map.set(_key, _map[_key] / value);

        return *this;

      }

      Reference& operator%=(int value) {

        _map.set(_key, _map[_key] % value);

        return *this;

      }

      Reference& operator&=(int value) {

        _map.set(_key, _map[_key] & value);

        return *this;

      }

      Reference& operator|=(int value) {

        _map.set(_key, _map[_key] | value);

        return *this;

      }

      Reference& operator^=(int value) {

        _map.set(_key, _map[_key] ^ value);

        return *this;

      }

      Reference& operator<<=(int value) {

        _map.set(_key, _map[_key] << value);

        return *this;

      }

      Reference& operator>>=(int value) {

        _map.set(_key, _map[_key] >> value);

        return *this;

      }

    private:

      Key _key;

      IterableIntMap& _map;

    };

    /// The const reference type.

    typedef const Value& ConstReference;

    /// \brief Gives back the maximal value plus one.

    ///

    /// Gives back the maximal value plus one.

    int size() const {

      return _first.size();

    }

    /// \brief Set operation of the map.

    ///

    /// Set operation of the map.

    void set(const Key& key, const Value& value) {

      unlace(key);

      Parent::operator[](key).value = value;

      lace(key);

    }

    /// \brief Const subscript operator of the map.

    ///

    /// Const subscript operator of the map.

    const Value& operator[](const Key& key) const {

      return Parent::operator[](key).value;

    }

    /// \brief Subscript operator of the map.

    ///

    /// Subscript operator of the map.

    Reference operator[](const Key& key) {

      return Reference(*this, key);

    }

    /// \brief Iterator for the keys with the same value.

    ///

    /// Iterator for the keys with the same value. It works

    /// like a graph item iterator, it can be converted to

    /// the item type of the map, incremented with \c ++ operator, and

    /// if the iterator leaves the last valid item, it will be equal to

    /// \c INVALID.

    class ItemIt : public Key {

    public:

      typedef Key Parent;

      /// \brief Invalid constructor \& conversion.

      ///

      /// This constructor initializes the iterator to be invalid.

      /// \sa Invalid for more details.

      ItemIt(Invalid) : Parent(INVALID), _map(0) {}

      /// \brief Creates an iterator with a value.

      ///

      /// Creates an iterator with a value. It iterates on the

      /// keys mapped to the given value.

      /// \param map The IterableIntMap.

      /// \param value The value.

      ItemIt(const IterableIntMap& map, int value) : _map(&map) {

        if (value < 0 || value >= int(_map->_first.size())) {

          Parent::operator=(INVALID);

        } else {

          Parent::operator=(_map->_first[value]);

        }

      }

      /// \brief Increment operator.

      ///

      /// Increment operator.

      ItemIt& operator++() {

        Parent::operator=(_map->IterableIntMap::Parent::

                          operator[](static_cast<Parent&>(*this)).next);

        return *this;

      }

    private:

      const IterableIntMap* _map;

    };

  protected:

    virtual void erase(const Key& key) {

      unlace(key);

      Parent::erase(key);

    }

    virtual void erase(const std::vector<Key>& keys) {

      for (int i = 0; i < int(keys.size()); ++i) {

        unlace(keys[i]);

      }

      Parent::erase(keys);

    }

    virtual void clear() {

      _first.clear();

      Parent::clear();

    }

  private:

    std::vector<Key> _first;

  };

  namespace _maps_bits {

    template <typename Item, typename Value>

    struct IterableValueMapNode {

      IterableValueMapNode(Value _value = Value()) : value(_value) {}

      Item prev, next;

      Value value;

    };

  }

  /// \brief Dynamic iterable map for comparable values.

  ///

  /// This class provides a special graph map type which can store a

  /// comparable value for graph items (\c Node, \c Arc or \c Edge).

  /// For each value it is possible to iterate on the keys mapped to

  /// the value (\c ItemIt), and the values of the map can be accessed

  /// with an STL compatible forward iterator (\c ValueIt).

  /// The map stores a linked list for each value, which contains

  /// the items mapped to the value, and the used values are stored

  /// in balanced binary tree (\c std::map).

  ///

  /// \ref IterableBoolMap and \ref IterableIntMap are similar classes

  /// specialized for \c bool and \c int values, respectively.

  ///

  /// This type is not reference map, so it cannot be modified with

  /// the subscript operator.

  ///

  /// \tparam GR The graph type.

  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or

  /// \c GR::Edge).

  /// \tparam V The value type of the map. It can be any comparable

  /// value type.

  ///

  /// \see IterableBoolMap, IterableIntMap

  /// \see CrossRefMap

  template <typename GR, typename K, typename V>

  class IterableValueMap

    : protected ItemSetTraits<GR, K>::

        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {

  public:

    typedef typename ItemSetTraits<GR, K>::

      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;

    /// The key type

    typedef K Key;

    /// The value type

    typedef V Value;

    /// The graph type

    typedef GR Graph;

  public:

    /// \brief Constructor of the map with a given value.

    ///

    /// Constructor of the map with a given value.

    explicit IterableValueMap(const Graph& graph,

                              const Value& value = Value())

      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {

      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {

        lace(it);

      }

    }

  protected:

    void unlace(const Key& key) {

      typename Parent::Value& node = Parent::operator[](key);

      if (node.prev != INVALID) {

        Parent::operator[](node.prev).next = node.next;

      } else {

        if (node.next != INVALID) {

          _first[node.value] = node.next;

        } else {

          _first.erase(node.value);

        }

      }

      if (node.next != INVALID) {

        Parent::operator[](node.next).prev = node.prev;

      }

    }

    void lace(const Key& key) {

      typename Parent::Value& node = Parent::operator[](key);

      typename std::map<Value, Key>::iterator it = _first.find(node.value);

      if (it == _first.end()) {

        node.prev = node.next = INVALID;

        _first.insert(std::make_pair(node.value, key));

      } else {

        node.prev = INVALID;

        node.next = it->second;

        if (node.next != INVALID) {

          Parent::operator[](node.next).prev = key;

        }

        it->second = key;

      }

    }

  public:

    /// \brief Forward iterator for values.

    ///

    /// This iterator is an STL compatible forward

    /// iterator on the values of the map. The values can

    /// be accessed in the <tt>[beginValue, endValue)</tt> range.

    class ValueIt

      : public std::iterator<std::forward_iterator_tag, Value> {

      friend class IterableValueMap;

    private:

      ValueIt(typename std::map<Value, Key>::const_iterator _it)

        : it(_it) {}

    public:

      /// Constructor

      ValueIt() {}

      /// \e

      ValueIt& operator++() { ++it; return *this; }

      /// \e

      ValueIt operator++(int) {

        ValueIt tmp(*this);

        operator++();

        return tmp;

      }

      /// \e

      const Value& operator*() const { return it->first; }

      /// \e

      const Value* operator->() const { return &(it->first); }

      /// \e

      bool operator==(ValueIt jt) const { return it == jt.it; }

      /// \e

      bool operator!=(ValueIt jt) const { return it != jt.it; }

    private:

      typename std::map<Value, Key>::const_iterator it;

    };

    /// \brief Returns an iterator to the first value.

    ///

    /// Returns an STL compatible iterator to the

    /// first value of the map. The values of the

    /// map can be accessed in the <tt>[beginValue, endValue)</tt>

    /// range.

    ValueIt beginValue() const {

      return ValueIt(_first.begin());

    }

    /// \brief Returns an iterator after the last value.

    ///

    /// Returns an STL compatible iterator after the

    /// last value of the map. The values of the

    /// map can be accessed in the <tt>[beginValue, endValue)</tt>

    /// range.

    ValueIt endValue() const {

      return ValueIt(_first.end());

    }

    /// \brief Set operation of the map.

    ///

    /// Set operation of the map.

    void set(const Key& key, const Value& value) {

      unlace(key);

      Parent::operator[](key).value = value;

      lace(key);

    }

    /// \brief Const subscript operator of the map.

    ///

    /// Const subscript operator of the map.

    const Value& operator[](const Key& key) const {

      return Parent::operator[](key).value;

    }

    /// \brief Iterator for the keys with the same value.

    ///

    /// Iterator for the keys with the same value. It works

    /// like a graph item iterator, it can be converted to

    /// the item type of the map, incremented with \c ++ operator, and

    /// if the iterator leaves the last valid item, it will be equal to

    /// \c INVALID.

    class ItemIt : public Key {

    public:

      typedef Key Parent;

      /// \brief Invalid constructor \& conversion.

      ///

      /// This constructor initializes the iterator to be invalid.

      /// \sa Invalid for more details.

      ItemIt(Invalid) : Parent(INVALID), _map(0) {}

      /// \brief Creates an iterator with a value.

      ///

      /// Creates an iterator with a value. It iterates on the

      /// keys which have the given value.

      /// \param map The IterableValueMap

      /// \param value The value

      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {

        typename std::map<Value, Key>::const_iterator it =

          map._first.find(value);

        if (it == map._first.end()) {

          Parent::operator=(INVALID);

        } else {

          Parent::operator=(it->second);

        }

      }

      /// \brief Increment operator.

      ///

      /// Increment Operator.

      ItemIt& operator++() {

        Parent::operator=(_map->IterableValueMap::Parent::

                          operator[](static_cast<Parent&>(*this)).next);

        return *this;

      }

    private:

      const IterableValueMap* _map;

    };

  protected:

    virtual void add(const Key& key) {

      Parent::add(key);

    }

    virtual void add(const std::vector<Key>& keys) {

      Parent::add(keys);

      for (int i = 0; i < int(keys.size()); ++i) {

        lace(keys[i]);

      }

    }

    virtual void erase(const Key& key) {

      unlace(key);

      Parent::erase(key);

    }

    virtual void erase(const std::vector<Key>& keys) {

      for (int i = 0; i < int(keys.size()); ++i) {

        unlace(keys[i]);

      }

      Parent::erase(keys);

    }

    virtual void build() {

      Parent::build();

      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {

        lace(it);

      }

    }

    virtual void clear() {

      _first.clear();

      Parent::clear();

    }

  private:

    std::map<Value, Key> _first;

  };

  /// \brief Map of the source nodes of arcs in a digraph.

  ///

  /// SourceMap provides access for the source node of each arc in a digraph,

  /// which is returned by the \c source() function of the digraph.

  /// \tparam GR The digraph type.

  /// \see TargetMap

  template <typename GR>

  class SourceMap {

  public:

    /// The key type (the \c Arc type of the digraph).

    typedef typename GR::Arc Key;

    /// The value type (the \c Node type of the digraph).

    typedef typename GR::Node Value;

    /// \brief Constructor

    ///

    /// Constructor.

    /// \param digraph The digraph that the map belongs to.

    explicit SourceMap(const GR& digraph) : _graph(digraph) {}

    /// \brief Returns the source node of the given arc.

    ///

    /// Returns the source node of the given arc.

    Value operator[](const Key& arc) const {

      return _graph.source(arc);

    }

  private:

    const GR& _graph;

  };

  /// \brief Returns a \c SourceMap class.

  ///

  /// This function just returns an \c SourceMap class.

  /// \relates SourceMap

  template <typename GR>

  inline SourceMap<GR> sourceMap(const GR& graph) {

    return SourceMap<GR>(graph);

  }

  /// \brief Map of the target nodes of arcs in a digraph.

  ///

  /// TargetMap provides access for the target node of each arc in a digraph,

  /// which is returned by the \c target() function of the digraph.

  /// \tparam GR The digraph type.

  /// \see SourceMap

  template <typename GR>

  class TargetMap {

  public:

    /// The key type (the \c Arc type of the digraph).

    typedef typename GR::Arc Key;

    /// The value type (the \c Node type of the digraph).

    typedef typename GR::Node Value;

    /// \brief Constructor

    ///

    /// Constructor.

    /// \param digraph The digraph that the map belongs to.

    explicit TargetMap(const GR& digraph) : _graph(digraph) {}

    /// \brief Returns the target node of the given arc.

    ///

    /// Returns the target node of the given arc.

    Value operator[](const Key& e) const {

      return _graph.target(e);

    }

  private:

    const GR& _graph;

  };

  /// \brief Returns a \c TargetMap class.

  ///

  /// This function just returns a \c TargetMap class.

  /// \relates TargetMap

  template <typename GR>

  inline TargetMap<GR> targetMap(const GR& graph) {

    return TargetMap<GR>(graph);

  }

  /// \brief Map of the "forward" directed arc view of edges in a graph.

  ///

  /// ForwardMap provides access for the "forward" directed arc view of

  /// each edge in a graph, which is returned by the \c direct() function

  /// of the graph with \c true parameter.

  /// \tparam GR The graph type.

  /// \see BackwardMap

  template <typename GR>

  class ForwardMap {

  public:

    /// The key type (the \c Edge type of the digraph).

    typedef typename GR::Edge Key;

    /// The value type (the \c Arc type of the digraph).

    typedef typename GR::Arc Value;

    /// \brief Constructor

    ///

    /// Constructor.

    /// \param graph The graph that the map belongs to.

    explicit ForwardMap(const GR& graph) : _graph(graph) {}

    /// \brief Returns the "forward" directed arc view of the given edge.

    ///

    /// Returns the "forward" directed arc view of the given edge.

    Value operator[](const Key& key) const {

      return _graph.direct(key, true);

    }

  private:

    const GR& _graph;

  };

  /// \brief Returns a \c ForwardMap class.

  ///

  /// This function just returns an \c ForwardMap class.

  /// \relates ForwardMap

  template <typename GR>

  inline ForwardMap<GR> forwardMap(const GR& graph) {

    return ForwardMap<GR>(graph);

  }

  /// \brief Map of the "backward" directed arc view of edges in a graph.

  ///

  /// BackwardMap provides access for the "backward" directed arc view of

  /// each edge in a graph, which is returned by the \c direct() function

  /// of the graph with \c false parameter.

  /// \tparam GR The graph type.

  /// \see ForwardMap

  template <typename GR>

  class BackwardMap {

  public:

    /// The key type (the \c Edge type of the digraph).

    typedef typename GR::Edge Key;

    /// The value type (the \c Arc type of the digraph).

    typedef typename GR::Arc Value;

    /// \brief Constructor

    ///

    /// Constructor.

    /// \param graph The graph that the map belongs to.

    explicit BackwardMap(const GR& graph) : _graph(graph) {}

    /// \brief Returns the "backward" directed arc view of the given edge.

    ///

    /// Returns the "backward" directed arc view of the given edge.

    Value operator[](const Key& key) const {

      return _graph.direct(key, false);

    }

  private:

    const GR& _graph;

  };

  /// \brief Returns a \c BackwardMap class

  /// This function just returns a \c BackwardMap class.

  /// \relates BackwardMap

  template <typename GR>

  inline BackwardMap<GR> backwardMap(const GR& graph) {

    return BackwardMap<GR>(graph);

  }

  /// \brief Map of the in-degrees of nodes in a digraph.

  ///

  /// This map returns the in-degree of a node. Once it is constructed,

  /// the degrees are stored in a standard \c NodeMap, so each query is done

  /// in constant time. On the other hand, the values are updated automatically

  /// whenever the digraph changes.

  ///

  /// \warning Besides \c addNode() and \c addArc(), a digraph structure

  /// may provide alternative ways to modify the digraph.

  /// The correct behavior of InDegMap is not guarantied if these additional

  /// features are used. For example, the functions

  /// \ref ListDigraph::changeSource() "changeSource()",

  /// \ref ListDigraph::changeTarget() "changeTarget()" and

  /// \ref ListDigraph::reverseArc() "reverseArc()"

  /// of \ref ListDigraph will \e not update the degree values correctly.

  ///

  /// \sa OutDegMap

  template <typename GR>

  class InDegMap

    : protected ItemSetTraits<GR, typename GR::Arc>

      ::ItemNotifier::ObserverBase {

  public:

    /// The graph type of InDegMap

    typedef GR Graph;

    typedef GR Digraph;

    /// The key type

    typedef typename Digraph::Node Key;

    /// The value type

    typedef int Value;

    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>

    ::ItemNotifier::ObserverBase Parent;

  private:

    class AutoNodeMap

      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {

    public:

      typedef typename ItemSetTraits<Digraph, Key>::

      template Map<int>::Type Parent;

      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}

      virtual void add(const Key& key) {

        Parent::add(key);

        Parent::set(key, 0);

      }

      virtual void add(const std::vector<Key>& keys) {

        Parent::add(keys);

        for (int i = 0; i < int(keys.size()); ++i) {

          Parent::set(keys[i], 0);

        }

      }

      virtual void build() {

        Parent::build();

        Key it;

        typename Parent::Notifier* nf = Parent::notifier();

        for (nf->first(it); it != INVALID; nf->next(it)) {

          Parent::set(it, 0);

        }

      }

    };

  public:

    /// \brief Constructor.

    ///

    /// Constructor for creating an in-degree map.

    explicit InDegMap(const Digraph& graph)

      : _digraph(graph), _deg(graph) {

      Parent::attach(_digraph.notifier(typename Digraph::Arc()));

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

        _deg[it] = countInArcs(_digraph, it);

      }

    }

    /// \brief Gives back the in-degree of a Node.

    ///

    /// Gives back the in-degree of a Node.

    int operator[](const Key& key) const {

      return _deg[key];

    }

  protected:

    typedef typename Digraph::Arc Arc;

    virtual void add(const Arc& arc) {

      ++_deg[_digraph.target(arc)];

    }

    virtual void add(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        ++_deg[_digraph.target(arcs[i])];

      }

    }

    virtual void erase(const Arc& arc) {

      --_deg[_digraph.target(arc)];

    }

    virtual void erase(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        --_deg[_digraph.target(arcs[i])];

      }

    }

    virtual void build() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

        _deg[it] = countInArcs(_digraph, it);

      }

    }

    virtual void clear() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

        _deg[it] = 0;

      }

    }

  private:

    const Digraph& _digraph;

    AutoNodeMap _deg;

  };

  /// \brief Map of the out-degrees of nodes in a digraph.

  ///

  /// This map returns the out-degree of a node. Once it is constructed,

  /// the degrees are stored in a standard \c NodeMap, so each query is done

  /// in constant time. On the other hand, the values are updated automatically

  /// whenever the digraph changes.

  ///

  /// \warning Besides \c addNode() and \c addArc(), a digraph structure

  /// may provide alternative ways to modify the digraph.

  /// The correct behavior of OutDegMap is not guarantied if these additional

  /// features are used. For example, the functions

  /// \ref ListDigraph::changeSource() "changeSource()",

  /// \ref ListDigraph::changeTarget() "changeTarget()" and

  /// \ref ListDigraph::reverseArc() "reverseArc()"

  /// of \ref ListDigraph will \e not update the degree values correctly.

  ///

  /// \sa InDegMap

  template <typename GR>

  class OutDegMap

    : protected ItemSetTraits<GR, typename GR::Arc>

      ::ItemNotifier::ObserverBase {

  public:

    /// The graph type of OutDegMap

    typedef GR Graph;

    typedef GR Digraph;

    /// The key type

    typedef typename Digraph::Node Key;

    /// The value type

    typedef int Value;

    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>

    ::ItemNotifier::ObserverBase Parent;

  private:

    class AutoNodeMap

      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {

    public:

      typedef typename ItemSetTraits<Digraph, Key>::

      template Map<int>::Type Parent;

      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}

      virtual void add(const Key& key) {

        Parent::add(key);

        Parent::set(key, 0);

      }

      virtual void add(const std::vector<Key>& keys) {

        Parent::add(keys);

        for (int i = 0; i < int(keys.size()); ++i) {

          Parent::set(keys[i], 0);

        }

      }

      virtual void build() {

        Parent::build();

        Key it;

        typename Parent::Notifier* nf = Parent::notifier();

        for (nf->first(it); it != INVALID; nf->next(it)) {

          Parent::set(it, 0);

        }

      }

    };

  public:

    /// \brief Constructor.

    ///

    /// Constructor for creating an out-degree map.

    explicit OutDegMap(const Digraph& graph)

      : _digraph(graph), _deg(graph) {

      Parent::attach(_digraph.notifier(typename Digraph::Arc()));

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

        _deg[it] = countOutArcs(_digraph, it);

      }

    }

    /// \brief Gives back the out-degree of a Node.

    ///

    /// Gives back the out-degree of a Node.

    int operator[](const Key& key) const {

      return _deg[key];

    }

  protected:

    typedef typename Digraph::Arc Arc;

    virtual void add(const Arc& arc) {

      ++_deg[_digraph.source(arc)];

    }

    virtual void add(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        ++_deg[_digraph.source(arcs[i])];

      }

    }

    virtual void erase(const Arc& arc) {

      --_deg[_digraph.source(arc)];

    }

    virtual void erase(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        --_deg[_digraph.source(arcs[i])];

      }

    }

    virtual void build() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

        _deg[it] = countOutArcs(_digraph, it);

      }

    }

    virtual void clear() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

        _deg[it] = 0;

      }

    }

  private:

    const Digraph& _digraph;

    AutoNodeMap _deg;

  };

  /// \brief Potential difference map

  ///

  /// PotentialDifferenceMap returns the difference between the potentials of

  /// the source and target nodes of each arc in a digraph, i.e. it returns

  /// \code

  ///   potential[gr.target(arc)] - potential[gr.source(arc)].

  /// \endcode

  /// \tparam GR The digraph type.

  /// \tparam POT A node map storing the potentials.

  template <typename GR, typename POT>

  class PotentialDifferenceMap {

  public:

    /// Key type

    typedef typename GR::Arc Key;

    /// Value type

    typedef typename POT::Value Value;

    /// \brief Constructor

    ///

    /// Contructor of the map.

    explicit PotentialDifferenceMap(const GR& gr,

                                    const POT& potential)

      : _digraph(gr), _potential(potential) {}

    /// \brief Returns the potential difference for the given arc.

    ///

    /// Returns the potential difference for the given arc, i.e.

    /// \code

    ///   potential[gr.target(arc)] - potential[gr.source(arc)].

    /// \endcode

    Value operator[](const Key& arc) const {

      return _potential[_digraph.target(arc)] -

        _potential[_digraph.source(arc)];

    }

  private:

    const GR& _digraph;

    const POT& _potential;

  };

  /// \brief Returns a PotentialDifferenceMap.

  ///

  /// This function just returns a PotentialDifferenceMap.

  /// \relates PotentialDifferenceMap

  template <typename GR, typename POT>

  PotentialDifferenceMap<GR, POT>

  potentialDifferenceMap(const GR& gr, const POT& potential) {

    return PotentialDifferenceMap<GR, POT>(gr, potential);

  }

    check(map6[A()] == 10 && map7[A()] == 10,

          "Something is wrong with ConstMap");

  }

  // IdentityMap

  {

    checkConcept<ReadMap<A,A>, IdentityMap<A> >();

    IdentityMap<A> map1;

    IdentityMap<A> map2 = map1;

    map1 = identityMap<A>();

    checkConcept<ReadMap<double,double>, IdentityMap<double> >();

    check(identityMap<double>()[1.0] == 1.0 &&

          identityMap<double>()[3.14] == 3.14,

          "Something is wrong with IdentityMap");

  }

  // RangeMap

  {

    checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();

    RangeMap<B> map1;

    RangeMap<B> map2(10);

    RangeMap<B> map3(10,B());

    RangeMap<B> map4 = map1;

    RangeMap<B> map5 = rangeMap<B>();

    RangeMap<B> map6 = rangeMap<B>(10);

    RangeMap<B> map7 = rangeMap(10,B());

    checkConcept< ReferenceMap<int, double, double&, const double&>,

                  RangeMap<double> >();

    std::vector<double> v(10, 0);

    v[5] = 100;

    RangeMap<double> map8(v);

    RangeMap<double> map9 = rangeMap(v);

    check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100,

          "Something is wrong with RangeMap");

  }

  // SparseMap

  {

    checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();

    SparseMap<A,B> map1;

    SparseMap<A,B> map2 = B();

    SparseMap<A,B> map3 = sparseMap<A,B>();

    SparseMap<A,B> map4 = sparseMap<A>(B());

    checkConcept< ReferenceMap<double, int, int&, const int&>,

                  SparseMap<double, int> >();

    std::map<double, int> m;

    SparseMap<double, int> map5(m);

    SparseMap<double, int> map6(m,10);

    SparseMap<double, int> map7 = sparseMap(m);

    SparseMap<double, int> map8 = sparseMap(m,10);

    check(map5[1.0] == 0 && map5[3.14] == 0 &&

          map6[1.0] == 10 && map6[3.14] == 10,

          "Something is wrong with SparseMap");

    map5[1.0] = map6[3.14] = 100;

    check(map5[1.0] == 100 && map5[3.14] == 0 &&

          map6[1.0] == 10 && map6[3.14] == 100,

          "Something is wrong with SparseMap");

  }

  // ComposeMap

  {

    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;

    checkConcept<ReadMap<B,double>, CompMap>();

    CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());

    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());

    SparseMap<double, bool> m1(false); m1[3.14] = true;

    RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14;

    check(!composeMap(m1,m2)[0] && composeMap(m1,m2)[1],

          "Something is wrong with ComposeMap")

  }

  // CombineMap

  {

    typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;

    checkConcept<ReadMap<A,double>, CombMap>();

    CombMap map1 = CombMap(DoubleMap(), DoubleMap());

    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());

    check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,

          "Something is wrong with CombineMap");

  }