1.1 --- a/lemon/list_graph.h Thu Nov 25 22:45:29 2010 +0100
1.2 +++ b/lemon/list_graph.h Thu Dec 01 09:05:47 2011 +0100
1.3 @@ -1647,6 +1647,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 ListBpGraphBase;
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 ListBpGraphBase;
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 ListBpGraphBase;
1.33 protected:
1.34 @@ -1692,6 +1716,9 @@
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 int maxNodeId() const { return nodes.size()-1; }
1.42 int maxRedId() const { return max_red; }
1.43 int maxBlueId() const { return max_blue; }
1.44 @@ -1701,8 +1728,12 @@
1.45 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
1.46 Node target(Arc e) const { return Node(arcs[e.id].target); }
1.47
1.48 - Node redNode(Edge e) const { return Node(arcs[2 * e.id].target); }
1.49 - Node blueNode(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
1.50 + RedNode redNode(Edge e) const {
1.51 + return RedNode(arcs[2 * e.id].target);
1.52 + }
1.53 + BlueNode blueNode(Edge e) const {
1.54 + return BlueNode(arcs[2 * e.id + 1].target);
1.55 + }
1.56
1.57 static bool direction(Arc e) {
1.58 return (e.id & 1) == 1;
1.59 @@ -1720,19 +1751,19 @@
1.60 node.id = nodes[node.id].next;
1.61 }
1.62
1.63 - void firstRed(Node& node) const {
1.64 + void first(RedNode& node) const {
1.65 node.id = first_red;
1.66 }
1.67
1.68 - void nextRed(Node& node) const {
1.69 + void next(RedNode& node) const {
1.70 node.id = nodes[node.id].partition_next;
1.71 }
1.72
1.73 - void firstBlue(Node& node) const {
1.74 + void first(BlueNode& node) const {
1.75 node.id = first_blue;
1.76 }
1.77
1.78 - void nextBlue(Node& node) const {
1.79 + void next(BlueNode& node) const {
1.80 node.id = nodes[node.id].partition_next;
1.81 }
1.82
1.83 @@ -1835,14 +1866,8 @@
1.84 }
1.85
1.86 static int id(Node v) { return v.id; }
1.87 - int redId(Node v) const {
1.88 - LEMON_DEBUG(nodes[v.id].red, "Node has to be red");
1.89 - return nodes[v.id].partition_index;
1.90 - }
1.91 - int blueId(Node v) const {
1.92 - LEMON_DEBUG(!nodes[v.id].red, "Node has to be blue");
1.93 - return nodes[v.id].partition_index;
1.94 - }
1.95 + int id(RedNode v) const { return nodes[v.id].partition_index; }
1.96 + int id(BlueNode v) const { return nodes[v.id].partition_index; }
1.97 static int id(Arc e) { return e.id; }
1.98 static int id(Edge e) { return e.id; }
1.99
1.100 @@ -1865,7 +1890,7 @@
1.101 arcs[2 * e.id].prev_out != -2;
1.102 }
1.103
1.104 - Node addRedNode() {
1.105 + RedNode addRedNode() {
1.106 int n;
1.107
1.108 if(first_free_red==-1) {
1.109 @@ -1890,10 +1915,10 @@
1.110
1.111 nodes[n].first_out = -1;
1.112
1.113 - return Node(n);
1.114 + return RedNode(n);
1.115 }
1.116
1.117 - Node addBlueNode() {
1.118 + BlueNode addBlueNode() {
1.119 int n;
1.120
1.121 if(first_free_blue==-1) {
1.122 @@ -1918,7 +1943,7 @@
1.123
1.124 nodes[n].first_out = -1;
1.125
1.126 - return Node(n);
1.127 + return BlueNode(n);
1.128 }
1.129
1.130 Edge addEdge(Node u, Node v) {
1.131 @@ -2029,8 +2054,7 @@
1.132
1.133 protected:
1.134
1.135 - void changeRed(Edge e, Node n) {
1.136 - LEMON_DEBUG(nodes[n].red, "Node has to be red");
1.137 + void changeRed(Edge e, RedNode n) {
1.138 if(arcs[(2 * e.id) | 1].next_out != -1) {
1.139 arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1.140 arcs[(2 * e.id) | 1].prev_out;
1.141 @@ -2052,9 +2076,8 @@
1.142 nodes[n.id].first_out = ((2 * e.id) | 1);
1.143 }
1.144
1.145 - void changeBlue(Edge e, Node n) {
1.146 - LEMON_DEBUG(nodes[n].red, "Node has to be blue");
1.147 - if(arcs[2 * e.id].next_out != -1) {
1.148 + void changeBlue(Edge e, BlueNode n) {
1.149 + if(arcs[2 * e.id].next_out != -1) {
1.150 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1.151 }
1.152 if(arcs[2 * e.id].prev_out != -1) {
1.153 @@ -2119,13 +2142,13 @@
1.154 ///
1.155 /// This function adds a red new node to the graph.
1.156 /// \return The new node.
1.157 - Node addRedNode() { return Parent::addRedNode(); }
1.158 + RedNode addRedNode() { return Parent::addRedNode(); }
1.159
1.160 /// \brief Add a new blue node to the graph.
1.161 ///
1.162 /// This function adds a blue new node to the graph.
1.163 /// \return The new node.
1.164 - Node addBlueNode() { return Parent::addBlueNode(); }
1.165 + BlueNode addBlueNode() { return Parent::addBlueNode(); }
1.166
1.167 /// \brief Add a new edge to the graph.
1.168 ///
1.169 @@ -2133,7 +2156,10 @@
1.170 /// \c u and \c v with inherent orientation from node \c u to
1.171 /// node \c v.
1.172 /// \return The new edge.
1.173 - Edge addEdge(Node u, Node v) {
1.174 + Edge addEdge(RedNode u, BlueNode v) {
1.175 + return Parent::addEdge(u, v);
1.176 + }
1.177 + Edge addEdge(BlueNode v, RedNode u) {
1.178 return Parent::addEdge(u, v);
1.179 }
1.180
1.181 @@ -2188,8 +2214,8 @@
1.182 ///
1.183 ///\warning This functionality cannot be used together with the
1.184 ///Snapshot feature.
1.185 - void changeRed(Edge e, Node n) {
1.186 - Parent::changeRed(e,n);
1.187 + void changeRed(Edge e, RedNode n) {
1.188 + Parent::changeRed(e, n);
1.189 }
1.190 /// \brief Change the blue node of an edge.
1.191 ///
1.192 @@ -2202,8 +2228,8 @@
1.193 ///
1.194 ///\warning This functionality cannot be used together with the
1.195 ///Snapshot feature.
1.196 - void changeBlue(Edge e, Node n) {
1.197 - Parent::changeBlue(e,n);
1.198 + void changeBlue(Edge e, BlueNode n) {
1.199 + Parent::changeBlue(e, n);
1.200 }
1.201
1.202 ///Clear the graph.