RhodeCode

        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);

    Node n2 = gr.addNode();

    Node n3 = gr.addNode();

    gr.addArc(n3, n0);

    gr.addArc(n3, n2);

    gr.addArc(n0, n2);

    gr.addArc(n2, n1);

    gr.addArc(n0, n1);

    {

      std::vector<Node> v;

      dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run();

      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,

            "Something is wrong with LoggerBoolMap");

    }

    {

      std::vector<Node> v(countNodes(gr));

      dfs(gr).processedMap(loggerBoolMap(v.begin())).run();

      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,

            "Something is wrong with LoggerBoolMap");

    }

  }

  // IdMap, RangeIdMap

  {

    typedef ListDigraph Graph;

    DIGRAPH_TYPEDEFS(Graph);

    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();

    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();

    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();

    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();

    Graph gr;

    IdMap<Graph, Node> nmap(gr);

    IdMap<Graph, Arc> amap(gr);

    RangeIdMap<Graph, Node> nrmap(gr);

    RangeIdMap<Graph, Arc> armap(gr);

    Node n0 = gr.addNode();

    Node n1 = gr.addNode();

    Node n2 = gr.addNode();

    Arc a0 = gr.addArc(n0, n1);

    Arc a1 = gr.addArc(n0, n2);

    Arc a2 = gr.addArc(n2, n1);

    Arc a3 = gr.addArc(n2, n0);

    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");

    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");

    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");

    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");

    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");

    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");

    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");

    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");

    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");

    check(nrmap.size() == 3 && armap.size() == 4,

          "Wrong RangeIdMap::size()");

    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");

    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");

    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");

    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");

    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");

    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");

    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");

    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");

    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");

    gr.erase(n1);

    if (nrmap[n0] == 1) nrmap.swap(n0, n2);

    nrmap.swap(n2, n0);

    if (armap[a1] == 1) armap.swap(a1, a3);

    armap.swap(a3, a1);

    check(nrmap.size() == 2 && armap.size() == 2,

          "Wrong RangeIdMap::size()");

    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");

    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");

    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");

    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");

    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");

    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");

  }

  // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap

  {

    typedef ListGraph Graph;

    GRAPH_TYPEDEFS(Graph);

    checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();

    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();

    checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();

    checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();

    checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();

    checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();

    Graph gr;

    Node n0 = gr.addNode();

    Node n1 = gr.addNode();

    Node n2 = gr.addNode();

    gr.addEdge(n0,n1);

    gr.addEdge(n1,n2);

    gr.addEdge(n0,n2);

    gr.addEdge(n2,n1);

    gr.addEdge(n1,n2);

    gr.addEdge(n0,n1);

    for (EdgeIt e(gr); e != INVALID; ++e) {

      check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");

      check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");

    }

    check(mapCompare(gr,

          sourceMap(orienter(gr, constMap<Edge, bool>(true))),

          targetMap(orienter(gr, constMap<Edge, bool>(false)))),

          "Wrong SourceMap or TargetMap");

    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;

    Digraph dgr(gr, constMap<Edge, bool>(true));

    OutDegMap<Digraph> odm(dgr);

    InDegMap<Digraph> idm(dgr);

    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");

    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");

    gr.addEdge(n2, n0);

    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");

    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");

  }

  // CrossRefMap

  {

    typedef ListDigraph Graph;

    DIGRAPH_TYPEDEFS(Graph);

    checkConcept<ReadWriteMap<Node, int>,

                 CrossRefMap<Graph, Node, int> >();

    checkConcept<ReadWriteMap<Node, bool>,

                 CrossRefMap<Graph, Node, bool> >();

    checkConcept<ReadWriteMap<Node, double>,

                 CrossRefMap<Graph, Node, double> >();

    Graph gr;

    typedef CrossRefMap<Graph, Node, char> CRMap;

    CRMap map(gr);

    Node n0 = gr.addNode();

    Node n1 = gr.addNode();

    Node n2 = gr.addNode();

    map.set(n0, 'A');

    map.set(n1, 'B');

    map.set(n2, 'C');

    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,

          "Wrong CrossRefMap");

    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,

          "Wrong CrossRefMap");

    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,

          "Wrong CrossRefMap");

    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,

          "Wrong CrossRefMap::count()");

    CRMap::ValueIt it = map.beginValue();

    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&

          it == map.endValue(), "Wrong value iterator");

    map.set(n2, 'A');

    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',

          "Wrong CrossRefMap");

    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");

    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");

    check(map('C') == INVALID && map.inverse()['C'] == INVALID,

          "Wrong CrossRefMap");

    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,

          "Wrong CrossRefMap::count()");

    it = map.beginValue();

    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&

          it == map.endValue(), "Wrong value iterator");

    map.set(n0, 'C');

    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',

          "Wrong CrossRefMap");

    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");

    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");

    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");

    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,

          "Wrong CrossRefMap::count()");

    it = map.beginValue();

    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&

          it == map.endValue(), "Wrong value iterator");

  }

  // CrossRefMap

  {

    typedef SmartDigraph Graph;

    DIGRAPH_TYPEDEFS(Graph);

    checkConcept<ReadWriteMap<Node, int>,

                 CrossRefMap<Graph, Node, int> >();

    Graph gr;

    typedef CrossRefMap<Graph, Node, char> CRMap;

    typedef CRMap::ValueIterator ValueIt;

    CRMap map(gr);

    Node n0 = gr.addNode();

    Node n1 = gr.addNode();

    Node n2 = gr.addNode();

    map.set(n0, 'A');

    map.set(n1, 'B');

    map.set(n2, 'C');

    map.set(n2, 'A');

    map.set(n0, 'C');

    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',

          "Wrong CrossRefMap");

    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");

    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");

    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");

    ValueIt it = map.beginValue();

    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&

          it == map.endValue(), "Wrong value iterator");

  }

  // Iterable bool map

  {

    typedef SmartGraph Graph;

    typedef SmartGraph::Node Item;

    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;

    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();

    const int num = 10;

    Graph g;

    std::vector<Item> items;

    for (int i = 0; i < num; ++i) {

      items.push_back(g.addNode());

    }

    Ibm map1(g, true);

    int n = 0;

    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {

      check(map1[static_cast<Item>(it)], "Wrong TrueIt");

      ++n;

    }

    check(n == num, "Wrong number");

    n = 0;

    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {

        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");

        ++n;

    }

    check(n == num, "Wrong number");

    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");

    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");

    map1[items[5]] = true;

    n = 0;

    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {

        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");

        ++n;

    }

    check(n == num, "Wrong number");

    map1[items[num / 2]] = false;

    check(map1[items[num / 2]] == false, "Wrong map value");

    n = 0;

    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {

        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");

        ++n;

    }

    check(n == num - 1, "Wrong number");

    n = 0;

    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {

        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");

        ++n;

    }

    check(n == 1, "Wrong number");

    map1[items[0]] = false;

    check(map1[items[0]] == false, "Wrong map value");

    map1[items[num - 1]] = false;

    check(map1[items[num - 1]] == false, "Wrong map value");

    n = 0;

    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {

        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");

        ++n;

    }

    check(n == num - 3, "Wrong number");

    check(map1.trueNum() == num - 3, "Wrong number");

    n = 0;

    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {

        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");

        ++n;

    }

    check(n == 3, "Wrong number");

    check(map1.falseNum() == 3, "Wrong number");

  }

  // Iterable int map

  {

    typedef SmartGraph Graph;

    typedef SmartGraph::Node Item;

    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;

    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();

    const int num = 10;

    Graph g;

    std::vector<Item> items;

    for (int i = 0; i < num; ++i) {

      items.push_back(g.addNode());

    }

    Iim map1(g);

    check(map1.size() == 0, "Wrong size");

    for (int i = 0; i < num; ++i) {

      map1[items[i]] = i;

    }

    check(map1.size() == num, "Wrong size");

    for (int i = 0; i < num; ++i) {

      Iim::ItemIt it(map1, i);

      check(static_cast<Item>(it) == items[i], "Wrong value");

      ++it;

      check(static_cast<Item>(it) == INVALID, "Wrong value");

    }

    for (int i = 0; i < num; ++i) {

      map1[items[i]] = i % 2;

    }

    check(map1.size() == 2, "Wrong size");

    int n = 0;

    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {

      check(map1[static_cast<Item>(it)] == 0, "Wrong value");

      ++n;

    }

    check(n == (num + 1) / 2, "Wrong number");

    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {

      check(map1[static_cast<Item>(it)] == 1, "Wrong value");

      ++n;

    }

    check(n == num, "Wrong number");

  }

  // Iterable value map

  {

    typedef SmartGraph Graph;

    typedef SmartGraph::Node Item;

    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;

    checkConcept<ReadWriteMap<Item, double>, Ivm>();

    const int num = 10;

    Graph g;

    std::vector<Item> items;

    for (int i = 0; i < num; ++i) {

      items.push_back(g.addNode());

    }

    Ivm map1(g, 0.0);

    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");

    check(*map1.beginValue() == 0.0, "Wrong value");

    for (int i = 0; i < num; ++i) {

      map1.set(items[i], static_cast<double>(i));

    }

    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");

    for (int i = 0; i < num; ++i) {

      Ivm::ItemIt it(map1, static_cast<double>(i));

      check(static_cast<Item>(it) == items[i], "Wrong value");

      ++it;

      check(static_cast<Item>(it) == INVALID, "Wrong value");

    }

    for (Ivm::ValueIt vit = map1.beginValue();

         vit != map1.endValue(); ++vit) {

      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,

            "Wrong ValueIt");

    }

    for (int i = 0; i < num; ++i) {

      map1.set(items[i], static_cast<double>(i % 2));

    }

    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");

    int n = 0;

    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {

      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");

      ++n;

    }

    check(n == (num + 1) / 2, "Wrong number");

    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {

      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");

      ++n;

    }

    check(n == num, "Wrong number");

  }

  // Graph map utilities:

  // mapMin(), mapMax(), mapMinValue(), mapMaxValue()

  // mapFind(), mapFindIf(), mapCount(), mapCountIf()

  // mapCopy(), mapCompare(), mapFill()

  {

    DIGRAPH_TYPEDEFS(SmartDigraph);

    SmartDigraph g;

    Node n1 = g.addNode();

    Node n2 = g.addNode();

    Node n3 = g.addNode();

    SmartDigraph::NodeMap<int> map1(g);

    SmartDigraph::ArcMap<char> map2(g);

    ConstMap<Node, A> cmap1 = A();

    ConstMap<Arc, C> cmap2 = C(0);

    map1[n1] = 10;

    map1[n2] = 5;

    map1[n3] = 12;

    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()

    check(mapMin(g, map1) == n2, "Wrong mapMin()");

    check(mapMax(g, map1) == n3, "Wrong mapMax()");

    check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");

    check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");

    check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");

    check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");

    check(mapMin(g, map2) == INVALID, "Wrong mapMin()");

    check(mapMax(g, map2) == INVALID, "Wrong mapMax()");

    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");

    check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");

    Arc a1 = g.addArc(n1, n2);

    Arc a2 = g.addArc(n1, n3);

    Arc a3 = g.addArc(n2, n3);

    Arc a4 = g.addArc(n3, n1);

    map2[a1] = 'b';

    map2[a2] = 'a';

    map2[a3] = 'b';

    map2[a4] = 'c';

    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()

    check(mapMin(g, map2) == a2, "Wrong mapMin()");

    check(mapMax(g, map2) == a4, "Wrong mapMax()");

    check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");

    check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");

    check(mapMinValue(g, map2, std::greater<int>()) == 'c',

          "Wrong mapMinValue()");

    check(mapMaxValue(g, map2, std::greater<int>()) == 'a',

          "Wrong mapMaxValue()");

    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");

    check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");

    check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");

    check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,

          "Wrong mapMin()");

    check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,

          "Wrong mapMax()");

    check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),

          "Wrong mapMinValue()");

    check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),

          "Wrong mapMaxValue()");

    // mapFind(), mapFindIf()

    check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");

    check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");

    check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");

    check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");

    check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");

    check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");

    check(mapFindIf(g, map1, Less<int>(7)) == n2,

          "Wrong mapFindIf()");

    check(mapFindIf(g, map1, Less<int>(5)) == INVALID,

          "Wrong mapFindIf()");

    check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),

          "Wrong mapFindIf()");

    check(mapFindIf(g, map2, Less<char>('a')) == INVALID,

          "Wrong mapFindIf()");

    // mapCount(), mapCountIf()

    check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");

    check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");

    check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");

    check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");

    check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");

    check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");

    check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");

    check(mapCountIf(g, map1, Less<int>(11)) == 2,

          "Wrong mapCountIf()");

    check(mapCountIf(g, map1, Less<int>(13)) == 3,

          "Wrong mapCountIf()");

    check(mapCountIf(g, map1, Less<int>(5)) == 0,

          "Wrong mapCountIf()");

    check(mapCountIf(g, map2, Less<char>('d')) == 4,

          "Wrong mapCountIf()");

    check(mapCountIf(g, map2, Less<char>('c')) == 3,

          "Wrong mapCountIf()");

    check(mapCountIf(g, map2, Less<char>('a')) == 0,

          "Wrong mapCountIf()");

    // MapIt, ConstMapIt

