Changeset 726:3fc2a801c39e in lemon-main

Timestamp:

09/26/09 07:08:10 (15 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

725:11404088d1a5 (diff), 719:ba79e8d64448 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge #302

Files:

• lemon/maps.h (modified) (31 diffs)
• lemon/maps.h (modified) (1 diff)
• test/maps_test.cc (modified) (5 diffs)
• test/maps_test.cc (modified) (1 diff)

lemon/maps.h

@@ -57 +57 @@
   /// but data written to it is not required (i.e. it will be sent to
   /// <tt>/dev/null</tt>).
-  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   ///
   /// \sa ConstMap
@@ -90 +90 @@
   ///
   /// In other aspects it is equivalent to \c NullMap.
-  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
+  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
   /// concept, but it absorbs the data written to it.
   ///
@@ -159 +159 @@
   ///
   /// In other aspects it is equivalent to \c NullMap.
-  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
+  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
   /// concept, but it absorbs the data written to it.
   ///
@@ -233 +233 @@
   /// It can be used with some data structures, for example
   /// \c UnionFind, \c BinHeap, when the used items are small
-  /// integers. This map conforms the \ref concepts::ReferenceMap
+  /// integers. This map conforms to the \ref concepts::ReferenceMap
   /// "ReferenceMap" concept.
   ///
@@ -341 +341 @@
   /// stored actually. This value can be different from the default
   /// contructed value (i.e. \c %Value()).
-  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
+  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
   /// concept.
   ///
@@ -707 +707 @@
   /// The \c Key type of it is inherited from \c M and the \c Value
   /// type is \c V.
-  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
+  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
   ///
   /// The simplest way of using this map is through the convertMap()
@@ -1826 +1826 @@
   /// the items stored in the graph, which is returned by the \c id()
   /// function of the graph. This map can be inverted with its member
-  /// class \c InverseMap or with the \c operator() member.
+  /// class \c InverseMap or with the \c operator()() member.
   ///
   /// \tparam GR The graph type.
@@ -1866 +1866 @@
   public:
 
-    /// \brief This class represents the inverse of its owner (IdMap).
-    ///
-    /// This class represents the inverse of its owner (IdMap).
+    /// \brief The inverse map type of IdMap.
+    ///
+    /// The inverse map type of IdMap. The subscript operator gives back
+    /// an item by its id.
+    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
     /// \see inverse()
     class InverseMap {
@@ -1883 +1885 @@
       explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
 
-      /// \brief Gives back the given item from its id.
+      /// \brief Gives back an item by its id.
       ///
-      /// Gives back the given item from its id.
+      /// Gives back an item by its id.
       Item operator[](int id) const { return _graph->fromId(id, Item());}
 
@@ -1898 +1900 @@
   };
 
+  /// \brief Returns an \c IdMap class.
+  ///
+  /// This function just returns an \c IdMap class.
+  /// \relates IdMap
+  template <typename K, typename GR>
+  inline IdMap<GR, K> idMap(const GR& graph) {
+    return IdMap<GR, K>(graph);
+  }
 
   /// \brief General cross reference graph map type.
@@ -1904 +1914 @@
   /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
   /// and if a key is set to a new value, then stores it in the inverse map.
-  /// The values of the map can be accessed
-  /// with stl compatible forward iterator.
+  /// The graph items can be accessed by their values either using
+  /// \c InverseMap or \c operator()(), and the values of the map can be
+  /// accessed with an STL compatible forward iterator (\c ValueIt).
+  /// 
+  /// This map is intended to be used when all associated values are
+  /// different (the map is actually invertable) or there are only a few
+  /// items with the same value.
+  /// Otherwise consider to use \c IterableValueMap, which is more 
+  /// suitable and more efficient for such cases. It provides iterators
+  /// to traverse the items with the same associated value, however
+  /// it does not have \c InverseMap.
   ///
   /// This type is not reference map, so it cannot be modified with
@@ -1946 +1965 @@
     /// \brief Forward iterator for values.
     ///
-    /// This iterator is an stl compatible forward
+    /// 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.
     /// They are considered with multiplicity, so each value is
     /// traversed for each item it is assigned to.
-    class ValueIterator
+    class ValueIt
       : public std::iterator<std::forward_iterator_tag, Value> {
       friend class CrossRefMap;
     private:
-      ValueIterator(typename Container::const_iterator _it)
+      ValueIt(typename Container::const_iterator _it)
         : it(_it) {}
     public:
 
-      ValueIterator() {}
-
-      ValueIterator& operator++() { ++it; return *this; }
-      ValueIterator operator++(int) {
-        ValueIterator tmp(*this);
+      /// 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); }
 
-      bool operator==(ValueIterator jt) const { return it == jt.it; }
-      bool operator!=(ValueIterator jt) const { return it != jt.it; }
+      /// \e
+      bool operator==(ValueIt jt) const { return it == jt.it; }
+      /// \e
+      bool operator!=(ValueIt jt) const { return it != jt.it; }
 
     private:
       typename Container::const_iterator it;
     };
+    
+    /// Alias for \c ValueIt
+    typedef ValueIt ValueIterator;
 
     /// \brief Returns an iterator to the first value.
     ///
-    /// Returns an stl compatible iterator to the
+    /// 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.
-    ValueIterator beginValue() const {
-      return ValueIterator(_inv_map.begin());
+    ValueIt beginValue() const {
+      return ValueIt(_inv_map.begin());
     }
 
     /// \brief Returns an iterator after the last value.
     ///
-    /// Returns an stl compatible iterator after the
+    /// 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.
-    ValueIterator endValue() const {
-      return ValueIterator(_inv_map.end());
+    ValueIt endValue() const {
+      return ValueIt(_inv_map.end());
     }
 
@@ -2032 +2061 @@
       typename Container::const_iterator it = _inv_map.find(val);
       return it != _inv_map.end() ? it->second : INVALID;
+    }
+    
+    /// \brief Returns the number of items with the given value.
+    ///
+    /// This function returns the number of items with the given value
+    /// associated with it.
+    int count(const Value &val) const {
+      return _inv_map.count(val);
     }
 
@@ -2083 +2120 @@
   public:
 
-    /// \brief The inverse map type.
-    ///
-    /// The inverse of this map. The subscript operator of the map
-    /// gives back the item that was last assigned to the value.
+    /// \brief The inverse map type of CrossRefMap.
+    ///
+    /// The inverse map type of CrossRefMap. The subscript operator gives
+    /// back an item by its value.
+    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
+    /// \see inverse()
     class InverseMap {
     public:
@@ -2113 +2152 @@
     };
 
-    /// \brief It gives back the read-only inverse map.
-    ///
-    /// It gives back the read-only inverse map.
+    /// \brief Gives back the inverse of the map.
+    ///
+    /// Gives back the inverse of the CrossRefMap.
     InverseMap inverse() const {
       return InverseMap(*this);
@@ -2122 +2161 @@
   };
 
-  /// \brief Provides continuous and unique ID for the
+  /// \brief Provides continuous and unique id for the
   /// items of a graph.
   ///
   /// RangeIdMap provides a unique and continuous
-  /// ID for each item of a given type (\c Node, \c Arc or
+  /// id for each item of a given type (\c Node, \c Arc or
   /// \c Edge) in a graph. This id is
   ///  - \b unique: different items get different ids,
@@ -2137 +2176 @@
   /// the \c id() function of the graph or \ref IdMap.
   /// This map can be inverted with its member class \c InverseMap,
-  /// or with the \c operator() member.
+  /// or with the \c operator()() member.
   ///
   /// \tparam GR The graph type.
@@ -2265 +2304 @@
     }
 
-    /// \brief Gives back the \e RangeId of the item
-    ///
-    /// Gives back the \e RangeId of the item.
+    /// \brief Gives back the \e range \e id of the item
+    ///
+    /// Gives back the \e range \e id of the item.
     int operator[](const Item& item) const {
       return Map::operator[](item);
     }
 
-    /// \brief Gives back the item belonging to a \e RangeId
-    ///
-    /// Gives back the item belonging to a \e RangeId.
+    /// \brief Gives back the item belonging to a \e range \e id
+    ///
+    /// Gives back the item belonging to the given \e range \e id.
     Item operator()(int id) const {
       return _inv_map[id];
@@ -2288 +2327 @@
     /// \brief The inverse map type of RangeIdMap.
     ///
-    /// The inverse map type of RangeIdMap.
+    /// The inverse map type of RangeIdMap. The subscript operator gives
+    /// back an item by its \e range \e id.
+    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
     class InverseMap {
     public:
@@ -2306 +2347 @@
       ///
       /// Subscript operator. It gives back the item
-      /// that the descriptor currently belongs to.
+      /// that the given \e range \e id currently belongs to.
       Value operator[](const Key& key) const {
         return _inverted(key);
@@ -2324 +2365 @@
     /// \brief Gives back the inverse of the map.
     ///
-    /// Gives back the inverse of the map.
+    /// Gives back the inverse of the RangeIdMap.
     const InverseMap inverse() const {
       return InverseMap(*this);
@@ -2330 +2371 @@
   };
 
+  /// \brief Returns a \c RangeIdMap class.
+  ///
+  /// This function just returns an \c RangeIdMap class.
+  /// \relates RangeIdMap
+  template <typename K, typename GR>
+  inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
+    return RangeIdMap<GR, K>(graph);
+  }
+  
   /// \brief Dynamic iterable \c bool map.
   ///
@@ -2335 +2385 @@
   /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
   /// For both \c true and \c false values it is possible to iterate on
-  /// the keys.
+  /// the keys mapped to the value.
   ///
   /// This type is a reference map, so it can be modified with the
@@ -2704 +2754 @@
   /// 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.
@@ -2985 +3040 @@
   /// \brief Dynamic iterable map for comparable values.
   ///
-  /// This class provides a special graph map type which can store an
+  /// 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.
-  ///
-  /// The map stores for each value a linked list with
-  /// the items which mapped to the value, and the values are stored
-  /// in balanced binary tree. The values of the map can be accessed
-  /// with stl compatible forward iterator.
+  /// 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
@@ -3072 +3129 @@
     /// \brief Forward iterator for values.
     ///
-    /// This iterator is an stl compatible forward
+    /// 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 ValueIterator
+    class ValueIt
       : public std::iterator<std::forward_iterator_tag, Value> {
       friend class IterableValueMap;
     private:
-      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
+      ValueIt(typename std::map<Value, Key>::const_iterator _it)
         : it(_it) {}
     public:
 
-      ValueIterator() {}
-
-      ValueIterator& operator++() { ++it; return *this; }
-      ValueIterator operator++(int) {
-        ValueIterator tmp(*this);
+      /// 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); }
 
-      bool operator==(ValueIterator jt) const { return it == jt.it; }
-      bool operator!=(ValueIterator jt) const { return it != jt.it; }
+      /// \e
+      bool operator==(ValueIt jt) const { return it == jt.it; }
+      /// \e
+      bool operator!=(ValueIt jt) const { return it != jt.it; }
 
     private:
@@ -3104 +3168 @@
     /// \brief Returns an iterator to the first value.
     ///
-    /// Returns an stl compatible iterator to the
+    /// 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.
-    ValueIterator beginValue() const {
-      return ValueIterator(_first.begin());
+    ValueIt beginValue() const {
+      return ValueIt(_first.begin());
     }
 
     /// \brief Returns an iterator after the last value.
     ///
-    /// Returns an stl compatible iterator after the
+    /// 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.
-    ValueIterator endValue() const {
-      return ValueIterator(_first.end());
+    ValueIt endValue() const {
+      return ValueIt(_first.end());
     }
 
@@ -3237 +3301 @@
   public:
 
-    ///\e
+    /// The key type (the \c Arc type of the digraph).
     typedef typename GR::Arc Key;
-    ///\e
+    /// The value type (the \c Node type of the digraph).
     typedef typename GR::Node Value;
 
@@ -3278 +3342 @@
   public:
 
-    ///\e
+    /// The key type (the \c Arc type of the digraph).
     typedef typename GR::Arc Key;
-    ///\e
+    /// The value type (the \c Node type of the digraph).
     typedef typename GR::Node Value;
 
@@ -3320 +3384 @@
   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;
-    typedef typename GR::Edge Key;
 
     /// \brief Constructor
@@ -3360 +3426 @@
   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;
-    typedef typename GR::Edge Key;
 
     /// \brief Constructor

lemon/maps.h

@@ -1790 +1790 @@
   /// \code
   ///   std::vector<Node> v;
-  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
+  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
   /// \endcode
   /// \code
   ///   std::vector<Node> v(countNodes(g));
-  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
+  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
   /// \endcode
   ///

test/maps_test.cc

@@ -23 +23 @@
 #include <lemon/concepts/maps.h>
 #include <lemon/maps.h>
+#include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
+#include <lemon/adaptors.h>
+#include <lemon/dfs.h>
 
 #include "test_tools.h"
@@ -61 +64 @@
 typedef ReadWriteMap<A, bool> BoolWriteMap;
 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
+
+template<typename Map1, typename Map2, typename ItemIt>
+void compareMap(const Map1& map1, const Map2& map2, ItemIt it) {
+  for (; it != INVALID; ++it)
+    check(map1[it] == map2[it], "The maps are not equal");
+}
 
 int main()
@@ -330 +339 @@
   {
     typedef std::vector<int> vec;
+    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
+    checkConcept<WriteMap<int, bool>,
+                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
+
     vec v1;
     vec v2(10);
@@ -349 +362 @@
           it != map2.end(); ++it )
       check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
+    
+    typedef ListDigraph Graph;
+    DIGRAPH_TYPEDEFS(Graph);
+    Graph gr;
+
+    Node n0 = gr.addNode();
+    Node n1 = gr.addNode();
+    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");
+    }
+    
+    compareMap(sourceMap(orienter(gr, constMap<Edge, bool>(true))),
+               targetMap(orienter(gr, constMap<Edge, bool>(false))),
+               EdgeIt(gr));
+
+    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");
   }
 
@@ -547 +776 @@
     }
 
-    for (Ivm::ValueIterator vit = map1.beginValue();
+    for (Ivm::ValueIt vit = map1.beginValue();
          vit != map1.endValue(); ++vit) {
       check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
-            "Wrong ValueIterator");
+            "Wrong ValueIt");
     }
 

test/maps_test.cc

@@ -580 +580 @@
   }
 
+  // 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
   {