1.1 --- a/lemon/smart_graph.h Thu Nov 25 22:45:29 2010 +0100
1.2 +++ b/lemon/smart_graph.h Thu Dec 01 09:05:47 2011 +0100
1.3 @@ -854,6 +854,30 @@
1.4 bool operator<(const Node& node) const {return _id < node._id;}
1.5 };
1.6
1.7 + class RedNode : public Node {
1.8 + friend class SmartBpGraphBase;
1.9 + protected:
1.10 +
1.11 + explicit RedNode(int pid) : Node(pid) {}
1.12 +
1.13 + public:
1.14 + RedNode() {}
1.15 + RedNode(const RedNode& node) : Node(node) {}
1.16 + RedNode(Invalid) : Node(INVALID){}
1.17 + };
1.18 +
1.19 + class BlueNode : public Node {
1.20 + friend class SmartBpGraphBase;
1.21 + protected:
1.22 +
1.23 + explicit BlueNode(int pid) : Node(pid) {}
1.24 +
1.25 + public:
1.26 + BlueNode() {}
1.27 + BlueNode(const BlueNode& node) : Node(node) {}
1.28 + BlueNode(Invalid) : Node(INVALID){}
1.29 + };
1.30 +
1.31 class Edge {
1.32 friend class SmartBpGraphBase;
1.33 protected:
1.34 @@ -913,11 +937,18 @@
1.35 bool red(Node n) const { return nodes[n._id].red; }
1.36 bool blue(Node n) const { return !nodes[n._id].red; }
1.37
1.38 + static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
1.39 + static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
1.40 +
1.41 Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
1.42 Node target(Arc a) const { return Node(arcs[a._id].target); }
1.43
1.44 - Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); }
1.45 - Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
1.46 + RedNode redNode(Edge e) const {
1.47 + return RedNode(arcs[2 * e._id].target);
1.48 + }
1.49 + BlueNode blueNode(Edge e) const {
1.50 + return BlueNode(arcs[2 * e._id + 1].target);
1.51 + }
1.52
1.53 static bool direction(Arc a) {
1.54 return (a._id & 1) == 1;
1.55 @@ -935,19 +966,19 @@
1.56 --node._id;
1.57 }
1.58
1.59 - void firstRed(Node& node) const {
1.60 + void first(RedNode& node) const {
1.61 node._id = first_red;
1.62 }
1.63
1.64 - void nextRed(Node& node) const {
1.65 + void next(RedNode& node) const {
1.66 node._id = nodes[node._id].partition_next;
1.67 }
1.68
1.69 - void firstBlue(Node& node) const {
1.70 + void first(BlueNode& node) const {
1.71 node._id = first_blue;
1.72 }
1.73
1.74 - void nextBlue(Node& node) const {
1.75 + void next(BlueNode& node) const {
1.76 node._id = nodes[node._id].partition_next;
1.77 }
1.78
1.79 @@ -1005,14 +1036,8 @@
1.80 }
1.81
1.82 static int id(Node v) { return v._id; }
1.83 - int redId(Node v) const {
1.84 - LEMON_DEBUG(nodes[v._id].red, "Node has to be red");
1.85 - return nodes[v._id].partition_index;
1.86 - }
1.87 - int blueId(Node v) const {
1.88 - LEMON_DEBUG(!nodes[v._id].red, "Node has to be blue");
1.89 - return nodes[v._id].partition_index;
1.90 - }
1.91 + int id(RedNode v) const { return nodes[v._id].partition_index; }
1.92 + int id(BlueNode v) const { return nodes[v._id].partition_index; }
1.93 static int id(Arc e) { return e._id; }
1.94 static int id(Edge e) { return e._id; }
1.95
1.96 @@ -1030,7 +1055,7 @@
1.97 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
1.98 }
1.99
1.100 - Node addRedNode() {
1.101 + RedNode addRedNode() {
1.102 int n = nodes.size();
1.103 nodes.push_back(NodeT());
1.104 nodes[n].first_out = -1;
1.105 @@ -1039,10 +1064,10 @@
1.106 nodes[n].partition_next = first_red;
1.107 first_red = n;
1.108
1.109 - return Node(n);
1.110 + return RedNode(n);
1.111 }
1.112
1.113 - Node addBlueNode() {
1.114 + BlueNode addBlueNode() {
1.115 int n = nodes.size();
1.116 nodes.push_back(NodeT());
1.117 nodes[n].first_out = -1;
1.118 @@ -1051,10 +1076,10 @@
1.119 nodes[n].partition_next = first_blue;
1.120 first_blue = n;
1.121
1.122 - return Node(n);
1.123 + return BlueNode(n);
1.124 }
1.125
1.126 - Edge addEdge(Node u, Node v) {
1.127 + Edge addEdge(RedNode u, BlueNode v) {
1.128 int n = arcs.size();
1.129 arcs.push_back(ArcT());
1.130 arcs.push_back(ArcT());
1.131 @@ -1124,13 +1149,13 @@
1.132 ///
1.133 /// This function adds a red new node to the graph.
1.134 /// \return The new node.
1.135 - Node addRedNode() { return Parent::addRedNode(); }
1.136 + RedNode addRedNode() { return Parent::addRedNode(); }
1.137
1.138 /// \brief Add a new blue node to the graph.
1.139 ///
1.140 /// This function adds a blue new node to the graph.
1.141 /// \return The new node.
1.142 - Node addBlueNode() { return Parent::addBlueNode(); }
1.143 + BlueNode addBlueNode() { return Parent::addBlueNode(); }
1.144
1.145 /// \brief Add a new edge to the graph.
1.146 ///
1.147 @@ -1138,10 +1163,11 @@
1.148 /// \c u and \c v with inherent orientation from node \c u to
1.149 /// node \c v.
1.150 /// \return The new edge.
1.151 - Edge addEdge(Node red, Node blue) {
1.152 - LEMON_DEBUG(Parent::red(red) && Parent::blue(blue),
1.153 - "Edge has to be formed by a red and a blue nodes");
1.154 - return Parent::addEdge(red, blue);
1.155 + Edge addEdge(RedNode u, BlueNode v) {
1.156 + return Parent::addEdge(u, v);
1.157 + }
1.158 + Edge addEdge(BlueNode v, RedNode u) {
1.159 + return Parent::addEdge(u, v);
1.160 }
1.161
1.162 /// \brief Node validity check
1.163 @@ -1237,7 +1263,7 @@
1.164 } else {
1.165 max_red = -1;
1.166 }
1.167 - Parent::notifier(RedNode()).erase(node);
1.168 + Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
1.169 } else {
1.170 first_blue = nodes[n].partition_next;
1.171 if (first_blue != -1) {
1.172 @@ -1245,7 +1271,7 @@
1.173 } else {
1.174 max_blue = -1;
1.175 }
1.176 - Parent::notifier(BlueNode()).erase(node);
1.177 + Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
1.178 }
1.179 Parent::notifier(Node()).erase(node);
1.180 nodes.pop_back();