1.1 --- a/lemon/bits/graph_extender.h Thu Nov 25 22:45:29 2010 +0100
1.2 +++ b/lemon/bits/graph_extender.h Thu Dec 01 09:05:47 2011 +0100
1.3 @@ -760,55 +760,17 @@
1.4 typedef True UndirectedTag;
1.5
1.6 typedef typename Parent::Node Node;
1.7 + typedef typename Parent::RedNode RedNode;
1.8 + typedef typename Parent::BlueNode BlueNode;
1.9 typedef typename Parent::Arc Arc;
1.10 typedef typename Parent::Edge Edge;
1.11
1.12 // BpGraph extension
1.13
1.14 - class RedNode : public Node {
1.15 - public:
1.16 - RedNode() {}
1.17 - RedNode(const RedNode& node) : Node(node) {}
1.18 - RedNode(Invalid) : Node(INVALID){}
1.19 - RedNode(const Node& node) : Node(node) {}
1.20 - };
1.21 - class BlueNode : public Node {
1.22 - public:
1.23 - BlueNode() {}
1.24 - BlueNode(const BlueNode& node) : Node(node) {}
1.25 - BlueNode(Invalid) : Node(INVALID){}
1.26 - BlueNode(const Node& node) : Node(node) {}
1.27 - };
1.28 -
1.29 using Parent::first;
1.30 using Parent::next;
1.31 -
1.32 - void first(RedNode& node) const {
1.33 - Parent::firstRed(node);
1.34 - }
1.35 -
1.36 - void next(RedNode& node) const {
1.37 - Parent::nextRed(node);
1.38 - }
1.39 -
1.40 - void first(BlueNode& node) const {
1.41 - Parent::firstBlue(node);
1.42 - }
1.43 -
1.44 - void next(BlueNode& node) const {
1.45 - Parent::nextBlue(node);
1.46 - }
1.47 -
1.48 using Parent::id;
1.49
1.50 - int id(const RedNode& node) const {
1.51 - return Parent::redId(node);
1.52 - }
1.53 -
1.54 - int id(const BlueNode& node) const {
1.55 - return Parent::blueId(node);
1.56 - }
1.57 -
1.58 int maxId(Node) const {
1.59 return Parent::maxNodeId();
1.60 }
1.61 @@ -862,6 +824,32 @@
1.62 return Parent::direct(edge, Parent::redNode(edge) == node);
1.63 }
1.64
1.65 + RedNode asRedNode(const Node& node) const {
1.66 + if (node == INVALID || Parent::blue(node)) {
1.67 + return INVALID;
1.68 + } else {
1.69 + return Parent::asRedNodeUnsafe(node);
1.70 + }
1.71 + }
1.72 +
1.73 + BlueNode asBlueNode(const Node& node) const {
1.74 + if (node == INVALID || Parent::red(node)) {
1.75 + return INVALID;
1.76 + } else {
1.77 + return Parent::asBlueNodeUnsafe(node);
1.78 + }
1.79 + }
1.80 +
1.81 + std::pair<RedNode, BlueNode> asRedBlueNode(const Node& node) const {
1.82 + if (node == INVALID) {
1.83 + return std::make_pair(RedNode(INVALID), BlueNode(INVALID));
1.84 + } else if (Parent::red(node)) {
1.85 + return std::make_pair(Parent::asRedNodeUnsafe(node), BlueNode(INVALID));
1.86 + } else {
1.87 + return std::make_pair(RedNode(INVALID), Parent::asBlueNodeUnsafe(node));
1.88 + }
1.89 + }
1.90 +
1.91 // Alterable extension
1.92
1.93 typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
1.94 @@ -925,49 +913,45 @@
1.95
1.96 };
1.97
1.98 - class RedIt : public Node {
1.99 + class RedIt : public RedNode {
1.100 const BpGraph* _graph;
1.101 public:
1.102
1.103 RedIt() {}
1.104
1.105 - RedIt(Invalid i) : Node(i) { }
1.106 + RedIt(Invalid i) : RedNode(i) { }
1.107
1.108 explicit RedIt(const BpGraph& graph) : _graph(&graph) {
1.109 - _graph->firstRed(static_cast<Node&>(*this));
1.110 + _graph->first(static_cast<RedNode&>(*this));
1.111 }
1.112
1.113 - RedIt(const BpGraph& graph, const Node& node)
1.114 - : Node(node), _graph(&graph) {
1.115 - LEMON_DEBUG(_graph->red(node), "Node has to be red.");
1.116 - }
1.117 + RedIt(const BpGraph& graph, const RedNode& node)
1.118 + : RedNode(node), _graph(&graph) {}
1.119
1.120 RedIt& operator++() {
1.121 - _graph->nextRed(*this);
1.122 + _graph->next(static_cast<RedNode&>(*this));
1.123 return *this;
1.124 }
1.125
1.126 };
1.127
1.128 - class BlueIt : public Node {
1.129 + class BlueIt : public BlueNode {
1.130 const BpGraph* _graph;
1.131 public:
1.132
1.133 BlueIt() {}
1.134
1.135 - BlueIt(Invalid i) : Node(i) { }
1.136 + BlueIt(Invalid i) : BlueNode(i) { }
1.137
1.138 explicit BlueIt(const BpGraph& graph) : _graph(&graph) {
1.139 - _graph->firstBlue(static_cast<Node&>(*this));
1.140 + _graph->first(static_cast<BlueNode&>(*this));
1.141 }
1.142
1.143 - BlueIt(const BpGraph& graph, const Node& node)
1.144 - : Node(node), _graph(&graph) {
1.145 - LEMON_DEBUG(_graph->blue(node), "Node has to be blue.");
1.146 - }
1.147 + BlueIt(const BpGraph& graph, const BlueNode& node)
1.148 + : BlueNode(node), _graph(&graph) {}
1.149
1.150 BlueIt& operator++() {
1.151 - _graph->nextBlue(*this);
1.152 + _graph->next(static_cast<BlueNode&>(*this));
1.153 return *this;
1.154 }
1.155
1.156 @@ -1258,21 +1242,21 @@
1.157
1.158 // Alteration extension
1.159
1.160 - Node addRedNode() {
1.161 - Node node = Parent::addRedNode();
1.162 + RedNode addRedNode() {
1.163 + RedNode node = Parent::addRedNode();
1.164 notifier(RedNode()).add(node);
1.165 notifier(Node()).add(node);
1.166 return node;
1.167 }
1.168
1.169 - Node addBlueNode() {
1.170 - Node node = Parent::addBlueNode();
1.171 + BlueNode addBlueNode() {
1.172 + BlueNode node = Parent::addBlueNode();
1.173 notifier(BlueNode()).add(node);
1.174 notifier(Node()).add(node);
1.175 return node;
1.176 }
1.177
1.178 - Edge addEdge(const Node& from, const Node& to) {
1.179 + Edge addEdge(const RedNode& from, const BlueNode& to) {
1.180 Edge edge = Parent::addEdge(from, to);
1.181 notifier(Edge()).add(edge);
1.182 std::vector<Arc> av;
1.183 @@ -1317,9 +1301,9 @@
1.184 }
1.185
1.186 if (Parent::red(node)) {
1.187 - notifier(RedNode()).erase(node);
1.188 + notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
1.189 } else {
1.190 - notifier(BlueNode()).erase(node);
1.191 + notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
1.192 }
1.193
1.194 notifier(Node()).erase(node);
2.1 --- a/lemon/concepts/bpgraph.h Thu Nov 25 22:45:29 2010 +0100
2.2 +++ b/lemon/concepts/bpgraph.h Thu Dec 01 09:05:47 2011 +0100
2.3 @@ -149,12 +149,6 @@
2.4 /// \sa Invalid for more details.
2.5 RedNode(Invalid) { }
2.6
2.7 - /// Constructor for conversion from a node.
2.8 -
2.9 - /// Constructor for conversion from a node. The conversion can
2.10 - /// be invalid, since the Node can be member of the blue
2.11 - /// set.
2.12 - RedNode(const Node&) {}
2.13 };
2.14
2.15 /// Class to represent blue nodes.
2.16 @@ -182,12 +176,6 @@
2.17 /// \sa Invalid for more details.
2.18 BlueNode(Invalid) { }
2.19
2.20 - /// Constructor for conversion from a node.
2.21 -
2.22 - /// Constructor for conversion from a node. The conversion can
2.23 - /// be invalid, since the Node can be member of the red
2.24 - /// set.
2.25 - BlueNode(const Node&) {}
2.26 };
2.27
2.28 /// Iterator class for the red nodes.
2.29 @@ -199,7 +187,7 @@
2.30 /// int count=0;
2.31 /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
2.32 ///\endcode
2.33 - class RedIt : public Node {
2.34 + class RedIt : public RedNode {
2.35 public:
2.36 /// Default constructor
2.37
2.38 @@ -210,7 +198,7 @@
2.39
2.40 /// Copy constructor.
2.41 ///
2.42 - RedIt(const RedIt& n) : Node(n) { }
2.43 + RedIt(const RedIt& n) : RedNode(n) { }
2.44 /// %Invalid constructor \& conversion.
2.45
2.46 /// Initializes the iterator to be invalid.
2.47 @@ -225,7 +213,7 @@
2.48
2.49 /// Sets the iterator to the given red node of the given
2.50 /// digraph.
2.51 - RedIt(const BpGraph&, const Node&) { }
2.52 + RedIt(const BpGraph&, const RedNode&) { }
2.53 /// Next node.
2.54
2.55 /// Assign the iterator to the next red node.
2.56 @@ -242,7 +230,7 @@
2.57 /// int count=0;
2.58 /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
2.59 ///\endcode
2.60 - class BlueIt : public Node {
2.61 + class BlueIt : public BlueNode {
2.62 public:
2.63 /// Default constructor
2.64
2.65 @@ -253,7 +241,7 @@
2.66
2.67 /// Copy constructor.
2.68 ///
2.69 - BlueIt(const BlueIt& n) : Node(n) { }
2.70 + BlueIt(const BlueIt& n) : BlueNode(n) { }
2.71 /// %Invalid constructor \& conversion.
2.72
2.73 /// Initializes the iterator to be invalid.
2.74 @@ -268,7 +256,7 @@
2.75
2.76 /// Sets the iterator to the given blue node of the given
2.77 /// digraph.
2.78 - BlueIt(const BpGraph&, const Node&) { }
2.79 + BlueIt(const BpGraph&, const BlueNode&) { }
2.80 /// Next node.
2.81
2.82 /// Assign the iterator to the next blue node.
2.83 @@ -784,15 +772,54 @@
2.84 /// Gives back %true for blue nodes.
2.85 bool blue(const Node&) const { return true; }
2.86
2.87 + /// \brief Converts the node to red node object.
2.88 + ///
2.89 + /// This class is converts unsafely the node to red node
2.90 + /// object. It should be called only if the node is from the red
2.91 + /// partition or INVALID.
2.92 + RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
2.93 +
2.94 + /// \brief Converts the node to blue node object.
2.95 + ///
2.96 + /// This class is converts unsafely the node to blue node
2.97 + /// object. It should be called only if the node is from the red
2.98 + /// partition or INVALID.
2.99 + BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
2.100 +
2.101 + /// \brief Converts the node to red node object.
2.102 + ///
2.103 + /// This class is converts safely the node to red node
2.104 + /// object. If the node is not from the red partition, then it
2.105 + /// returns INVALID.
2.106 + RedNode asRedNode(const Node&) const { return RedNode(); }
2.107 +
2.108 + /// \brief Converts the node to blue node object.
2.109 + ///
2.110 + /// This class is converts unsafely the node to blue node
2.111 + /// object. If the node is not from the blue partition, then it
2.112 + /// returns INVALID.
2.113 + BlueNode asBlueNode(const Node&) const { return BlueNode(); }
2.114 +
2.115 + /// \brief Convert the node to either red or blue node.
2.116 + ///
2.117 + /// If the node is from the red partition then it is returned in
2.118 + /// first and second is INVALID. If the node is from the blue
2.119 + /// partition then it is returned in second and first is
2.120 + /// INVALID. If the node INVALID then both first and second are
2.121 + /// INVALID in the return value.
2.122 + std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
2.123 + return std::make_pair(RedNode(), BlueNode());
2.124 + }
2.125 +
2.126 /// \brief Gives back the red end node of the edge.
2.127 ///
2.128 /// Gives back the red end node of the edge.
2.129 - Node redNode(const Edge&) const { return Node(); }
2.130 + RedNode redNode(const Edge&) const { return RedNode(); }
2.131
2.132 /// \brief Gives back the blue end node of the edge.
2.133 ///
2.134 /// Gives back the blue end node of the edge.
2.135 - Node blueNode(const Edge&) const { return Node(); }
2.136 + BlueNode blueNode(const Edge&) const { return BlueNode(); }
2.137
2.138 /// \brief The first node of the edge.
2.139 ///
2.140 @@ -822,21 +849,11 @@
2.141 /// \brief The red ID of the node.
2.142 ///
2.143 /// Returns the red ID of the given node.
2.144 - int redId(Node) const { return -1; }
2.145 -
2.146 - /// \brief The red ID of the node.
2.147 - ///
2.148 - /// Returns the red ID of the given node.
2.149 int id(RedNode) const { return -1; }
2.150
2.151 /// \brief The blue ID of the node.
2.152 ///
2.153 /// Returns the blue ID of the given node.
2.154 - int blueId(Node) const { return -1; }
2.155 -
2.156 - /// \brief The blue ID of the node.
2.157 - ///
2.158 - /// Returns the blue ID of the given node.
2.159 int id(BlueNode) const { return -1; }
2.160
2.161 /// \brief The ID of the edge.
2.162 @@ -928,11 +945,11 @@
2.163 void first(Node&) const {}
2.164 void next(Node&) const {}
2.165
2.166 - void firstRed(Node&) const {}
2.167 - void nextRed(Node&) const {}
2.168 + void firstRed(RedNode&) const {}
2.169 + void nextRed(RedNode&) const {}
2.170
2.171 - void firstBlue(Node&) const {}
2.172 - void nextBlue(Node&) const {}
2.173 + void firstBlue(BlueNode&) const {}
2.174 + void nextBlue(BlueNode&) const {}
2.175
2.176 void first(Edge&) const {}
2.177 void next(Edge&) const {}
3.1 --- a/lemon/concepts/graph_components.h Thu Nov 25 22:45:29 2010 +0100
3.2 +++ b/lemon/concepts/graph_components.h Thu Dec 01 09:05:47 2011 +0100
3.3 @@ -317,10 +317,8 @@
3.4
3.5 /// \brief Class to represent red nodes.
3.6 ///
3.7 - /// This class represents the red nodes of the graph. It does
3.8 - /// not supposed to be used directly, because the nodes can be
3.9 - /// represented as Node instances. This class can be used as
3.10 - /// template parameter for special map classes.
3.11 + /// This class represents the red nodes of the graph. The red
3.12 + /// nodes can be used also as normal nodes.
3.13 class RedNode : public Node {
3.14 typedef Node Parent;
3.15
3.16 @@ -344,21 +342,12 @@
3.17 /// It initializes the item to be invalid.
3.18 /// \sa Invalid for more details.
3.19 RedNode(Invalid) {}
3.20 -
3.21 - /// \brief Constructor for conversion from a node.
3.22 - ///
3.23 - /// Constructor for conversion from a node. The conversion can
3.24 - /// be invalid, since the Node can be member of the blue
3.25 - /// set.
3.26 - RedNode(const Node&) {}
3.27 };
3.28
3.29 /// \brief Class to represent blue nodes.
3.30 ///
3.31 - /// This class represents the blue nodes of the graph. It does
3.32 - /// not supposed to be used directly, because the nodes can be
3.33 - /// represented as Node instances. This class can be used as
3.34 - /// template parameter for special map classes.
3.35 + /// This class represents the blue nodes of the graph. The blue
3.36 + /// nodes can be used also as normal nodes.
3.37 class BlueNode : public Node {
3.38 typedef Node Parent;
3.39
3.40 @@ -404,12 +393,51 @@
3.41 /// \brief Gives back the red end node of the edge.
3.42 ///
3.43 /// Gives back the red end node of the edge.
3.44 - Node redNode(const Edge&) const { return Node(); }
3.45 + RedNode redNode(const Edge&) const { return RedNode(); }
3.46
3.47 /// \brief Gives back the blue end node of the edge.
3.48 ///
3.49 /// Gives back the blue end node of the edge.
3.50 - Node blueNode(const Edge&) const { return Node(); }
3.51 + BlueNode blueNode(const Edge&) const { return BlueNode(); }
3.52 +
3.53 + /// \brief Converts the node to red node object.
3.54 + ///
3.55 + /// This class is converts unsafely the node to red node
3.56 + /// object. It should be called only if the node is from the red
3.57 + /// partition or INVALID.
3.58 + RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
3.59 +
3.60 + /// \brief Converts the node to blue node object.
3.61 + ///
3.62 + /// This class is converts unsafely the node to blue node
3.63 + /// object. It should be called only if the node is from the red
3.64 + /// partition or INVALID.
3.65 + BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
3.66 +
3.67 + /// \brief Converts the node to red node object.
3.68 + ///
3.69 + /// This class is converts safely the node to red node
3.70 + /// object. If the node is not from the red partition, then it
3.71 + /// returns INVALID.
3.72 + RedNode asRedNode(const Node&) const { return RedNode(); }
3.73 +
3.74 + /// \brief Converts the node to blue node object.
3.75 + ///
3.76 + /// This class is converts unsafely the node to blue node
3.77 + /// object. If the node is not from the blue partition, then it
3.78 + /// returns INVALID.
3.79 + BlueNode asBlueNode(const Node&) const { return BlueNode(); }
3.80 +
3.81 + /// \brief Convert the node to either red or blue node.
3.82 + ///
3.83 + /// If the node is from the red partition then it is returned in
3.84 + /// first and second is INVALID. If the node is from the blue
3.85 + /// partition then it is returned in second and first is
3.86 + /// INVALID. If the node INVALID then both first and second are
3.87 + /// INVALID in the return value.
3.88 + std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
3.89 + return std::make_pair(RedNode(), BlueNode());
3.90 + }
3.91
3.92 template <typename _BpGraph>
3.93 struct Constraints {
3.94 @@ -425,17 +453,22 @@
3.95 checkConcept<GraphItem<'n'>, BlueNode>();
3.96 {
3.97 Node n;
3.98 - RedNode rn = n;
3.99 - BlueNode bn = bn;
3.100 + RedNode rn;
3.101 + BlueNode bn;
3.102 + Node rnan = rn;
3.103 + Node bnan = bn;
3.104 Edge e;
3.105 bool b;
3.106 - b = bpgraph.red(n);
3.107 - b = bpgraph.blue(n);
3.108 - ignore_unused_variable_warning(b);
3.109 - n = bpgraph.redNode(e);
3.110 - n = bpgraph.blueNode(e);
3.111 - rn = n;
3.112 - bn = n;
3.113 + b = bpgraph.red(rnan);
3.114 + b = bpgraph.blue(bnan);
3.115 + rn = bpgraph.redNode(e);
3.116 + bn = bpgraph.blueNode(e);
3.117 + rn = bpgraph.asRedNodeUnsafe(rnan);
3.118 + bn = bpgraph.asBlueNodeUnsafe(bnan);
3.119 + rn = bpgraph.asRedNode(rnan);
3.120 + bn = bpgraph.asBlueNode(bnan);
3.121 + std::pair<RedNode, BlueNode> p = bpgraph.asRedBlueNode(rnan);
3.122 + ignore_unused_variable_warning(b,p);
3.123 }
3.124 }
3.125
3.126 @@ -599,21 +632,11 @@
3.127 /// \brief Return a unique integer id for the given node in the red set.
3.128 ///
3.129 /// Return a unique integer id for the given node in the red set.
3.130 - int redId(const Node&) const { return -1; }
3.131 -
3.132 - /// \brief Return the same value as redId().
3.133 - ///
3.134 - /// Return the same value as redId().
3.135 int id(const RedNode&) const { return -1; }
3.136
3.137 /// \brief Return a unique integer id for the given node in the blue set.
3.138 ///
3.139 /// Return a unique integer id for the given node in the blue set.
3.140 - int blueId(const Node&) const { return -1; }
3.141 -
3.142 - /// \brief Return the same value as blueId().
3.143 - ///
3.144 - /// Return the same value as blueId().
3.145 int id(const BlueNode&) const { return -1; }
3.146
3.147 /// \brief Return an integer greater or equal to the maximum
3.148 @@ -638,10 +661,8 @@
3.149 typename _BpGraph::Node node;
3.150 typename _BpGraph::RedNode red;
3.151 typename _BpGraph::BlueNode blue;
3.152 - int rid = bpgraph.redId(node);
3.153 - int bid = bpgraph.blueId(node);
3.154 - rid = bpgraph.id(red);
3.155 - bid = bpgraph.id(blue);
3.156 + int rid = bpgraph.id(red);
3.157 + int bid = bpgraph.id(blue);
3.158 rid = bpgraph.maxRedId();
3.159 bid = bpgraph.maxBlueId();
3.160 ignore_unused_variable_warning(rid);
3.161 @@ -1137,11 +1158,15 @@
3.162
3.163 typedef BAS Base;
3.164 typedef typename Base::Node Node;
3.165 + typedef typename Base::RedNode RedNode;
3.166 + typedef typename Base::BlueNode BlueNode;
3.167 typedef typename Base::Arc Arc;
3.168 typedef typename Base::Edge Edge;
3.169 +
3.170 + typedef IterableBpGraphComponent BpGraph;
3.171
3.172 -
3.173 - typedef IterableBpGraphComponent BpGraph;
3.174 + using IterableGraphComponent<BAS>::first;
3.175 + using IterableGraphComponent<BAS>::next;
3.176
3.177 /// \name Base Iteration
3.178 ///
3.179 @@ -1152,22 +1177,22 @@
3.180 /// \brief Return the first red node.
3.181 ///
3.182 /// This function gives back the first red node in the iteration order.
3.183 - void firstRed(Node&) const {}
3.184 + void first(RedNode&) const {}
3.185
3.186 /// \brief Return the next red node.
3.187 ///
3.188 /// This function gives back the next red node in the iteration order.
3.189 - void nextRed(Node&) const {}
3.190 + void next(RedNode&) const {}
3.191
3.192 /// \brief Return the first blue node.
3.193 ///
3.194 /// This function gives back the first blue node in the iteration order.
3.195 - void firstBlue(Node&) const {}
3.196 + void first(BlueNode&) const {}
3.197
3.198 /// \brief Return the next blue node.
3.199 ///
3.200 /// This function gives back the next blue node in the iteration order.
3.201 - void nextBlue(Node&) const {}
3.202 + void next(BlueNode&) const {}
3.203
3.204
3.205 /// @}
3.206 @@ -1181,12 +1206,12 @@
3.207 /// \brief This iterator goes through each red node.
3.208 ///
3.209 /// This iterator goes through each red node.
3.210 - typedef GraphItemIt<BpGraph, Node> RedIt;
3.211 + typedef GraphItemIt<BpGraph, RedNode> RedIt;
3.212
3.213 /// \brief This iterator goes through each blue node.
3.214 ///
3.215 /// This iterator goes through each blue node.
3.216 - typedef GraphItemIt<BpGraph, Node> BlueIt;
3.217 + typedef GraphItemIt<BpGraph, BlueNode> BlueIt;
3.218
3.219 /// @}
3.220
3.221 @@ -1195,15 +1220,16 @@
3.222 void constraints() {
3.223 checkConcept<IterableGraphComponent<Base>, _BpGraph>();
3.224
3.225 - typename _BpGraph::Node node(INVALID);
3.226 - bpgraph.firstRed(node);
3.227 - bpgraph.nextRed(node);
3.228 - bpgraph.firstBlue(node);
3.229 - bpgraph.nextBlue(node);
3.230 + typename _BpGraph::RedNode rn(INVALID);
3.231 + bpgraph.first(rn);
3.232 + bpgraph.next(rn);
3.233 + typename _BpGraph::BlueNode bn(INVALID);
3.234 + bpgraph.first(bn);
3.235 + bpgraph.next(bn);
3.236
3.237 - checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
3.238 + checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
3.239 typename _BpGraph::RedIt>();
3.240 - checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
3.241 + checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
3.242 typename _BpGraph::BlueIt>();
3.243 }
3.244
3.245 @@ -1790,29 +1816,29 @@
3.246
3.247 { // int map test
3.248 typedef typename _BpGraph::template RedMap<int> IntRedMap;
3.249 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
3.250 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
3.251 IntRedMap >();
3.252 } { // bool map test
3.253 typedef typename _BpGraph::template RedMap<bool> BoolRedMap;
3.254 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
3.255 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
3.256 BoolRedMap >();
3.257 } { // Dummy map test
3.258 typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap;
3.259 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
3.260 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
3.261 DummyRedMap >();
3.262 }
3.263
3.264 { // int map test
3.265 typedef typename _BpGraph::template BlueMap<int> IntBlueMap;
3.266 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
3.267 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
3.268 IntBlueMap >();
3.269 } { // bool map test
3.270 typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap;
3.271 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
3.272 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
3.273 BoolBlueMap >();
3.274 } { // Dummy map test
3.275 typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap;
3.276 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
3.277 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
3.278 DummyBlueMap >();
3.279 }
3.280 }
3.281 @@ -1923,19 +1949,21 @@
3.282
3.283 typedef BAS Base;
3.284 typedef typename Base::Node Node;
3.285 + typedef typename Base::RedNode RedNode;
3.286 + typedef typename Base::BlueNode BlueNode;
3.287 typedef typename Base::Edge Edge;
3.288
3.289 /// \brief Add a new red node to the digraph.
3.290 ///
3.291 /// This function adds a red new node to the digraph.
3.292 - Node addRedNode() {
3.293 + RedNode addRedNode() {
3.294 return INVALID;
3.295 }
3.296
3.297 /// \brief Add a new blue node to the digraph.
3.298 ///
3.299 /// This function adds a blue new node to the digraph.
3.300 - Node addBlueNode() {
3.301 + BlueNode addBlueNode() {
3.302 return INVALID;
3.303 }
3.304
3.305 @@ -1944,7 +1972,10 @@
3.306 /// This function adds a new edge connecting the given two nodes
3.307 /// of the graph. The first node has to be a red node, and the
3.308 /// second one a blue node.
3.309 - Edge addEdge(const Node&, const Node&) {
3.310 + Edge addEdge(const RedNode&, const BlueNode&) {
3.311 + return INVALID;
3.312 + }
3.313 + Edge addEdge(const BlueNode&, const RedNode&) {
3.314 return INVALID;
3.315 }
3.316
3.317 @@ -1952,11 +1983,13 @@
3.318 struct Constraints {
3.319 void constraints() {
3.320 checkConcept<Base, _BpGraph>();
3.321 - typename _BpGraph::Node red_node, blue_node;
3.322 + typename _BpGraph::RedNode red_node;
3.323 + typename _BpGraph::BlueNode blue_node;
3.324 red_node = bpgraph.addRedNode();
3.325 blue_node = bpgraph.addBlueNode();
3.326 typename _BpGraph::Edge edge;
3.327 edge = bpgraph.addEdge(red_node, blue_node);
3.328 + edge = bpgraph.addEdge(blue_node, red_node);
3.329 }
3.330
3.331 _BpGraph& bpgraph;
4.1 --- a/lemon/core.h Thu Nov 25 22:45:29 2010 +0100
4.2 +++ b/lemon/core.h Thu Dec 01 09:05:47 2011 +0100
4.3 @@ -550,26 +550,30 @@
4.4 {
4.5 template <typename From, typename NodeRefMap, typename EdgeRefMap>
4.6 static void copy(const From& from, Graph &to,
4.7 - NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
4.8 + NodeRefMap& nodeRefMap,
4.9 + EdgeRefMap& edgeRefMap) {
4.10 to.build(from, nodeRefMap, edgeRefMap);
4.11 }
4.12 };
4.13
4.14 template <typename BpGraph, typename Enable = void>
4.15 struct BpGraphCopySelector {
4.16 - template <typename From, typename NodeRefMap, typename EdgeRefMap>
4.17 + template <typename From, typename RedNodeRefMap,
4.18 + typename BlueNodeRefMap, typename EdgeRefMap>
4.19 static void copy(const From& from, BpGraph &to,
4.20 - NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
4.21 + RedNodeRefMap& redNodeRefMap,
4.22 + BlueNodeRefMap& blueNodeRefMap,
4.23 + EdgeRefMap& edgeRefMap) {
4.24 to.clear();
4.25 for (typename From::RedIt it(from); it != INVALID; ++it) {
4.26 - nodeRefMap[it] = to.addRedNode();
4.27 + redNodeRefMap[it] = to.addRedNode();
4.28 }
4.29 for (typename From::BlueIt it(from); it != INVALID; ++it) {
4.30 - nodeRefMap[it] = to.addBlueNode();
4.31 + blueNodeRefMap[it] = to.addBlueNode();
4.32 }
4.33 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
4.34 - edgeRefMap[it] = to.addEdge(nodeRefMap[from.redNode(it)],
4.35 - nodeRefMap[from.blueNode(it)]);
4.36 + edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
4.37 + blueNodeRefMap[from.blueNode(it)]);
4.38 }
4.39 }
4.40 };
4.41 @@ -579,10 +583,13 @@
4.42 BpGraph,
4.43 typename enable_if<typename BpGraph::BuildTag, void>::type>
4.44 {
4.45 - template <typename From, typename NodeRefMap, typename EdgeRefMap>
4.46 + template <typename From, typename RedNodeRefMap,
4.47 + typename BlueNodeRefMap, typename EdgeRefMap>
4.48 static void copy(const From& from, BpGraph &to,
4.49 - NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
4.50 - to.build(from, nodeRefMap, edgeRefMap);
4.51 + RedNodeRefMap& redNodeRefMap,
4.52 + BlueNodeRefMap& blueNodeRefMap,
4.53 + EdgeRefMap& edgeRefMap) {
4.54 + to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
4.55 }
4.56 };
4.57
4.58 @@ -1182,12 +1189,38 @@
4.59 typedef typename From::EdgeIt EdgeIt;
4.60
4.61 typedef typename To::Node TNode;
4.62 + typedef typename To::RedNode TRedNode;
4.63 + typedef typename To::BlueNode TBlueNode;
4.64 typedef typename To::Arc TArc;
4.65 typedef typename To::Edge TEdge;
4.66
4.67 - typedef typename From::template NodeMap<TNode> NodeRefMap;
4.68 + typedef typename From::template RedMap<TRedNode> RedNodeRefMap;
4.69 + typedef typename From::template BlueMap<TBlueNode> BlueNodeRefMap;
4.70 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
4.71
4.72 + struct NodeRefMap {
4.73 + NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
4.74 + const BlueNodeRefMap& blue_node_ref)
4.75 + : _from(from), _red_node_ref(red_node_ref),
4.76 + _blue_node_ref(blue_node_ref) {}
4.77 +
4.78 + typedef typename From::Node Key;
4.79 + typedef typename To::Node Value;
4.80 +
4.81 + Value operator[](const Key& key) const {
4.82 + std::pair<RedNode, BlueNode> red_blue_pair = _from.asRedBlueNode(key);
4.83 + if (red_blue_pair.first != INVALID) {
4.84 + return _red_node_ref[red_blue_pair.first];
4.85 + } else {
4.86 + return _blue_node_ref[red_blue_pair.second];
4.87 + }
4.88 + }
4.89 +
4.90 + const From& _from;
4.91 + const RedNodeRefMap& _red_node_ref;
4.92 + const BlueNodeRefMap& _blue_node_ref;
4.93 + };
4.94 +
4.95 struct ArcRefMap {
4.96 ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
4.97 : _from(from), _to(to), _edge_ref(edge_ref) {}
4.98 @@ -1292,7 +1325,7 @@
4.99 template <typename RedRef>
4.100 BpGraphCopy& redRef(RedRef& map) {
4.101 _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
4.102 - NodeRefMap, RedRef>(map));
4.103 + RedNodeRefMap, RedRef>(map));
4.104 return *this;
4.105 }
4.106
4.107 @@ -1306,7 +1339,7 @@
4.108 template <typename RedCrossRef>
4.109 BpGraphCopy& redCrossRef(RedCrossRef& map) {
4.110 _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
4.111 - NodeRefMap, RedCrossRef>(map));
4.112 + RedNodeRefMap, RedCrossRef>(map));
4.113 return *this;
4.114 }
4.115
4.116 @@ -1321,7 +1354,16 @@
4.117 template <typename FromMap, typename ToMap>
4.118 BpGraphCopy& redMap(const FromMap& map, ToMap& tmap) {
4.119 _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
4.120 - NodeRefMap, FromMap, ToMap>(map, tmap));
4.121 + RedNodeRefMap, FromMap, ToMap>(map, tmap));
4.122 + return *this;
4.123 + }
4.124 +
4.125 + /// \brief Make a copy of the given red node.
4.126 + ///
4.127 + /// This function makes a copy of the given red node.
4.128 + BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
4.129 + _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
4.130 + RedNodeRefMap, TRedNode>(node, tnode));
4.131 return *this;
4.132 }
4.133
4.134 @@ -1334,7 +1376,7 @@
4.135 template <typename BlueRef>
4.136 BpGraphCopy& blueRef(BlueRef& map) {
4.137 _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
4.138 - NodeRefMap, BlueRef>(map));
4.139 + BlueNodeRefMap, BlueRef>(map));
4.140 return *this;
4.141 }
4.142
4.143 @@ -1348,7 +1390,7 @@
4.144 template <typename BlueCrossRef>
4.145 BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
4.146 _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
4.147 - NodeRefMap, BlueCrossRef>(map));
4.148 + BlueNodeRefMap, BlueCrossRef>(map));
4.149 return *this;
4.150 }
4.151
4.152 @@ -1363,7 +1405,16 @@
4.153 template <typename FromMap, typename ToMap>
4.154 BpGraphCopy& blueMap(const FromMap& map, ToMap& tmap) {
4.155 _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
4.156 - NodeRefMap, FromMap, ToMap>(map, tmap));
4.157 + BlueNodeRefMap, FromMap, ToMap>(map, tmap));
4.158 + return *this;
4.159 + }
4.160 +
4.161 + /// \brief Make a copy of the given blue node.
4.162 + ///
4.163 + /// This function makes a copy of the given blue node.
4.164 + BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
4.165 + _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
4.166 + BlueNodeRefMap, TBlueNode>(node, tnode));
4.167 return *this;
4.168 }
4.169
4.170 @@ -1470,19 +1521,21 @@
4.171 /// This function executes the copying of the graph along with the
4.172 /// copying of the assigned data.
4.173 void run() {
4.174 - NodeRefMap nodeRefMap(_from);
4.175 + RedNodeRefMap redNodeRefMap(_from);
4.176 + BlueNodeRefMap blueNodeRefMap(_from);
4.177 + NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
4.178 EdgeRefMap edgeRefMap(_from);
4.179 ArcRefMap arcRefMap(_from, _to, edgeRefMap);
4.180 _core_bits::BpGraphCopySelector<To>::
4.181 - copy(_from, _to, nodeRefMap, edgeRefMap);
4.182 + copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
4.183 for (int i = 0; i < int(_node_maps.size()); ++i) {
4.184 _node_maps[i]->copy(_from, nodeRefMap);
4.185 }
4.186 for (int i = 0; i < int(_red_maps.size()); ++i) {
4.187 - _red_maps[i]->copy(_from, nodeRefMap);
4.188 + _red_maps[i]->copy(_from, redNodeRefMap);
4.189 }
4.190 for (int i = 0; i < int(_blue_maps.size()); ++i) {
4.191 - _blue_maps[i]->copy(_from, nodeRefMap);
4.192 + _blue_maps[i]->copy(_from, blueNodeRefMap);
4.193 }
4.194 for (int i = 0; i < int(_edge_maps.size()); ++i) {
4.195 _edge_maps[i]->copy(_from, edgeRefMap);
4.196 @@ -1500,10 +1553,10 @@
4.197 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
4.198 _node_maps;
4.199
4.200 - std::vector<_core_bits::MapCopyBase<From, RedNode, NodeRefMap>* >
4.201 + std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
4.202 _red_maps;
4.203
4.204 - std::vector<_core_bits::MapCopyBase<From, BlueNode, NodeRefMap>* >
4.205 + std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
4.206 _blue_maps;
4.207
4.208 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
5.1 --- a/lemon/full_graph.h Thu Nov 25 22:45:29 2010 +0100
5.2 +++ b/lemon/full_graph.h Thu Dec 01 09:05:47 2011 +0100
5.3 @@ -651,6 +651,30 @@
5.4 bool operator<(const Node& node) const {return _id < node._id;}
5.5 };
5.6
5.7 + class RedNode : public Node {
5.8 + friend class FullBpGraphBase;
5.9 + protected:
5.10 +
5.11 + explicit RedNode(int pid) : Node(pid) {}
5.12 +
5.13 + public:
5.14 + RedNode() {}
5.15 + RedNode(const RedNode& node) : Node(node) {}
5.16 + RedNode(Invalid) : Node(INVALID){}
5.17 + };
5.18 +
5.19 + class BlueNode : public Node {
5.20 + friend class FullBpGraphBase;
5.21 + protected:
5.22 +
5.23 + explicit BlueNode(int pid) : Node(pid) {}
5.24 +
5.25 + public:
5.26 + BlueNode() {}
5.27 + BlueNode(const BlueNode& node) : Node(node) {}
5.28 + BlueNode(Invalid) : Node(INVALID){}
5.29 + };
5.30 +
5.31 class Edge {
5.32 friend class FullBpGraphBase;
5.33 protected:
5.34 @@ -717,6 +741,9 @@
5.35 bool red(Node n) const { return n._id < _red_num; }
5.36 bool blue(Node n) const { return n._id >= _red_num; }
5.37
5.38 + static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
5.39 + static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
5.40 +
5.41 Node source(Arc a) const {
5.42 if (a._id & 1) {
5.43 return Node((a._id >> 1) % _red_num);
5.44 @@ -732,11 +759,11 @@
5.45 }
5.46 }
5.47
5.48 - Node redNode(Edge e) const {
5.49 - return Node(e._id % _red_num);
5.50 + RedNode redNode(Edge e) const {
5.51 + return RedNode(e._id % _red_num);
5.52 }
5.53 - Node blueNode(Edge e) const {
5.54 - return Node(e._id / _red_num + _red_num);
5.55 + BlueNode blueNode(Edge e) const {
5.56 + return BlueNode(e._id / _red_num + _red_num);
5.57 }
5.58
5.59 static bool direction(Arc a) {
5.60 @@ -755,20 +782,20 @@
5.61 --node._id;
5.62 }
5.63
5.64 - void firstRed(Node& node) const {
5.65 + void first(RedNode& node) const {
5.66 node._id = _red_num - 1;
5.67 }
5.68
5.69 - static void nextRed(Node& node) {
5.70 + static void next(RedNode& node) {
5.71 --node._id;
5.72 }
5.73
5.74 - void firstBlue(Node& node) const {
5.75 + void first(BlueNode& node) const {
5.76 if (_red_num == _node_num) node._id = -1;
5.77 else node._id = _node_num - 1;
5.78 }
5.79
5.80 - void nextBlue(Node& node) const {
5.81 + void next(BlueNode& node) const {
5.82 if (node._id == _red_num) node._id = -1;
5.83 else --node._id;
5.84 }
5.85 @@ -842,15 +869,9 @@
5.86 }
5.87 }
5.88
5.89 - static int id(Node v) { return v._id; }
5.90 - int redId(Node v) const {
5.91 - LEMON_DEBUG(v._id < _red_num, "Node has to be red");
5.92 - return v._id;
5.93 - }
5.94 - int blueId(Node v) const {
5.95 - LEMON_DEBUG(v._id >= _red_num, "Node has to be blue");
5.96 - return v._id - _red_num;
5.97 - }
5.98 + static int id(const Node& v) { return v._id; }
5.99 + int id(const RedNode& v) const { return v._id; }
5.100 + int id(const BlueNode& v) const { return v._id - _red_num; }
5.101 static int id(Arc e) { return e._id; }
5.102 static int id(Edge e) { return e._id; }
5.103
5.104 @@ -868,19 +889,19 @@
5.105 return e._id >= 0 && e._id < _edge_num;
5.106 }
5.107
5.108 - Node redNode(int index) const {
5.109 - return Node(index);
5.110 + RedNode redNode(int index) const {
5.111 + return RedNode(index);
5.112 }
5.113
5.114 - int redIndex(Node n) const {
5.115 + int index(RedNode n) const {
5.116 return n._id;
5.117 }
5.118
5.119 - Node blueNode(int index) const {
5.120 - return Node(index + _red_num);
5.121 + BlueNode blueNode(int index) const {
5.122 + return BlueNode(index + _red_num);
5.123 }
5.124
5.125 - int blueIndex(Node n) const {
5.126 + int index(BlueNode n) const {
5.127 return n._id - _red_num;
5.128 }
5.129
5.130 @@ -1000,7 +1021,7 @@
5.131 /// structure is completely static, the red nodes can be indexed
5.132 /// with integers from the range <tt>[0..redNum()-1]</tt>.
5.133 /// \sa redIndex()
5.134 - Node redNode(int index) const { return Parent::redNode(index); }
5.135 + RedNode redNode(int index) const { return Parent::redNode(index); }
5.136
5.137 /// \brief Returns the index of the given red node.
5.138 ///
5.139 @@ -1009,7 +1030,7 @@
5.140 /// integers from the range <tt>[0..redNum()-1]</tt>.
5.141 ///
5.142 /// \sa operator()()
5.143 - int redIndex(Node node) const { return Parent::redIndex(node); }
5.144 + int index(RedNode node) const { return Parent::index(node); }
5.145
5.146 /// \brief Returns the blue node with the given index.
5.147 ///
5.148 @@ -1017,7 +1038,7 @@
5.149 /// structure is completely static, the blue nodes can be indexed
5.150 /// with integers from the range <tt>[0..blueNum()-1]</tt>.
5.151 /// \sa blueIndex()
5.152 - Node blueNode(int index) const { return Parent::blueNode(index); }
5.153 + BlueNode blueNode(int index) const { return Parent::blueNode(index); }
5.154
5.155 /// \brief Returns the index of the given blue node.
5.156 ///
5.157 @@ -1026,7 +1047,7 @@
5.158 /// integers from the range <tt>[0..blueNum()-1]</tt>.
5.159 ///
5.160 /// \sa operator()()
5.161 - int blueIndex(Node node) const { return Parent::blueIndex(node); }
5.162 + int index(BlueNode node) const { return Parent::index(node); }
5.163
5.164 /// \brief Returns the edge which connects the given nodes.
5.165 ///
6.1 --- a/lemon/list_graph.h Thu Nov 25 22:45:29 2010 +0100
6.2 +++ b/lemon/list_graph.h Thu Dec 01 09:05:47 2011 +0100
6.3 @@ -1647,6 +1647,30 @@
6.4 bool operator<(const Node& node) const {return id < node.id;}
6.5 };
6.6
6.7 + class RedNode : public Node {
6.8 + friend class ListBpGraphBase;
6.9 + protected:
6.10 +
6.11 + explicit RedNode(int pid) : Node(pid) {}
6.12 +
6.13 + public:
6.14 + RedNode() {}
6.15 + RedNode(const RedNode& node) : Node(node) {}
6.16 + RedNode(Invalid) : Node(INVALID){}
6.17 + };
6.18 +
6.19 + class BlueNode : public Node {
6.20 + friend class ListBpGraphBase;
6.21 + protected:
6.22 +
6.23 + explicit BlueNode(int pid) : Node(pid) {}
6.24 +
6.25 + public:
6.26 + BlueNode() {}
6.27 + BlueNode(const BlueNode& node) : Node(node) {}
6.28 + BlueNode(Invalid) : Node(INVALID){}
6.29 + };
6.30 +
6.31 class Edge {
6.32 friend class ListBpGraphBase;
6.33 protected:
6.34 @@ -1692,6 +1716,9 @@
6.35 bool red(Node n) const { return nodes[n.id].red; }
6.36 bool blue(Node n) const { return !nodes[n.id].red; }
6.37
6.38 + static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
6.39 + static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
6.40 +
6.41 int maxNodeId() const { return nodes.size()-1; }
6.42 int maxRedId() const { return max_red; }
6.43 int maxBlueId() const { return max_blue; }
6.44 @@ -1701,8 +1728,12 @@
6.45 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
6.46 Node target(Arc e) const { return Node(arcs[e.id].target); }
6.47
6.48 - Node redNode(Edge e) const { return Node(arcs[2 * e.id].target); }
6.49 - Node blueNode(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
6.50 + RedNode redNode(Edge e) const {
6.51 + return RedNode(arcs[2 * e.id].target);
6.52 + }
6.53 + BlueNode blueNode(Edge e) const {
6.54 + return BlueNode(arcs[2 * e.id + 1].target);
6.55 + }
6.56
6.57 static bool direction(Arc e) {
6.58 return (e.id & 1) == 1;
6.59 @@ -1720,19 +1751,19 @@
6.60 node.id = nodes[node.id].next;
6.61 }
6.62
6.63 - void firstRed(Node& node) const {
6.64 + void first(RedNode& node) const {
6.65 node.id = first_red;
6.66 }
6.67
6.68 - void nextRed(Node& node) const {
6.69 + void next(RedNode& node) const {
6.70 node.id = nodes[node.id].partition_next;
6.71 }
6.72
6.73 - void firstBlue(Node& node) const {
6.74 + void first(BlueNode& node) const {
6.75 node.id = first_blue;
6.76 }
6.77
6.78 - void nextBlue(Node& node) const {
6.79 + void next(BlueNode& node) const {
6.80 node.id = nodes[node.id].partition_next;
6.81 }
6.82
6.83 @@ -1835,14 +1866,8 @@
6.84 }
6.85
6.86 static int id(Node v) { return v.id; }
6.87 - int redId(Node v) const {
6.88 - LEMON_DEBUG(nodes[v.id].red, "Node has to be red");
6.89 - return nodes[v.id].partition_index;
6.90 - }
6.91 - int blueId(Node v) const {
6.92 - LEMON_DEBUG(!nodes[v.id].red, "Node has to be blue");
6.93 - return nodes[v.id].partition_index;
6.94 - }
6.95 + int id(RedNode v) const { return nodes[v.id].partition_index; }
6.96 + int id(BlueNode v) const { return nodes[v.id].partition_index; }
6.97 static int id(Arc e) { return e.id; }
6.98 static int id(Edge e) { return e.id; }
6.99
6.100 @@ -1865,7 +1890,7 @@
6.101 arcs[2 * e.id].prev_out != -2;
6.102 }
6.103
6.104 - Node addRedNode() {
6.105 + RedNode addRedNode() {
6.106 int n;
6.107
6.108 if(first_free_red==-1) {
6.109 @@ -1890,10 +1915,10 @@
6.110
6.111 nodes[n].first_out = -1;
6.112
6.113 - return Node(n);
6.114 + return RedNode(n);
6.115 }
6.116
6.117 - Node addBlueNode() {
6.118 + BlueNode addBlueNode() {
6.119 int n;
6.120
6.121 if(first_free_blue==-1) {
6.122 @@ -1918,7 +1943,7 @@
6.123
6.124 nodes[n].first_out = -1;
6.125
6.126 - return Node(n);
6.127 + return BlueNode(n);
6.128 }
6.129
6.130 Edge addEdge(Node u, Node v) {
6.131 @@ -2029,8 +2054,7 @@
6.132
6.133 protected:
6.134
6.135 - void changeRed(Edge e, Node n) {
6.136 - LEMON_DEBUG(nodes[n].red, "Node has to be red");
6.137 + void changeRed(Edge e, RedNode n) {
6.138 if(arcs[(2 * e.id) | 1].next_out != -1) {
6.139 arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
6.140 arcs[(2 * e.id) | 1].prev_out;
6.141 @@ -2052,9 +2076,8 @@
6.142 nodes[n.id].first_out = ((2 * e.id) | 1);
6.143 }
6.144
6.145 - void changeBlue(Edge e, Node n) {
6.146 - LEMON_DEBUG(nodes[n].red, "Node has to be blue");
6.147 - if(arcs[2 * e.id].next_out != -1) {
6.148 + void changeBlue(Edge e, BlueNode n) {
6.149 + if(arcs[2 * e.id].next_out != -1) {
6.150 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
6.151 }
6.152 if(arcs[2 * e.id].prev_out != -1) {
6.153 @@ -2119,13 +2142,13 @@
6.154 ///
6.155 /// This function adds a red new node to the graph.
6.156 /// \return The new node.
6.157 - Node addRedNode() { return Parent::addRedNode(); }
6.158 + RedNode addRedNode() { return Parent::addRedNode(); }
6.159
6.160 /// \brief Add a new blue node to the graph.
6.161 ///
6.162 /// This function adds a blue new node to the graph.
6.163 /// \return The new node.
6.164 - Node addBlueNode() { return Parent::addBlueNode(); }
6.165 + BlueNode addBlueNode() { return Parent::addBlueNode(); }
6.166
6.167 /// \brief Add a new edge to the graph.
6.168 ///
6.169 @@ -2133,7 +2156,10 @@
6.170 /// \c u and \c v with inherent orientation from node \c u to
6.171 /// node \c v.
6.172 /// \return The new edge.
6.173 - Edge addEdge(Node u, Node v) {
6.174 + Edge addEdge(RedNode u, BlueNode v) {
6.175 + return Parent::addEdge(u, v);
6.176 + }
6.177 + Edge addEdge(BlueNode v, RedNode u) {
6.178 return Parent::addEdge(u, v);
6.179 }
6.180
6.181 @@ -2188,8 +2214,8 @@
6.182 ///
6.183 ///\warning This functionality cannot be used together with the
6.184 ///Snapshot feature.
6.185 - void changeRed(Edge e, Node n) {
6.186 - Parent::changeRed(e,n);
6.187 + void changeRed(Edge e, RedNode n) {
6.188 + Parent::changeRed(e, n);
6.189 }
6.190 /// \brief Change the blue node of an edge.
6.191 ///
6.192 @@ -2202,8 +2228,8 @@
6.193 ///
6.194 ///\warning This functionality cannot be used together with the
6.195 ///Snapshot feature.
6.196 - void changeBlue(Edge e, Node n) {
6.197 - Parent::changeBlue(e,n);
6.198 + void changeBlue(Edge e, BlueNode n) {
6.199 + Parent::changeBlue(e, n);
6.200 }
6.201
6.202 ///Clear the graph.
7.1 --- a/lemon/smart_graph.h Thu Nov 25 22:45:29 2010 +0100
7.2 +++ b/lemon/smart_graph.h Thu Dec 01 09:05:47 2011 +0100
7.3 @@ -854,6 +854,30 @@
7.4 bool operator<(const Node& node) const {return _id < node._id;}
7.5 };
7.6
7.7 + class RedNode : public Node {
7.8 + friend class SmartBpGraphBase;
7.9 + protected:
7.10 +
7.11 + explicit RedNode(int pid) : Node(pid) {}
7.12 +
7.13 + public:
7.14 + RedNode() {}
7.15 + RedNode(const RedNode& node) : Node(node) {}
7.16 + RedNode(Invalid) : Node(INVALID){}
7.17 + };
7.18 +
7.19 + class BlueNode : public Node {
7.20 + friend class SmartBpGraphBase;
7.21 + protected:
7.22 +
7.23 + explicit BlueNode(int pid) : Node(pid) {}
7.24 +
7.25 + public:
7.26 + BlueNode() {}
7.27 + BlueNode(const BlueNode& node) : Node(node) {}
7.28 + BlueNode(Invalid) : Node(INVALID){}
7.29 + };
7.30 +
7.31 class Edge {
7.32 friend class SmartBpGraphBase;
7.33 protected:
7.34 @@ -913,11 +937,18 @@
7.35 bool red(Node n) const { return nodes[n._id].red; }
7.36 bool blue(Node n) const { return !nodes[n._id].red; }
7.37
7.38 + static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
7.39 + static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
7.40 +
7.41 Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
7.42 Node target(Arc a) const { return Node(arcs[a._id].target); }
7.43
7.44 - Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); }
7.45 - Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
7.46 + RedNode redNode(Edge e) const {
7.47 + return RedNode(arcs[2 * e._id].target);
7.48 + }
7.49 + BlueNode blueNode(Edge e) const {
7.50 + return BlueNode(arcs[2 * e._id + 1].target);
7.51 + }
7.52
7.53 static bool direction(Arc a) {
7.54 return (a._id & 1) == 1;
7.55 @@ -935,19 +966,19 @@
7.56 --node._id;
7.57 }
7.58
7.59 - void firstRed(Node& node) const {
7.60 + void first(RedNode& node) const {
7.61 node._id = first_red;
7.62 }
7.63
7.64 - void nextRed(Node& node) const {
7.65 + void next(RedNode& node) const {
7.66 node._id = nodes[node._id].partition_next;
7.67 }
7.68
7.69 - void firstBlue(Node& node) const {
7.70 + void first(BlueNode& node) const {
7.71 node._id = first_blue;
7.72 }
7.73
7.74 - void nextBlue(Node& node) const {
7.75 + void next(BlueNode& node) const {
7.76 node._id = nodes[node._id].partition_next;
7.77 }
7.78
7.79 @@ -1005,14 +1036,8 @@
7.80 }
7.81
7.82 static int id(Node v) { return v._id; }
7.83 - int redId(Node v) const {
7.84 - LEMON_DEBUG(nodes[v._id].red, "Node has to be red");
7.85 - return nodes[v._id].partition_index;
7.86 - }
7.87 - int blueId(Node v) const {
7.88 - LEMON_DEBUG(!nodes[v._id].red, "Node has to be blue");
7.89 - return nodes[v._id].partition_index;
7.90 - }
7.91 + int id(RedNode v) const { return nodes[v._id].partition_index; }
7.92 + int id(BlueNode v) const { return nodes[v._id].partition_index; }
7.93 static int id(Arc e) { return e._id; }
7.94 static int id(Edge e) { return e._id; }
7.95
7.96 @@ -1030,7 +1055,7 @@
7.97 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
7.98 }
7.99
7.100 - Node addRedNode() {
7.101 + RedNode addRedNode() {
7.102 int n = nodes.size();
7.103 nodes.push_back(NodeT());
7.104 nodes[n].first_out = -1;
7.105 @@ -1039,10 +1064,10 @@
7.106 nodes[n].partition_next = first_red;
7.107 first_red = n;
7.108
7.109 - return Node(n);
7.110 + return RedNode(n);
7.111 }
7.112
7.113 - Node addBlueNode() {
7.114 + BlueNode addBlueNode() {
7.115 int n = nodes.size();
7.116 nodes.push_back(NodeT());
7.117 nodes[n].first_out = -1;
7.118 @@ -1051,10 +1076,10 @@
7.119 nodes[n].partition_next = first_blue;
7.120 first_blue = n;
7.121
7.122 - return Node(n);
7.123 + return BlueNode(n);
7.124 }
7.125
7.126 - Edge addEdge(Node u, Node v) {
7.127 + Edge addEdge(RedNode u, BlueNode v) {
7.128 int n = arcs.size();
7.129 arcs.push_back(ArcT());
7.130 arcs.push_back(ArcT());
7.131 @@ -1124,13 +1149,13 @@
7.132 ///
7.133 /// This function adds a red new node to the graph.
7.134 /// \return The new node.
7.135 - Node addRedNode() { return Parent::addRedNode(); }
7.136 + RedNode addRedNode() { return Parent::addRedNode(); }
7.137
7.138 /// \brief Add a new blue node to the graph.
7.139 ///
7.140 /// This function adds a blue new node to the graph.
7.141 /// \return The new node.
7.142 - Node addBlueNode() { return Parent::addBlueNode(); }
7.143 + BlueNode addBlueNode() { return Parent::addBlueNode(); }
7.144
7.145 /// \brief Add a new edge to the graph.
7.146 ///
7.147 @@ -1138,10 +1163,11 @@
7.148 /// \c u and \c v with inherent orientation from node \c u to
7.149 /// node \c v.
7.150 /// \return The new edge.
7.151 - Edge addEdge(Node red, Node blue) {
7.152 - LEMON_DEBUG(Parent::red(red) && Parent::blue(blue),
7.153 - "Edge has to be formed by a red and a blue nodes");
7.154 - return Parent::addEdge(red, blue);
7.155 + Edge addEdge(RedNode u, BlueNode v) {
7.156 + return Parent::addEdge(u, v);
7.157 + }
7.158 + Edge addEdge(BlueNode v, RedNode u) {
7.159 + return Parent::addEdge(u, v);
7.160 }
7.161
7.162 /// \brief Node validity check
7.163 @@ -1237,7 +1263,7 @@
7.164 } else {
7.165 max_red = -1;
7.166 }
7.167 - Parent::notifier(RedNode()).erase(node);
7.168 + Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
7.169 } else {
7.170 first_blue = nodes[n].partition_next;
7.171 if (first_blue != -1) {
7.172 @@ -1245,7 +1271,7 @@
7.173 } else {
7.174 max_blue = -1;
7.175 }
7.176 - Parent::notifier(BlueNode()).erase(node);
7.177 + Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
7.178 }
7.179 Parent::notifier(Node()).erase(node);
7.180 nodes.pop_back();
8.1 --- a/test/bpgraph_test.cc Thu Nov 25 22:45:29 2010 +0100
8.2 +++ b/test/bpgraph_test.cc Thu Dec 01 09:05:47 2011 +0100
8.3 @@ -41,7 +41,7 @@
8.4 G.reserveNode(3);
8.5 G.reserveEdge(3);
8.6
8.7 - Node
8.8 + RedNode
8.9 rn1 = G.addRedNode();
8.10 checkGraphNodeList(G, 1);
8.11 checkGraphRedNodeList(G, 1);
8.12 @@ -49,7 +49,7 @@
8.13 checkGraphEdgeList(G, 0);
8.14 checkGraphArcList(G, 0);
8.15
8.16 - Node
8.17 + BlueNode
8.18 bn1 = G.addBlueNode(),
8.19 bn2 = G.addBlueNode();
8.20 checkGraphNodeList(G, 3);
8.21 @@ -76,7 +76,7 @@
8.22 checkGraphConArcList(G, 2);
8.23
8.24 Edge
8.25 - e2 = G.addEdge(rn1, bn1),
8.26 + e2 = G.addEdge(bn1, rn1),
8.27 e3 = G.addEdge(rn1, bn2);
8.28
8.29 checkGraphNodeList(G, 3);
8.30 @@ -112,9 +112,10 @@
8.31 TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
8.32
8.33 BpGraph G;
8.34 - Node
8.35 - n1 = G.addRedNode(), n2 = G.addBlueNode(),
8.36 - n3 = G.addBlueNode(), n4 = G.addRedNode();
8.37 + RedNode
8.38 + n1 = G.addRedNode(), n4 = G.addRedNode();
8.39 + BlueNode
8.40 + n2 = G.addBlueNode(), n3 = G.addBlueNode();
8.41 Edge
8.42 e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
8.43 e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
8.44 @@ -159,9 +160,10 @@
8.45 TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
8.46
8.47 BpGraph G;
8.48 - Node
8.49 - n1 = G.addRedNode(), n2 = G.addBlueNode(),
8.50 - n3 = G.addBlueNode(), n4 = G.addRedNode();
8.51 + RedNode
8.52 + n1 = G.addRedNode(), n4 = G.addRedNode();
8.53 + BlueNode
8.54 + n2 = G.addBlueNode(), n3 = G.addBlueNode();
8.55 Edge
8.56 e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
8.57 e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
8.58 @@ -209,8 +211,9 @@
8.59 TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
8.60
8.61 BpGraph G;
8.62 - Node
8.63 - n1 = G.addRedNode(),
8.64 + RedNode
8.65 + n1 = G.addRedNode();
8.66 + BlueNode
8.67 n2 = G.addBlueNode(),
8.68 n3 = G.addBlueNode();
8.69 Edge
8.70 @@ -225,7 +228,7 @@
8.71
8.72 typename BpGraph::Snapshot snapshot(G);
8.73
8.74 - Node n4 = G.addRedNode();
8.75 + RedNode n4 = G.addRedNode();
8.76 G.addEdge(n4, n2);
8.77 G.addEdge(n4, n3);
8.78
8.79 @@ -292,8 +295,9 @@
8.80 TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
8.81 BpGraph g;
8.82
8.83 - Node
8.84 - n1 = g.addRedNode(),
8.85 + RedNode
8.86 + n1 = g.addRedNode();
8.87 + BlueNode
8.88 n2 = g.addBlueNode(),
8.89 n3 = g.addBlueNode();
8.90
8.91 @@ -396,12 +400,12 @@
8.92
8.93 for (int i = 0; i < G.redNum(); ++i) {
8.94 check(G.red(G.redNode(i)), "Wrong node");
8.95 - check(G.redIndex(G.redNode(i)) == i, "Wrong index");
8.96 + check(G.index(G.redNode(i)) == i, "Wrong index");
8.97 }
8.98
8.99 for (int i = 0; i < G.blueNum(); ++i) {
8.100 check(G.blue(G.blueNode(i)), "Wrong node");
8.101 - check(G.blueIndex(G.blueNode(i)) == i, "Wrong index");
8.102 + check(G.index(G.blueNode(i)) == i, "Wrong index");
8.103 }
8.104
8.105 for (NodeIt u(G); u != INVALID; ++u) {
9.1 --- a/test/graph_copy_test.cc Thu Nov 25 22:45:29 2010 +0100
9.2 +++ b/test/graph_copy_test.cc Thu Dec 01 09:05:47 2011 +0100
9.3 @@ -221,24 +221,30 @@
9.4 SmartBpGraph::ArcMap<int> fam(from);
9.5 SmartBpGraph::EdgeMap<int> fem(from);
9.6 SmartBpGraph::Node fn = INVALID;
9.7 + SmartBpGraph::RedNode frn = INVALID;
9.8 + SmartBpGraph::BlueNode fbn = INVALID;
9.9 SmartBpGraph::Arc fa = INVALID;
9.10 SmartBpGraph::Edge fe = INVALID;
9.11
9.12 - std::vector<SmartBpGraph::Node> frnv;
9.13 + std::vector<SmartBpGraph::RedNode> frnv;
9.14 for (int i = 0; i < nn; ++i) {
9.15 - SmartBpGraph::Node node = from.addRedNode();
9.16 + SmartBpGraph::RedNode node = from.addRedNode();
9.17 frnv.push_back(node);
9.18 fnm[node] = i * i;
9.19 frnm[node] = i + i;
9.20 - if (i == 0) fn = node;
9.21 + if (i == 0) {
9.22 + fn = node;
9.23 + frn = node;
9.24 + }
9.25 }
9.26
9.27 - std::vector<SmartBpGraph::Node> fbnv;
9.28 + std::vector<SmartBpGraph::BlueNode> fbnv;
9.29 for (int i = 0; i < nn; ++i) {
9.30 - SmartBpGraph::Node node = from.addBlueNode();
9.31 + SmartBpGraph::BlueNode node = from.addBlueNode();
9.32 fbnv.push_back(node);
9.33 fnm[node] = i * i;
9.34 fbnm[node] = i + i;
9.35 + if (i == 0) fbn = node;
9.36 }
9.37
9.38 for (int i = 0; i < nn; ++i) {
9.39 @@ -260,18 +266,20 @@
9.40 typename GR::template ArcMap<int> tam(to);
9.41 typename GR::template EdgeMap<int> tem(to);
9.42 typename GR::Node tn;
9.43 + typename GR::RedNode trn;
9.44 + typename GR::BlueNode tbn;
9.45 typename GR::Arc ta;
9.46 typename GR::Edge te;
9.47
9.48 SmartBpGraph::NodeMap<typename GR::Node> nr(from);
9.49 - SmartBpGraph::RedMap<typename GR::Node> rnr(from);
9.50 - SmartBpGraph::BlueMap<typename GR::Node> bnr(from);
9.51 + SmartBpGraph::RedMap<typename GR::RedNode> rnr(from);
9.52 + SmartBpGraph::BlueMap<typename GR::BlueNode> bnr(from);
9.53 SmartBpGraph::ArcMap<typename GR::Arc> ar(from);
9.54 SmartBpGraph::EdgeMap<typename GR::Edge> er(from);
9.55
9.56 typename GR::template NodeMap<SmartBpGraph::Node> ncr(to);
9.57 - typename GR::template RedMap<SmartBpGraph::Node> rncr(to);
9.58 - typename GR::template BlueMap<SmartBpGraph::Node> bncr(to);
9.59 + typename GR::template RedMap<SmartBpGraph::RedNode> rncr(to);
9.60 + typename GR::template BlueMap<SmartBpGraph::BlueNode> bncr(to);
9.61 typename GR::template ArcMap<SmartBpGraph::Arc> acr(to);
9.62 typename GR::template EdgeMap<SmartBpGraph::Edge> ecr(to);
9.63
9.64 @@ -282,7 +290,8 @@
9.65 arcRef(ar).edgeRef(er).
9.66 nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr).
9.67 arcCrossRef(acr).edgeCrossRef(ecr).
9.68 - node(fn, tn).arc(fa, ta).edge(fe, te).run();
9.69 + node(fn, tn).redNode(frn, trn).blueNode(fbn, tbn).
9.70 + arc(fa, ta).edge(fe, te).run();
9.71
9.72 check(countNodes(from) == countNodes(to), "Wrong copy.");
9.73 check(countRedNodes(from) == countRedNodes(to), "Wrong copy.");
9.74 @@ -293,17 +302,24 @@
9.75 for (SmartBpGraph::NodeIt it(from); it != INVALID; ++it) {
9.76 check(ncr[nr[it]] == it, "Wrong copy.");
9.77 check(fnm[it] == tnm[nr[it]], "Wrong copy.");
9.78 - if (from.red(it)) {
9.79 - check(rnr[it] == nr[it], "Wrong copy.");
9.80 - check(rncr[rnr[it]] == it, "Wrong copy.");
9.81 - check(frnm[it] == trnm[rnr[it]], "Wrong copy.");
9.82 - check(to.red(rnr[it]), "Wrong copy.");
9.83 - } else {
9.84 - check(bnr[it] == nr[it], "Wrong copy.");
9.85 - check(bncr[bnr[it]] == it, "Wrong copy.");
9.86 - check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");
9.87 - check(to.blue(bnr[it]), "Wrong copy.");
9.88 - }
9.89 + }
9.90 +
9.91 + for (SmartBpGraph::RedIt it(from); it != INVALID; ++it) {
9.92 + check(ncr[nr[it]] == it, "Wrong copy.");
9.93 + check(fnm[it] == tnm[nr[it]], "Wrong copy.");
9.94 + check(rnr[it] == nr[it], "Wrong copy.");
9.95 + check(rncr[rnr[it]] == it, "Wrong copy.");
9.96 + check(frnm[it] == trnm[rnr[it]], "Wrong copy.");
9.97 + check(to.red(rnr[it]), "Wrong copy.");
9.98 + }
9.99 +
9.100 + for (SmartBpGraph::BlueIt it(from); it != INVALID; ++it) {
9.101 + check(ncr[nr[it]] == it, "Wrong copy.");
9.102 + check(fnm[it] == tnm[nr[it]], "Wrong copy.");
9.103 + check(bnr[it] == nr[it], "Wrong copy.");
9.104 + check(bncr[bnr[it]] == it, "Wrong copy.");
9.105 + check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");
9.106 + check(to.blue(bnr[it]), "Wrong copy.");
9.107 }
9.108
9.109 for (SmartBpGraph::ArcIt it(from); it != INVALID; ++it) {
9.110 @@ -342,6 +358,8 @@
9.111 check(er[ecr[it]] == it, "Wrong copy.");
9.112 }
9.113 check(tn == nr[fn], "Wrong copy.");
9.114 + check(trn == rnr[frn], "Wrong copy.");
9.115 + check(tbn == bnr[fbn], "Wrong copy.");
9.116 check(ta == ar[fa], "Wrong copy.");
9.117 check(te == er[fe], "Wrong copy.");
9.118
10.1 --- a/test/graph_test.h Thu Nov 25 22:45:29 2010 +0100
10.2 +++ b/test/graph_test.h Thu Dec 01 09:05:47 2011 +0100
10.3 @@ -46,6 +46,16 @@
10.4 typename Graph::RedIt n(G);
10.5 for(int i=0;i<cnt;i++) {
10.6 check(n!=INVALID,"Wrong red Node list linking.");
10.7 + check(G.red(n),"Wrong node set check.");
10.8 + check(!G.blue(n),"Wrong node set check.");
10.9 + typename Graph::Node nn = n;
10.10 + check(G.asRedNodeUnsafe(nn) == n,"Wrong node conversion.");
10.11 + check(G.asRedNode(nn) == n,"Wrong node conversion.");
10.12 + check(G.asBlueNode(nn) == INVALID,"Wrong node conversion.");
10.13 + std::pair<typename Graph::RedNode, typename Graph::BlueNode> rbn =
10.14 + G.asRedBlueNode(nn);
10.15 + check(rbn.first == n,"Wrong node conversion.");
10.16 + check(rbn.second == INVALID,"Wrong node conversion.");
10.17 ++n;
10.18 }
10.19 check(n==INVALID,"Wrong red Node list linking.");
10.20 @@ -58,6 +68,16 @@
10.21 typename Graph::BlueIt n(G);
10.22 for(int i=0;i<cnt;i++) {
10.23 check(n!=INVALID,"Wrong blue Node list linking.");
10.24 + check(G.blue(n),"Wrong node set check.");
10.25 + check(!G.red(n),"Wrong node set check.");
10.26 + typename Graph::Node nn = n;
10.27 + check(G.asBlueNodeUnsafe(nn) == n,"Wrong node conversion.");
10.28 + check(G.asBlueNode(nn) == n,"Wrong node conversion.");
10.29 + check(G.asRedNode(nn) == INVALID,"Wrong node conversion.");
10.30 + std::pair<typename Graph::RedNode, typename Graph::BlueNode> rbn =
10.31 + G.asRedBlueNode(nn);
10.32 + check(rbn.first == INVALID,"Wrong node conversion.");
10.33 + check(rbn.second == n,"Wrong node conversion.");
10.34 ++n;
10.35 }
10.36 check(n==INVALID,"Wrong blue Node list linking.");
10.37 @@ -207,9 +227,8 @@
10.38 std::set<int> values;
10.39 for (typename Graph::RedIt n(G); n != INVALID; ++n) {
10.40 check(G.red(n), "Wrong partition");
10.41 - check(G.redId(n) == G.id(RedNode(n)), "Wrong id");
10.42 - check(values.find(G.redId(n)) == values.end(), "Wrong id");
10.43 - check(G.redId(n) <= G.maxRedId(), "Wrong maximum id");
10.44 + check(values.find(G.id(n)) == values.end(), "Wrong id");
10.45 + check(G.id(n) <= G.maxRedId(), "Wrong maximum id");
10.46 values.insert(G.id(n));
10.47 }
10.48 check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id");
10.49 @@ -221,9 +240,8 @@
10.50 std::set<int> values;
10.51 for (typename Graph::BlueIt n(G); n != INVALID; ++n) {
10.52 check(G.blue(n), "Wrong partition");
10.53 - check(G.blueId(n) == G.id(BlueNode(n)), "Wrong id");
10.54 - check(values.find(G.blueId(n)) == values.end(), "Wrong id");
10.55 - check(G.blueId(n) <= G.maxBlueId(), "Wrong maximum id");
10.56 + check(values.find(G.id(n)) == values.end(), "Wrong id");
10.57 + check(G.id(n) <= G.maxBlueId(), "Wrong maximum id");
10.58 values.insert(G.id(n));
10.59 }
10.60 check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id");