1 /* -*- C++ -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 4 * 5 * Copyright (C) 2003-2008 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 8 * 9 * Permission to use, modify and distribute this software is granted 10 * provided that this copyright notice appears in all copies. For 11 * precise terms see the accompanying LICENSE file. 12 * 13 * This software is provided "AS IS" with no warranty of any kind, 14 * express or implied, and with no claim as to its suitability for any 15 * purpose. 16 * 17 */ 18 19 ///\ingroup graph_concepts 20 ///\file 21 ///\brief The concept of graph components. 22 23 24 #ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H 25 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H 26 27 #include <lemon/bits/invalid.h> 28 #include <lemon/concepts/maps.h> 29 30 #include <lemon/bits/alteration_notifier.h> 31 32 namespace lemon { 33 namespace concepts { 34 35 /// \brief Skeleton class for graph Node and Edge types 36 /// 37 /// This class describes the interface of Node and Edge (and UEdge 38 /// in undirected graphs) subtypes of graph types. 39 /// 40 /// \note This class is a template class so that we can use it to 41 /// create graph skeleton classes. The reason for this is than Node 42 /// and Edge types should \em not derive from the same base class. 43 /// For Node you should instantiate it with character 'n' and for Edge 44 /// with 'e'. 45 46 #ifndef DOXYGEN 47 template <char _selector = '0'> 48 #endif 49 class GraphItem { 50 public: 51 /// \brief Default constructor. 52 /// 53 /// \warning The default constructor is not required to set 54 /// the item to some well-defined value. So you should consider it 55 /// as uninitialized. GraphItem()56 GraphItem() {} 57 /// \brief Copy constructor. 58 /// 59 /// Copy constructor. 60 /// GraphItem(const GraphItem &)61 GraphItem(const GraphItem &) {} 62 /// \brief Invalid constructor \& conversion. 63 /// 64 /// This constructor initializes the item to be invalid. 65 /// \sa Invalid for more details. GraphItem(Invalid)66 GraphItem(Invalid) {} 67 /// \brief Assign operator for nodes. 68 /// 69 /// The nodes are assignable. 70 /// 71 GraphItem& operator=(GraphItem const&) { return *this; } 72 /// \brief Equality operator. 73 /// 74 /// Two iterators are equal if and only if they represents the 75 /// same node in the graph or both are invalid. 76 bool operator==(GraphItem) const { return false; } 77 /// \brief Inequality operator. 78 /// 79 /// \sa operator==(const Node& n) 80 /// 81 bool operator!=(GraphItem) const { return false; } 82 83 /// \brief Artificial ordering operator. 84 /// 85 /// To allow the use of graph descriptors as key type in std::map or 86 /// similar associative container we require this. 87 /// 88 /// \note This operator only have to define some strict ordering of 89 /// the items; this order has nothing to do with the iteration 90 /// ordering of the items. 91 bool operator<(GraphItem) const { return false; } 92 93 template<typename _GraphItem> 94 struct Constraints { constraintsConstraints95 void constraints() { 96 _GraphItem i1; 97 _GraphItem i2 = i1; 98 _GraphItem i3 = INVALID; 99 100 i1 = i2 = i3; 101 102 bool b; 103 // b = (ia == ib) && (ia != ib) && (ia < ib); 104 b = (ia == ib) && (ia != ib); 105 b = (ia == INVALID) && (ib != INVALID); 106 b = (ia < ib); 107 } 108 109 const _GraphItem &ia; 110 const _GraphItem &ib; 111 }; 112 }; 113 114 /// \brief An empty base graph class. 115 /// 116 /// This class provides the minimal set of features needed for a graph 117 /// structure. All graph concepts have to be conform to this base 118 /// graph. It just provides types for nodes and edges and functions to 119 /// get the source and the target of the edges. 120 class BaseGraphComponent { 121 public: 122 123 typedef BaseGraphComponent Graph; 124 125 /// \brief Node class of the graph. 126 /// 127 /// This class represents the Nodes of the graph. 128 /// 129 typedef GraphItem<'n'> Node; 130 131 /// \brief Edge class of the graph. 132 /// 133 /// This class represents the Edges of the graph. 134 /// 135 typedef GraphItem<'e'> Edge; 136 137 /// \brief Gives back the target node of an edge. 138 /// 139 /// Gives back the target node of an edge. 140 /// target(const Edge &)141 Node target(const Edge&) const { return INVALID;} 142 143 /// \brief Gives back the source node of an edge. 144 /// 145 /// Gives back the source node of an edge. 146 /// source(const Edge &)147 Node source(const Edge&) const { return INVALID;} 148 149 /// \brief Gives back the opposite node on the given edge. 150 /// 151 /// Gives back the opposite node on the given edge. oppositeNode(const Node &,const Edge &)152 Node oppositeNode(const Node&, const Edge&) const { 153 return INVALID; 154 } 155 156 template <typename _Graph> 157 struct Constraints { 158 typedef typename _Graph::Node Node; 159 typedef typename _Graph::Edge Edge; 160 constraintsConstraints161 void constraints() { 162 checkConcept<GraphItem<'n'>, Node>(); 163 checkConcept<GraphItem<'e'>, Edge>(); 164 { 165 Node n; 166 Edge e(INVALID); 167 n = graph.source(e); 168 n = graph.target(e); 169 n = graph.oppositeNode(n, e); 170 } 171 } 172 173 const _Graph& graph; 174 }; 175 }; 176 177 /// \brief An empty base undirected graph class. 178 /// 179 /// This class provides the minimal set of features needed for an 180 /// undirected graph structure. All undirected graph concepts have 181 /// to be conform to this base graph. It just provides types for 182 /// nodes, edges and undirected edges and functions to get the 183 /// source and the target of the edges and undirected edges, 184 /// conversion from edges to undirected edges and function to get 185 /// both direction of the undirected edges. 186 class BaseUGraphComponent : public BaseGraphComponent { 187 public: 188 typedef BaseGraphComponent::Node Node; 189 typedef BaseGraphComponent::Edge Edge; 190 /// \brief Undirected edge class of the graph. 191 /// 192 /// This class represents the undirected edges of the graph. 193 /// The undirected graphs can be used as a directed graph which 194 /// for each edge contains the opposite edge too so the graph is 195 /// bidirected. The undirected edge represents two opposite 196 /// directed edges. 197 class UEdge : public GraphItem<'u'> { 198 public: 199 typedef GraphItem<'u'> Parent; 200 /// \brief Default constructor. 201 /// 202 /// \warning The default constructor is not required to set 203 /// the item to some well-defined value. So you should consider it 204 /// as uninitialized. UEdge()205 UEdge() {} 206 /// \brief Copy constructor. 207 /// 208 /// Copy constructor. 209 /// UEdge(const UEdge &)210 UEdge(const UEdge &) : Parent() {} 211 /// \brief Invalid constructor \& conversion. 212 /// 213 /// This constructor initializes the item to be invalid. 214 /// \sa Invalid for more details. UEdge(Invalid)215 UEdge(Invalid) {} 216 /// \brief Converter from edge to undirected edge. 217 /// 218 /// Besides the core graph item functionality each edge should 219 /// be convertible to the represented undirected edge. UEdge(const Edge &)220 UEdge(const Edge&) {} 221 /// \brief Assign edge to undirected edge. 222 /// 223 /// Besides the core graph item functionality each edge should 224 /// be convertible to the represented undirected edge. 225 UEdge& operator=(const Edge&) { return *this; } 226 }; 227 228 /// \brief Returns the direction of the edge. 229 /// 230 /// Returns the direction of the edge. Each edge represents an 231 /// undirected edge with a direction. It gives back the 232 /// direction. direction(const Edge &)233 bool direction(const Edge&) const { return true; } 234 235 /// \brief Returns the directed edge. 236 /// 237 /// Returns the directed edge from its direction and the 238 /// represented undirected edge. direct(const UEdge &,bool)239 Edge direct(const UEdge&, bool) const { return INVALID;} 240 241 /// \brief Returns the directed edge. 242 /// 243 /// Returns the directed edge from its source and the 244 /// represented undirected edge. direct(const UEdge &,const Node &)245 Edge direct(const UEdge&, const Node&) const { return INVALID;} 246 247 /// \brief Returns the opposite edge. 248 /// 249 /// Returns the opposite edge. It is the edge representing the 250 /// same undirected edge and has opposite direction. oppositeEdge(const Edge &)251 Edge oppositeEdge(const Edge&) const { return INVALID;} 252 253 /// \brief Gives back the target node of an undirected edge. 254 /// 255 /// Gives back the target node of an undirected edge. The name 256 /// target is a little confusing because the undirected edge 257 /// does not have target but it just means that one of the end 258 /// node. target(const UEdge &)259 Node target(const UEdge&) const { return INVALID;} 260 261 /// \brief Gives back the source node of an undirected edge. 262 /// 263 /// Gives back the source node of an undirected edge. The name 264 /// source is a little confusing because the undirected edge 265 /// does not have source but it just means that one of the end 266 /// node. source(const UEdge &)267 Node source(const UEdge&) const { return INVALID;} 268 269 template <typename _Graph> 270 struct Constraints { 271 typedef typename _Graph::Node Node; 272 typedef typename _Graph::Edge Edge; 273 typedef typename _Graph::UEdge UEdge; 274 constraintsConstraints275 void constraints() { 276 checkConcept<BaseGraphComponent, _Graph>(); 277 checkConcept<GraphItem<'u'>, UEdge>(); 278 { 279 Node n; 280 UEdge ue(INVALID); 281 Edge e; 282 n = graph.source(ue); 283 n = graph.target(ue); 284 e = graph.direct(ue, true); 285 e = graph.direct(ue, n); 286 e = graph.oppositeEdge(e); 287 ue = e; 288 bool d = graph.direction(e); 289 ignore_unused_variable_warning(d); 290 } 291 } 292 293 const _Graph& graph; 294 }; 295 296 }; 297 298 /// \brief An empty base bipartite undirected graph class. 299 /// 300 /// This class provides the minimal set of features needed for an 301 /// bipartite undirected graph structure. All bipartite undirected 302 /// graph concepts have to be conform to this base graph. It just 303 /// provides types for nodes, A-nodes, B-nodes, edges and 304 /// undirected edges and functions to get the source and the 305 /// target of the edges and undirected edges, conversion from 306 /// edges to undirected edges and function to get both direction 307 /// of the undirected edges. 308 class BaseBpUGraphComponent : public BaseUGraphComponent { 309 public: 310 typedef BaseUGraphComponent::Node Node; 311 typedef BaseUGraphComponent::Edge Edge; 312 typedef BaseUGraphComponent::UEdge UEdge; 313 314 /// \brief Helper class for A-nodes. 315 /// 316 /// This class is just a helper class for A-nodes, it is not 317 /// suggested to use it directly. It can be converted easily to 318 /// node and vice versa. The usage of this class is limited 319 /// to use just as template parameters for special map types. 320 class ANode : public Node { 321 public: 322 typedef Node Parent; 323 324 /// \brief Default constructor. 325 /// 326 /// \warning The default constructor is not required to set 327 /// the item to some well-defined value. So you should consider it 328 /// as uninitialized. ANode()329 ANode() {} 330 /// \brief Copy constructor. 331 /// 332 /// Copy constructor. 333 /// ANode(const ANode &)334 ANode(const ANode &) : Parent() {} 335 /// \brief Invalid constructor \& conversion. 336 /// 337 /// This constructor initializes the item to be invalid. 338 /// \sa Invalid for more details. ANode(Invalid)339 ANode(Invalid) {} 340 /// \brief Converter from node to A-node. 341 /// 342 /// Besides the core graph item functionality each node should 343 /// be convertible to the represented A-node if it is it possible. ANode(const Node &)344 ANode(const Node&) {} 345 /// \brief Assign node to A-node. 346 /// 347 /// Besides the core graph item functionality each node should 348 /// be convertible to the represented A-node if it is it possible. 349 ANode& operator=(const Node&) { return *this; } 350 }; 351 352 /// \brief Helper class for B-nodes. 353 /// 354 /// This class is just a helper class for B-nodes, it is not 355 /// suggested to use it directly. It can be converted easily to 356 /// node and vice versa. The usage of this class is limited 357 /// to use just as template parameters for special map types. 358 class BNode : public Node { 359 public: 360 typedef Node Parent; 361 362 /// \brief Default constructor. 363 /// 364 /// \warning The default constructor is not required to set 365 /// the item to some well-defined value. So you should consider it 366 /// as uninitialized. BNode()367 BNode() {} 368 /// \brief Copy constructor. 369 /// 370 /// Copy constructor. 371 /// BNode(const BNode &)372 BNode(const BNode &) : Parent() {} 373 /// \brief Invalid constructor \& conversion. 374 /// 375 /// This constructor initializes the item to be invalid. 376 /// \sa Invalid for more details. BNode(Invalid)377 BNode(Invalid) {} 378 /// \brief Converter from node to B-node. 379 /// 380 /// Besides the core graph item functionality each node should 381 /// be convertible to the represented B-node if it is it possible. BNode(const Node &)382 BNode(const Node&) {} 383 /// \brief Assign node to B-node. 384 /// 385 /// Besides the core graph item functionality each node should 386 /// be convertible to the represented B-node if it is it possible. 387 BNode& operator=(const Node&) { return *this; } 388 }; 389 390 /// \brief Gives back %true when the node is A-node. 391 /// 392 /// Gives back %true when the node is A-node. aNode(const Node &)393 bool aNode(const Node&) const { return false; } 394 395 /// \brief Gives back %true when the node is B-node. 396 /// 397 /// Gives back %true when the node is B-node. bNode(const Node &)398 bool bNode(const Node&) const { return false; } 399 400 /// \brief Gives back the A-node of the undirected edge. 401 /// 402 /// Gives back the A-node of the undirected edge. aNode(const UEdge &)403 Node aNode(const UEdge&) const { return INVALID; } 404 405 /// \brief Gives back the B-node of the undirected edge. 406 /// 407 /// Gives back the B-node of the undirected edge. bNode(const UEdge &)408 Node bNode(const UEdge&) const { return INVALID; } 409 410 template <typename _Graph> 411 struct Constraints { 412 typedef typename _Graph::Node Node; 413 typedef typename _Graph::ANode ANode; 414 typedef typename _Graph::BNode BNode; 415 typedef typename _Graph::Edge Edge; 416 typedef typename _Graph::UEdge UEdge; 417 constraintsConstraints418 void constraints() { 419 checkConcept<BaseUGraphComponent, _Graph>(); 420 checkConcept<GraphItem<'a'>, ANode>(); 421 checkConcept<GraphItem<'b'>, BNode>(); 422 { 423 Node n; 424 UEdge ue(INVALID); 425 bool b; 426 n = graph.aNode(ue); 427 n = graph.bNode(ue); 428 b = graph.aNode(n); 429 b = graph.bNode(n); 430 ANode an; 431 an = n; n = an; 432 BNode bn; 433 bn = n; n = bn; 434 ignore_unused_variable_warning(b); 435 } 436 } 437 438 const _Graph& graph; 439 }; 440 441 }; 442 443 /// \brief An empty idable base graph class. 444 /// 445 /// This class provides beside the core graph features 446 /// core id functions for the graph structure. 447 /// The most of the base graphs should be conform to this concept. 448 /// The id's are unique and immutable. 449 template <typename _Base = BaseGraphComponent> 450 class IDableGraphComponent : public _Base { 451 public: 452 453 typedef _Base Base; 454 typedef typename Base::Node Node; 455 typedef typename Base::Edge Edge; 456 457 /// \brief Gives back an unique integer id for the Node. 458 /// 459 /// Gives back an unique integer id for the Node. 460 /// id(const Node &)461 int id(const Node&) const { return -1;} 462 463 /// \brief Gives back the node by the unique id. 464 /// 465 /// Gives back the node by the unique id. 466 /// If the graph does not contain node with the given id 467 /// then the result of the function is undetermined. nodeFromId(int)468 Node nodeFromId(int) const { return INVALID;} 469 470 /// \brief Gives back an unique integer id for the Edge. 471 /// 472 /// Gives back an unique integer id for the Edge. 473 /// id(const Edge &)474 int id(const Edge&) const { return -1;} 475 476 /// \brief Gives back the edge by the unique id. 477 /// 478 /// Gives back the edge by the unique id. 479 /// If the graph does not contain edge with the given id 480 /// then the result of the function is undetermined. edgeFromId(int)481 Edge edgeFromId(int) const { return INVALID;} 482 483 /// \brief Gives back an integer greater or equal to the maximum 484 /// Node id. 485 /// 486 /// Gives back an integer greater or equal to the maximum Node 487 /// id. maxNodeId()488 int maxNodeId() const { return -1;} 489 490 /// \brief Gives back an integer greater or equal to the maximum 491 /// Edge id. 492 /// 493 /// Gives back an integer greater or equal to the maximum Edge 494 /// id. maxEdgeId()495 int maxEdgeId() const { return -1;} 496 497 template <typename _Graph> 498 struct Constraints { 499 constraintsConstraints500 void constraints() { 501 checkConcept<Base, _Graph >(); 502 typename _Graph::Node node; 503 int nid = graph.id(node); 504 nid = graph.id(node); 505 node = graph.nodeFromId(nid); 506 typename _Graph::Edge edge; 507 int eid = graph.id(edge); 508 eid = graph.id(edge); 509 edge = graph.edgeFromId(eid); 510 511 nid = graph.maxNodeId(); 512 ignore_unused_variable_warning(nid); 513 eid = graph.maxEdgeId(); 514 ignore_unused_variable_warning(eid); 515 } 516 517 const _Graph& graph; 518 }; 519 }; 520 521 /// \brief An empty idable base undirected graph class. 522 /// 523 /// This class provides beside the core undirected graph features 524 /// core id functions for the undirected graph structure. The 525 /// most of the base undirected graphs should be conform to this 526 /// concept. The id's are unique and immutable. 527 template <typename _Base = BaseUGraphComponent> 528 class IDableUGraphComponent : public IDableGraphComponent<_Base> { 529 public: 530 531 typedef _Base Base; 532 typedef typename Base::UEdge UEdge; 533 534 using IDableGraphComponent<_Base>::id; 535 536 /// \brief Gives back an unique integer id for the UEdge. 537 /// 538 /// Gives back an unique integer id for the UEdge. 539 /// id(const UEdge &)540 int id(const UEdge&) const { return -1;} 541 542 /// \brief Gives back the undirected edge by the unique id. 543 /// 544 /// Gives back the undirected edge by the unique id. If the 545 /// graph does not contain edge with the given id then the 546 /// result of the function is undetermined. uEdgeFromId(int)547 UEdge uEdgeFromId(int) const { return INVALID;} 548 549 /// \brief Gives back an integer greater or equal to the maximum 550 /// UEdge id. 551 /// 552 /// Gives back an integer greater or equal to the maximum UEdge 553 /// id. maxUEdgeId()554 int maxUEdgeId() const { return -1;} 555 556 template <typename _Graph> 557 struct Constraints { 558 constraintsConstraints559 void constraints() { 560 checkConcept<Base, _Graph >(); 561 checkConcept<IDableGraphComponent<Base>, _Graph >(); 562 typename _Graph::UEdge uedge; 563 int ueid = graph.id(uedge); 564 ueid = graph.id(uedge); 565 uedge = graph.uEdgeFromId(ueid); 566 ueid = graph.maxUEdgeId(); 567 ignore_unused_variable_warning(ueid); 568 } 569 570 const _Graph& graph; 571 }; 572 }; 573 574 /// \brief An empty idable base bipartite undirected graph class. 575 /// 576 /// This class provides beside the core bipartite undirected graph 577 /// features core id functions for the bipartite undirected graph 578 /// structure. The most of the base undirected graphs should be 579 /// conform to this concept. 580 template <typename _Base = BaseBpUGraphComponent> 581 class IDableBpUGraphComponent : public IDableUGraphComponent<_Base> { 582 public: 583 584 typedef _Base Base; 585 typedef typename Base::Node Node; 586 587 using IDableUGraphComponent<_Base>::id; 588 589 /// \brief Gives back an unique integer id for the ANode. 590 /// 591 /// Gives back an unique integer id for the ANode. 592 /// aNodeId(const Node &)593 int aNodeId(const Node&) const { return -1;} 594 595 /// \brief Gives back the undirected edge by the unique id. 596 /// 597 /// Gives back the undirected edge by the unique id. If the 598 /// graph does not contain edge with the given id then the 599 /// result of the function is undetermined. nodeFromANodeId(int)600 Node nodeFromANodeId(int) const { return INVALID;} 601 602 /// \brief Gives back an integer greater or equal to the maximum 603 /// ANode id. 604 /// 605 /// Gives back an integer greater or equal to the maximum ANode 606 /// id. maxANodeId()607 int maxANodeId() const { return -1;} 608 609 /// \brief Gives back an unique integer id for the BNode. 610 /// 611 /// Gives back an unique integer id for the BNode. 612 /// bNodeId(const Node &)613 int bNodeId(const Node&) const { return -1;} 614 615 /// \brief Gives back the undirected edge by the unique id. 616 /// 617 /// Gives back the undirected edge by the unique id. If the 618 /// graph does not contain edge with the given id then the 619 /// result of the function is undetermined. nodeFromBNodeId(int)620 Node nodeFromBNodeId(int) const { return INVALID;} 621 622 /// \brief Gives back an integer greater or equal to the maximum 623 /// BNode id. 624 /// 625 /// Gives back an integer greater or equal to the maximum BNode 626 /// id. maxBNodeId()627 int maxBNodeId() const { return -1;} 628 629 template <typename _Graph> 630 struct Constraints { 631 constraintsConstraints632 void constraints() { 633 checkConcept<Base, _Graph >(); 634 checkConcept<IDableGraphComponent<Base>, _Graph >(); 635 typename _Graph::Node node(INVALID); 636 int id; 637 id = graph.aNodeId(node); 638 id = graph.bNodeId(node); 639 node = graph.nodeFromANodeId(id); 640 node = graph.nodeFromBNodeId(id); 641 id = graph.maxANodeId(); 642 id = graph.maxBNodeId(); 643 } 644 645 const _Graph& graph; 646 }; 647 }; 648 649 /// \brief Skeleton class for graph NodeIt and EdgeIt 650 /// 651 /// Skeleton class for graph NodeIt and EdgeIt. 652 /// 653 template <typename _Graph, typename _Item> 654 class GraphItemIt : public _Item { 655 public: 656 /// \brief Default constructor. 657 /// 658 /// @warning The default constructor sets the iterator 659 /// to an undefined value. GraphItemIt()660 GraphItemIt() {} 661 /// \brief Copy constructor. 662 /// 663 /// Copy constructor. 664 /// GraphItemIt(const GraphItemIt &)665 GraphItemIt(const GraphItemIt& ) {} 666 /// \brief Sets the iterator to the first item. 667 /// 668 /// Sets the iterator to the first item of \c the graph. 669 /// GraphItemIt(const _Graph &)670 explicit GraphItemIt(const _Graph&) {} 671 /// \brief Invalid constructor \& conversion. 672 /// 673 /// This constructor initializes the item to be invalid. 674 /// \sa Invalid for more details. GraphItemIt(Invalid)675 GraphItemIt(Invalid) {} 676 /// \brief Assign operator for items. 677 /// 678 /// The items are assignable. 679 /// 680 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 681 /// \brief Next item. 682 /// 683 /// Assign the iterator to the next item. 684 /// 685 GraphItemIt& operator++() { return *this; } 686 /// \brief Equality operator 687 /// 688 /// Two iterators are equal if and only if they point to the 689 /// same object or both are invalid. 690 bool operator==(const GraphItemIt&) const { return true;} 691 /// \brief Inequality operator 692 /// 693 /// \sa operator==(Node n) 694 /// 695 bool operator!=(const GraphItemIt&) const { return true;} 696 697 template<typename _GraphItemIt> 698 struct Constraints { constraintsConstraints699 void constraints() { 700 _GraphItemIt it1(g); 701 _GraphItemIt it2; 702 703 it2 = ++it1; 704 ++it2 = it1; 705 ++(++it1); 706 707 _Item bi = it1; 708 bi = it2; 709 } 710 _Graph& g; 711 }; 712 }; 713 714 /// \brief Skeleton class for graph InEdgeIt and OutEdgeIt 715 /// 716 /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same 717 /// base class, the _selector is a additional template parameter. For 718 /// InEdgeIt you should instantiate it with character 'i' and for 719 /// OutEdgeIt with 'o'. 720 template <typename _Graph, 721 typename _Item = typename _Graph::Edge, 722 typename _Base = typename _Graph::Node, 723 char _selector = '0'> 724 class GraphIncIt : public _Item { 725 public: 726 /// \brief Default constructor. 727 /// 728 /// @warning The default constructor sets the iterator 729 /// to an undefined value. GraphIncIt()730 GraphIncIt() {} 731 /// \brief Copy constructor. 732 /// 733 /// Copy constructor. 734 /// GraphIncIt(GraphIncIt const & gi)735 GraphIncIt(GraphIncIt const& gi) : _Item(gi) {} 736 /// \brief Sets the iterator to the first edge incoming into or outgoing 737 /// from the node. 738 /// 739 /// Sets the iterator to the first edge incoming into or outgoing 740 /// from the node. 741 /// GraphIncIt(const _Graph &,const _Base &)742 explicit GraphIncIt(const _Graph&, const _Base&) {} 743 /// \brief Invalid constructor \& conversion. 744 /// 745 /// This constructor initializes the item to be invalid. 746 /// \sa Invalid for more details. GraphIncIt(Invalid)747 GraphIncIt(Invalid) {} 748 /// \brief Assign operator for iterators. 749 /// 750 /// The iterators are assignable. 751 /// 752 GraphIncIt& operator=(GraphIncIt const&) { return *this; } 753 /// \brief Next item. 754 /// 755 /// Assign the iterator to the next item. 756 /// 757 GraphIncIt& operator++() { return *this; } 758 759 /// \brief Equality operator 760 /// 761 /// Two iterators are equal if and only if they point to the 762 /// same object or both are invalid. 763 bool operator==(const GraphIncIt&) const { return true;} 764 765 /// \brief Inequality operator 766 /// 767 /// \sa operator==(Node n) 768 /// 769 bool operator!=(const GraphIncIt&) const { return true;} 770 771 template <typename _GraphIncIt> 772 struct Constraints { constraintsConstraints773 void constraints() { 774 checkConcept<GraphItem<_selector>, _GraphIncIt>(); 775 _GraphIncIt it1(graph, node); 776 _GraphIncIt it2; 777 778 it2 = ++it1; 779 ++it2 = it1; 780 ++(++it1); 781 _Item e = it1; 782 e = it2; 783 784 } 785 786 _Item edge; 787 _Base node; 788 _Graph graph; 789 _GraphIncIt it; 790 }; 791 }; 792 793 794 /// \brief An empty iterable graph class. 795 /// 796 /// This class provides beside the core graph features 797 /// iterator based iterable interface for the graph structure. 798 /// This concept is part of the Graph concept. 799 template <typename _Base = BaseGraphComponent> 800 class IterableGraphComponent : public _Base { 801 802 public: 803 804 typedef _Base Base; 805 typedef typename Base::Node Node; 806 typedef typename Base::Edge Edge; 807 808 typedef IterableGraphComponent Graph; 809 810 /// \name Base iteration 811 /// 812 /// This interface provides functions for iteration on graph items 813 /// 814 /// @{ 815 816 /// \brief Gives back the first node in the iterating order. 817 /// 818 /// Gives back the first node in the iterating order. 819 /// first(Node &)820 void first(Node&) const {} 821 822 /// \brief Gives back the next node in the iterating order. 823 /// 824 /// Gives back the next node in the iterating order. 825 /// next(Node &)826 void next(Node&) const {} 827 828 /// \brief Gives back the first edge in the iterating order. 829 /// 830 /// Gives back the first edge in the iterating order. 831 /// first(Edge &)832 void first(Edge&) const {} 833 834 /// \brief Gives back the next edge in the iterating order. 835 /// 836 /// Gives back the next edge in the iterating order. 837 /// next(Edge &)838 void next(Edge&) const {} 839 840 841 /// \brief Gives back the first of the edges point to the given 842 /// node. 843 /// 844 /// Gives back the first of the edges point to the given node. 845 /// firstIn(Edge &,const Node &)846 void firstIn(Edge&, const Node&) const {} 847 848 /// \brief Gives back the next of the edges points to the given 849 /// node. 850 /// 851 /// Gives back the next of the edges points to the given node. 852 /// nextIn(Edge &)853 void nextIn(Edge&) const {} 854 855 /// \brief Gives back the first of the edges start from the 856 /// given node. 857 /// 858 /// Gives back the first of the edges start from the given node. 859 /// firstOut(Edge &,const Node &)860 void firstOut(Edge&, const Node&) const {} 861 862 /// \brief Gives back the next of the edges start from the given 863 /// node. 864 /// 865 /// Gives back the next of the edges start from the given node. 866 /// nextOut(Edge &)867 void nextOut(Edge&) const {} 868 869 /// @} 870 871 /// \name Class based iteration 872 /// 873 /// This interface provides functions for iteration on graph items 874 /// 875 /// @{ 876 877 /// \brief This iterator goes through each node. 878 /// 879 /// This iterator goes through each node. 880 /// 881 typedef GraphItemIt<Graph, Node> NodeIt; 882 883 /// \brief This iterator goes through each node. 884 /// 885 /// This iterator goes through each node. 886 /// 887 typedef GraphItemIt<Graph, Edge> EdgeIt; 888 889 /// \brief This iterator goes trough the incoming edges of a node. 890 /// 891 /// This iterator goes trough the \e inccoming edges of a certain node 892 /// of a graph. 893 typedef GraphIncIt<Graph, Edge, Node, 'i'> InEdgeIt; 894 895 /// \brief This iterator goes trough the outgoing edges of a node. 896 /// 897 /// This iterator goes trough the \e outgoing edges of a certain node 898 /// of a graph. 899 typedef GraphIncIt<Graph, Edge, Node, 'o'> OutEdgeIt; 900 901 /// \brief The base node of the iterator. 902 /// 903 /// Gives back the base node of the iterator. 904 /// It is always the target of the pointed edge. baseNode(const InEdgeIt &)905 Node baseNode(const InEdgeIt&) const { return INVALID; } 906 907 /// \brief The running node of the iterator. 908 /// 909 /// Gives back the running node of the iterator. 910 /// It is always the source of the pointed edge. runningNode(const InEdgeIt &)911 Node runningNode(const InEdgeIt&) const { return INVALID; } 912 913 /// \brief The base node of the iterator. 914 /// 915 /// Gives back the base node of the iterator. 916 /// It is always the source of the pointed edge. baseNode(const OutEdgeIt &)917 Node baseNode(const OutEdgeIt&) const { return INVALID; } 918 919 /// \brief The running node of the iterator. 920 /// 921 /// Gives back the running node of the iterator. 922 /// It is always the target of the pointed edge. runningNode(const OutEdgeIt &)923 Node runningNode(const OutEdgeIt&) const { return INVALID; } 924 925 /// @} 926 927 template <typename _Graph> 928 struct Constraints { constraintsConstraints929 void constraints() { 930 checkConcept<Base, _Graph>(); 931 932 { 933 typename _Graph::Node node(INVALID); 934 typename _Graph::Edge edge(INVALID); 935 { 936 graph.first(node); 937 graph.next(node); 938 } 939 { 940 graph.first(edge); 941 graph.next(edge); 942 } 943 { 944 graph.firstIn(edge, node); 945 graph.nextIn(edge); 946 } 947 { 948 graph.firstOut(edge, node); 949 graph.nextOut(edge); 950 } 951 } 952 953 { 954 checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>, 955 typename _Graph::EdgeIt >(); 956 checkConcept<GraphItemIt<_Graph, typename _Graph::Node>, 957 typename _Graph::NodeIt >(); 958 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 959 typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>(); 960 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 961 typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>(); 962 963 typename _Graph::Node n; 964 typename _Graph::InEdgeIt ieit(INVALID); 965 typename _Graph::OutEdgeIt oeit(INVALID); 966 n = graph.baseNode(ieit); 967 n = graph.runningNode(ieit); 968 n = graph.baseNode(oeit); 969 n = graph.runningNode(oeit); 970 ignore_unused_variable_warning(n); 971 } 972 } 973 974 const _Graph& graph; 975 976 }; 977 }; 978 979 /// \brief An empty iterable undirected graph class. 980 /// 981 /// This class provides beside the core graph features iterator 982 /// based iterable interface for the undirected graph structure. 983 /// This concept is part of the UGraph concept. 984 template <typename _Base = BaseUGraphComponent> 985 class IterableUGraphComponent : public IterableGraphComponent<_Base> { 986 public: 987 988 typedef _Base Base; 989 typedef typename Base::Node Node; 990 typedef typename Base::Edge Edge; 991 typedef typename Base::UEdge UEdge; 992 993 994 typedef IterableUGraphComponent Graph; 995 996 /// \name Base iteration 997 /// 998 /// This interface provides functions for iteration on graph items 999 /// @{ 1000 1001 using IterableGraphComponent<_Base>::first; 1002 using IterableGraphComponent<_Base>::next; 1003 1004 /// \brief Gives back the first undirected edge in the iterating 1005 /// order. 1006 /// 1007 /// Gives back the first undirected edge in the iterating order. 1008 /// first(UEdge &)1009 void first(UEdge&) const {} 1010 1011 /// \brief Gives back the next undirected edge in the iterating 1012 /// order. 1013 /// 1014 /// Gives back the next undirected edge in the iterating order. 1015 /// next(UEdge &)1016 void next(UEdge&) const {} 1017 1018 1019 /// \brief Gives back the first of the undirected edges from the 1020 /// given node. 1021 /// 1022 /// Gives back the first of the undirected edges from the given 1023 /// node. The bool parameter gives back that direction which 1024 /// gives a good direction of the uedge so the source of the 1025 /// directed edge is the given node. firstInc(UEdge &,bool &,const Node &)1026 void firstInc(UEdge&, bool&, const Node&) const {} 1027 1028 /// \brief Gives back the next of the undirected edges from the 1029 /// given node. 1030 /// 1031 /// Gives back the next of the undirected edges from the given 1032 /// node. The bool parameter should be used as the \c firstInc() 1033 /// use it. nextInc(UEdge &,bool &)1034 void nextInc(UEdge&, bool&) const {} 1035 1036 using IterableGraphComponent<_Base>::baseNode; 1037 using IterableGraphComponent<_Base>::runningNode; 1038 1039 /// @} 1040 1041 /// \name Class based iteration 1042 /// 1043 /// This interface provides functions for iteration on graph items 1044 /// 1045 /// @{ 1046 1047 /// \brief This iterator goes through each node. 1048 /// 1049 /// This iterator goes through each node. 1050 typedef GraphItemIt<Graph, UEdge> UEdgeIt; 1051 /// \brief This iterator goes trough the incident edges of a 1052 /// node. 1053 /// 1054 /// This iterator goes trough the incident edges of a certain 1055 /// node of a graph. 1056 typedef GraphIncIt<Graph, UEdge, Node, 'u'> IncEdgeIt; 1057 /// \brief The base node of the iterator. 1058 /// 1059 /// Gives back the base node of the iterator. baseNode(const IncEdgeIt &)1060 Node baseNode(const IncEdgeIt&) const { return INVALID; } 1061 1062 /// \brief The running node of the iterator. 1063 /// 1064 /// Gives back the running node of the iterator. runningNode(const IncEdgeIt &)1065 Node runningNode(const IncEdgeIt&) const { return INVALID; } 1066 1067 /// @} 1068 1069 template <typename _Graph> 1070 struct Constraints { constraintsConstraints1071 void constraints() { 1072 checkConcept<IterableGraphComponent<Base>, _Graph>(); 1073 1074 { 1075 typename _Graph::Node node(INVALID); 1076 typename _Graph::UEdge uedge(INVALID); 1077 bool dir; 1078 { 1079 graph.first(uedge); 1080 graph.next(uedge); 1081 } 1082 { 1083 graph.firstInc(uedge, dir, node); 1084 graph.nextInc(uedge, dir); 1085 } 1086 1087 } 1088 1089 { 1090 checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>, 1091 typename _Graph::UEdgeIt >(); 1092 checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge, 1093 typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>(); 1094 1095 typename _Graph::Node n; 1096 typename _Graph::IncEdgeIt ueit(INVALID); 1097 n = graph.baseNode(ueit); 1098 n = graph.runningNode(ueit); 1099 } 1100 } 1101 1102 const _Graph& graph; 1103 1104 }; 1105 }; 1106 1107 /// \brief An empty iterable bipartite undirected graph class. 1108 /// 1109 /// This class provides beside the core graph features iterator 1110 /// based iterable interface for the bipartite undirected graph 1111 /// structure. This concept is part of the BpUGraph concept. 1112 template <typename _Base = BaseUGraphComponent> 1113 class IterableBpUGraphComponent : public IterableUGraphComponent<_Base> { 1114 public: 1115 1116 typedef _Base Base; 1117 typedef typename Base::Node Node; 1118 typedef typename Base::UEdge UEdge; 1119 1120 typedef IterableBpUGraphComponent Graph; 1121 1122 /// \name Base iteration 1123 /// 1124 /// This interface provides functions for iteration on graph items 1125 /// @{ 1126 1127 using IterableUGraphComponent<_Base>::first; 1128 using IterableUGraphComponent<_Base>::next; 1129 1130 /// \brief Gives back the first A-node in the iterating order. 1131 /// 1132 /// Gives back the first undirected A-node in the iterating 1133 /// order. 1134 /// firstANode(Node &)1135 void firstANode(Node&) const {} 1136 1137 /// \brief Gives back the next A-node in the iterating order. 1138 /// 1139 /// Gives back the next A-node in the iterating order. 1140 /// nextANode(Node &)1141 void nextANode(Node&) const {} 1142 1143 /// \brief Gives back the first B-node in the iterating order. 1144 /// 1145 /// Gives back the first undirected B-node in the iterating 1146 /// order. 1147 /// firstBNode(Node &)1148 void firstBNode(Node&) const {} 1149 1150 /// \brief Gives back the next B-node in the iterating order. 1151 /// 1152 /// Gives back the next B-node in the iterating order. 1153 /// nextBNode(Node &)1154 void nextBNode(Node&) const {} 1155 1156 1157 /// \brief Gives back the first of the undirected edges start 1158 /// from the given A-node. 1159 /// 1160 /// Gives back the first of the undirected edges start from the 1161 /// given A-node. firstFromANode(UEdge &,const Node &)1162 void firstFromANode(UEdge&, const Node&) const {} 1163 1164 /// \brief Gives back the next of the undirected edges start 1165 /// from the given A-node. 1166 /// 1167 /// Gives back the next of the undirected edges start from the 1168 /// given A-node. nextFromANode(UEdge &)1169 void nextFromANode(UEdge&) const {} 1170 1171 /// \brief Gives back the first of the undirected edges start 1172 /// from the given B-node. 1173 /// 1174 /// Gives back the first of the undirected edges start from the 1175 /// given B-node. firstFromBNode(UEdge &,const Node &)1176 void firstFromBNode(UEdge&, const Node&) const {} 1177 1178 /// \brief Gives back the next of the undirected edges start 1179 /// from the given B-node. 1180 /// 1181 /// Gives back the next of the undirected edges start from the 1182 /// given B-node. nextFromBNode(UEdge &)1183 void nextFromBNode(UEdge&) const {} 1184 1185 1186 /// @} 1187 1188 /// \name Class based iteration 1189 /// 1190 /// This interface provides functions for iteration on graph items 1191 /// 1192 /// @{ 1193 1194 /// \brief This iterator goes through each A-node. 1195 /// 1196 /// This iterator goes through each A-node. 1197 typedef GraphItemIt<Graph, Node> ANodeIt; 1198 1199 /// \brief This iterator goes through each B-node. 1200 /// 1201 /// This iterator goes through each B-node. 1202 typedef GraphItemIt<Graph, Node> BNodeIt; 1203 1204 /// @} 1205 1206 template <typename _Graph> 1207 struct Constraints { constraintsConstraints1208 void constraints() { 1209 checkConcept<IterableUGraphComponent<Base>, _Graph>(); 1210 1211 { 1212 typename _Graph::Node node(INVALID); 1213 typename _Graph::UEdge uedge(INVALID); 1214 graph.firstANode(node); 1215 graph.nextANode(node); 1216 graph.firstBNode(node); 1217 graph.nextBNode(node); 1218 1219 graph.firstFromANode(uedge, node); 1220 graph.nextFromANode(uedge); 1221 graph.firstFromBNode(uedge, node); 1222 graph.nextFromBNode(uedge); 1223 } 1224 { 1225 checkConcept<GraphItemIt<_Graph, typename _Graph::Node>, 1226 typename _Graph::ANodeIt >(); 1227 checkConcept<GraphItemIt<_Graph, typename _Graph::Node>, 1228 typename _Graph::BNodeIt >(); 1229 } 1230 1231 } 1232 1233 const _Graph& graph; 1234 1235 }; 1236 }; 1237 1238 /// \brief An empty alteration notifier graph class. 1239 /// 1240 /// This class provides beside the core graph features alteration 1241 /// notifier interface for the graph structure. This implements 1242 /// an observer-notifier pattern for each graph item. More 1243 /// obsevers can be registered into the notifier and whenever an 1244 /// alteration occured in the graph all the observers will 1245 /// notified about it. 1246 template <typename _Base = BaseGraphComponent> 1247 class AlterableGraphComponent : public _Base { 1248 public: 1249 1250 typedef _Base Base; 1251 typedef typename Base::Node Node; 1252 typedef typename Base::Edge Edge; 1253 1254 1255 /// The node observer registry. 1256 typedef AlterationNotifier<AlterableGraphComponent, Node> 1257 NodeNotifier; 1258 /// The edge observer registry. 1259 typedef AlterationNotifier<AlterableGraphComponent, Edge> 1260 EdgeNotifier; 1261 1262 /// \brief Gives back the node alteration notifier. 1263 /// 1264 /// Gives back the node alteration notifier. notifier(Node)1265 NodeNotifier& notifier(Node) const { 1266 return NodeNotifier(); 1267 } 1268 1269 /// \brief Gives back the edge alteration notifier. 1270 /// 1271 /// Gives back the edge alteration notifier. notifier(Edge)1272 EdgeNotifier& notifier(Edge) const { 1273 return EdgeNotifier(); 1274 } 1275 1276 template <typename _Graph> 1277 struct Constraints { constraintsConstraints1278 void constraints() { 1279 checkConcept<Base, _Graph>(); 1280 typename _Graph::NodeNotifier& nn 1281 = graph.notifier(typename _Graph::Node()); 1282 1283 typename _Graph::EdgeNotifier& en 1284 = graph.notifier(typename _Graph::Edge()); 1285 1286 ignore_unused_variable_warning(nn); 1287 ignore_unused_variable_warning(en); 1288 } 1289 1290 const _Graph& graph; 1291 1292 }; 1293 1294 }; 1295 1296 /// \brief An empty alteration notifier undirected graph class. 1297 /// 1298 /// This class provides beside the core graph features alteration 1299 /// notifier interface for the graph structure. This implements 1300 /// an observer-notifier pattern for each graph item. More 1301 /// obsevers can be registered into the notifier and whenever an 1302 /// alteration occured in the graph all the observers will 1303 /// notified about it. 1304 template <typename _Base = BaseUGraphComponent> 1305 class AlterableUGraphComponent : public AlterableGraphComponent<_Base> { 1306 public: 1307 1308 typedef _Base Base; 1309 typedef typename Base::UEdge UEdge; 1310 1311 1312 /// The edge observer registry. 1313 typedef AlterationNotifier<AlterableUGraphComponent, UEdge> 1314 UEdgeNotifier; 1315 1316 /// \brief Gives back the edge alteration notifier. 1317 /// 1318 /// Gives back the edge alteration notifier. notifier(UEdge)1319 UEdgeNotifier& notifier(UEdge) const { 1320 return UEdgeNotifier(); 1321 } 1322 1323 template <typename _Graph> 1324 struct Constraints { constraintsConstraints1325 void constraints() { 1326 checkConcept<AlterableGraphComponent<Base>, _Graph>(); 1327 typename _Graph::UEdgeNotifier& uen 1328 = graph.notifier(typename _Graph::UEdge()); 1329 ignore_unused_variable_warning(uen); 1330 } 1331 1332 const _Graph& graph; 1333 1334 }; 1335 1336 }; 1337 1338 /// \brief An empty alteration notifier bipartite undirected graph 1339 /// class. 1340 /// 1341 /// This class provides beside the core graph features alteration 1342 /// notifier interface for the graph structure. This implements 1343 /// an observer-notifier pattern for each graph item. More 1344 /// obsevers can be registered into the notifier and whenever an 1345 /// alteration occured in the graph all the observers will 1346 /// notified about it. 1347 template <typename _Base = BaseUGraphComponent> 1348 class AlterableBpUGraphComponent : public AlterableUGraphComponent<_Base> { 1349 public: 1350 1351 typedef _Base Base; 1352 typedef typename Base::ANode ANode; 1353 typedef typename Base::BNode BNode; 1354 1355 1356 /// The A-node observer registry. 1357 typedef AlterationNotifier<AlterableBpUGraphComponent, ANode> 1358 ANodeNotifier; 1359 1360 /// The B-node observer registry. 1361 typedef AlterationNotifier<AlterableBpUGraphComponent, BNode> 1362 BNodeNotifier; 1363 1364 /// \brief Gives back the A-node alteration notifier. 1365 /// 1366 /// Gives back the A-node alteration notifier. notifier(ANode)1367 ANodeNotifier& notifier(ANode) const { 1368 return ANodeNotifier(); 1369 } 1370 1371 /// \brief Gives back the B-node alteration notifier. 1372 /// 1373 /// Gives back the B-node alteration notifier. notifier(BNode)1374 BNodeNotifier& notifier(BNode) const { 1375 return BNodeNotifier(); 1376 } 1377 1378 template <typename _Graph> 1379 struct Constraints { constraintsConstraints1380 void constraints() { 1381 checkConcept<AlterableUGraphComponent<Base>, _Graph>(); 1382 typename _Graph::ANodeNotifier& ann 1383 = graph.notifier(typename _Graph::ANode()); 1384 typename _Graph::BNodeNotifier& bnn 1385 = graph.notifier(typename _Graph::BNode()); 1386 ignore_unused_variable_warning(ann); 1387 ignore_unused_variable_warning(bnn); 1388 } 1389 1390 const _Graph& graph; 1391 1392 }; 1393 1394 }; 1395 1396 1397 /// \brief Class describing the concept of graph maps 1398 /// 1399 /// This class describes the common interface of the graph maps 1400 /// (NodeMap, EdgeMap), that is \ref maps-page "maps" which can be used to 1401 /// associate data to graph descriptors (nodes or edges). 1402 template <typename _Graph, typename _Item, typename _Value> 1403 class GraphMap : public ReadWriteMap<_Item, _Value> { 1404 public: 1405 1406 typedef ReadWriteMap<_Item, _Value> Parent; 1407 1408 /// The graph type of the map. 1409 typedef _Graph Graph; 1410 /// The key type of the map. 1411 typedef _Item Key; 1412 /// The value type of the map. 1413 typedef _Value Value; 1414 1415 /// \brief Construct a new map. 1416 /// 1417 /// Construct a new map for the graph. GraphMap(const Graph &)1418 explicit GraphMap(const Graph&) {} 1419 /// \brief Construct a new map with default value. 1420 /// 1421 /// Construct a new map for the graph and initalise the values. GraphMap(const Graph &,const Value &)1422 GraphMap(const Graph&, const Value&) {} 1423 /// \brief Copy constructor. 1424 /// 1425 /// Copy Constructor. GraphMap(const GraphMap &)1426 GraphMap(const GraphMap&) : Parent() {} 1427 1428 /// \brief Assign operator. 1429 /// 1430 /// Assign operator. It does not mofify the underlying graph, 1431 /// it just iterates on the current item set and set the map 1432 /// with the value returned by the assigned map. 1433 template <typename CMap> 1434 GraphMap& operator=(const CMap&) { 1435 checkConcept<ReadMap<Key, Value>, CMap>(); 1436 return *this; 1437 } 1438 1439 template<typename _Map> 1440 struct Constraints { constraintsConstraints1441 void constraints() { 1442 checkConcept<ReadWriteMap<Key, Value>, _Map >(); 1443 // Construction with a graph parameter 1444 _Map a(g); 1445 // Constructor with a graph and a default value parameter 1446 _Map a2(g,t); 1447 // Copy constructor. 1448 _Map b(c); 1449 1450 ReadMap<Key, Value> cmap; 1451 b = cmap; 1452 1453 ignore_unused_variable_warning(a2); 1454 ignore_unused_variable_warning(b); 1455 } 1456 1457 const _Map &c; 1458 const Graph &g; 1459 const typename GraphMap::Value &t; 1460 }; 1461 1462 }; 1463 1464 /// \brief An empty mappable graph class. 1465 /// 1466 /// This class provides beside the core graph features 1467 /// map interface for the graph structure. 1468 /// This concept is part of the Graph concept. 1469 template <typename _Base = BaseGraphComponent> 1470 class MappableGraphComponent : public _Base { 1471 public: 1472 1473 typedef _Base Base; 1474 typedef typename Base::Node Node; 1475 typedef typename Base::Edge Edge; 1476 1477 typedef MappableGraphComponent Graph; 1478 1479 /// \brief ReadWrite map of the nodes. 1480 /// 1481 /// ReadWrite map of the nodes. 1482 /// 1483 template <typename _Value> 1484 class NodeMap : public GraphMap<Graph, Node, _Value> { 1485 public: 1486 typedef GraphMap<MappableGraphComponent, Node, _Value> Parent; 1487 1488 /// \brief Construct a new map. 1489 /// 1490 /// Construct a new map for the graph. NodeMap(const MappableGraphComponent & graph)1491 explicit NodeMap(const MappableGraphComponent& graph) 1492 : Parent(graph) {} 1493 1494 /// \brief Construct a new map with default value. 1495 /// 1496 /// Construct a new map for the graph and initalise the values. NodeMap(const MappableGraphComponent & graph,const _Value & value)1497 NodeMap(const MappableGraphComponent& graph, const _Value& value) 1498 : Parent(graph, value) {} 1499 1500 /// \brief Copy constructor. 1501 /// 1502 /// Copy Constructor. NodeMap(const NodeMap & nm)1503 NodeMap(const NodeMap& nm) : Parent(nm) {} 1504 1505 /// \brief Assign operator. 1506 /// 1507 /// Assign operator. 1508 template <typename CMap> 1509 NodeMap& operator=(const CMap&) { 1510 checkConcept<ReadMap<Node, _Value>, CMap>(); 1511 return *this; 1512 } 1513 1514 }; 1515 1516 /// \brief ReadWrite map of the edges. 1517 /// 1518 /// ReadWrite map of the edges. 1519 /// 1520 template <typename _Value> 1521 class EdgeMap : public GraphMap<Graph, Edge, _Value> { 1522 public: 1523 typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent; 1524 1525 /// \brief Construct a new map. 1526 /// 1527 /// Construct a new map for the graph. EdgeMap(const MappableGraphComponent & graph)1528 explicit EdgeMap(const MappableGraphComponent& graph) 1529 : Parent(graph) {} 1530 1531 /// \brief Construct a new map with default value. 1532 /// 1533 /// Construct a new map for the graph and initalise the values. EdgeMap(const MappableGraphComponent & graph,const _Value & value)1534 EdgeMap(const MappableGraphComponent& graph, const _Value& value) 1535 : Parent(graph, value) {} 1536 1537 /// \brief Copy constructor. 1538 /// 1539 /// Copy Constructor. EdgeMap(const EdgeMap & nm)1540 EdgeMap(const EdgeMap& nm) : Parent(nm) {} 1541 1542 /// \brief Assign operator. 1543 /// 1544 /// Assign operator. 1545 template <typename CMap> 1546 EdgeMap& operator=(const CMap&) { 1547 checkConcept<ReadMap<Edge, _Value>, CMap>(); 1548 return *this; 1549 } 1550 1551 }; 1552 1553 1554 template <typename _Graph> 1555 struct Constraints { 1556 1557 struct Dummy { 1558 int value; DummyConstraints::Dummy1559 Dummy() : value(0) {} DummyConstraints::Dummy1560 Dummy(int _v) : value(_v) {} 1561 }; 1562 constraintsConstraints1563 void constraints() { 1564 checkConcept<Base, _Graph>(); 1565 { // int map test 1566 typedef typename _Graph::template NodeMap<int> IntNodeMap; 1567 checkConcept<GraphMap<_Graph, typename _Graph::Node, int>, 1568 IntNodeMap >(); 1569 } { // bool map test 1570 typedef typename _Graph::template NodeMap<bool> BoolNodeMap; 1571 checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>, 1572 BoolNodeMap >(); 1573 } { // Dummy map test 1574 typedef typename _Graph::template NodeMap<Dummy> DummyNodeMap; 1575 checkConcept<GraphMap<_Graph, typename _Graph::Node, Dummy>, 1576 DummyNodeMap >(); 1577 } 1578 1579 { // int map test 1580 typedef typename _Graph::template EdgeMap<int> IntEdgeMap; 1581 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, 1582 IntEdgeMap >(); 1583 } { // bool map test 1584 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap; 1585 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, 1586 BoolEdgeMap >(); 1587 } { // Dummy map test 1588 typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap; 1589 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>, 1590 DummyEdgeMap >(); 1591 } 1592 } 1593 1594 _Graph& graph; 1595 }; 1596 }; 1597 1598 /// \brief An empty mappable base bipartite undirected graph class. 1599 /// 1600 /// This class provides beside the core graph features 1601 /// map interface for the graph structure. 1602 /// This concept is part of the UGraph concept. 1603 template <typename _Base = BaseUGraphComponent> 1604 class MappableUGraphComponent : public MappableGraphComponent<_Base> { 1605 public: 1606 1607 typedef _Base Base; 1608 typedef typename Base::UEdge UEdge; 1609 1610 typedef MappableUGraphComponent Graph; 1611 1612 /// \brief ReadWrite map of the uedges. 1613 /// 1614 /// ReadWrite map of the uedges. 1615 /// 1616 template <typename _Value> 1617 class UEdgeMap : public GraphMap<Graph, UEdge, _Value> { 1618 public: 1619 typedef GraphMap<MappableUGraphComponent, UEdge, _Value> Parent; 1620 1621 /// \brief Construct a new map. 1622 /// 1623 /// Construct a new map for the graph. UEdgeMap(const MappableUGraphComponent & graph)1624 explicit UEdgeMap(const MappableUGraphComponent& graph) 1625 : Parent(graph) {} 1626 1627 /// \brief Construct a new map with default value. 1628 /// 1629 /// Construct a new map for the graph and initalise the values. UEdgeMap(const MappableUGraphComponent & graph,const _Value & value)1630 UEdgeMap(const MappableUGraphComponent& graph, const _Value& value) 1631 : Parent(graph, value) {} 1632 1633 /// \brief Copy constructor. 1634 /// 1635 /// Copy Constructor. UEdgeMap(const UEdgeMap & nm)1636 UEdgeMap(const UEdgeMap& nm) : Parent(nm) {} 1637 1638 /// \brief Assign operator. 1639 /// 1640 /// Assign operator. 1641 template <typename CMap> 1642 UEdgeMap& operator=(const CMap&) { 1643 checkConcept<ReadMap<UEdge, _Value>, CMap>(); 1644 return *this; 1645 } 1646 1647 }; 1648 1649 1650 template <typename _Graph> 1651 struct Constraints { 1652 1653 struct Dummy { 1654 int value; DummyConstraints::Dummy1655 Dummy() : value(0) {} DummyConstraints::Dummy1656 Dummy(int _v) : value(_v) {} 1657 }; 1658 constraintsConstraints1659 void constraints() { 1660 checkConcept<MappableGraphComponent<Base>, _Graph>(); 1661 1662 { // int map test 1663 typedef typename _Graph::template UEdgeMap<int> IntUEdgeMap; 1664 checkConcept<GraphMap<_Graph, typename _Graph::UEdge, int>, 1665 IntUEdgeMap >(); 1666 } { // bool map test 1667 typedef typename _Graph::template UEdgeMap<bool> BoolUEdgeMap; 1668 checkConcept<GraphMap<_Graph, typename _Graph::UEdge, bool>, 1669 BoolUEdgeMap >(); 1670 } { // Dummy map test 1671 typedef typename _Graph::template UEdgeMap<Dummy> DummyUEdgeMap; 1672 checkConcept<GraphMap<_Graph, typename _Graph::UEdge, Dummy>, 1673 DummyUEdgeMap >(); 1674 } 1675 } 1676 1677 _Graph& graph; 1678 }; 1679 }; 1680 1681 /// \brief An empty mappable base bipartite undirected graph 1682 /// class. 1683 /// 1684 /// This class provides beside the core graph features 1685 /// map interface for the graph structure. 1686 /// This concept is part of the BpUGraph concept. 1687 template <typename _Base = BaseBpUGraphComponent> 1688 class MappableBpUGraphComponent : public MappableUGraphComponent<_Base> { 1689 public: 1690 1691 typedef _Base Base; 1692 typedef typename Base::Node Node; 1693 1694 typedef MappableBpUGraphComponent Graph; 1695 1696 /// \brief ReadWrite map of the A-nodes. 1697 /// 1698 /// ReadWrite map of the A-nodes. 1699 /// 1700 template <typename _Value> 1701 class ANodeMap : public GraphMap<Graph, Node, _Value> { 1702 public: 1703 typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent; 1704 1705 /// \brief Construct a new map. 1706 /// 1707 /// Construct a new map for the graph. ANodeMap(const MappableBpUGraphComponent & graph)1708 explicit ANodeMap(const MappableBpUGraphComponent& graph) 1709 : Parent(graph) {} 1710 1711 /// \brief Construct a new map with default value. 1712 /// 1713 /// Construct a new map for the graph and initalise the values. ANodeMap(const MappableBpUGraphComponent & graph,const _Value & value)1714 ANodeMap(const MappableBpUGraphComponent& graph, const _Value& value) 1715 : Parent(graph, value) {} 1716 1717 /// \brief Copy constructor. 1718 /// 1719 /// Copy Constructor. ANodeMap(const ANodeMap & nm)1720 ANodeMap(const ANodeMap& nm) : Parent(nm) {} 1721 1722 /// \brief Assign operator. 1723 /// 1724 /// Assign operator. 1725 template <typename CMap> 1726 ANodeMap& operator=(const CMap&) { 1727 checkConcept<ReadMap<Node, _Value>, CMap>(); 1728 return *this; 1729 } 1730 1731 }; 1732 1733 /// \brief ReadWrite map of the B-nodes. 1734 /// 1735 /// ReadWrite map of the A-nodes. 1736 /// 1737 template <typename _Value> 1738 class BNodeMap : public GraphMap<Graph, Node, _Value> { 1739 public: 1740 typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent; 1741 1742 /// \brief Construct a new map. 1743 /// 1744 /// Construct a new map for the graph. BNodeMap(const MappableBpUGraphComponent & graph)1745 explicit BNodeMap(const MappableBpUGraphComponent& graph) 1746 : Parent(graph) {} 1747 1748 /// \brief Construct a new map with default value. 1749 /// 1750 /// Construct a new map for the graph and initalise the values. BNodeMap(const MappableBpUGraphComponent & graph,const _Value & value)1751 BNodeMap(const MappableBpUGraphComponent& graph, const _Value& value) 1752 : Parent(graph, value) {} 1753 1754 /// \brief Copy constructor. 1755 /// 1756 /// Copy Constructor. BNodeMap(const BNodeMap & nm)1757 BNodeMap(const BNodeMap& nm) : Parent(nm) {} 1758 1759 /// \brief Assign operator. 1760 /// 1761 /// Assign operator. 1762 template <typename CMap> 1763 BNodeMap& operator=(const CMap&) { 1764 checkConcept<ReadMap<Node, _Value>, CMap>(); 1765 return *this; 1766 } 1767 1768 }; 1769 1770 1771 template <typename _Graph> 1772 struct Constraints { 1773 1774 struct Dummy { 1775 int value; DummyConstraints::Dummy1776 Dummy() : value(0) {} DummyConstraints::Dummy1777 Dummy(int _v) : value(_v) {} 1778 }; 1779 constraintsConstraints1780 void constraints() { 1781 checkConcept<MappableUGraphComponent<Base>, _Graph>(); 1782 1783 { // int map test 1784 typedef typename _Graph::template ANodeMap<int> IntANodeMap; 1785 checkConcept<GraphMap<_Graph, typename _Graph::ANode, int>, 1786 IntANodeMap >(); 1787 } { // bool map test 1788 typedef typename _Graph::template ANodeMap<bool> BoolANodeMap; 1789 checkConcept<GraphMap<_Graph, typename _Graph::ANode, bool>, 1790 BoolANodeMap >(); 1791 } { // Dummy map test 1792 typedef typename _Graph::template ANodeMap<Dummy> DummyANodeMap; 1793 checkConcept<GraphMap<_Graph, typename _Graph::ANode, Dummy>, 1794 DummyANodeMap >(); 1795 } 1796 } 1797 1798 _Graph& graph; 1799 }; 1800 }; 1801 1802 1803 /// \brief An empty extendable graph class. 1804 /// 1805 /// This class provides beside the core graph features graph 1806 /// extendable interface for the graph structure. The main 1807 /// difference between the base and this interface is that the 1808 /// graph alterations should handled already on this level. 1809 template <typename _Base = BaseGraphComponent> 1810 class ExtendableGraphComponent : public _Base { 1811 public: 1812 typedef _Base Base; 1813 1814 typedef typename _Base::Node Node; 1815 typedef typename _Base::Edge Edge; 1816 1817 /// \brief Adds a new node to the graph. 1818 /// 1819 /// Adds a new node to the graph. 1820 /// addNode()1821 Node addNode() { 1822 return INVALID; 1823 } 1824 1825 /// \brief Adds a new edge connects the given two nodes. 1826 /// 1827 /// Adds a new edge connects the the given two nodes. addEdge(const Node &,const Node &)1828 Edge addEdge(const Node&, const Node&) { 1829 return INVALID; 1830 } 1831 1832 template <typename _Graph> 1833 struct Constraints { constraintsConstraints1834 void constraints() { 1835 checkConcept<Base, _Graph>(); 1836 typename _Graph::Node node_a, node_b; 1837 node_a = graph.addNode(); 1838 node_b = graph.addNode(); 1839 typename _Graph::Edge edge; 1840 edge = graph.addEdge(node_a, node_b); 1841 } 1842 1843 _Graph& graph; 1844 }; 1845 }; 1846 1847 /// \brief An empty extendable base undirected graph class. 1848 /// 1849 /// This class provides beside the core undirected graph features 1850 /// core undircted graph extend interface for the graph structure. 1851 /// The main difference between the base and this interface is 1852 /// that the graph alterations should handled already on this 1853 /// level. 1854 template <typename _Base = BaseUGraphComponent> 1855 class ExtendableUGraphComponent : public _Base { 1856 public: 1857 1858 typedef _Base Base; 1859 typedef typename _Base::Node Node; 1860 typedef typename _Base::UEdge UEdge; 1861 1862 /// \brief Adds a new node to the graph. 1863 /// 1864 /// Adds a new node to the graph. 1865 /// addNode()1866 Node addNode() { 1867 return INVALID; 1868 } 1869 1870 /// \brief Adds a new edge connects the given two nodes. 1871 /// 1872 /// Adds a new edge connects the the given two nodes. addEdge(const Node &,const Node &)1873 UEdge addEdge(const Node&, const Node&) { 1874 return INVALID; 1875 } 1876 1877 template <typename _Graph> 1878 struct Constraints { constraintsConstraints1879 void constraints() { 1880 checkConcept<Base, _Graph>(); 1881 typename _Graph::Node node_a, node_b; 1882 node_a = graph.addNode(); 1883 node_b = graph.addNode(); 1884 typename _Graph::UEdge uedge; 1885 uedge = graph.addUEdge(node_a, node_b); 1886 } 1887 1888 _Graph& graph; 1889 }; 1890 }; 1891 1892 /// \brief An empty extendable base undirected graph class. 1893 /// 1894 /// This class provides beside the core bipartite undirected graph 1895 /// features core undircted graph extend interface for the graph 1896 /// structure. The main difference between the base and this 1897 /// interface is that the graph alterations should handled already 1898 /// on this level. 1899 template <typename _Base = BaseBpUGraphComponent> 1900 class ExtendableBpUGraphComponent 1901 : public ExtendableUGraphComponent<_Base> { 1902 1903 typedef _Base Base; 1904 1905 template <typename _Graph> 1906 struct Constraints { constraintsConstraints1907 void constraints() { 1908 checkConcept<ExtendableUGraphComponent<Base>, _Graph>(); 1909 } 1910 }; 1911 }; 1912 1913 /// \brief An empty erasable graph class. 1914 /// 1915 /// This class provides beside the core graph features core erase 1916 /// functions for the graph structure. The main difference between 1917 /// the base and this interface is that the graph alterations 1918 /// should handled already on this level. 1919 template <typename _Base = BaseGraphComponent> 1920 class ErasableGraphComponent : public _Base { 1921 public: 1922 1923 typedef _Base Base; 1924 typedef typename Base::Node Node; 1925 typedef typename Base::Edge Edge; 1926 1927 /// \brief Erase a node from the graph. 1928 /// 1929 /// Erase a node from the graph. This function should 1930 /// erase all edges connecting to the node. erase(const Node &)1931 void erase(const Node&) {} 1932 1933 /// \brief Erase an edge from the graph. 1934 /// 1935 /// Erase an edge from the graph. 1936 /// erase(const Edge &)1937 void erase(const Edge&) {} 1938 1939 template <typename _Graph> 1940 struct Constraints { constraintsConstraints1941 void constraints() { 1942 checkConcept<Base, _Graph>(); 1943 typename _Graph::Node node; 1944 graph.erase(node); 1945 typename _Graph::Edge edge; 1946 graph.erase(edge); 1947 } 1948 1949 _Graph& graph; 1950 }; 1951 }; 1952 1953 /// \brief An empty erasable base undirected graph class. 1954 /// 1955 /// This class provides beside the core undirected graph features 1956 /// core erase functions for the undirceted graph structure. The 1957 /// main difference between the base and this interface is that 1958 /// the graph alterations should handled already on this level. 1959 template <typename _Base = BaseUGraphComponent> 1960 class ErasableUGraphComponent : public _Base { 1961 public: 1962 1963 typedef _Base Base; 1964 typedef typename Base::Node Node; 1965 typedef typename Base::UEdge UEdge; 1966 1967 /// \brief Erase a node from the graph. 1968 /// 1969 /// Erase a node from the graph. This function should erase 1970 /// edges connecting to the node. erase(const Node &)1971 void erase(const Node&) {} 1972 1973 /// \brief Erase an edge from the graph. 1974 /// 1975 /// Erase an edge from the graph. 1976 /// erase(const UEdge &)1977 void erase(const UEdge&) {} 1978 1979 template <typename _Graph> 1980 struct Constraints { constraintsConstraints1981 void constraints() { 1982 checkConcept<Base, _Graph>(); 1983 typename _Graph::Node node; 1984 graph.erase(node); 1985 typename _Graph::Edge edge; 1986 graph.erase(edge); 1987 } 1988 1989 _Graph& graph; 1990 }; 1991 }; 1992 1993 /// \brief An empty erasable base bipartite undirected graph class. 1994 /// 1995 /// This class provides beside the core bipartite undirected graph 1996 /// features core erase functions for the undirceted graph 1997 /// structure. The main difference between the base and this 1998 /// interface is that the graph alterations should handled already 1999 /// on this level. 2000 template <typename _Base = BaseBpUGraphComponent> 2001 class ErasableBpUGraphComponent : public ErasableUGraphComponent<_Base> { 2002 public: 2003 2004 typedef _Base Base; 2005 2006 template <typename _Graph> 2007 struct Constraints { constraintsConstraints2008 void constraints() { 2009 checkConcept<ErasableUGraphComponent<Base>, _Graph>(); 2010 } 2011 }; 2012 }; 2013 2014 /// \brief An empty clearable base graph class. 2015 /// 2016 /// This class provides beside the core graph features core clear 2017 /// functions for the graph structure. The main difference between 2018 /// the base and this interface is that the graph alterations 2019 /// should handled already on this level. 2020 template <typename _Base = BaseGraphComponent> 2021 class ClearableGraphComponent : public _Base { 2022 public: 2023 2024 typedef _Base Base; 2025 2026 /// \brief Erase all nodes and edges from the graph. 2027 /// 2028 /// Erase all nodes and edges from the graph. 2029 /// clear()2030 void clear() {} 2031 2032 template <typename _Graph> 2033 struct Constraints { constraintsConstraints2034 void constraints() { 2035 checkConcept<Base, _Graph>(); 2036 graph.clear(); 2037 } 2038 2039 _Graph graph; 2040 }; 2041 }; 2042 2043 /// \brief An empty clearable base undirected graph class. 2044 /// 2045 /// This class provides beside the core undirected graph features 2046 /// core clear functions for the undirected graph structure. The 2047 /// main difference between the base and this interface is that 2048 /// the graph alterations should handled already on this level. 2049 template <typename _Base = BaseUGraphComponent> 2050 class ClearableUGraphComponent : public ClearableGraphComponent<_Base> { 2051 public: 2052 2053 typedef _Base Base; 2054 2055 template <typename _Graph> 2056 struct Constraints { constraintsConstraints2057 void constraints() { 2058 checkConcept<ClearableUGraphComponent<Base>, _Graph>(); 2059 } 2060 2061 _Graph graph; 2062 }; 2063 }; 2064 2065 /// \brief An empty clearable base bipartite undirected graph 2066 /// class. 2067 /// 2068 /// This class provides beside the core bipartite undirected graph 2069 /// features core clear functions for the undirected graph 2070 /// structure. The main difference between the base and this 2071 /// interface is that the graph alterations should handled already 2072 /// on this level. 2073 template <typename _Base = BaseUGraphComponent> 2074 class ClearableBpUGraphComponent : public ClearableUGraphComponent<_Base> { 2075 public: 2076 2077 typedef _Base Base; 2078 2079 template <typename _Graph> 2080 struct Constraints { constraintsConstraints2081 void constraints() { 2082 checkConcept<ClearableBpUGraphComponent<Base>, _Graph>(); 2083 } 2084 2085 }; 2086 2087 }; 2088 2089 } 2090 2091 } 2092 2093 #endif 2094