1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 * 5 * Copyright (C) 2003-2013 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 undirected graphs. 22 23 #ifndef LEMON_CONCEPTS_BPGRAPH_H 24 #define LEMON_CONCEPTS_BPGRAPH_H 25 26 #include <lemon/concepts/graph_components.h> 27 #include <lemon/concepts/maps.h> 28 #include <lemon/concept_check.h> 29 #include <lemon/core.h> 30 31 namespace lemon { 32 namespace concepts { 33 34 /// \ingroup graph_concepts 35 /// 36 /// \brief Class describing the concept of undirected bipartite graphs. 37 /// 38 /// This class describes the common interface of all undirected 39 /// bipartite graphs. 40 /// 41 /// Like all concept classes, it only provides an interface 42 /// without any sensible implementation. So any general algorithm for 43 /// undirected bipartite graphs should compile with this class, 44 /// but it will not run properly, of course. 45 /// An actual graph implementation like \ref ListBpGraph or 46 /// \ref SmartBpGraph may have additional functionality. 47 /// 48 /// The bipartite graphs also fulfill the concept of \ref Graph 49 /// "undirected graphs". Bipartite graphs provide a bipartition of 50 /// the node set, namely a red and blue set of the nodes. The 51 /// nodes can be iterated with the RedNodeIt and BlueNodeIt in the 52 /// two node sets. With RedNodeMap and BlueNodeMap values can be 53 /// assigned to the nodes in the two sets. 54 /// 55 /// The edges of the graph cannot connect two nodes of the same 56 /// set. The edges inherent orientation is from the red nodes to 57 /// the blue nodes. 58 /// 59 /// \sa Graph 60 class BpGraph { 61 private: 62 /// BpGraphs are \e not copy constructible. Use bpGraphCopy instead. BpGraph(const BpGraph &)63 BpGraph(const BpGraph&) {} 64 /// \brief Assignment of a graph to another one is \e not allowed. 65 /// Use bpGraphCopy instead. 66 void operator=(const BpGraph&) {} 67 68 public: 69 /// Default constructor. BpGraph()70 BpGraph() {} 71 72 /// \brief Undirected graphs should be tagged with \c UndirectedTag. 73 /// 74 /// Undirected graphs should be tagged with \c UndirectedTag. 75 /// 76 /// This tag helps the \c enable_if technics to make compile time 77 /// specializations for undirected graphs. 78 typedef True UndirectedTag; 79 80 /// The node type of the graph 81 82 /// This class identifies a node of the graph. It also serves 83 /// as a base class of the node iterators, 84 /// thus they convert to this type. 85 class Node { 86 public: 87 /// Default constructor 88 89 /// Default constructor. 90 /// \warning It sets the object to an undefined value. Node()91 Node() { } 92 /// Copy constructor. 93 94 /// Copy constructor. 95 /// Node(const Node &)96 Node(const Node&) { } 97 98 /// %Invalid constructor \& conversion. 99 100 /// Initializes the object to be invalid. 101 /// \sa Invalid for more details. Node(Invalid)102 Node(Invalid) { } 103 /// Equality operator 104 105 /// Equality operator. 106 /// 107 /// Two iterators are equal if and only if they point to the 108 /// same object or both are \c INVALID. 109 bool operator==(Node) const { return true; } 110 111 /// Inequality operator 112 113 /// Inequality operator. 114 bool operator!=(Node) const { return true; } 115 116 /// Artificial ordering operator. 117 118 /// Artificial ordering operator. 119 /// 120 /// \note This operator only has to define some strict ordering of 121 /// the items; this order has nothing to do with the iteration 122 /// ordering of the items. 123 bool operator<(Node) const { return false; } 124 125 }; 126 127 /// Class to represent red nodes. 128 129 /// This class represents the red nodes of the graph. It does 130 /// not supposed to be used directly, because the nodes can be 131 /// represented as Node instances. This class can be used as 132 /// template parameter for special map classes. 133 class RedNode : public Node { 134 public: 135 /// Default constructor 136 137 /// Default constructor. 138 /// \warning It sets the object to an undefined value. RedNode()139 RedNode() { } 140 /// Copy constructor. 141 142 /// Copy constructor. 143 /// RedNode(const RedNode &)144 RedNode(const RedNode&) : Node() { } 145 146 /// %Invalid constructor \& conversion. 147 148 /// Initializes the object to be invalid. 149 /// \sa Invalid for more details. RedNode(Invalid)150 RedNode(Invalid) { } 151 152 }; 153 154 /// Class to represent blue nodes. 155 156 /// This class represents the blue nodes of the graph. It does 157 /// not supposed to be used directly, because the nodes can be 158 /// represented as Node instances. This class can be used as 159 /// template parameter for special map classes. 160 class BlueNode : public Node { 161 public: 162 /// Default constructor 163 164 /// Default constructor. 165 /// \warning It sets the object to an undefined value. BlueNode()166 BlueNode() { } 167 /// Copy constructor. 168 169 /// Copy constructor. 170 /// BlueNode(const BlueNode &)171 BlueNode(const BlueNode&) : Node() { } 172 173 /// %Invalid constructor \& conversion. 174 175 /// Initializes the object to be invalid. 176 /// \sa Invalid for more details. BlueNode(Invalid)177 BlueNode(Invalid) { } 178 179 }; 180 181 /// Iterator class for the red nodes. 182 183 /// This iterator goes through each red node of the graph. 184 /// Its usage is quite simple, for example, you can count the number 185 /// of red nodes in a graph \c g of type \c %BpGraph like this: 186 ///\code 187 /// int count=0; 188 /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count; 189 ///\endcode 190 class RedNodeIt : public RedNode { 191 public: 192 /// Default constructor 193 194 /// Default constructor. 195 /// \warning It sets the iterator to an undefined value. RedNodeIt()196 RedNodeIt() { } 197 /// Copy constructor. 198 199 /// Copy constructor. 200 /// RedNodeIt(const RedNodeIt & n)201 RedNodeIt(const RedNodeIt& n) : RedNode(n) { } 202 /// %Invalid constructor \& conversion. 203 204 /// Initializes the iterator to be invalid. 205 /// \sa Invalid for more details. RedNodeIt(Invalid)206 RedNodeIt(Invalid) { } 207 /// Sets the iterator to the first red node. 208 209 /// Sets the iterator to the first red node of the given 210 /// digraph. RedNodeIt(const BpGraph &)211 explicit RedNodeIt(const BpGraph&) { } 212 /// Sets the iterator to the given red node. 213 214 /// Sets the iterator to the given red node of the given 215 /// digraph. RedNodeIt(const BpGraph &,const RedNode &)216 RedNodeIt(const BpGraph&, const RedNode&) { } 217 /// Next node. 218 219 /// Assign the iterator to the next red node. 220 /// 221 RedNodeIt& operator++() { return *this; } 222 }; 223 224 /// Iterator class for the blue nodes. 225 226 /// This iterator goes through each blue node of the graph. 227 /// Its usage is quite simple, for example, you can count the number 228 /// of blue nodes in a graph \c g of type \c %BpGraph like this: 229 ///\code 230 /// int count=0; 231 /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count; 232 ///\endcode 233 class BlueNodeIt : public BlueNode { 234 public: 235 /// Default constructor 236 237 /// Default constructor. 238 /// \warning It sets the iterator to an undefined value. BlueNodeIt()239 BlueNodeIt() { } 240 /// Copy constructor. 241 242 /// Copy constructor. 243 /// BlueNodeIt(const BlueNodeIt & n)244 BlueNodeIt(const BlueNodeIt& n) : BlueNode(n) { } 245 /// %Invalid constructor \& conversion. 246 247 /// Initializes the iterator to be invalid. 248 /// \sa Invalid for more details. BlueNodeIt(Invalid)249 BlueNodeIt(Invalid) { } 250 /// Sets the iterator to the first blue node. 251 252 /// Sets the iterator to the first blue node of the given 253 /// digraph. BlueNodeIt(const BpGraph &)254 explicit BlueNodeIt(const BpGraph&) { } 255 /// Sets the iterator to the given blue node. 256 257 /// Sets the iterator to the given blue node of the given 258 /// digraph. BlueNodeIt(const BpGraph &,const BlueNode &)259 BlueNodeIt(const BpGraph&, const BlueNode&) { } 260 /// Next node. 261 262 /// Assign the iterator to the next blue node. 263 /// 264 BlueNodeIt& operator++() { return *this; } 265 }; 266 267 /// Iterator class for the nodes. 268 269 /// This iterator goes through each node of the graph. 270 /// Its usage is quite simple, for example, you can count the number 271 /// of nodes in a graph \c g of type \c %BpGraph like this: 272 ///\code 273 /// int count=0; 274 /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count; 275 ///\endcode 276 class NodeIt : public Node { 277 public: 278 /// Default constructor 279 280 /// Default constructor. 281 /// \warning It sets the iterator to an undefined value. NodeIt()282 NodeIt() { } 283 /// Copy constructor. 284 285 /// Copy constructor. 286 /// NodeIt(const NodeIt & n)287 NodeIt(const NodeIt& n) : Node(n) { } 288 /// %Invalid constructor \& conversion. 289 290 /// Initializes the iterator to be invalid. 291 /// \sa Invalid for more details. NodeIt(Invalid)292 NodeIt(Invalid) { } 293 /// Sets the iterator to the first node. 294 295 /// Sets the iterator to the first node of the given digraph. 296 /// NodeIt(const BpGraph &)297 explicit NodeIt(const BpGraph&) { } 298 /// Sets the iterator to the given node. 299 300 /// Sets the iterator to the given node of the given digraph. 301 /// NodeIt(const BpGraph &,const Node &)302 NodeIt(const BpGraph&, const Node&) { } 303 /// Next node. 304 305 /// Assign the iterator to the next node. 306 /// 307 NodeIt& operator++() { return *this; } 308 }; 309 310 311 /// The edge type of the graph 312 313 /// This class identifies an edge of the graph. It also serves 314 /// as a base class of the edge iterators, 315 /// thus they will convert to this type. 316 class Edge { 317 public: 318 /// Default constructor 319 320 /// Default constructor. 321 /// \warning It sets the object to an undefined value. Edge()322 Edge() { } 323 /// Copy constructor. 324 325 /// Copy constructor. 326 /// Edge(const Edge &)327 Edge(const Edge&) { } 328 /// %Invalid constructor \& conversion. 329 330 /// Initializes the object to be invalid. 331 /// \sa Invalid for more details. Edge(Invalid)332 Edge(Invalid) { } 333 /// Equality operator 334 335 /// Equality operator. 336 /// 337 /// Two iterators are equal if and only if they point to the 338 /// same object or both are \c INVALID. 339 bool operator==(Edge) const { return true; } 340 /// Inequality operator 341 342 /// Inequality operator. 343 bool operator!=(Edge) const { return true; } 344 345 /// Artificial ordering operator. 346 347 /// Artificial ordering operator. 348 /// 349 /// \note This operator only has to define some strict ordering of 350 /// the edges; this order has nothing to do with the iteration 351 /// ordering of the edges. 352 bool operator<(Edge) const { return false; } 353 }; 354 355 /// Iterator class for the edges. 356 357 /// This iterator goes through each edge of the graph. 358 /// Its usage is quite simple, for example, you can count the number 359 /// of edges in a graph \c g of type \c %BpGraph as follows: 360 ///\code 361 /// int count=0; 362 /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count; 363 ///\endcode 364 class EdgeIt : public Edge { 365 public: 366 /// Default constructor 367 368 /// Default constructor. 369 /// \warning It sets the iterator to an undefined value. EdgeIt()370 EdgeIt() { } 371 /// Copy constructor. 372 373 /// Copy constructor. 374 /// EdgeIt(const EdgeIt & e)375 EdgeIt(const EdgeIt& e) : Edge(e) { } 376 /// %Invalid constructor \& conversion. 377 378 /// Initializes the iterator to be invalid. 379 /// \sa Invalid for more details. EdgeIt(Invalid)380 EdgeIt(Invalid) { } 381 /// Sets the iterator to the first edge. 382 383 /// Sets the iterator to the first edge of the given graph. 384 /// EdgeIt(const BpGraph &)385 explicit EdgeIt(const BpGraph&) { } 386 /// Sets the iterator to the given edge. 387 388 /// Sets the iterator to the given edge of the given graph. 389 /// EdgeIt(const BpGraph &,const Edge &)390 EdgeIt(const BpGraph&, const Edge&) { } 391 /// Next edge 392 393 /// Assign the iterator to the next edge. 394 /// 395 EdgeIt& operator++() { return *this; } 396 }; 397 398 /// Iterator class for the incident edges of a node. 399 400 /// This iterator goes trough the incident undirected edges 401 /// of a certain node of a graph. 402 /// Its usage is quite simple, for example, you can compute the 403 /// degree (i.e. the number of incident edges) of a node \c n 404 /// in a graph \c g of type \c %BpGraph as follows. 405 /// 406 ///\code 407 /// int count=0; 408 /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 409 ///\endcode 410 /// 411 /// \warning Loop edges will be iterated twice. 412 class IncEdgeIt : public Edge { 413 public: 414 /// Default constructor 415 416 /// Default constructor. 417 /// \warning It sets the iterator to an undefined value. IncEdgeIt()418 IncEdgeIt() { } 419 /// Copy constructor. 420 421 /// Copy constructor. 422 /// IncEdgeIt(const IncEdgeIt & e)423 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } 424 /// %Invalid constructor \& conversion. 425 426 /// Initializes the iterator to be invalid. 427 /// \sa Invalid for more details. IncEdgeIt(Invalid)428 IncEdgeIt(Invalid) { } 429 /// Sets the iterator to the first incident edge. 430 431 /// Sets the iterator to the first incident edge of the given node. 432 /// IncEdgeIt(const BpGraph &,const Node &)433 IncEdgeIt(const BpGraph&, const Node&) { } 434 /// Sets the iterator to the given edge. 435 436 /// Sets the iterator to the given edge of the given graph. 437 /// IncEdgeIt(const BpGraph &,const Edge &)438 IncEdgeIt(const BpGraph&, const Edge&) { } 439 /// Next incident edge 440 441 /// Assign the iterator to the next incident edge 442 /// of the corresponding node. 443 IncEdgeIt& operator++() { return *this; } 444 }; 445 446 /// The arc type of the graph 447 448 /// This class identifies a directed arc of the graph. It also serves 449 /// as a base class of the arc iterators, 450 /// thus they will convert to this type. 451 class Arc { 452 public: 453 /// Default constructor 454 455 /// Default constructor. 456 /// \warning It sets the object to an undefined value. Arc()457 Arc() { } 458 /// Copy constructor. 459 460 /// Copy constructor. 461 /// Arc(const Arc &)462 Arc(const Arc&) { } 463 /// %Invalid constructor \& conversion. 464 465 /// Initializes the object to be invalid. 466 /// \sa Invalid for more details. Arc(Invalid)467 Arc(Invalid) { } 468 /// Equality operator 469 470 /// Equality operator. 471 /// 472 /// Two iterators are equal if and only if they point to the 473 /// same object or both are \c INVALID. 474 bool operator==(Arc) const { return true; } 475 /// Inequality operator 476 477 /// Inequality operator. 478 bool operator!=(Arc) const { return true; } 479 480 /// Artificial ordering operator. 481 482 /// Artificial ordering operator. 483 /// 484 /// \note This operator only has to define some strict ordering of 485 /// the arcs; this order has nothing to do with the iteration 486 /// ordering of the arcs. 487 bool operator<(Arc) const { return false; } 488 489 /// Converison to \c Edge 490 491 /// Converison to \c Edge. 492 /// Edge()493 operator Edge() const { return Edge(); } 494 }; 495 496 /// Iterator class for the arcs. 497 498 /// This iterator goes through each directed arc of the graph. 499 /// Its usage is quite simple, for example, you can count the number 500 /// of arcs in a graph \c g of type \c %BpGraph as follows: 501 ///\code 502 /// int count=0; 503 /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count; 504 ///\endcode 505 class ArcIt : public Arc { 506 public: 507 /// Default constructor 508 509 /// Default constructor. 510 /// \warning It sets the iterator to an undefined value. ArcIt()511 ArcIt() { } 512 /// Copy constructor. 513 514 /// Copy constructor. 515 /// ArcIt(const ArcIt & e)516 ArcIt(const ArcIt& e) : Arc(e) { } 517 /// %Invalid constructor \& conversion. 518 519 /// Initializes the iterator to be invalid. 520 /// \sa Invalid for more details. ArcIt(Invalid)521 ArcIt(Invalid) { } 522 /// Sets the iterator to the first arc. 523 524 /// Sets the iterator to the first arc of the given graph. 525 /// ArcIt(const BpGraph & g)526 explicit ArcIt(const BpGraph &g) 527 { 528 ::lemon::ignore_unused_variable_warning(g); 529 } 530 /// Sets the iterator to the given arc. 531 532 /// Sets the iterator to the given arc of the given graph. 533 /// ArcIt(const BpGraph &,const Arc &)534 ArcIt(const BpGraph&, const Arc&) { } 535 /// Next arc 536 537 /// Assign the iterator to the next arc. 538 /// 539 ArcIt& operator++() { return *this; } 540 }; 541 542 /// Iterator class for the outgoing arcs of a node. 543 544 /// This iterator goes trough the \e outgoing directed arcs of a 545 /// certain node of a graph. 546 /// Its usage is quite simple, for example, you can count the number 547 /// of outgoing arcs of a node \c n 548 /// in a graph \c g of type \c %BpGraph as follows. 549 ///\code 550 /// int count=0; 551 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; 552 ///\endcode 553 class OutArcIt : public Arc { 554 public: 555 /// Default constructor 556 557 /// Default constructor. 558 /// \warning It sets the iterator to an undefined value. OutArcIt()559 OutArcIt() { } 560 /// Copy constructor. 561 562 /// Copy constructor. 563 /// OutArcIt(const OutArcIt & e)564 OutArcIt(const OutArcIt& e) : Arc(e) { } 565 /// %Invalid constructor \& conversion. 566 567 /// Initializes the iterator to be invalid. 568 /// \sa Invalid for more details. OutArcIt(Invalid)569 OutArcIt(Invalid) { } 570 /// Sets the iterator to the first outgoing arc. 571 572 /// Sets the iterator to the first outgoing arc of the given node. 573 /// OutArcIt(const BpGraph & n,const Node & g)574 OutArcIt(const BpGraph& n, const Node& g) { 575 ::lemon::ignore_unused_variable_warning(n); 576 ::lemon::ignore_unused_variable_warning(g); 577 } 578 /// Sets the iterator to the given arc. 579 580 /// Sets the iterator to the given arc of the given graph. 581 /// OutArcIt(const BpGraph &,const Arc &)582 OutArcIt(const BpGraph&, const Arc&) { } 583 /// Next outgoing arc 584 585 /// Assign the iterator to the next 586 /// outgoing arc of the corresponding node. 587 OutArcIt& operator++() { return *this; } 588 }; 589 590 /// Iterator class for the incoming arcs of a node. 591 592 /// This iterator goes trough the \e incoming directed arcs of a 593 /// certain node of a graph. 594 /// Its usage is quite simple, for example, you can count the number 595 /// of incoming arcs of a node \c n 596 /// in a graph \c g of type \c %BpGraph as follows. 597 ///\code 598 /// int count=0; 599 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; 600 ///\endcode 601 class InArcIt : public Arc { 602 public: 603 /// Default constructor 604 605 /// Default constructor. 606 /// \warning It sets the iterator to an undefined value. InArcIt()607 InArcIt() { } 608 /// Copy constructor. 609 610 /// Copy constructor. 611 /// InArcIt(const InArcIt & e)612 InArcIt(const InArcIt& e) : Arc(e) { } 613 /// %Invalid constructor \& conversion. 614 615 /// Initializes the iterator to be invalid. 616 /// \sa Invalid for more details. InArcIt(Invalid)617 InArcIt(Invalid) { } 618 /// Sets the iterator to the first incoming arc. 619 620 /// Sets the iterator to the first incoming arc of the given node. 621 /// InArcIt(const BpGraph & g,const Node & n)622 InArcIt(const BpGraph& g, const Node& n) { 623 ::lemon::ignore_unused_variable_warning(n); 624 ::lemon::ignore_unused_variable_warning(g); 625 } 626 /// Sets the iterator to the given arc. 627 628 /// Sets the iterator to the given arc of the given graph. 629 /// InArcIt(const BpGraph &,const Arc &)630 InArcIt(const BpGraph&, const Arc&) { } 631 /// Next incoming arc 632 633 /// Assign the iterator to the next 634 /// incoming arc of the corresponding node. 635 InArcIt& operator++() { return *this; } 636 }; 637 638 /// \brief Standard graph map type for the nodes. 639 /// 640 /// Standard graph map type for the nodes. 641 /// It conforms to the ReferenceMap concept. 642 template<class T> 643 class NodeMap : public ReferenceMap<Node, T, T&, const T&> 644 { 645 public: 646 647 /// Constructor NodeMap(const BpGraph &)648 explicit NodeMap(const BpGraph&) { } 649 /// Constructor with given initial value NodeMap(const BpGraph &,T)650 NodeMap(const BpGraph&, T) { } 651 652 private: 653 ///Copy constructor NodeMap(const NodeMap & nm)654 NodeMap(const NodeMap& nm) : 655 ReferenceMap<Node, T, T&, const T&>(nm) { } 656 ///Assignment operator 657 template <typename CMap> 658 NodeMap& operator=(const CMap&) { 659 checkConcept<ReadMap<Node, T>, CMap>(); 660 return *this; 661 } 662 }; 663 664 /// \brief Standard graph map type for the red nodes. 665 /// 666 /// Standard graph map type for the red nodes. 667 /// It conforms to the ReferenceMap concept. 668 template<class T> 669 class RedNodeMap : public ReferenceMap<Node, T, T&, const T&> 670 { 671 public: 672 673 /// Constructor RedNodeMap(const BpGraph &)674 explicit RedNodeMap(const BpGraph&) { } 675 /// Constructor with given initial value RedNodeMap(const BpGraph &,T)676 RedNodeMap(const BpGraph&, T) { } 677 678 private: 679 ///Copy constructor RedNodeMap(const RedNodeMap & nm)680 RedNodeMap(const RedNodeMap& nm) : 681 ReferenceMap<Node, T, T&, const T&>(nm) { } 682 ///Assignment operator 683 template <typename CMap> 684 RedNodeMap& operator=(const CMap&) { 685 checkConcept<ReadMap<Node, T>, CMap>(); 686 return *this; 687 } 688 }; 689 690 /// \brief Standard graph map type for the blue nodes. 691 /// 692 /// Standard graph map type for the blue nodes. 693 /// It conforms to the ReferenceMap concept. 694 template<class T> 695 class BlueNodeMap : public ReferenceMap<Node, T, T&, const T&> 696 { 697 public: 698 699 /// Constructor BlueNodeMap(const BpGraph &)700 explicit BlueNodeMap(const BpGraph&) { } 701 /// Constructor with given initial value BlueNodeMap(const BpGraph &,T)702 BlueNodeMap(const BpGraph&, T) { } 703 704 private: 705 ///Copy constructor BlueNodeMap(const BlueNodeMap & nm)706 BlueNodeMap(const BlueNodeMap& nm) : 707 ReferenceMap<Node, T, T&, const T&>(nm) { } 708 ///Assignment operator 709 template <typename CMap> 710 BlueNodeMap& operator=(const CMap&) { 711 checkConcept<ReadMap<Node, T>, CMap>(); 712 return *this; 713 } 714 }; 715 716 /// \brief Standard graph map type for the arcs. 717 /// 718 /// Standard graph map type for the arcs. 719 /// It conforms to the ReferenceMap concept. 720 template<class T> 721 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> 722 { 723 public: 724 725 /// Constructor ArcMap(const BpGraph &)726 explicit ArcMap(const BpGraph&) { } 727 /// Constructor with given initial value ArcMap(const BpGraph &,T)728 ArcMap(const BpGraph&, T) { } 729 730 private: 731 ///Copy constructor ArcMap(const ArcMap & em)732 ArcMap(const ArcMap& em) : 733 ReferenceMap<Arc, T, T&, const T&>(em) { } 734 ///Assignment operator 735 template <typename CMap> 736 ArcMap& operator=(const CMap&) { 737 checkConcept<ReadMap<Arc, T>, CMap>(); 738 return *this; 739 } 740 }; 741 742 /// \brief Standard graph map type for the edges. 743 /// 744 /// Standard graph map type for the edges. 745 /// It conforms to the ReferenceMap concept. 746 template<class T> 747 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&> 748 { 749 public: 750 751 /// Constructor EdgeMap(const BpGraph &)752 explicit EdgeMap(const BpGraph&) { } 753 /// Constructor with given initial value EdgeMap(const BpGraph &,T)754 EdgeMap(const BpGraph&, T) { } 755 756 private: 757 ///Copy constructor EdgeMap(const EdgeMap & em)758 EdgeMap(const EdgeMap& em) : 759 ReferenceMap<Edge, T, T&, const T&>(em) {} 760 ///Assignment operator 761 template <typename CMap> 762 EdgeMap& operator=(const CMap&) { 763 checkConcept<ReadMap<Edge, T>, CMap>(); 764 return *this; 765 } 766 }; 767 768 /// \brief Gives back %true for red nodes. 769 /// 770 /// Gives back %true for red nodes. red(const Node &)771 bool red(const Node&) const { return true; } 772 773 /// \brief Gives back %true for blue nodes. 774 /// 775 /// Gives back %true for blue nodes. blue(const Node &)776 bool blue(const Node&) const { return true; } 777 778 /// \brief Converts the node to red node object. 779 /// 780 /// This function converts unsafely the node to red node 781 /// object. It should be called only if the node is from the red 782 /// partition or INVALID. asRedNodeUnsafe(const Node &)783 RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); } 784 785 /// \brief Converts the node to blue node object. 786 /// 787 /// This function converts unsafely the node to blue node 788 /// object. It should be called only if the node is from the red 789 /// partition or INVALID. asBlueNodeUnsafe(const Node &)790 BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); } 791 792 /// \brief Converts the node to red node object. 793 /// 794 /// This function converts safely the node to red node 795 /// object. If the node is not from the red partition, then it 796 /// returns INVALID. asRedNode(const Node &)797 RedNode asRedNode(const Node&) const { return RedNode(); } 798 799 /// \brief Converts the node to blue node object. 800 /// 801 /// This function converts unsafely the node to blue node 802 /// object. If the node is not from the blue partition, then it 803 /// returns INVALID. asBlueNode(const Node &)804 BlueNode asBlueNode(const Node&) const { return BlueNode(); } 805 806 /// \brief Gives back the red end node of the edge. 807 /// 808 /// Gives back the red end node of the edge. redNode(const Edge &)809 RedNode redNode(const Edge&) const { return RedNode(); } 810 811 /// \brief Gives back the blue end node of the edge. 812 /// 813 /// Gives back the blue end node of the edge. blueNode(const Edge &)814 BlueNode blueNode(const Edge&) const { return BlueNode(); } 815 816 /// \brief The first node of the edge. 817 /// 818 /// It is a synonim for the \c redNode(). u(Edge)819 Node u(Edge) const { return INVALID; } 820 821 /// \brief The second node of the edge. 822 /// 823 /// It is a synonim for the \c blueNode(). v(Edge)824 Node v(Edge) const { return INVALID; } 825 826 /// \brief The source node of the arc. 827 /// 828 /// Returns the source node of the given arc. source(Arc)829 Node source(Arc) const { return INVALID; } 830 831 /// \brief The target node of the arc. 832 /// 833 /// Returns the target node of the given arc. target(Arc)834 Node target(Arc) const { return INVALID; } 835 836 /// \brief The ID of the node. 837 /// 838 /// Returns the ID of the given node. id(Node)839 int id(Node) const { return -1; } 840 841 /// \brief The red ID of the node. 842 /// 843 /// Returns the red ID of the given node. id(RedNode)844 int id(RedNode) const { return -1; } 845 846 /// \brief The blue ID of the node. 847 /// 848 /// Returns the blue ID of the given node. id(BlueNode)849 int id(BlueNode) const { return -1; } 850 851 /// \brief The ID of the edge. 852 /// 853 /// Returns the ID of the given edge. id(Edge)854 int id(Edge) const { return -1; } 855 856 /// \brief The ID of the arc. 857 /// 858 /// Returns the ID of the given arc. id(Arc)859 int id(Arc) const { return -1; } 860 861 /// \brief The node with the given ID. 862 /// 863 /// Returns the node with the given ID. 864 /// \pre The argument should be a valid node ID in the graph. nodeFromId(int)865 Node nodeFromId(int) const { return INVALID; } 866 867 /// \brief The edge with the given ID. 868 /// 869 /// Returns the edge with the given ID. 870 /// \pre The argument should be a valid edge ID in the graph. edgeFromId(int)871 Edge edgeFromId(int) const { return INVALID; } 872 873 /// \brief The arc with the given ID. 874 /// 875 /// Returns the arc with the given ID. 876 /// \pre The argument should be a valid arc ID in the graph. arcFromId(int)877 Arc arcFromId(int) const { return INVALID; } 878 879 /// \brief An upper bound on the node IDs. 880 /// 881 /// Returns an upper bound on the node IDs. maxNodeId()882 int maxNodeId() const { return -1; } 883 884 /// \brief An upper bound on the red IDs. 885 /// 886 /// Returns an upper bound on the red IDs. maxRedId()887 int maxRedId() const { return -1; } 888 889 /// \brief An upper bound on the blue IDs. 890 /// 891 /// Returns an upper bound on the blue IDs. maxBlueId()892 int maxBlueId() const { return -1; } 893 894 /// \brief An upper bound on the edge IDs. 895 /// 896 /// Returns an upper bound on the edge IDs. maxEdgeId()897 int maxEdgeId() const { return -1; } 898 899 /// \brief An upper bound on the arc IDs. 900 /// 901 /// Returns an upper bound on the arc IDs. maxArcId()902 int maxArcId() const { return -1; } 903 904 /// \brief The direction of the arc. 905 /// 906 /// Returns \c true if the given arc goes from a red node to a blue node. direction(Arc)907 bool direction(Arc) const { return true; } 908 909 /// \brief Direct the edge. 910 /// 911 /// Direct the given edge. The returned arc 912 /// represents the given edge and its direction comes 913 /// from the bool parameter. If it is \c true, then the source of the node 914 /// will be a red node. direct(Edge,bool)915 Arc direct(Edge, bool) const { 916 return INVALID; 917 } 918 919 /// \brief Direct the edge. 920 /// 921 /// Direct the given edge. The returned arc represents the given 922 /// edge and its source node is the given node. direct(Edge,Node)923 Arc direct(Edge, Node) const { 924 return INVALID; 925 } 926 927 /// \brief The oppositely directed arc. 928 /// 929 /// Returns the oppositely directed arc representing the same edge. oppositeArc(Arc)930 Arc oppositeArc(Arc) const { return INVALID; } 931 932 /// \brief The opposite node on the edge. 933 /// 934 /// Returns the opposite node on the given edge. oppositeNode(Node,Edge)935 Node oppositeNode(Node, Edge) const { return INVALID; } 936 first(Node &)937 void first(Node&) const {} next(Node &)938 void next(Node&) const {} 939 firstRed(RedNode &)940 void firstRed(RedNode&) const {} nextRed(RedNode &)941 void nextRed(RedNode&) const {} 942 firstBlue(BlueNode &)943 void firstBlue(BlueNode&) const {} nextBlue(BlueNode &)944 void nextBlue(BlueNode&) const {} 945 first(Edge &)946 void first(Edge&) const {} next(Edge &)947 void next(Edge&) const {} 948 first(Arc &)949 void first(Arc&) const {} next(Arc &)950 void next(Arc&) const {} 951 firstOut(Arc &,Node)952 void firstOut(Arc&, Node) const {} nextOut(Arc &)953 void nextOut(Arc&) const {} 954 firstIn(Arc &,Node)955 void firstIn(Arc&, Node) const {} nextIn(Arc &)956 void nextIn(Arc&) const {} 957 firstInc(Edge &,bool &,const Node &)958 void firstInc(Edge &, bool &, const Node &) const {} nextInc(Edge &,bool &)959 void nextInc(Edge &, bool &) const {} 960 961 // The second parameter is dummy. fromId(int,Node)962 Node fromId(int, Node) const { return INVALID; } 963 // The second parameter is dummy. fromId(int,Edge)964 Edge fromId(int, Edge) const { return INVALID; } 965 // The second parameter is dummy. fromId(int,Arc)966 Arc fromId(int, Arc) const { return INVALID; } 967 968 // Dummy parameter. maxId(Node)969 int maxId(Node) const { return -1; } 970 // Dummy parameter. maxId(RedNode)971 int maxId(RedNode) const { return -1; } 972 // Dummy parameter. maxId(BlueNode)973 int maxId(BlueNode) const { return -1; } 974 // Dummy parameter. maxId(Edge)975 int maxId(Edge) const { return -1; } 976 // Dummy parameter. maxId(Arc)977 int maxId(Arc) const { return -1; } 978 979 /// \brief The base node of the iterator. 980 /// 981 /// Returns the base node of the given incident edge iterator. baseNode(IncEdgeIt)982 Node baseNode(IncEdgeIt) const { return INVALID; } 983 984 /// \brief The running node of the iterator. 985 /// 986 /// Returns the running node of the given incident edge iterator. runningNode(IncEdgeIt)987 Node runningNode(IncEdgeIt) const { return INVALID; } 988 989 /// \brief The base node of the iterator. 990 /// 991 /// Returns the base node of the given outgoing arc iterator 992 /// (i.e. the source node of the corresponding arc). baseNode(OutArcIt)993 Node baseNode(OutArcIt) const { return INVALID; } 994 995 /// \brief The running node of the iterator. 996 /// 997 /// Returns the running node of the given outgoing arc iterator 998 /// (i.e. the target node of the corresponding arc). runningNode(OutArcIt)999 Node runningNode(OutArcIt) const { return INVALID; } 1000 1001 /// \brief The base node of the iterator. 1002 /// 1003 /// Returns the base node of the given incoming arc iterator 1004 /// (i.e. the target node of the corresponding arc). baseNode(InArcIt)1005 Node baseNode(InArcIt) const { return INVALID; } 1006 1007 /// \brief The running node of the iterator. 1008 /// 1009 /// Returns the running node of the given incoming arc iterator 1010 /// (i.e. the source node of the corresponding arc). runningNode(InArcIt)1011 Node runningNode(InArcIt) const { return INVALID; } 1012 1013 template <typename _BpGraph> 1014 struct Constraints { constraintsConstraints1015 void constraints() { 1016 checkConcept<BaseBpGraphComponent, _BpGraph>(); 1017 checkConcept<IterableBpGraphComponent<>, _BpGraph>(); 1018 checkConcept<IDableBpGraphComponent<>, _BpGraph>(); 1019 checkConcept<MappableBpGraphComponent<>, _BpGraph>(); 1020 } 1021 }; 1022 1023 }; 1024 1025 } 1026 1027 } 1028 1029 #endif 1030