Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h	(revision 1020)
+++ lemon/bits/graph_extender.h	(revision 1025)
@@ -761,4 +761,6 @@
 
     typedef typename Parent::Node Node;
+    typedef typename Parent::RedNode RedNode;
+    typedef typename Parent::BlueNode BlueNode;
     typedef typename Parent::Arc Arc;
     typedef typename Parent::Edge Edge;
@@ -766,47 +768,7 @@
     // BpGraph extension
 
-    class RedNode : public Node {
-    public:
-      RedNode() {}
-      RedNode(const RedNode& node) : Node(node) {}
-      RedNode(Invalid) : Node(INVALID){}
-      RedNode(const Node& node) : Node(node) {}
-    };
-    class BlueNode : public Node {
-    public:
-      BlueNode() {}
-      BlueNode(const BlueNode& node) : Node(node) {}
-      BlueNode(Invalid) : Node(INVALID){}
-      BlueNode(const Node& node) : Node(node) {}
-    };
-
     using Parent::first;
     using Parent::next;
-
-    void first(RedNode& node) const {
-      Parent::firstRed(node);
-    }
-    
-    void next(RedNode& node) const {
-      Parent::nextRed(node);
-    }
-
-    void first(BlueNode& node) const {
-      Parent::firstBlue(node);
-    }
-
-    void next(BlueNode& node) const {
-      Parent::nextBlue(node);
-    }
-
     using Parent::id;
-
-    int id(const RedNode& node) const {
-      return Parent::redId(node);
-    }
-
-    int id(const BlueNode& node) const {
-      return Parent::blueId(node);
-    }
 
     int maxId(Node) const {
@@ -863,4 +825,30 @@
     }
 
+    RedNode asRedNode(const Node& node) const {
+      if (node == INVALID || Parent::blue(node)) {
+        return INVALID;
+      } else {
+        return Parent::asRedNodeUnsafe(node);
+      }
+    }
+
+    BlueNode asBlueNode(const Node& node) const {
+      if (node == INVALID || Parent::red(node)) {
+        return INVALID;
+      } else {
+        return Parent::asBlueNodeUnsafe(node);
+      }
+    }
+
+    std::pair<RedNode, BlueNode> asRedBlueNode(const Node& node) const {
+      if (node == INVALID) {
+        return std::make_pair(RedNode(INVALID), BlueNode(INVALID));
+      } else if (Parent::red(node)) {
+        return std::make_pair(Parent::asRedNodeUnsafe(node), BlueNode(INVALID));
+      } else {
+        return std::make_pair(RedNode(INVALID), Parent::asBlueNodeUnsafe(node));
+      }
+    }
+
     // Alterable extension
 
@@ -926,5 +914,5 @@
     };
 
-    class RedIt : public Node {
+    class RedIt : public RedNode {
       const BpGraph* _graph;
     public:
@@ -932,23 +920,21 @@
       RedIt() {}
 
-      RedIt(Invalid i) : Node(i) { }
+      RedIt(Invalid i) : RedNode(i) { }
 
       explicit RedIt(const BpGraph& graph) : _graph(&graph) {
-        _graph->firstRed(static_cast<Node&>(*this));
-      }
-
-      RedIt(const BpGraph& graph, const Node& node)
-        : Node(node), _graph(&graph) {
-        LEMON_DEBUG(_graph->red(node), "Node has to be red.");
-      }
+        _graph->first(static_cast<RedNode&>(*this));
+      }
+
+      RedIt(const BpGraph& graph, const RedNode& node)
+        : RedNode(node), _graph(&graph) {}
 
       RedIt& operator++() {
-        _graph->nextRed(*this);
-        return *this;
-      }
-
-    };
-
-    class BlueIt : public Node {
+        _graph->next(static_cast<RedNode&>(*this));
+        return *this;
+      }
+
+    };
+
+    class BlueIt : public BlueNode {
       const BpGraph* _graph;
     public:
@@ -956,17 +942,15 @@
       BlueIt() {}
 
-      BlueIt(Invalid i) : Node(i) { }
+      BlueIt(Invalid i) : BlueNode(i) { }
 
       explicit BlueIt(const BpGraph& graph) : _graph(&graph) {
-        _graph->firstBlue(static_cast<Node&>(*this));
-      }
-
-      BlueIt(const BpGraph& graph, const Node& node)
-        : Node(node), _graph(&graph) {
-        LEMON_DEBUG(_graph->blue(node), "Node has to be blue.");
-      }
+        _graph->first(static_cast<BlueNode&>(*this));
+      }
+
+      BlueIt(const BpGraph& graph, const BlueNode& node)
+        : BlueNode(node), _graph(&graph) {}
 
       BlueIt& operator++() {
-        _graph->nextBlue(*this);
+        _graph->next(static_cast<BlueNode&>(*this));
         return *this;
       }
@@ -1259,6 +1243,6 @@
     // Alteration extension
 
