1.1 --- a/lemon/concepts/graph_components.h Thu Nov 25 22:45:29 2010 +0100
1.2 +++ b/lemon/concepts/graph_components.h Thu Dec 01 09:05:47 2011 +0100
1.3 @@ -317,10 +317,8 @@
1.4
1.5 /// \brief Class to represent red nodes.
1.6 ///
1.7 - /// This class represents the red nodes of the graph. It does
1.8 - /// not supposed to be used directly, because the nodes can be
1.9 - /// represented as Node instances. This class can be used as
1.10 - /// template parameter for special map classes.
1.11 + /// This class represents the red nodes of the graph. The red
1.12 + /// nodes can be used also as normal nodes.
1.13 class RedNode : public Node {
1.14 typedef Node Parent;
1.15
1.16 @@ -344,21 +342,12 @@
1.17 /// It initializes the item to be invalid.
1.18 /// \sa Invalid for more details.
1.19 RedNode(Invalid) {}
1.20 -
1.21 - /// \brief Constructor for conversion from a node.
1.22 - ///
1.23 - /// Constructor for conversion from a node. The conversion can
1.24 - /// be invalid, since the Node can be member of the blue
1.25 - /// set.
1.26 - RedNode(const Node&) {}
1.27 };
1.28
1.29 /// \brief Class to represent blue nodes.
1.30 ///
1.31 - /// This class represents the blue nodes of the graph. It does
1.32 - /// not supposed to be used directly, because the nodes can be
1.33 - /// represented as Node instances. This class can be used as
1.34 - /// template parameter for special map classes.
1.35 + /// This class represents the blue nodes of the graph. The blue
1.36 + /// nodes can be used also as normal nodes.
1.37 class BlueNode : public Node {
1.38 typedef Node Parent;
1.39
1.40 @@ -404,12 +393,51 @@
1.41 /// \brief Gives back the red end node of the edge.
1.42 ///
1.43 /// Gives back the red end node of the edge.
1.44 - Node redNode(const Edge&) const { return Node(); }
1.45 + RedNode redNode(const Edge&) const { return RedNode(); }
1.46
1.47 /// \brief Gives back the blue end node of the edge.
1.48 ///
1.49 /// Gives back the blue end node of the edge.
1.50 - Node blueNode(const Edge&) const { return Node(); }
1.51 + BlueNode blueNode(const Edge&) const { return BlueNode(); }
1.52 +
1.53 + /// \brief Converts the node to red node object.
1.54 + ///
1.55 + /// This class is converts unsafely the node to red node
1.56 + /// object. It should be called only if the node is from the red
1.57 + /// partition or INVALID.
1.58 + RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
1.59 +
1.60 + /// \brief Converts the node to blue node object.
1.61 + ///
1.62 + /// This class is converts unsafely the node to blue node
1.63 + /// object. It should be called only if the node is from the red
1.64 + /// partition or INVALID.
1.65 + BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
1.66 +
1.67 + /// \brief Converts the node to red node object.
1.68 + ///
1.69 + /// This class is converts safely the node to red node
1.70 + /// object. If the node is not from the red partition, then it
1.71 + /// returns INVALID.
1.72 + RedNode asRedNode(const Node&) const { return RedNode(); }
1.73 +
1.74 + /// \brief Converts the node to blue node object.
1.75 + ///
1.76 + /// This class is converts unsafely the node to blue node
1.77 + /// object. If the node is not from the blue partition, then it
1.78 + /// returns INVALID.
1.79 + BlueNode asBlueNode(const Node&) const { return BlueNode(); }
1.80 +
1.81 + /// \brief Convert the node to either red or blue node.
1.82 + ///
1.83 + /// If the node is from the red partition then it is returned in
1.84 + /// first and second is INVALID. If the node is from the blue
1.85 + /// partition then it is returned in second and first is
1.86 + /// INVALID. If the node INVALID then both first and second are
1.87 + /// INVALID in the return value.
1.88 + std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
1.89 + return std::make_pair(RedNode(), BlueNode());
1.90 + }
1.91
1.92 template <typename _BpGraph>
1.93 struct Constraints {
1.94 @@ -425,17 +453,22 @@
1.95 checkConcept<GraphItem<'n'>, BlueNode>();
1.96 {
1.97 Node n;
1.98 - RedNode rn = n;
1.99 - BlueNode bn = bn;
1.100 + RedNode rn;
1.101 + BlueNode bn;
1.102 + Node rnan = rn;
1.103 + Node bnan = bn;
1.104 Edge e;
1.105 bool b;
1.106 - b = bpgraph.red(n);
1.107 - b = bpgraph.blue(n);
1.108 - ignore_unused_variable_warning(b);
1.109 - n = bpgraph.redNode(e);
1.110 - n = bpgraph.blueNode(e);
1.111 - rn = n;
1.112 - bn = n;
1.113 + b = bpgraph.red(rnan);
1.114 + b = bpgraph.blue(bnan);
1.115 + rn = bpgraph.redNode(e);
1.116 + bn = bpgraph.blueNode(e);
1.117 + rn = bpgraph.asRedNodeUnsafe(rnan);
1.118 + bn = bpgraph.asBlueNodeUnsafe(bnan);
1.119 + rn = bpgraph.asRedNode(rnan);
1.120 + bn = bpgraph.asBlueNode(bnan);
1.121 + std::pair<RedNode, BlueNode> p = bpgraph.asRedBlueNode(rnan);
1.122 + ignore_unused_variable_warning(b,p);
1.123 }
1.124 }
1.125
1.126 @@ -599,21 +632,11 @@
1.127 /// \brief Return a unique integer id for the given node in the red set.
1.128 ///
1.129 /// Return a unique integer id for the given node in the red set.
1.130 - int redId(const Node&) const { return -1; }
1.131 -
1.132 - /// \brief Return the same value as redId().
1.133 - ///
1.134 - /// Return the same value as redId().
1.135 int id(const RedNode&) const { return -1; }
1.136
1.137 /// \brief Return a unique integer id for the given node in the blue set.
1.138 ///
1.139 /// Return a unique integer id for the given node in the blue set.
1.140 - int blueId(const Node&) const { return -1; }
1.141 -
1.142 - /// \brief Return the same value as blueId().
1.143 - ///
1.144 - /// Return the same value as blueId().
1.145 int id(const BlueNode&) const { return -1; }
1.146
1.147 /// \brief Return an integer greater or equal to the maximum
1.148 @@ -638,10 +661,8 @@
1.149 typename _BpGraph::Node node;
1.150 typename _BpGraph::RedNode red;
1.151 typename _BpGraph::BlueNode blue;
1.152 - int rid = bpgraph.redId(node);
1.153 - int bid = bpgraph.blueId(node);
1.154 - rid = bpgraph.id(red);
1.155 - bid = bpgraph.id(blue);
1.156 + int rid = bpgraph.id(red);
1.157 + int bid = bpgraph.id(blue);
1.158 rid = bpgraph.maxRedId();
1.159 bid = bpgraph.maxBlueId();
1.160 ignore_unused_variable_warning(rid);
1.161 @@ -1137,11 +1158,15 @@
1.162
1.163 typedef BAS Base;
1.164 typedef typename Base::Node Node;
1.165 + typedef typename Base::RedNode RedNode;
1.166 + typedef typename Base::BlueNode BlueNode;
1.167 typedef typename Base::Arc Arc;
1.168 typedef typename Base::Edge Edge;
1.169 +
1.170 + typedef IterableBpGraphComponent BpGraph;
1.171
1.172 -
1.173 - typedef IterableBpGraphComponent BpGraph;
1.174 + using IterableGraphComponent<BAS>::first;
1.175 + using IterableGraphComponent<BAS>::next;
1.176
1.177 /// \name Base Iteration
1.178 ///
1.179 @@ -1152,22 +1177,22 @@
1.180 /// \brief Return the first red node.
1.181 ///
1.182 /// This function gives back the first red node in the iteration order.
1.183 - void firstRed(Node&) const {}
1.184 + void first(RedNode&) const {}
1.185
1.186 /// \brief Return the next red node.
1.187 ///
1.188 /// This function gives back the next red node in the iteration order.
1.189 - void nextRed(Node&) const {}
1.190 + void next(RedNode&) const {}
1.191
1.192 /// \brief Return the first blue node.
1.193 ///
1.194 /// This function gives back the first blue node in the iteration order.
1.195 - void firstBlue(Node&) const {}
1.196 + void first(BlueNode&) const {}
1.197
1.198 /// \brief Return the next blue node.
1.199 ///
1.200 /// This function gives back the next blue node in the iteration order.
1.201 - void nextBlue(Node&) const {}
1.202 + void next(BlueNode&) const {}
1.203
1.204
1.205 /// @}
1.206 @@ -1181,12 +1206,12 @@
1.207 /// \brief This iterator goes through each red node.
1.208 ///
1.209 /// This iterator goes through each red node.
1.210 - typedef GraphItemIt<BpGraph, Node> RedIt;
1.211 + typedef GraphItemIt<BpGraph, RedNode> RedIt;
1.212
1.213 /// \brief This iterator goes through each blue node.
1.214 ///
1.215 /// This iterator goes through each blue node.
1.216 - typedef GraphItemIt<BpGraph, Node> BlueIt;
1.217 + typedef GraphItemIt<BpGraph, BlueNode> BlueIt;
1.218
1.219 /// @}
1.220
1.221 @@ -1195,15 +1220,16 @@
1.222 void constraints() {
1.223 checkConcept<IterableGraphComponent<Base>, _BpGraph>();
1.224
1.225 - typename _BpGraph::Node node(INVALID);
1.226 - bpgraph.firstRed(node);
1.227 - bpgraph.nextRed(node);
1.228 - bpgraph.firstBlue(node);
1.229 - bpgraph.nextBlue(node);
1.230 + typename _BpGraph::RedNode rn(INVALID);
1.231 + bpgraph.first(rn);
1.232 + bpgraph.next(rn);
1.233 + typename _BpGraph::BlueNode bn(INVALID);
1.234 + bpgraph.first(bn);
1.235 + bpgraph.next(bn);
1.236
1.237 - checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
1.238 + checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
1.239 typename _BpGraph::RedIt>();
1.240 - checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
1.241 + checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
1.242 typename _BpGraph::BlueIt>();
1.243 }
1.244
1.245 @@ -1790,29 +1816,29 @@
1.246
1.247 { // int map test
1.248 typedef typename _BpGraph::template RedMap<int> IntRedMap;
1.249 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
1.250 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
1.251 IntRedMap >();
1.252 } { // bool map test
1.253 typedef typename _BpGraph::template RedMap<bool> BoolRedMap;
1.254 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
1.255 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
1.256 BoolRedMap >();
1.257 } { // Dummy map test
1.258 typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap;
1.259 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
1.260 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
1.261 DummyRedMap >();
1.262 }
1.263
1.264 { // int map test
1.265 typedef typename _BpGraph::template BlueMap<int> IntBlueMap;
1.266 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
1.267 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
1.268 IntBlueMap >();
1.269 } { // bool map test
1.270 typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap;
1.271 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
1.272 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
1.273 BoolBlueMap >();
1.274 } { // Dummy map test
1.275 typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap;
1.276 - checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
1.277 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
1.278 DummyBlueMap >();
1.279 }
1.280 }
1.281 @@ -1923,19 +1949,21 @@
1.282
1.283 typedef BAS Base;
1.284 typedef typename Base::Node Node;
1.285 + typedef typename Base::RedNode RedNode;
1.286 + typedef typename Base::BlueNode BlueNode;
1.287 typedef typename Base::Edge Edge;
1.288
1.289 /// \brief Add a new red node to the digraph.
1.290 ///
1.291 /// This function adds a red new node to the digraph.
1.292 - Node addRedNode() {
1.293 + RedNode addRedNode() {
1.294 return INVALID;
1.295 }
1.296
1.297 /// \brief Add a new blue node to the digraph.
1.298 ///
1.299 /// This function adds a blue new node to the digraph.
1.300 - Node addBlueNode() {
1.301 + BlueNode addBlueNode() {
1.302 return INVALID;
1.303 }
1.304
1.305 @@ -1944,7 +1972,10 @@
1.306 /// This function adds a new edge connecting the given two nodes
1.307 /// of the graph. The first node has to be a red node, and the
1.308 /// second one a blue node.
1.309 - Edge addEdge(const Node&, const Node&) {
1.310 + Edge addEdge(const RedNode&, const BlueNode&) {
1.311 + return INVALID;
1.312 + }
1.313 + Edge addEdge(const BlueNode&, const RedNode&) {
1.314 return INVALID;
1.315 }
1.316
1.317 @@ -1952,11 +1983,13 @@
1.318 struct Constraints {
1.319 void constraints() {
1.320 checkConcept<Base, _BpGraph>();
1.321 - typename _BpGraph::Node red_node, blue_node;
1.322 + typename _BpGraph::RedNode red_node;
1.323 + typename _BpGraph::BlueNode blue_node;
1.324 red_node = bpgraph.addRedNode();
1.325 blue_node = bpgraph.addBlueNode();
1.326 typename _BpGraph::Edge edge;
1.327 edge = bpgraph.addEdge(red_node, blue_node);
1.328 + edge = bpgraph.addEdge(blue_node, red_node);
1.329 }
1.330
1.331 _BpGraph& bpgraph;