Index: test/graph_test.h
===================================================================
--- test/graph_test.h	(revision 463)
+++ test/graph_test.h	(revision 1187)
@@ -42,4 +42,28 @@
 
   template<class Graph>
+  void checkGraphRedNodeList(const Graph &G, int cnt)
+  {
+    typename Graph::RedIt n(G);
+    for(int i=0;i<cnt;i++) {
+      check(n!=INVALID,"Wrong red Node list linking.");
+      ++n;
+    }
+    check(n==INVALID,"Wrong red Node list linking.");
+    check(countRedNodes(G)==cnt,"Wrong red Node number.");
+  }
+
+  template<class Graph>
+  void checkGraphBlueNodeList(const Graph &G, int cnt)
+  {
+    typename Graph::BlueIt n(G);
+    for(int i=0;i<cnt;i++) {
+      check(n!=INVALID,"Wrong blue Node list linking.");
+      ++n;
+    }
+    check(n==INVALID,"Wrong blue Node list linking.");
+    check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
+  }
+
+  template<class Graph>
   void checkGraphArcList(const Graph &G, int cnt)
   {
@@ -167,4 +191,5 @@
   template <typename Graph>
   void checkNodeIds(const Graph& G) {
+    typedef typename Graph::Node Node;
     std::set<int> values;
     for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
@@ -174,8 +199,38 @@
       values.insert(G.id(n));
     }
+    check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id");
+  }
+
+  template <typename Graph>
+  void checkRedNodeIds(const Graph& G) {
+    typedef typename Graph::RedNode RedNode;
+    std::set<int> values;
+    for (typename Graph::RedIt n(G); n != INVALID; ++n) {
+      check(G.red(n), "Wrong partition");
+      check(G.redId(n) == G.id(RedNode(n)), "Wrong id");
+      check(values.find(G.redId(n)) == values.end(), "Wrong id");
+      check(G.redId(n) <= G.maxRedId(), "Wrong maximum id");
+      values.insert(G.id(n));
+    }
+    check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id");
+  }
+
+  template <typename Graph>
+  void checkBlueNodeIds(const Graph& G) {
+    typedef typename Graph::BlueNode BlueNode;
+    std::set<int> values;
+    for (typename Graph::BlueIt n(G); n != INVALID; ++n) {
+      check(G.blue(n), "Wrong partition");
+      check(G.blueId(n) == G.id(BlueNode(n)), "Wrong id");
+      check(values.find(G.blueId(n)) == values.end(), "Wrong id");
+      check(G.blueId(n) <= G.maxBlueId(), "Wrong maximum id");
+      values.insert(G.id(n));
+    }
+    check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id");
   }
 
   template <typename Graph>
   void checkArcIds(const Graph& G) {
+    typedef typename Graph::Arc Arc;
     std::set<int> values;
     for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
@@ -185,8 +240,10 @@
       values.insert(G.id(a));
     }
+    check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id");
   }
 
   template <typename Graph>
   void checkEdgeIds(const Graph& G) {
+    typedef typename Graph::Edge Edge;
     std::set<int> values;
     for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
@@ -196,4 +253,5 @@
       values.insert(G.id(e));
     }
+    check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id");
   }
 
@@ -229,4 +287,64 @@
 
   template <typename Graph>
+  void checkGraphRedMap(const Graph& G) {
+    typedef typename Graph::Node Node;
+    typedef typename Graph::RedIt RedIt;
+
+    typedef typename Graph::template RedMap<int> IntRedMap;
+    IntRedMap map(G, 42);
+    for (RedIt it(G); it != INVALID; ++it) {
+      check(map[it] == 42, "Wrong map constructor.");
+    }
+    int s = 0;
+    for (RedIt it(G); it != INVALID; ++it) {
+      map[it] = 0;
+      check(map[it] == 0, "Wrong operator[].");
+      map.set(it, s);
+      check(map[it] == s, "Wrong set.");
+      ++s;
+    }
+    s = s * (s - 1) / 2;
+    for (RedIt it(G); it != INVALID; ++it) {
+      s -= map[it];
+    }
+    check(s == 0, "Wrong sum.");
+
+    // map = constMap<Node>(12);
+    // for (NodeIt it(G); it != INVALID; ++it) {
+    //   check(map[it] == 12, "Wrong operator[].");
+    // }
+  }
+
+  template <typename Graph>
+  void checkGraphBlueMap(const Graph& G) {
+    typedef typename Graph::Node Node;
+    typedef typename Graph::BlueIt BlueIt;
+
+    typedef typename Graph::template BlueMap<int> IntBlueMap;
+    IntBlueMap map(G, 42);
+    for (BlueIt it(G); it != INVALID; ++it) {
+      check(map[it] == 42, "Wrong map constructor.");
+    }
+    int s = 0;
+    for (BlueIt it(G); it != INVALID; ++it) {
+      map[it] = 0;
+      check(map[it] == 0, "Wrong operator[].");
+      map.set(it, s);
+      check(map[it] == s, "Wrong set.");
+      ++s;
+    }
+    s = s * (s - 1) / 2;
+    for (BlueIt it(G); it != INVALID; ++it) {
+      s -= map[it];
+    }
+    check(s == 0, "Wrong sum.");
+
+    // map = constMap<Node>(12);
+    // for (NodeIt it(G); it != INVALID; ++it) {
+    //   check(map[it] == 12, "Wrong operator[].");
+    // }
+  }
+
+  template <typename Graph>
   void checkGraphArcMap(const Graph& G) {
     typedef typename Graph::Arc Arc;