-    Node addRedNode() {
-      Node node = Parent::addRedNode();
+    RedNode addRedNode() {
+      RedNode node = Parent::addRedNode();
       notifier(RedNode()).add(node);
       notifier(Node()).add(node);
@@ -1266,6 +1250,6 @@
     }
 
-    Node addBlueNode() {
-      Node node = Parent::addBlueNode();
+    BlueNode addBlueNode() {
+      BlueNode node = Parent::addBlueNode();
       notifier(BlueNode()).add(node);
       notifier(Node()).add(node);
@@ -1273,5 +1257,5 @@
     }
 
-    Edge addEdge(const Node& from, const Node& to) {
+    Edge addEdge(const RedNode& from, const BlueNode& to) {
       Edge edge = Parent::addEdge(from, to);
       notifier(Edge()).add(edge);
@@ -1318,7 +1302,7 @@
 
       if (Parent::red(node)) {
-        notifier(RedNode()).erase(node);
+        notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
       } else {
-        notifier(BlueNode()).erase(node);        
+        notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
       }
 
Index: lemon/concepts/bpgraph.h
===================================================================
--- lemon/concepts/bpgraph.h	(revision 1018)
+++ lemon/concepts/bpgraph.h	(revision 1025)
@@ -150,10 +150,4 @@
         RedNode(Invalid) { }
 
-        /// Constructor for conversion from a node.
-
-        /// Constructor for conversion from a node. The conversion can
-        /// be invalid, since the Node can be member of the blue
-        /// set.
-        RedNode(const Node&) {}
       };
 
@@ -183,10 +177,4 @@
         BlueNode(Invalid) { }
 
-        /// Constructor for conversion from a node.
-
-        /// Constructor for conversion from a node. The conversion can
-        /// be invalid, since the Node can be member of the red
-        /// set.
-        BlueNode(const Node&) {}
       };
 
@@ -200,5 +188,5 @@
       /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
       ///\endcode
-      class RedIt : public Node {
+      class RedIt : public RedNode {
       public:
         /// Default constructor
@@ -211,5 +199,5 @@
         /// Copy constructor.
         ///
-        RedIt(const RedIt& n) : Node(n) { }
+        RedIt(const RedIt& n) : RedNode(n) { }
         /// %Invalid constructor \& conversion.
 
@@ -226,5 +214,5 @@
         /// Sets the iterator to the given red node of the given
         /// digraph.
-        RedIt(const BpGraph&, const Node&) { }
+        RedIt(const BpGraph&, const RedNode&) { }
         /// Next node.
 
@@ -243,5 +231,5 @@
       /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
       ///\endcode
-      class BlueIt : public Node {
+      class BlueIt : public BlueNode {
       public:
         /// Default constructor
@@ -254,5 +242,5 @@
         /// Copy constructor.
         ///
-        BlueIt(const BlueIt& n) : Node(n) { }
+        BlueIt(const BlueIt& n) : BlueNode(n) { }
         /// %Invalid constructor \& conversion.
 
@@ -269,5 +257,5 @@
         /// Sets the iterator to the given blue node of the given
         /// digraph.
-        BlueIt(const BpGraph&, const Node&) { }
+        BlueIt(const BpGraph&, const BlueNode&) { }
         /// Next node.
 
@@ -785,13 +773,52 @@
       bool blue(const Node&) const { return true; }
 
+      /// \brief Converts the node to red node object.
+      ///
+      /// This class is converts unsafely the node to red node
+      /// object. It should be called only if the node is from the red
+      /// partition or INVALID.
+      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
+
+      /// \brief Converts the node to blue node object.
+      ///
+      /// This class is converts unsafely the node to blue node
+      /// object. It should be called only if the node is from the red
+      /// partition or INVALID.
+      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
+
+      /// \brief Converts the node to red node object.
+      ///
+      /// This class is converts safely the node to red node
+      /// object. If the node is not from the red partition, then it
+      /// returns INVALID.
+      RedNode asRedNode(const Node&) const { return RedNode(); }
+
+      /// \brief Converts the node to blue node object.
+      ///
+      /// This class is converts unsafely the node to blue node
+      /// object. If the node is not from the blue partition, then it
+      /// returns INVALID.
+      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
+
+      /// \brief Convert the node to either red or blue node.
+      ///
+      /// If the node is from the red partition then it is returned in
+      /// first and second is INVALID. If the node is from the blue
+      /// partition then it is returned in second and first is
+      /// INVALID. If the node INVALID then both first and second are
+      /// INVALID in the return value.
+      std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
+        return std::make_pair(RedNode(), BlueNode());
+      }
+
       /// \brief Gives back the red end node of the edge.
       /// 
       /// Gives back the red end node of the edge.
-      Node redNode(const Edge&) const { return Node(); }
+      RedNode redNode(const Edge&) const { return RedNode(); }
 
       /// \brief Gives back the blue end node of the edge.
       /// 
       /// Gives back the blue end node of the edge.
-      Node blueNode(const Edge&) const { return Node(); }
+      BlueNode blueNode(const Edge&) const { return BlueNode(); }
 
       /// \brief The first node of the edge.
@@ -823,15 +850,5 @@
       ///
       /// Returns the red ID of the given node.
-      int redId(Node) const { return -1; }
-
-      /// \brief The red ID of the node.
-      ///
-      /// Returns the red ID of the given node.
       int id(RedNode) const { return -1; }
-
-      /// \brief The blue ID of the node.
-      ///
-      /// Returns the blue ID of the given node.
-      int blueId(Node) const { return -1; }
 
       /// \brief The blue ID of the node.
@@ -929,9 +946,9 @@
       void next(Node&) const {}
 
-      void firstRed(Node&) const {}
-      void nextRed(Node&) const {}
-
-      void firstBlue(Node&) const {}
-      void nextBlue(Node&) const {}
+      void firstRed(RedNode&) const {}
+      void nextRed(RedNode&) const {}
+
+      void firstBlue(BlueNode&) const {}
+      void nextBlue(BlueNode&) const {}
 
       void first(Edge&) const {}
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h	(revision 1018)
+++ lemon/concepts/graph_components.h	(revision 1025)
@@ -318,8 +318,6 @@
       /// \brief Class to represent red nodes.
       ///
-      /// This class represents the red nodes of the graph. It does
-      /// not supposed to be used directly, because the nodes can be
-      /// represented as Node instances. This class can be used as
-      /// template parameter for special map classes.
+      /// This class represents the red nodes of the graph. The red
+      /// nodes can be used also as normal nodes.
       class RedNode : public Node {
         typedef Node Parent;
@@ -345,19 +343,10 @@
         /// \sa Invalid for more details.
         RedNode(Invalid) {}
-
-        /// \brief Constructor for conversion from a node.
-        ///
-        /// Constructor for conversion from a node. The conversion can
-        /// be invalid, since the Node can be member of the blue
-        /// set.
-        RedNode(const Node&) {}
       };
 
       /// \brief Class to represent blue nodes.
       ///
-      /// This class represents the blue nodes of the graph. It does
-      /// not supposed to be used directly, because the nodes can be
-      /// represented as Node instances. This class can be used as
-      /// template parameter for special map classes.
+      /// This class represents the blue nodes of the graph. The blue
+      /// nodes can be used also as normal nodes.
       class BlueNode : public Node {
         typedef Node Parent;
@@ -405,10 +394,49 @@
       /// 
       /// Gives back the red end node of the edge.
-      Node redNode(const Edge&) const { return Node(); }
+      RedNode redNode(const Edge&) const { return RedNode(); }
 
       /// \brief Gives back the blue end node of the edge.
       /// 
       /// Gives back the blue end node of the edge.
-      Node blueNode(const Edge&) const { return Node(); }
+      BlueNode blueNode(const Edge&) const { return BlueNode(); }
+
+      /// \brief Converts the node to red node object.
+      ///
+      /// This class is converts unsafely the node to red node
+      /// object. It should be called only if the node is from the red
+      /// partition or INVALID.
+      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
+
+      /// \brief Converts the node to blue node object.
+      ///
+      /// This class is converts unsafely the node to blue node
+      /// object. It should be called only if the node is from the red
+      /// partition or INVALID.
+      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
+
+      /// \brief Converts the node to red node object.
+      ///
+      /// This class is converts safely the node to red node
+      /// object. If the node is not from the red partition, then it
+      /// returns INVALID.
+      RedNode asRedNode(const Node&) const { return RedNode(); }
+
+      /// \brief Converts the node to blue node object.
+      ///
+      /// This class is converts unsafely the node to blue node
+      /// object. If the node is not from the blue partition, then it
+      /// returns INVALID.
+      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
+
+      /// \brief Convert the node to either red or blue node.
+      ///
+      /// If the node is from the red partition then it is returned in
+      /// first and second is INVALID. If the node is from the blue
+      /// partition then it is returned in second and first is
+      /// INVALID. If the node INVALID then both first and second are
+      /// INVALID in the return value.
+      std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
+        return std::make_pair(RedNode(), BlueNode());
+      }
 
       template <typename _BpGraph>
@@ -426,15 +454,20 @@
           {
             Node n;
-            RedNode rn = n;
-            BlueNode bn = bn;
+            RedNode rn;
+            BlueNode bn;
+            Node rnan = rn;
+            Node bnan = bn;
             Edge e;
             bool b;
-            b = bpgraph.red(n);
-            b = bpgraph.blue(n);
-            ignore_unused_variable_warning(b);
-            n = bpgraph.redNode(e);
-            n = bpgraph.blueNode(e);
-            rn = n;
-            bn = n;
+            b = bpgraph.red(rnan);
+            b = bpgraph.blue(bnan);
+            rn = bpgraph.redNode(e);
+            bn = bpgraph.blueNode(e);
+            rn = bpgraph.asRedNodeUnsafe(rnan);
+            bn = bpgraph.asBlueNodeUnsafe(bnan);
+            rn = bpgraph.asRedNode(rnan);
+            bn = bpgraph.asBlueNode(bnan);
+            std::pair<RedNode, BlueNode> p = bpgraph.asRedBlueNode(rnan);
+            ignore_unused_variable_warning(b,p);
           }
         }
@@ -600,9 +633,4 @@
       ///
       /// Return a unique integer id for the given node in the red set.
-      int redId(const Node&) const { return -1; }
-
-      /// \brief Return the same value as redId().
-      ///
-      /// Return the same value as redId().
       int id(const RedNode&) const { return -1; }
 
@@ -610,9 +638,4 @@
       ///
       /// Return a unique integer id for the given node in the blue set.
-      int blueId(const Node&) const { return -1; }
-
-      /// \brief Return the same value as blueId().
-      ///
-      /// Return the same value as blueId().
       int id(const BlueNode&) const { return -1; }
 
@@ -639,8 +662,6 @@
           typename _BpGraph::RedNode red;
           typename _BpGraph::BlueNode blue;
-          int rid = bpgraph.redId(node);
-          int bid = bpgraph.blueId(node);
-          rid = bpgraph.id(red);
-          bid = bpgraph.id(blue);
+          int rid = bpgraph.id(red);
+          int bid = bpgraph.id(blue);
           rid = bpgraph.maxRedId();
           bid = bpgraph.maxBlueId();
@@ -1138,10 +1159,14 @@
       typedef BAS Base;
       typedef typename Base::Node Node;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
       typedef typename Base::Arc Arc;
       typedef typename Base::Edge Edge;
-
-
+      
       typedef IterableBpGraphComponent BpGraph;
 
+      using IterableGraphComponent<BAS>::first;
+      using IterableGraphComponent<BAS>::next;
+
       /// \name Base Iteration
       ///
@@ -1153,20 +1178,20 @@
       ///
       /// This function gives back the first red node in the iteration order.
-      void firstRed(Node&) const {}
+      void first(RedNode&) const {}
 
       /// \brief Return the next red node.
       ///
       /// This function gives back the next red node in the iteration order.
-      void nextRed(Node&) const {}
+      void next(RedNode&) const {}
 
       /// \brief Return the first blue node.
       ///
       /// This function gives back the first blue node in the iteration order.
-      void firstBlue(Node&) const {}
+      void first(BlueNode&) const {}
 
       /// \brief Return the next blue node.
       ///
       /// This function gives back the next blue node in the iteration order.
-      void nextBlue(Node&) const {}
+      void next(BlueNode&) const {}
 
 
@@ -1182,10 +1207,10 @@
       ///
       /// This iterator goes through each red node.
-      typedef GraphItemIt<BpGraph, Node> RedIt;
+      typedef GraphItemIt<BpGraph, RedNode> RedIt;
 
       /// \brief This iterator goes through each blue node.
       ///
       /// This iterator goes through each blue node.
-      typedef GraphItemIt<BpGraph, Node> BlueIt;
+      typedef GraphItemIt<BpGraph, BlueNode> BlueIt;
 
       /// @}
@@ -1196,13 +1221,14 @@
           checkConcept<IterableGraphComponent<Base>, _BpGraph>();
 
-          typename _BpGraph::Node node(INVALID);
-          bpgraph.firstRed(node);
-          bpgraph.nextRed(node); 
-          bpgraph.firstBlue(node);
-          bpgraph.nextBlue(node);
-
-          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
+          typename _BpGraph::RedNode rn(INVALID);
+          bpgraph.first(rn);
+          bpgraph.next(rn); 
+          typename _BpGraph::BlueNode bn(INVALID);
+          bpgraph.first(bn);
+          bpgraph.next(bn);
+
+          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
             typename _BpGraph::RedIt>();
-          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
+          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
             typename _BpGraph::BlueIt>();
         }
@@ -1791,13 +1817,13 @@
           { // int map test
             typedef typename _BpGraph::template RedMap<int> IntRedMap;
-            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
               IntRedMap >();
           } { // bool map test
             typedef typename _BpGraph::template RedMap<bool> BoolRedMap;
-            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
               BoolRedMap >();
           } { // Dummy map test
             typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap;
-            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
               DummyRedMap >();
           }
@@ -1805,13 +1831,13 @@
           { // int map test
             typedef typename _BpGraph::template BlueMap<int> IntBlueMap;
-            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
               IntBlueMap >();
           } { // bool map test
             typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap;
-            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
               BoolBlueMap >();
           } { // Dummy map test
             typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap;
-            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
               DummyBlueMap >();
           }
@@ -1924,4 +1950,6 @@
       typedef BAS Base;
       typedef typename Base::Node Node;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
       typedef typename Base::Edge Edge;
 
@@ -1929,5 +1957,5 @@
       ///
       /// This function adds a red new node to the digraph.
-      Node addRedNode() {
+      RedNode addRedNode() {
         return INVALID;
       }
@@ -1936,5 +1964,5 @@
       ///
       /// This function adds a blue new node to the digraph.
-      Node addBlueNode() {
+      BlueNode addBlueNode() {
         return INVALID;
       }
@@ -1945,7 +1973,10 @@
       /// of the graph. The first node has to be a red node, and the
       /// second one a blue node.
-      Edge addEdge(const Node&, const Node&) {
+      Edge addEdge(const RedNode&, const BlueNode&) {
         return INVALID;
       }
+      Edge addEdge(const BlueNode&, const RedNode&) {
+        return INVALID;
+      }
 
       template <typename _BpGraph>
@@ -1953,9 +1984,11 @@
         void constraints() {
           checkConcept<Base, _BpGraph>();
-          typename _BpGraph::Node red_node, blue_node;
+          typename _BpGraph::RedNode red_node;
+          typename _BpGraph::BlueNode blue_node;
           red_node = bpgraph.addRedNode();
           blue_node = bpgraph.addBlueNode();
           typename _BpGraph::Edge edge;
           edge = bpgraph.addEdge(red_node, blue_node);
+          edge = bpgraph.addEdge(blue_node, red_node);
         }
 
Index: lemon/core.h
===================================================================
--- lemon/core.h	(revision 1022)
+++ lemon/core.h	(revision 1025)
@@ -551,5 +551,6 @@
       template <typename From, typename NodeRefMap, typename EdgeRefMap>
       static void copy(const From& from, Graph &to,
-                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
+                       NodeRefMap& nodeRefMap,
+                       EdgeRefMap& edgeRefMap) {
         to.build(from, nodeRefMap, edgeRefMap);
       }
@@ -558,17 +559,20 @@
     template <typename BpGraph, typename Enable = void>
     struct BpGraphCopySelector {
-      template <typename From, typename NodeRefMap, typename EdgeRefMap>
+      template <typename From, typename RedNodeRefMap,
+                typename BlueNodeRefMap, typename EdgeRefMap>
       static void copy(const From& from, BpGraph &to,
-                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
+                       RedNodeRefMap& redNodeRefMap,
+                       BlueNodeRefMap& blueNodeRefMap,
+                       EdgeRefMap& edgeRefMap) {
         to.clear();
         for (typename From::RedIt it(from); it != INVALID; ++it) {
-          nodeRefMap[it] = to.addRedNode();
+          redNodeRefMap[it] = to.addRedNode();
         }
         for (typename From::BlueIt it(from); it != INVALID; ++it) {
-          nodeRefMap[it] = to.addBlueNode();
+          blueNodeRefMap[it] = to.addBlueNode();
         }
         for (typename From::EdgeIt it(from); it != INVALID; ++it) {
-          edgeRefMap[it] = to.addEdge(nodeRefMap[from.redNode(it)],
-                                      nodeRefMap[from.blueNode(it)]);
+          edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
+                                      blueNodeRefMap[from.blueNode(it)]);
         }
       }
@@ -580,8 +584,11 @@
       typename enable_if<typename BpGraph::BuildTag, void>::type>
     {
-      template <typename From, typename NodeRefMap, typename EdgeRefMap>
+      template <typename From, typename RedNodeRefMap,
+                typename BlueNodeRefMap, typename EdgeRefMap>
       static void copy(const From& from, BpGraph &to,
-                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
-        to.build(from, nodeRefMap, edgeRefMap);
+                       RedNodeRefMap& redNodeRefMap,
+                       BlueNodeRefMap& blueNodeRefMap,
+                       EdgeRefMap& edgeRefMap) {
+        to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
       }
     };
@@ -1183,9 +1190,35 @@
 
     typedef typename To::Node TNode;
+    typedef typename To::RedNode TRedNode;
+    typedef typename To::BlueNode TBlueNode;
     typedef typename To::Arc TArc;
     typedef typename To::Edge TEdge;
 
-    typedef typename From::template NodeMap<TNode> NodeRefMap;
+    typedef typename From::template RedMap<TRedNode> RedNodeRefMap;
+    typedef typename From::template BlueMap<TBlueNode> BlueNodeRefMap;
     typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
+
+    struct NodeRefMap {
+      NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
+                 const BlueNodeRefMap& blue_node_ref)
+        : _from(from), _red_node_ref(red_node_ref),
+          _blue_node_ref(blue_node_ref) {}
+
+      typedef typename From::Node Key;
+      typedef typename To::Node Value;
+
+      Value operator[](const Key& key) const {
+        std::pair<RedNode, BlueNode> red_blue_pair = _from.asRedBlueNode(key);
+        if (red_blue_pair.first != INVALID) {
+          return _red_node_ref[red_blue_pair.first];
+        } else {
+          return _blue_node_ref[red_blue_pair.second];
+        }
+      }
+
+      const From& _from;
+      const RedNodeRefMap& _red_node_ref;
+      const BlueNodeRefMap& _blue_node_ref;
+    };
 
     struct ArcRefMap {
@@ -1293,5 +1326,5 @@
     BpGraphCopy& redRef(RedRef& map) {
       _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
-                          NodeRefMap, RedRef>(map));
+                          RedNodeRefMap, RedRef>(map));
       return *this;
     }
@@ -1307,5 +1340,5 @@
     BpGraphCopy& redCrossRef(RedCrossRef& map) {
       _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
-                          NodeRefMap, RedCrossRef>(map));
+                          RedNodeRefMap, RedCrossRef>(map));
       return *this;
     }
@@ -1322,5 +1355,14 @@
     BpGraphCopy& redMap(const FromMap& map, ToMap& tmap) {
       _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
-                           NodeRefMap, FromMap, ToMap>(map, tmap));
+                          RedNodeRefMap, FromMap, ToMap>(map, tmap));
+      return *this;
+    }
+
+    /// \brief Make a copy of the given red node.
+    ///
+    /// This function makes a copy of the given red node.
+    BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
+      _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
+                          RedNodeRefMap, TRedNode>(node, tnode));
       return *this;
     }