/*

These tests can be used after applying bugfix #330

    typedef SmartDigraph::NodeMap<int>::MapIt MapIt;

    typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;

    check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,

          "Wrong NodeMap<>::MapIt");

    check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,

          "Wrong NodeMap<>::MapIt");

    int sum = 0;

    std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));

    check(sum == 27, "Wrong NodeMap<>::MapIt");

    std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));

    check(sum == 54, "Wrong NodeMap<>::ConstMapIt");

*/

    // mapCopy(), mapCompare(), mapFill()

    check(mapCompare(g, map1, map1), "Wrong mapCompare()");

    check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");

    check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");

    check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");

    check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");

    SmartDigraph::NodeMap<int> map3(g, 0);

    SmartDigraph::ArcMap<char> map4(g, 'a');

    check(!mapCompare(g, map1, map3), "Wrong mapCompare()");

    check(!mapCompare(g, map2, map4), "Wrong mapCompare()");

    mapCopy(g, map1, map3);

    mapCopy(g, map2, map4);

    check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");

    check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");

    Undirector<SmartDigraph> ug(g);

    Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');

    Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);

    check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");

    check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");

    check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");

    check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");

    mapCopy(g, map2, umap1);

    check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");

    check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");

    check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");

    check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");

    mapCopy(g, map2, umap1);

    mapCopy(g, umap1, map2);