315 typedef BaseDigraphComponent::Node Node; |
315 typedef BaseDigraphComponent::Node Node; |
316 typedef BaseDigraphComponent::Arc Arc; |
316 typedef BaseDigraphComponent::Arc Arc; |
317 |
317 |
318 /// \brief Class to represent red nodes. |
318 /// \brief Class to represent red nodes. |
319 /// |
319 /// |
320 /// This class represents the red nodes of the graph. It does |
320 /// This class represents the red nodes of the graph. The red |
321 /// not supposed to be used directly, because the nodes can be |
321 /// nodes can be used also as normal nodes. |
322 /// represented as Node instances. This class can be used as |
|
323 /// template parameter for special map classes. |
|
324 class RedNode : public Node { |
322 class RedNode : public Node { |
325 typedef Node Parent; |
323 typedef Node Parent; |
326 |
324 |
327 public: |
325 public: |
328 /// \brief Default constructor. |
326 /// \brief Default constructor. |
342 /// |
340 /// |
343 /// Constructor for conversion from \c INVALID. |
341 /// Constructor for conversion from \c INVALID. |
344 /// It initializes the item to be invalid. |
342 /// It initializes the item to be invalid. |
345 /// \sa Invalid for more details. |
343 /// \sa Invalid for more details. |
346 RedNode(Invalid) {} |
344 RedNode(Invalid) {} |
347 |
|
348 /// \brief Constructor for conversion from a node. |
|
349 /// |
|
350 /// Constructor for conversion from a node. The conversion can |
|
351 /// be invalid, since the Node can be member of the blue |
|
352 /// set. |
|
353 RedNode(const Node&) {} |
|
354 }; |
345 }; |
355 |
346 |
356 /// \brief Class to represent blue nodes. |
347 /// \brief Class to represent blue nodes. |
357 /// |
348 /// |
358 /// This class represents the blue nodes of the graph. It does |
349 /// This class represents the blue nodes of the graph. The blue |
359 /// not supposed to be used directly, because the nodes can be |
350 /// nodes can be used also as normal nodes. |
360 /// represented as Node instances. This class can be used as |
|
361 /// template parameter for special map classes. |
|
362 class BlueNode : public Node { |
351 class BlueNode : public Node { |
363 typedef Node Parent; |
352 typedef Node Parent; |
364 |
353 |
365 public: |
354 public: |
366 /// \brief Default constructor. |
355 /// \brief Default constructor. |
402 bool blue(const Node&) const { return true; } |
391 bool blue(const Node&) const { return true; } |
403 |
392 |
404 /// \brief Gives back the red end node of the edge. |
393 /// \brief Gives back the red end node of the edge. |
405 /// |
394 /// |
406 /// Gives back the red end node of the edge. |
395 /// Gives back the red end node of the edge. |
407 Node redNode(const Edge&) const { return Node(); } |
396 RedNode redNode(const Edge&) const { return RedNode(); } |
408 |
397 |
409 /// \brief Gives back the blue end node of the edge. |
398 /// \brief Gives back the blue end node of the edge. |
410 /// |
399 /// |
411 /// Gives back the blue end node of the edge. |
400 /// Gives back the blue end node of the edge. |
412 Node blueNode(const Edge&) const { return Node(); } |
401 BlueNode blueNode(const Edge&) const { return BlueNode(); } |
|
402 |
|
403 /// \brief Converts the node to red node object. |
|
404 /// |
|
405 /// This class is converts unsafely the node to red node |
|
406 /// object. It should be called only if the node is from the red |
|
407 /// partition or INVALID. |
|
408 RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); } |
|
409 |
|
410 /// \brief Converts the node to blue node object. |
|
411 /// |
|
412 /// This class is converts unsafely the node to blue node |
|
413 /// object. It should be called only if the node is from the red |
|
414 /// partition or INVALID. |
|
415 BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); } |
|
416 |
|
417 /// \brief Converts the node to red node object. |
|
418 /// |
|
419 /// This class is converts safely the node to red node |
|
420 /// object. If the node is not from the red partition, then it |
|
421 /// returns INVALID. |
|
422 RedNode asRedNode(const Node&) const { return RedNode(); } |
|
423 |
|
424 /// \brief Converts the node to blue node object. |
|
425 /// |
|
426 /// This class is converts unsafely the node to blue node |
|
427 /// object. If the node is not from the blue partition, then it |
|
428 /// returns INVALID. |
|
429 BlueNode asBlueNode(const Node&) const { return BlueNode(); } |
|
430 |
|
431 /// \brief Convert the node to either red or blue node. |
|
432 /// |
|
433 /// If the node is from the red partition then it is returned in |
|
434 /// first and second is INVALID. If the node is from the blue |
|
435 /// partition then it is returned in second and first is |
|
436 /// INVALID. If the node INVALID then both first and second are |
|
437 /// INVALID in the return value. |
|
438 std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const { |
|
439 return std::make_pair(RedNode(), BlueNode()); |
|
440 } |
413 |
441 |
414 template <typename _BpGraph> |
442 template <typename _BpGraph> |
415 struct Constraints { |
443 struct Constraints { |
416 typedef typename _BpGraph::Node Node; |
444 typedef typename _BpGraph::Node Node; |
417 typedef typename _BpGraph::RedNode RedNode; |
445 typedef typename _BpGraph::RedNode RedNode; |
423 checkConcept<BaseGraphComponent, _BpGraph>(); |
451 checkConcept<BaseGraphComponent, _BpGraph>(); |
424 checkConcept<GraphItem<'n'>, RedNode>(); |
452 checkConcept<GraphItem<'n'>, RedNode>(); |
425 checkConcept<GraphItem<'n'>, BlueNode>(); |
453 checkConcept<GraphItem<'n'>, BlueNode>(); |
426 { |
454 { |
427 Node n; |
455 Node n; |
428 RedNode rn = n; |
456 RedNode rn; |
429 BlueNode bn = bn; |
457 BlueNode bn; |
|
458 Node rnan = rn; |
|
459 Node bnan = bn; |
430 Edge e; |
460 Edge e; |
431 bool b; |
461 bool b; |
432 b = bpgraph.red(n); |
462 b = bpgraph.red(rnan); |
433 b = bpgraph.blue(n); |
463 b = bpgraph.blue(bnan); |
434 ignore_unused_variable_warning(b); |
464 rn = bpgraph.redNode(e); |
435 n = bpgraph.redNode(e); |
465 bn = bpgraph.blueNode(e); |
436 n = bpgraph.blueNode(e); |
466 rn = bpgraph.asRedNodeUnsafe(rnan); |
437 rn = n; |
467 bn = bpgraph.asBlueNodeUnsafe(bnan); |
438 bn = n; |
468 rn = bpgraph.asRedNode(rnan); |
|
469 bn = bpgraph.asBlueNode(bnan); |
|
470 std::pair<RedNode, BlueNode> p = bpgraph.asRedBlueNode(rnan); |
|
471 ignore_unused_variable_warning(b,p); |
439 } |
472 } |
440 } |
473 } |
441 |
474 |
442 const _BpGraph& bpgraph; |
475 const _BpGraph& bpgraph; |
443 }; |
476 }; |
597 using Parent::id; |
630 using Parent::id; |
598 |
631 |
599 /// \brief Return a unique integer id for the given node in the red set. |
632 /// \brief Return a unique integer id for the given node in the red set. |
600 /// |
633 /// |
601 /// Return a unique integer id for the given node in the red set. |
634 /// Return a unique integer id for the given node in the red set. |
602 int redId(const Node&) const { return -1; } |
|
603 |
|
604 /// \brief Return the same value as redId(). |
|
605 /// |
|
606 /// Return the same value as redId(). |
|
607 int id(const RedNode&) const { return -1; } |
635 int id(const RedNode&) const { return -1; } |
608 |
636 |
609 /// \brief Return a unique integer id for the given node in the blue set. |
637 /// \brief Return a unique integer id for the given node in the blue set. |
610 /// |
638 /// |
611 /// Return a unique integer id for the given node in the blue set. |
639 /// Return a unique integer id for the given node in the blue set. |
612 int blueId(const Node&) const { return -1; } |
|
613 |
|
614 /// \brief Return the same value as blueId(). |
|
615 /// |
|
616 /// Return the same value as blueId(). |
|
617 int id(const BlueNode&) const { return -1; } |
640 int id(const BlueNode&) const { return -1; } |
618 |
641 |
619 /// \brief Return an integer greater or equal to the maximum |
642 /// \brief Return an integer greater or equal to the maximum |
620 /// node id in the red set. |
643 /// node id in the red set. |
621 /// |
644 /// |
636 void constraints() { |
659 void constraints() { |
637 checkConcept<IDableGraphComponent<Base>, _BpGraph>(); |
660 checkConcept<IDableGraphComponent<Base>, _BpGraph>(); |
638 typename _BpGraph::Node node; |
661 typename _BpGraph::Node node; |
639 typename _BpGraph::RedNode red; |
662 typename _BpGraph::RedNode red; |
640 typename _BpGraph::BlueNode blue; |
663 typename _BpGraph::BlueNode blue; |
641 int rid = bpgraph.redId(node); |
664 int rid = bpgraph.id(red); |
642 int bid = bpgraph.blueId(node); |
665 int bid = bpgraph.id(blue); |
643 rid = bpgraph.id(red); |
|
644 bid = bpgraph.id(blue); |
|
645 rid = bpgraph.maxRedId(); |
666 rid = bpgraph.maxRedId(); |
646 bid = bpgraph.maxBlueId(); |
667 bid = bpgraph.maxBlueId(); |
647 ignore_unused_variable_warning(rid); |
668 ignore_unused_variable_warning(rid); |
648 ignore_unused_variable_warning(bid); |
669 ignore_unused_variable_warning(bid); |
649 } |
670 } |
1135 class IterableBpGraphComponent : public IterableGraphComponent<BAS> { |
1156 class IterableBpGraphComponent : public IterableGraphComponent<BAS> { |
1136 public: |
1157 public: |
1137 |
1158 |
1138 typedef BAS Base; |
1159 typedef BAS Base; |
1139 typedef typename Base::Node Node; |
1160 typedef typename Base::Node Node; |
|
1161 typedef typename Base::RedNode RedNode; |
|
1162 typedef typename Base::BlueNode BlueNode; |
1140 typedef typename Base::Arc Arc; |
1163 typedef typename Base::Arc Arc; |
1141 typedef typename Base::Edge Edge; |
1164 typedef typename Base::Edge Edge; |
1142 |
1165 |
1143 |
|
1144 typedef IterableBpGraphComponent BpGraph; |
1166 typedef IterableBpGraphComponent BpGraph; |
1145 |
1167 |
|
1168 using IterableGraphComponent<BAS>::first; |
|
1169 using IterableGraphComponent<BAS>::next; |
|
1170 |
1146 /// \name Base Iteration |
1171 /// \name Base Iteration |
1147 /// |
1172 /// |
1148 /// This interface provides functions for iteration on red and blue nodes. |
1173 /// This interface provides functions for iteration on red and blue nodes. |
1149 /// |
1174 /// |
1150 /// @{ |
1175 /// @{ |
1151 |
1176 |
1152 /// \brief Return the first red node. |
1177 /// \brief Return the first red node. |
1153 /// |
1178 /// |
1154 /// This function gives back the first red node in the iteration order. |
1179 /// This function gives back the first red node in the iteration order. |
1155 void firstRed(Node&) const {} |
1180 void first(RedNode&) const {} |
1156 |
1181 |
1157 /// \brief Return the next red node. |
1182 /// \brief Return the next red node. |
1158 /// |
1183 /// |
1159 /// This function gives back the next red node in the iteration order. |
1184 /// This function gives back the next red node in the iteration order. |
1160 void nextRed(Node&) const {} |
1185 void next(RedNode&) const {} |
1161 |
1186 |
1162 /// \brief Return the first blue node. |
1187 /// \brief Return the first blue node. |
1163 /// |
1188 /// |
1164 /// This function gives back the first blue node in the iteration order. |
1189 /// This function gives back the first blue node in the iteration order. |
1165 void firstBlue(Node&) const {} |
1190 void first(BlueNode&) const {} |
1166 |
1191 |
1167 /// \brief Return the next blue node. |
1192 /// \brief Return the next blue node. |
1168 /// |
1193 /// |
1169 /// This function gives back the next blue node in the iteration order. |
1194 /// This function gives back the next blue node in the iteration order. |
1170 void nextBlue(Node&) const {} |
1195 void next(BlueNode&) const {} |
1171 |
1196 |
1172 |
1197 |
1173 /// @} |
1198 /// @} |
1174 |
1199 |
1175 /// \name Class Based Iteration |
1200 /// \name Class Based Iteration |
1179 /// @{ |
1204 /// @{ |
1180 |
1205 |
1181 /// \brief This iterator goes through each red node. |
1206 /// \brief This iterator goes through each red node. |
1182 /// |
1207 /// |
1183 /// This iterator goes through each red node. |
1208 /// This iterator goes through each red node. |
1184 typedef GraphItemIt<BpGraph, Node> RedIt; |
1209 typedef GraphItemIt<BpGraph, RedNode> RedIt; |
1185 |
1210 |
1186 /// \brief This iterator goes through each blue node. |
1211 /// \brief This iterator goes through each blue node. |
1187 /// |
1212 /// |
1188 /// This iterator goes through each blue node. |
1213 /// This iterator goes through each blue node. |
1189 typedef GraphItemIt<BpGraph, Node> BlueIt; |
1214 typedef GraphItemIt<BpGraph, BlueNode> BlueIt; |
1190 |
1215 |
1191 /// @} |
1216 /// @} |
1192 |
1217 |
1193 template <typename _BpGraph> |
1218 template <typename _BpGraph> |
1194 struct Constraints { |
1219 struct Constraints { |
1195 void constraints() { |
1220 void constraints() { |
1196 checkConcept<IterableGraphComponent<Base>, _BpGraph>(); |
1221 checkConcept<IterableGraphComponent<Base>, _BpGraph>(); |
1197 |
1222 |
1198 typename _BpGraph::Node node(INVALID); |
1223 typename _BpGraph::RedNode rn(INVALID); |
1199 bpgraph.firstRed(node); |
1224 bpgraph.first(rn); |
1200 bpgraph.nextRed(node); |
1225 bpgraph.next(rn); |
1201 bpgraph.firstBlue(node); |
1226 typename _BpGraph::BlueNode bn(INVALID); |
1202 bpgraph.nextBlue(node); |
1227 bpgraph.first(bn); |
1203 |
1228 bpgraph.next(bn); |
1204 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>, |
1229 |
|
1230 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>, |
1205 typename _BpGraph::RedIt>(); |
1231 typename _BpGraph::RedIt>(); |
1206 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>, |
1232 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>, |
1207 typename _BpGraph::BlueIt>(); |
1233 typename _BpGraph::BlueIt>(); |
1208 } |
1234 } |
1209 |
1235 |
1210 const _BpGraph& bpgraph; |
1236 const _BpGraph& bpgraph; |
1211 }; |
1237 }; |
1788 void constraints() { |
1814 void constraints() { |
1789 checkConcept<MappableGraphComponent<Base>, _BpGraph>(); |
1815 checkConcept<MappableGraphComponent<Base>, _BpGraph>(); |
1790 |
1816 |
1791 { // int map test |
1817 { // int map test |
1792 typedef typename _BpGraph::template RedMap<int> IntRedMap; |
1818 typedef typename _BpGraph::template RedMap<int> IntRedMap; |
1793 checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>, |
1819 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>, |
1794 IntRedMap >(); |
1820 IntRedMap >(); |
1795 } { // bool map test |
1821 } { // bool map test |
1796 typedef typename _BpGraph::template RedMap<bool> BoolRedMap; |
1822 typedef typename _BpGraph::template RedMap<bool> BoolRedMap; |
1797 checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>, |
1823 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>, |
1798 BoolRedMap >(); |
1824 BoolRedMap >(); |
1799 } { // Dummy map test |
1825 } { // Dummy map test |
1800 typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap; |
1826 typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap; |
1801 checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>, |
1827 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>, |
1802 DummyRedMap >(); |
1828 DummyRedMap >(); |
1803 } |
1829 } |
1804 |
1830 |
1805 { // int map test |
1831 { // int map test |
1806 typedef typename _BpGraph::template BlueMap<int> IntBlueMap; |
1832 typedef typename _BpGraph::template BlueMap<int> IntBlueMap; |
1807 checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>, |
1833 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>, |
1808 IntBlueMap >(); |
1834 IntBlueMap >(); |
1809 } { // bool map test |
1835 } { // bool map test |
1810 typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap; |
1836 typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap; |
1811 checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>, |
1837 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>, |
1812 BoolBlueMap >(); |
1838 BoolBlueMap >(); |
1813 } { // Dummy map test |
1839 } { // Dummy map test |
1814 typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap; |
1840 typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap; |
1815 checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>, |
1841 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>, |
1816 DummyBlueMap >(); |
1842 DummyBlueMap >(); |
1817 } |
1843 } |
1818 } |
1844 } |
1819 |
1845 |
1820 const _BpGraph& bpgraph; |
1846 const _BpGraph& bpgraph; |
1921 class ExtendableBpGraphComponent : public BAS { |
1947 class ExtendableBpGraphComponent : public BAS { |
1922 public: |
1948 public: |
1923 |
1949 |
1924 typedef BAS Base; |
1950 typedef BAS Base; |
1925 typedef typename Base::Node Node; |
1951 typedef typename Base::Node Node; |
|
1952 typedef typename Base::RedNode RedNode; |
|
1953 typedef typename Base::BlueNode BlueNode; |
1926 typedef typename Base::Edge Edge; |
1954 typedef typename Base::Edge Edge; |
1927 |
1955 |
1928 /// \brief Add a new red node to the digraph. |
1956 /// \brief Add a new red node to the digraph. |
1929 /// |
1957 /// |
1930 /// This function adds a red new node to the digraph. |
1958 /// This function adds a red new node to the digraph. |
1931 Node addRedNode() { |
1959 RedNode addRedNode() { |
1932 return INVALID; |
1960 return INVALID; |
1933 } |
1961 } |
1934 |
1962 |
1935 /// \brief Add a new blue node to the digraph. |
1963 /// \brief Add a new blue node to the digraph. |
1936 /// |
1964 /// |
1937 /// This function adds a blue new node to the digraph. |
1965 /// This function adds a blue new node to the digraph. |
1938 Node addBlueNode() { |
1966 BlueNode addBlueNode() { |
1939 return INVALID; |
1967 return INVALID; |
1940 } |
1968 } |
1941 |
1969 |
1942 /// \brief Add a new edge connecting the given two nodes. |
1970 /// \brief Add a new edge connecting the given two nodes. |
1943 /// |
1971 /// |
1944 /// This function adds a new edge connecting the given two nodes |
1972 /// This function adds a new edge connecting the given two nodes |
1945 /// of the graph. The first node has to be a red node, and the |
1973 /// of the graph. The first node has to be a red node, and the |
1946 /// second one a blue node. |
1974 /// second one a blue node. |
1947 Edge addEdge(const Node&, const Node&) { |
1975 Edge addEdge(const RedNode&, const BlueNode&) { |
1948 return INVALID; |
1976 return INVALID; |
1949 } |
1977 } |
|
1978 Edge addEdge(const BlueNode&, const RedNode&) { |
|
1979 return INVALID; |
|
1980 } |
1950 |
1981 |
1951 template <typename _BpGraph> |
1982 template <typename _BpGraph> |
1952 struct Constraints { |
1983 struct Constraints { |
1953 void constraints() { |
1984 void constraints() { |
1954 checkConcept<Base, _BpGraph>(); |
1985 checkConcept<Base, _BpGraph>(); |
1955 typename _BpGraph::Node red_node, blue_node; |
1986 typename _BpGraph::RedNode red_node; |
|
1987 typename _BpGraph::BlueNode blue_node; |
1956 red_node = bpgraph.addRedNode(); |
1988 red_node = bpgraph.addRedNode(); |
1957 blue_node = bpgraph.addBlueNode(); |
1989 blue_node = bpgraph.addBlueNode(); |
1958 typename _BpGraph::Edge edge; |
1990 typename _BpGraph::Edge edge; |
1959 edge = bpgraph.addEdge(red_node, blue_node); |
1991 edge = bpgraph.addEdge(red_node, blue_node); |
|
1992 edge = bpgraph.addEdge(blue_node, red_node); |
1960 } |
1993 } |
1961 |
1994 |
1962 _BpGraph& bpgraph; |
1995 _BpGraph& bpgraph; |
1963 }; |
1996 }; |
1964 }; |
1997 }; |