@@ -1335,5 +1377,5 @@
     BpGraphCopy& blueRef(BlueRef& map) {
       _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
-                           NodeRefMap, BlueRef>(map));
+                           BlueNodeRefMap, BlueRef>(map));
       return *this;
     }
@@ -1349,5 +1391,5 @@
     BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
       _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
-                           NodeRefMap, BlueCrossRef>(map));
+                           BlueNodeRefMap, BlueCrossRef>(map));
       return *this;
     }
@@ -1364,5 +1406,14 @@
     BpGraphCopy& blueMap(const FromMap& map, ToMap& tmap) {
       _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
-                           NodeRefMap, FromMap, ToMap>(map, tmap));
+                           BlueNodeRefMap, FromMap, ToMap>(map, tmap));
+      return *this;
+    }
+
+    /// \brief Make a copy of the given blue node.
+    ///
+    /// This function makes a copy of the given blue node.
+    BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
+      _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
+                           BlueNodeRefMap, TBlueNode>(node, tnode));
       return *this;
     }
@@ -1471,17 +1522,19 @@
     /// copying of the assigned data.
     void run() {
-      NodeRefMap nodeRefMap(_from);
+      RedNodeRefMap redNodeRefMap(_from);
+      BlueNodeRefMap blueNodeRefMap(_from);
+      NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
       EdgeRefMap edgeRefMap(_from);
       ArcRefMap arcRefMap(_from, _to, edgeRefMap);
       _core_bits::BpGraphCopySelector<To>::
-        copy(_from, _to, nodeRefMap, edgeRefMap);
+        copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
       for (int i = 0; i < int(_node_maps.size()); ++i) {
         _node_maps[i]->copy(_from, nodeRefMap);
       }
       for (int i = 0; i < int(_red_maps.size()); ++i) {
-        _red_maps[i]->copy(_from, nodeRefMap);
+        _red_maps[i]->copy(_from, redNodeRefMap);
       }
       for (int i = 0; i < int(_blue_maps.size()); ++i) {
-        _blue_maps[i]->copy(_from, nodeRefMap);
+        _blue_maps[i]->copy(_from, blueNodeRefMap);
       }
       for (int i = 0; i < int(_edge_maps.size()); ++i) {
@@ -1501,8 +1554,8 @@
       _node_maps;
 
-    std::vector<_core_bits::MapCopyBase<From, RedNode, NodeRefMap>* >
+    std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
       _red_maps;
 
-    std::vector<_core_bits::MapCopyBase<From, BlueNode, NodeRefMap>* >
+    std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
       _blue_maps;
 
Index: lemon/full_graph.h
===================================================================
--- lemon/full_graph.h	(revision 1024)
+++ lemon/full_graph.h	(revision 1025)
@@ -652,4 +652,28 @@
     };
 
+    class RedNode : public Node {
+      friend class FullBpGraphBase;
+    protected:
+
+      explicit RedNode(int pid) : Node(pid) {}
+
+    public:
+      RedNode() {}
+      RedNode(const RedNode& node) : Node(node) {}
+      RedNode(Invalid) : Node(INVALID){}
+    };
+
+    class BlueNode : public Node {
+      friend class FullBpGraphBase;
+    protected:
+
+      explicit BlueNode(int pid) : Node(pid) {}
+
+    public:
+      BlueNode() {}
+      BlueNode(const BlueNode& node) : Node(node) {}
+      BlueNode(Invalid) : Node(INVALID){}
+    };
+
     class Edge {
       friend class FullBpGraphBase;
@@ -718,4 +742,7 @@
     bool blue(Node n) const { return n._id >= _red_num; }
 
+    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
+    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
+
     Node source(Arc a) const {
       if (a._id & 1) {
@@ -733,9 +760,9 @@
     }
 
-    Node redNode(Edge e) const {
-      return Node(e._id % _red_num);
-    }
-    Node blueNode(Edge e) const {
-      return Node(e._id / _red_num + _red_num);
+    RedNode redNode(Edge e) const {
+      return RedNode(e._id % _red_num);
+    }
+    BlueNode blueNode(Edge e) const {
+      return BlueNode(e._id / _red_num + _red_num);
     }
 
@@ -756,18 +783,18 @@
     }
 
-    void firstRed(Node& node) const {
+    void first(RedNode& node) const {
       node._id = _red_num - 1;
     }
 
-    static void nextRed(Node& node) {
+    static void next(RedNode& node) {
       --node._id;
     }
 
-    void firstBlue(Node& node) const {
+    void first(BlueNode& node) const {
       if (_red_num == _node_num) node._id = -1;
       else node._id = _node_num - 1;
     }
 
-    void nextBlue(Node& node) const {
+    void next(BlueNode& node) const {
       if (node._id == _red_num) node._id = -1;
       else --node._id;
@@ -843,13 +870,7 @@
     }
 
-    static int id(Node v) { return v._id; }
-    int redId(Node v) const {
-      LEMON_DEBUG(v._id < _red_num, "Node has to be red");
-      return v._id;
-    }
-    int blueId(Node v) const {
-      LEMON_DEBUG(v._id >= _red_num, "Node has to be blue");
-      return v._id - _red_num;
-    }
+    static int id(const Node& v) { return v._id; }
+    int id(const RedNode& v) const { return v._id; }
+    int id(const BlueNode& v) const { return v._id - _red_num; }
     static int id(Arc e) { return e._id; }
     static int id(Edge e) { return e._id; }
@@ -869,17 +890,17 @@
     }
 
-    Node redNode(int index) const {
-      return Node(index);
-    }
-
-    int redIndex(Node n) const {
+    RedNode redNode(int index) const {
+      return RedNode(index);
+    }
+
+    int index(RedNode n) const {
       return n._id;
     }
 
-    Node blueNode(int index) const {
-      return Node(index + _red_num);
-    }
-
-    int blueIndex(Node n) const {
+    BlueNode blueNode(int index) const {
+      return BlueNode(index + _red_num);
+    }
+
+    int index(BlueNode n) const {
       return n._id - _red_num;
     }
@@ -1001,5 +1022,5 @@
     /// with integers from the range <tt>[0..redNum()-1]</tt>.
     /// \sa redIndex()
-    Node redNode(int index) const { return Parent::redNode(index); }
+    RedNode redNode(int index) const { return Parent::redNode(index); }
 
     /// \brief Returns the index of the given red node.
@@ -1010,5 +1031,5 @@
     ///
     /// \sa operator()()
-    int redIndex(Node node) const { return Parent::redIndex(node); }
+    int index(RedNode node) const { return Parent::index(node); }
 
     /// \brief Returns the blue node with the given index.
@@ -1018,5 +1039,5 @@
     /// with integers from the range <tt>[0..blueNum()-1]</tt>.
     /// \sa blueIndex()
-    Node blueNode(int index) const { return Parent::blueNode(index); }
+    BlueNode blueNode(int index) const { return Parent::blueNode(index); }
 
     /// \brief Returns the index of the given blue node.
@@ -1027,5 +1048,5 @@
     ///
     /// \sa operator()()
-    int blueIndex(Node node) const { return Parent::blueIndex(node); }
+    int index(BlueNode node) const { return Parent::index(node); }
 
     /// \brief Returns the edge which connects the given nodes.
Index: lemon/list_graph.h
===================================================================
--- lemon/list_graph.h	(revision 1021)
+++ lemon/list_graph.h	(revision 1025)
@@ -1648,4 +1648,28 @@
     };
 
+    class RedNode : public Node {
+      friend class ListBpGraphBase;
+    protected:
+
+      explicit RedNode(int pid) : Node(pid) {}
+
+    public:
+      RedNode() {}
+      RedNode(const RedNode& node) : Node(node) {}
+      RedNode(Invalid) : Node(INVALID){}
+    };
+
+    class BlueNode : public Node {
+      friend class ListBpGraphBase;
+    protected:
+
+      explicit BlueNode(int pid) : Node(pid) {}
+
+    public:
+      BlueNode() {}
+      BlueNode(const BlueNode& node) : Node(node) {}
+      BlueNode(Invalid) : Node(INVALID){}
+    };
+
     class Edge {
       friend class ListBpGraphBase;
@@ -1693,4 +1717,7 @@
     bool blue(Node n) const { return !nodes[n.id].red; }
 
+    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
+    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
+
     int maxNodeId() const { return nodes.size()-1; }
     int maxRedId() const { return max_red; }
@@ -1702,6 +1729,10 @@
     Node target(Arc e) const { return Node(arcs[e.id].target); }
 
-    Node redNode(Edge e) const { return Node(arcs[2 * e.id].target); }
-    Node blueNode(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
+    RedNode redNode(Edge e) const {
+      return RedNode(arcs[2 * e.id].target);
+    }
+    BlueNode blueNode(Edge e) const {
+      return BlueNode(arcs[2 * e.id + 1].target);
+    }
 
     static bool direction(Arc e) {
@@ -1721,17 +1752,17 @@
     }
 
-    void firstRed(Node& node) const {
+    void first(RedNode& node) const {
       node.id = first_red;
     }
 
-    void nextRed(Node& node) const {
+    void next(RedNode& node) const {
       node.id = nodes[node.id].partition_next;
     }
 
-    void firstBlue(Node& node) const {
+    void first(BlueNode& node) const {
       node.id = first_blue;
     }
 
-    void nextBlue(Node& node) const {
+    void next(BlueNode& node) const {
       node.id = nodes[node.id].partition_next;
     }    
@@ -1836,12 +1867,6 @@
 
     static int id(Node v) { return v.id; }
-    int redId(Node v) const {
-      LEMON_DEBUG(nodes[v.id].red, "Node has to be red");
-      return nodes[v.id].partition_index;
-    }
-    int blueId(Node v) const {
-      LEMON_DEBUG(!nodes[v.id].red, "Node has to be blue");
-      return nodes[v.id].partition_index;
-    }
+    int id(RedNode v) const { return nodes[v.id].partition_index; }
+    int id(BlueNode v) const { return nodes[v.id].partition_index; }
     static int id(Arc e) { return e.id; }
     static int id(Edge e) { return e.id; }
@@ -1866,5 +1891,5 @@
     }
 
-    Node addRedNode() {
+    RedNode addRedNode() {
       int n;
 
@@ -1891,8 +1916,8 @@
       nodes[n].first_out = -1;
 
-      return Node(n);
-    }
-
-    Node addBlueNode() {
+      return RedNode(n);
+    }
+
+    BlueNode addBlueNode() {
       int n;
 
@@ -1919,5 +1944,5 @@
       nodes[n].first_out = -1;
 
-      return Node(n);
+      return BlueNode(n);
     }
 
@@ -2030,6 +2055,5 @@
   protected:
 
-    void changeRed(Edge e, Node n) {
-      LEMON_DEBUG(nodes[n].red, "Node has to be red");
+    void changeRed(Edge e, RedNode n) {
       if(arcs[(2 * e.id) | 1].next_out != -1) {
         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
@@ -2053,7 +2077,6 @@
     }
 
-    void changeBlue(Edge e, Node n) {
-      LEMON_DEBUG(nodes[n].red, "Node has to be blue");
-      if(arcs[2 * e.id].next_out != -1) {
+    void changeBlue(Edge e, BlueNode n) {
+       if(arcs[2 * e.id].next_out != -1) {
         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
       }
@@ -2120,5 +2143,5 @@
     /// This function adds a red new node to the graph.
     /// \return The new node.
-    Node addRedNode() { return Parent::addRedNode(); }
+    RedNode addRedNode() { return Parent::addRedNode(); }
 
     /// \brief Add a new blue node to the graph.
@@ -2126,5 +2149,5 @@
     /// This function adds a blue new node to the graph.
     /// \return The new node.
-    Node addBlueNode() { return Parent::addBlueNode(); }
+    BlueNode addBlueNode() { return Parent::addBlueNode(); }
 
     /// \brief Add a new edge to the graph.
@@ -2134,5 +2157,8 @@
     /// node \c v.
     /// \return The new edge.
-    Edge addEdge(Node u, Node v) {
+    Edge addEdge(RedNode u, BlueNode v) {
+      return Parent::addEdge(u, v);
+    }
+    Edge addEdge(BlueNode v, RedNode u) {
       return Parent::addEdge(u, v);
     }
@@ -2189,6 +2215,6 @@
     ///\warning This functionality cannot be used together with the
     ///Snapshot feature.
-    void changeRed(Edge e, Node n) {
-      Parent::changeRed(e,n);
+    void changeRed(Edge e, RedNode n) {
+      Parent::changeRed(e, n);
     }
     /// \brief Change the blue node of an edge.
@@ -2203,6 +2229,6 @@
     ///\warning This functionality cannot be used together with the
     ///Snapshot feature.
-    void changeBlue(Edge e, Node n) {
-      Parent::changeBlue(e,n);
+    void changeBlue(Edge e, BlueNode n) {
+      Parent::changeBlue(e, n);
     }
 
Index: lemon/smart_graph.h
===================================================================
--- lemon/smart_graph.h	(revision 1023)
+++ lemon/smart_graph.h	(revision 1025)
@@ -855,4 +855,28 @@
     };
 
+    class RedNode : public Node {
+      friend class SmartBpGraphBase;
+    protected:
+
+      explicit RedNode(int pid) : Node(pid) {}
+
+    public:
+      RedNode() {}
+      RedNode(const RedNode& node) : Node(node) {}
+      RedNode(Invalid) : Node(INVALID){}
+    };
+
+    class BlueNode : public Node {
+      friend class SmartBpGraphBase;
+    protected:
+
+      explicit BlueNode(int pid) : Node(pid) {}
+
+    public:
+      BlueNode() {}
+      BlueNode(const BlueNode& node) : Node(node) {}
+      BlueNode(Invalid) : Node(INVALID){}
+    };
+
     class Edge {
       friend class SmartBpGraphBase;
@@ -914,9 +938,16 @@
     bool blue(Node n) const { return !nodes[n._id].red; }
 
+    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
+    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
+
     Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
     Node target(Arc a) const { return Node(arcs[a._id].target); }
 
-    Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); }
-    Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
+    RedNode redNode(Edge e) const {
+      return RedNode(arcs[2 * e._id].target);
+    }
+    BlueNode blueNode(Edge e) const {
+      return BlueNode(arcs[2 * e._id + 1].target);
+    }
 
     static bool direction(Arc a) {
@@ -936,17 +967,17 @@
     }
 
-    void firstRed(Node& node) const {
+    void first(RedNode& node) const {
       node._id = first_red;
     }
 
-    void nextRed(Node& node) const {
+    void next(RedNode& node) const {
       node._id = nodes[node._id].partition_next;
     }
 
-    void firstBlue(Node& node) const {
+    void first(BlueNode& node) const {
       node._id = first_blue;
     }
 
-    void nextBlue(Node& node) const {
+    void next(BlueNode& node) const {
       node._id = nodes[node._id].partition_next;
     }
@@ -1006,12 +1037,6 @@
 
     static int id(Node v) { return v._id; }
-    int redId(Node v) const {
-      LEMON_DEBUG(nodes[v._id].red, "Node has to be red");
-      return nodes[v._id].partition_index;
-    }
-    int blueId(Node v) const {
-      LEMON_DEBUG(!nodes[v._id].red, "Node has to be blue");
-      return nodes[v._id].partition_index;
-    }
+    int id(RedNode v) const { return nodes[v._id].partition_index; }
+    int id(BlueNode v) const { return nodes[v._id].partition_index; }
     static int id(Arc e) { return e._id; }
     static int id(Edge e) { return e._id; }
@@ -1031,5 +1056,5 @@
     }
 
-    Node addRedNode() {
+    RedNode addRedNode() {
       int n = nodes.size();
       nodes.push_back(NodeT());
@@ -1040,8 +1065,8 @@
       first_red = n;
 
-      return Node(n);
-    }
-
-    Node addBlueNode() {
+      return RedNode(n);
+    }
+
+    BlueNode addBlueNode() {
       int n = nodes.size();
       nodes.push_back(NodeT());
@@ -1052,8 +1077,8 @@
       first_blue = n;
 
-      return Node(n);
-    }
-
-    Edge addEdge(Node u, Node v) {
+      return BlueNode(n);
+    }
+
+    Edge addEdge(RedNode u, BlueNode v) {
       int n = arcs.size();
       arcs.push_back(ArcT());
@@ -1125,5 +1150,5 @@
     /// This function adds a red new node to the graph.
     /// \return The new node.
-    Node addRedNode() { return Parent::addRedNode(); }
+    RedNode addRedNode() { return Parent::addRedNode(); }
 
     /// \brief Add a new blue node to the graph.
@@ -1131,5 +1156,5 @@
     /// This function adds a blue new node to the graph.
     /// \return The new node.
-    Node addBlueNode() { return Parent::addBlueNode(); }
+    BlueNode addBlueNode() { return Parent::addBlueNode(); }
 
     /// \brief Add a new edge to the graph.
@@ -1139,8 +1164,9 @@
     /// node \c v.
     /// \return The new edge.
-    Edge addEdge(Node red, Node blue) {
-      LEMON_DEBUG(Parent::red(red) && Parent::blue(blue),
-                  "Edge has to be formed by a red and a blue nodes");
-      return Parent::addEdge(red, blue);
+    Edge addEdge(RedNode u, BlueNode v) {
+      return Parent::addEdge(u, v);
+    }
+    Edge addEdge(BlueNode v, RedNode u) {
+      return Parent::addEdge(u, v);
     }
 
@@ -1238,5 +1264,5 @@
             max_red = -1;
           }
-          Parent::notifier(RedNode()).erase(node);          
+          Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));          
         } else {
           first_blue = nodes[n].partition_next;
@@ -1246,5 +1272,5 @@
             max_blue = -1;
           }
-          Parent::notifier(BlueNode()).erase(node);
+          Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
         }
         Parent::notifier(Node()).erase(node);
Index: test/bpgraph_test.cc
===================================================================
--- test/bpgraph_test.cc	(revision 1021)
+++ test/bpgraph_test.cc	(revision 1025)
@@ -42,5 +42,5 @@
   G.reserveEdge(3);
 
-  Node
+  RedNode
     rn1 = G.addRedNode();
   checkGraphNodeList(G, 1);
@@ -50,5 +50,5 @@
   checkGraphArcList(G, 0);
 
-  Node
+  BlueNode
     bn1 = G.addBlueNode(),
     bn2 = G.addBlueNode();
@@ -77,5 +77,5 @@
 
   Edge
-    e2 = G.addEdge(rn1, bn1),
+    e2 = G.addEdge(bn1, rn1),
     e3 = G.addEdge(rn1, bn2);
 
@@ -113,7 +113,8 @@
 
   BpGraph G;
-  Node
-    n1 = G.addRedNode(), n2 = G.addBlueNode(),
-    n3 = G.addBlueNode(), n4 = G.addRedNode();
+  RedNode
+    n1 = G.addRedNode(), n4 = G.addRedNode(); 
+  BlueNode
+    n2 = G.addBlueNode(), n3 = G.addBlueNode();
   Edge
     e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
@@ -160,7 +161,8 @@
 
   BpGraph G;
-  Node
-    n1 = G.addRedNode(), n2 = G.addBlueNode(),
-    n3 = G.addBlueNode(), n4 = G.addRedNode();
+  RedNode
+    n1 = G.addRedNode(), n4 = G.addRedNode(); 
+  BlueNode
+    n2 = G.addBlueNode(), n3 = G.addBlueNode();
   Edge
     e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
@@ -210,6 +212,7 @@
 
   BpGraph G;
-  Node 
-    n1 = G.addRedNode(),
+  RedNode
+    n1 = G.addRedNode();
+  BlueNode
     n2 = G.addBlueNode(),
     n3 = G.addBlueNode();
@@ -226,5 +229,5 @@
   typename BpGraph::Snapshot snapshot(G);
 
-  Node n4 = G.addRedNode();
+  RedNode n4 = G.addRedNode();
   G.addEdge(n4, n2);
   G.addEdge(n4, n3);
@@ -293,6 +296,7 @@
   BpGraph g;
 
-  Node
-    n1 = g.addRedNode(),
+  RedNode
+    n1 = g.addRedNode();
+  BlueNode
     n2 = g.addBlueNode(),
     n3 = g.addBlueNode();
@@ -397,10 +401,10 @@
   for (int i = 0; i < G.redNum(); ++i) {
     check(G.red(G.redNode(i)), "Wrong node");
-    check(G.redIndex(G.redNode(i)) == i, "Wrong index");
+    check(G.index(G.redNode(i)) == i, "Wrong index");
   }
 
   for (int i = 0; i < G.blueNum(); ++i) {
     check(G.blue(G.blueNode(i)), "Wrong node");
-    check(G.blueIndex(G.blueNode(i)) == i, "Wrong index");
+    check(G.index(G.blueNode(i)) == i, "Wrong index");
   }
 
Index: test/graph_copy_test.cc
===================================================================
--- test/graph_copy_test.cc	(revision 1022)
+++ test/graph_copy_test.cc	(revision 1025)
@@ -222,22 +222,28 @@
   SmartBpGraph::EdgeMap<int> fem(from);
   SmartBpGraph::Node fn = INVALID;
+  SmartBpGraph::RedNode frn = INVALID;
+  SmartBpGraph::BlueNode fbn = INVALID;
   SmartBpGraph::Arc fa = INVALID;
   SmartBpGraph::Edge fe = INVALID;
 
-  std::vector<SmartBpGraph::Node> frnv;
-  for (int i = 0; i < nn; ++i) {
-    SmartBpGraph::Node node = from.addRedNode();
+  std::vector<SmartBpGraph::RedNode> frnv;
+  for (int i = 0; i < nn; ++i) {
+    SmartBpGraph::RedNode node = from.addRedNode();
     frnv.push_back(node);
     fnm[node] = i * i;
     frnm[node] = i + i;
-    if (i == 0) fn = node;
-  }
-
-  std::vector<SmartBpGraph::Node> fbnv;
-  for (int i = 0; i < nn; ++i) {
-    SmartBpGraph::Node node = from.addBlueNode();
+    if (i == 0) {
+      fn = node;
+      frn = node;
+    }
+  }
+
+  std::vector<SmartBpGraph::BlueNode> fbnv;
+  for (int i = 0; i < nn; ++i) {
+    SmartBpGraph::BlueNode node = from.addBlueNode();
     fbnv.push_back(node);
     fnm[node] = i * i;
     fbnm[node] = i + i;
+    if (i == 0) fbn = node;
   }
 
@@ -261,16 +267,18 @@
   typename GR::template EdgeMap<int> tem(to);
   typename GR::Node tn;
+  typename GR::RedNode trn;
+  typename GR::BlueNode tbn;
   typename GR::Arc ta;
   typename GR::Edge te;
 
   SmartBpGraph::NodeMap<typename GR::Node> nr(from);
-  SmartBpGraph::RedMap<typename GR::Node> rnr(from);
-  SmartBpGraph::BlueMap<typename GR::Node> bnr(from);
+  SmartBpGraph::RedMap<typename GR::RedNode> rnr(from);
+  SmartBpGraph::BlueMap<typename GR::BlueNode> bnr(from);
   SmartBpGraph::ArcMap<typename GR::Arc> ar(from);
   SmartBpGraph::EdgeMap<typename GR::Edge> er(from);
 
   typename GR::template NodeMap<SmartBpGraph::Node> ncr(to);
-  typename GR::template RedMap<SmartBpGraph::Node> rncr(to);
-  typename GR::template BlueMap<SmartBpGraph::Node> bncr(to);
+  typename GR::template RedMap<SmartBpGraph::RedNode> rncr(to);
+  typename GR::template BlueMap<SmartBpGraph::BlueNode> bncr(to);
   typename GR::template ArcMap<SmartBpGraph::Arc> acr(to);
   typename GR::template EdgeMap<SmartBpGraph::Edge> ecr(to);
@@ -283,5 +291,6 @@
     nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr).
     arcCrossRef(acr).edgeCrossRef(ecr).
-    node(fn, tn).arc(fa, ta).edge(fe, te).run();
+    node(fn, tn).redNode(frn, trn).blueNode(fbn, tbn).
+    arc(fa, ta).edge(fe, te).run();
 
   check(countNodes(from) == countNodes(to), "Wrong copy.");
@@ -294,15 +303,22 @@
     check(ncr[nr[it]] == it, "Wrong copy.");
     check(fnm[it] == tnm[nr[it]], "Wrong copy.");
-    if (from.red(it)) {
-      check(rnr[it] == nr[it], "Wrong copy.");
-      check(rncr[rnr[it]] == it, "Wrong copy.");
-      check(frnm[it] == trnm[rnr[it]], "Wrong copy.");
-      check(to.red(rnr[it]), "Wrong copy.");
-    } else {
-      check(bnr[it] == nr[it], "Wrong copy.");
-      check(bncr[bnr[it]] == it, "Wrong copy.");
-      check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");
-      check(to.blue(bnr[it]), "Wrong copy.");
-    }
+  }
+
+  for (SmartBpGraph::RedIt it(from); it != INVALID; ++it) {
+    check(ncr[nr[it]] == it, "Wrong copy.");
+    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
+    check(rnr[it] == nr[it], "Wrong copy.");
+    check(rncr[rnr[it]] == it, "Wrong copy.");
+    check(frnm[it] == trnm[rnr[it]], "Wrong copy.");
+    check(to.red(rnr[it]), "Wrong copy.");
+  }
+
+  for (SmartBpGraph::BlueIt it(from); it != INVALID; ++it) {
+    check(ncr[nr[it]] == it, "Wrong copy.");
+    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
+    check(bnr[it] == nr[it], "Wrong copy.");
+    check(bncr[bnr[it]] == it, "Wrong copy.");
+    check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");
+    check(to.blue(bnr[it]), "Wrong copy.");
   }
 
@@ -343,4 +359,6 @@
   }
   check(tn == nr[fn], "Wrong copy.");
+  check(trn == rnr[frn], "Wrong copy.");
+  check(tbn == bnr[fbn], "Wrong copy.");
   check(ta == ar[fa], "Wrong copy.");
   check(te == er[fe], "Wrong copy.");
Index: test/graph_test.h
===================================================================
--- test/graph_test.h	(revision 1019)
+++ test/graph_test.h	(revision 1025)
@@ -47,4 +47,14 @@
     for(int i=0;i<cnt;i++) {
       check(n!=INVALID,"Wrong red Node list linking.");
+      check(G.red(n),"Wrong node set check.");
+      check(!G.blue(n),"Wrong node set check.");
+      typename Graph::Node nn = n;
+      check(G.asRedNodeUnsafe(nn) == n,"Wrong node conversion.");
+      check(G.asRedNode(nn) == n,"Wrong node conversion.");
+      check(G.asBlueNode(nn) == INVALID,"Wrong node conversion.");
+      std::pair<typename Graph::RedNode, typename Graph::BlueNode> rbn =
+        G.asRedBlueNode(nn);
+      check(rbn.first == n,"Wrong node conversion.");
+      check(rbn.second == INVALID,"Wrong node conversion.");
       ++n;
     }
@@ -59,4 +69,14 @@
     for(int i=0;i<cnt;i++) {
       check(n!=INVALID,"Wrong blue Node list linking.");
+      check(G.blue(n),"Wrong node set check.");
+      check(!G.red(n),"Wrong node set check.");
+      typename Graph::Node nn = n;
+      check(G.asBlueNodeUnsafe(nn) == n,"Wrong node conversion.");
+      check(G.asBlueNode(nn) == n,"Wrong node conversion.");
+      check(G.asRedNode(nn) == INVALID,"Wrong node conversion.");
+      std::pair<typename Graph::RedNode, typename Graph::BlueNode> rbn =
+        G.asRedBlueNode(nn);
+      check(rbn.first == INVALID,"Wrong node conversion.");
+      check(rbn.second == n,"Wrong node conversion.");
       ++n;
     }
@@ -208,7 +228,6 @@
     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");
+      check(values.find(G.id(n)) == values.end(), "Wrong id");
+      check(G.id(n) <= G.maxRedId(), "Wrong maximum id");
       values.insert(G.id(n));
     }
@@ -222,7 +241,6 @@
     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");
+      check(values.find(G.id(n)) == values.end(), "Wrong id");
+      check(G.id(n) <= G.maxBlueId(), "Wrong maximum id");
       values.insert(G.id(n));
     }
