Changeset 1193:c8fa41fcc4a7 in lemon for lemon

Timestamp:

12/01/11 09:05:47 (12 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

Type safe red and blue node set (#69)

Location:

lemon

Files:

• bits/graph_extender.h (modified) (10 diffs)
• concepts/bpgraph.h (modified) (11 diffs)
• concepts/graph_components.h (modified) (18 diffs)
• core.h (modified) (12 diffs)
• full_graph.h (modified) (10 diffs)
• list_graph.h (modified) (15 diffs)
• smart_graph.h (modified) (12 diffs)

lemon/bits/graph_extender.h

@@ -761 +761 @@
 
     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 +768 @@
     // 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 +825 @@
     }
 
+    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 +914 @@
     };
 
-    class RedIt : public Node {
+    class RedIt : public RedNode {
       const BpGraph* _graph;
     public:
@@ -932 +920 @@
       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 +942 @@
       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 +1243 @@
     // Alteration extension
 
-    Node addRedNode() {
-      Node node = Parent::addRedNode();
+    RedNode addRedNode() {
+      RedNode node = Parent::addRedNode();
       notifier(RedNode()).add(node);
       notifier(Node()).add(node);
@@ -1266 +1250 @@
     }
 
-    Node addBlueNode() {
-      Node node = Parent::addBlueNode();
+    BlueNode addBlueNode() {
+      BlueNode node = Parent::addBlueNode();
       notifier(BlueNode()).add(node);
       notifier(Node()).add(node);
@@ -1273 +1257 @@
     }
 
-    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 +1302 @@
 
       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));
       }
 

lemon/concepts/bpgraph.h

@@ -150 +150 @@
         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 +177 @@
         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 +188 @@
       /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
       ///\endcode
-      class RedIt : public Node {
+      class RedIt : public RedNode {
       public:
         /// Default constructor
@@ -211 +199 @@
         /// Copy constructor.
         ///
-        RedIt(const RedIt& n) : Node(n) { }
+        RedIt(const RedIt& n) : RedNode(n) { }
         /// %Invalid constructor \& conversion.
 
@@ -226 +214 @@
         /// 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 +231 @@
       /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
       ///\endcode
-      class BlueIt : public Node {
+      class BlueIt : public BlueNode {
       public:
         /// Default constructor
@@ -254 +242 @@
         /// Copy constructor.
         ///
-        BlueIt(const BlueIt& n) : Node(n) { }
+        BlueIt(const BlueIt& n) : BlueNode(n) { }
         /// %Invalid constructor \& conversion.
 
@@ -269 +257 @@
         /// 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 +773 @@
       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 +850 @@
       ///
       /// 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 +946 @@
       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 {}

lemon/concepts/graph_components.h

@@ -318 +318 @@
       /// \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 +343 @@
         /// \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 +394 @@
       /// 
       /// 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 +454 @@
           {
             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 +633 @@
       ///
       /// 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 +638 @@
       ///
       /// 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 +662 @@
           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 +1159 @@
       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 +1178 @@
       ///
       /// 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 +1207 @@
       ///
       /// 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 +1221 @@
           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 +1817 @@
           { // 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 +1831 @@
           { // 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 +1950 @@
       typedef BAS Base;
       typedef typename Base::Node Node;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
       typedef typename Base::Edge Edge;
 
@@ -1929 +1957 @@
       ///
       /// This function adds a red new node to the digraph.
-      Node addRedNode() {
+      RedNode addRedNode() {
         return INVALID;
       }
@@ -1936 +1964 @@
       ///
       /// This function adds a blue new node to the digraph.
-      Node addBlueNode() {
+      BlueNode addBlueNode() {
         return INVALID;
       }
@@ -1945 +1973 @@
       /// 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 +1984 @@
         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);
         }
 

lemon/core.h

@@ -551 +551 @@
       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 +559 @@
     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 +584 @@
       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 +1190 @@
 
     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 +1326 @@
     BpGraphCopy& redRef(RedRef& map) {
       _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
-                          NodeRefMap, RedRef>(map));
+                          RedNodeRefMap, RedRef>(map));
       return *this;
     }
@@ -1307 +1340 @@
     BpGraphCopy& redCrossRef(RedCrossRef& map) {
       _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
-                          NodeRefMap, RedCrossRef>(map));
+                          RedNodeRefMap, RedCrossRef>(map));
       return *this;
     }
@@ -1322 +1355 @@
     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 +1377 @@
     BpGraphCopy& blueRef(BlueRef& map) {
       _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
-                           NodeRefMap, BlueRef>(map));
+                           BlueNodeRefMap, BlueRef>(map));
       return *this;
     }
@@ -1349 +1391 @@
     BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
       _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
-                           NodeRefMap, BlueCrossRef>(map));
+                           BlueNodeRefMap, BlueCrossRef>(map));
       return *this;
     }
@@ -1364 +1406 @@
     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 +1522 @@
     /// 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 +1554 @@
       _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;
 

lemon/full_graph.h

@@ -652 +652 @@
     };
 
+    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 +742 @@
     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 +760 @@
     }
 
-    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 +783 @@
     }
 
-    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 +870 @@
     }
 
-    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 +890 @@
     }
 
-    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 +1022 @@
     /// 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 +1031 @@
     ///
     /// \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 +1039 @@
     /// 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 +1048 @@
     ///
     /// \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.

lemon/list_graph.h

@@ -1648 +1648 @@
     };
 
+    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 +1717 @@
     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 +1729 @@
     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 +1752 @@
     }
 
-    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 +1867 @@
 
     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 +1891 @@
     }
 
-    Node addRedNode() {
+    RedNode addRedNode() {
       int n;
 
@@ -1891 +1916 @@
       nodes[n].first_out = -1;
 
-      return Node(n);
-    }
-
-    Node addBlueNode() {
+      return RedNode(n);
+    }
+
+    BlueNode addBlueNode() {
       int n;
 
@@ -1919 +1944 @@
       nodes[n].first_out = -1;
 
-      return Node(n);
+      return BlueNode(n);
     }
 
@@ -2030 +2055 @@
   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 +2077 @@
     }
 
-    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 +2143 @@
     /// 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 +2149 @@
     /// 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 +2157 @@
     /// 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 +2215 @@
     ///\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 +2229 @@
     ///\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);
     }
 

lemon/smart_graph.h

@@ -855 +855 @@
     };
 
+    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 +938 @@
     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 +967 @@
     }
 
-    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 +1037 @@
 
     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 +1056 @@
     }
 
-    Node addRedNode() {
+    RedNode addRedNode() {
       int n = nodes.size();
       nodes.push_back(NodeT());
@@ -1040 +1065 @@
       first_red = n;
 
-      return Node(n);
-    }
-
-    Node addBlueNode() {
+      return RedNode(n);
+    }
+
+    BlueNode addBlueNode() {
       int n = nodes.size();
       nodes.push_back(NodeT());
@@ -1052 +1077 @@
       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 +1150 @@
     /// 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 +1156 @@
     /// 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 +1164 @@
     /// 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 +1264 @@
             max_red = -1;
           }
-          Parent::notifier(RedNode()).erase(node);          
+          Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));          
         } else {
           first_blue = nodes[n].partition_next;
@@ -1246 +1272 @@
             max_blue = -1;
           }
-          Parent::notifier(BlueNode()).erase(node);
+          Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
         }
         Parent::notifier(Node()).erase(node);