Changeset 1627:3fd1ba6e9872 in lemon0.x for lemon/concept/undir_graph.h
 Timestamp:
 08/11/05 17:55:17 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2135
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/concept/undir_graph.h
r1624 r1627 120 120 121 121 bool b; 122 b = graph.forward(e); 122 b = graph.direction(e); 123 Edge e = graph.direct(UndirEdge(), true); 124 e = graph.direct(UndirEdge(), n); 125 123 126 ignore_unused_variable_warning(b); 124 127 } … … 233 236 /// explanation of this and more see also the page \ref undir_graphs, 234 237 /// a tutorial about undirected graphs. 235 236 class UndirGraph : public StaticGraph { 238 /// 239 /// You can assume that all undirected graph can be handled 240 /// as a static directed graph. This way it is fully conform 241 /// to the StaticGraph concept. 242 243 class UndirGraph { 237 244 public: 238 245 ///\e … … 242 249 typedef True UndirTag; 243 250 251 /// The base type of node iterators, 252 /// or in other words, the trivial node iterator. 253 254 /// This is the base type of each node iterator, 255 /// thus each kind of node iterator converts to this. 256 /// More precisely each kind of node iterator should be inherited 257 /// from the trivial node iterator. 258 class Node { 259 public: 260 /// Default constructor 261 262 /// @warning The default constructor sets the iterator 263 /// to an undefined value. 264 Node() { } 265 /// Copy constructor. 266 267 /// Copy constructor. 268 /// 269 Node(const Node&) { } 270 271 /// Invalid constructor \& conversion. 272 273 /// This constructor initializes the iterator to be invalid. 274 /// \sa Invalid for more details. 275 Node(Invalid) { } 276 /// Equality operator 277 278 /// Two iterators are equal if and only if they point to the 279 /// same object or both are invalid. 280 bool operator==(Node) const { return true; } 281 282 /// Inequality operator 283 284 /// \sa operator==(Node n) 285 /// 286 bool operator!=(Node) const { return true; } 287 288 /// Artificial ordering operator. 289 290 /// To allow the use of graph descriptors as key type in std::map or 291 /// similar associative container we require this. 292 /// 293 /// \note This operator only have to define some strict ordering of 294 /// the items; this order has nothing to do with the iteration 295 /// ordering of the items. 296 /// 297 /// \bug This is a technical requirement. Do we really need this? 298 bool operator<(Node) const { return false; } 299 300 }; 301 302 /// This iterator goes through each node. 303 304 /// This iterator goes through each node. 305 /// Its usage is quite simple, for example you can count the number 306 /// of nodes in graph \c g of type \c Graph like this: 307 /// \code 308 /// int count=0; 309 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; 310 /// \endcode 311 class NodeIt : public Node { 312 public: 313 /// Default constructor 314 315 /// @warning The default constructor sets the iterator 316 /// to an undefined value. 317 NodeIt() { } 318 /// Copy constructor. 319 320 /// Copy constructor. 321 /// 322 NodeIt(const NodeIt& n) : Node(n) { } 323 /// Invalid constructor \& conversion. 324 325 /// Initialize the iterator to be invalid. 326 /// \sa Invalid for more details. 327 NodeIt(Invalid) { } 328 /// Sets the iterator to the first node. 329 330 /// Sets the iterator to the first node of \c g. 331 /// 332 NodeIt(const UndirGraph&) { } 333 /// Node > NodeIt conversion. 334 335 /// Sets the iterator to the node of \c the graph pointed by 336 /// the trivial iterator. 337 /// This feature necessitates that each time we 338 /// iterate the edgeset, the iteration order is the same. 339 NodeIt(const UndirGraph&, const Node&) { } 340 /// Next node. 341 342 /// Assign the iterator to the next node. 343 /// 344 NodeIt& operator++() { return *this; } 345 }; 346 347 244 348 /// The base type of the undirected edge iterators. 245 349 246 350 /// The base type of the undirected edge iterators. 247 351 /// … … 258 362 /// 259 363 UndirEdge(const UndirEdge&) { } 260 /// Edge > UndirEdge conversion261 262 /// Edge > UndirEdge conversion263 ///264 UndirEdge(const Edge&) { }265 364 /// Initialize the iterator to be invalid. 266 365 … … 279 378 bool operator!=(UndirEdge) const { return true; } 280 379 281 ///\e 282 283 ///\todo Do we need this? 380 /// Artificial ordering operator. 381 382 /// To allow the use of graph descriptors as key type in std::map or 383 /// similar associative container we require this. 284 384 /// 285 bool operator<(const UndirEdge &that) const { return true; } 286 }; 287 385 /// \note This operator only have to define some strict ordering of 386 /// the items; this order has nothing to do with the iteration 387 /// ordering of the items. 388 /// 389 /// \bug This is a technical requirement. Do we really need this? 390 bool operator<(UndirEdge) const { return false; } 391 }; 392 288 393 /// This iterator goes through each undirected edge. 289 394 290 395 /// This iterator goes through each undirected edge of a graph. 291 396 /// Its usage is quite simple, for example you can count the number 292 /// of edges in a graph \c g of type \c Graph as follows:397 /// of undirected edges in a graph \c g of type \c Graph as follows: 293 398 /// \code 294 399 /// int count=0; … … 298 403 public: 299 404 /// Default constructor 300 405 301 406 /// @warning The default constructor sets the iterator 302 407 /// to an undefined value. 303 408 UndirEdgeIt() { } 304 409 /// Copy constructor. 305 410 306 411 /// Copy constructor. 307 412 /// … … 312 417 /// 313 418 UndirEdgeIt(Invalid) { } 314 /// This constructor sets the iterator to the first edge.419 /// This constructor sets the iterator to the first undirected edge. 315 420 316 /// This constructor sets the iterator to the first edge of \c g.421 /// This constructor sets the iterator to the first undirected edge. 317 422 UndirEdgeIt(const UndirGraph&) { } 318 423 /// UndirEdge > UndirEdgeIt conversion 319 424 320 /// Sets the iterator to the value of the trivial iterator \c e. 321 /// This feature necessitates that each time we 322 /// iterate the edgeset, the iteration order is the same. 425 /// Sets the iterator to the value of the trivial iterator. 426 /// This feature necessitates that each time we 427 /// iterate the undirected edgeset, the iteration order is the 428 /// same. 323 429 UndirEdgeIt(const UndirGraph&, const UndirEdge&) { } 324 /// Nextedge430 /// Next undirected edge 325 431 326 /// Assign the iterator to the next edge.432 /// Assign the iterator to the next undirected edge. 327 433 UndirEdgeIt& operator++() { return *this; } 328 434 }; 329 435 330 /// This iterator goes trough the incident undirected edges of a node. 331 436 /// \brief This iterator goes trough the incident undirected 437 /// edges of a node. 438 /// 332 439 /// This iterator goes trough the incident undirected edges 333 440 /// of a certain node … … 376 483 }; 377 484 485 /// The directed edge type. 486 487 /// The directed edge type. It can be converted to the 488 /// undirected edge. 489 class Edge : public UndirEdge { 490 public: 491 /// Default constructor 492 493 /// @warning The default constructor sets the iterator 494 /// to an undefined value. 495 Edge() { } 496 /// Copy constructor. 497 498 /// Copy constructor. 499 /// 500 Edge(const Edge& e) : UndirEdge(e) { } 501 /// Initialize the iterator to be invalid. 502 503 /// Initialize the iterator to be invalid. 504 /// 505 Edge(Invalid) { } 506 /// Equality operator 507 508 /// Two iterators are equal if and only if they point to the 509 /// same object or both are invalid. 510 bool operator==(Edge) const { return true; } 511 /// Inequality operator 512 513 /// \sa operator==(Edge n) 514 /// 515 bool operator!=(Edge) const { return true; } 516 517 /// Artificial ordering operator. 518 519 /// To allow the use of graph descriptors as key type in std::map or 520 /// similar associative container we require this. 521 /// 522 /// \note This operator only have to define some strict ordering of 523 /// the items; this order has nothing to do with the iteration 524 /// ordering of the items. 525 /// 526 /// \bug This is a technical requirement. Do we really need this? 527 bool operator<(Edge) const { return false; } 528 529 }; 530 /// This iterator goes through each directed edge. 531 532 /// This iterator goes through each edge of a graph. 533 /// Its usage is quite simple, for example you can count the number 534 /// of edges in a graph \c g of type \c Graph as follows: 535 /// \code 536 /// int count=0; 537 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; 538 /// \endcode 539 class EdgeIt : public Edge { 540 public: 541 /// Default constructor 542 543 /// @warning The default constructor sets the iterator 544 /// to an undefined value. 545 EdgeIt() { } 546 /// Copy constructor. 547 548 /// Copy constructor. 549 /// 550 EdgeIt(const EdgeIt& e) : Edge(e) { } 551 /// Initialize the iterator to be invalid. 552 553 /// Initialize the iterator to be invalid. 554 /// 555 EdgeIt(Invalid) { } 556 /// This constructor sets the iterator to the first edge. 557 558 /// This constructor sets the iterator to the first edge of \c g. 559 ///@param g the graph 560 EdgeIt(const UndirGraph&) { } 561 /// Edge > EdgeIt conversion 562 563 /// Sets the iterator to the value of the trivial iterator \c e. 564 /// This feature necessitates that each time we 565 /// iterate the edgeset, the iteration order is the same. 566 EdgeIt(const UndirGraph&, const Edge&) { } 567 ///Next edge 568 569 /// Assign the iterator to the next edge. 570 EdgeIt& operator++() { return *this; } 571 }; 572 573 /// This iterator goes trough the outgoing directed edges of a node. 574 575 /// This iterator goes trough the \e outgoing edges of a certain node 576 /// of a graph. 577 /// Its usage is quite simple, for example you can count the number 578 /// of outgoing edges of a node \c n 579 /// in graph \c g of type \c Graph as follows. 580 /// \code 581 /// int count=0; 582 /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; 583 /// \endcode 584 585 class OutEdgeIt : public Edge { 586 public: 587 /// Default constructor 588 589 /// @warning The default constructor sets the iterator 590 /// to an undefined value. 591 OutEdgeIt() { } 592 /// Copy constructor. 593 594 /// Copy constructor. 595 /// 596 OutEdgeIt(const OutEdgeIt& e) : Edge(e) { } 597 /// Initialize the iterator to be invalid. 598 599 /// Initialize the iterator to be invalid. 600 /// 601 OutEdgeIt(Invalid) { } 602 /// This constructor sets the iterator to the first outgoing edge. 603 604 /// This constructor sets the iterator to the first outgoing edge of 605 /// the node. 606 ///@param n the node 607 ///@param g the graph 608 OutEdgeIt(const UndirGraph&, const Node&) { } 609 /// Edge > OutEdgeIt conversion 610 611 /// Sets the iterator to the value of the trivial iterator. 612 /// This feature necessitates that each time we 613 /// iterate the edgeset, the iteration order is the same. 614 OutEdgeIt(const UndirGraph&, const Edge&) { } 615 ///Next outgoing edge 616 617 /// Assign the iterator to the next 618 /// outgoing edge of the corresponding node. 619 OutEdgeIt& operator++() { return *this; } 620 }; 621 622 /// This iterator goes trough the incoming directed edges of a node. 623 624 /// This iterator goes trough the \e incoming edges of a certain node 625 /// of a graph. 626 /// Its usage is quite simple, for example you can count the number 627 /// of outgoing edges of a node \c n 628 /// in graph \c g of type \c Graph as follows. 629 /// \code 630 /// int count=0; 631 /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; 632 /// \endcode 633 634 class InEdgeIt : public Edge { 635 public: 636 /// Default constructor 637 638 /// @warning The default constructor sets the iterator 639 /// to an undefined value. 640 InEdgeIt() { } 641 /// Copy constructor. 642 643 /// Copy constructor. 644 /// 645 InEdgeIt(const InEdgeIt& e) : Edge(e) { } 646 /// Initialize the iterator to be invalid. 647 648 /// Initialize the iterator to be invalid. 649 /// 650 InEdgeIt(Invalid) { } 651 /// This constructor sets the iterator to first incoming edge. 652 653 /// This constructor set the iterator to the first incoming edge of 654 /// the node. 655 ///@param n the node 656 ///@param g the graph 657 InEdgeIt(const UndirGraph&, const Node&) { } 658 /// Edge > InEdgeIt conversion 659 660 /// Sets the iterator to the value of the trivial iterator \c e. 661 /// This feature necessitates that each time we 662 /// iterate the edgeset, the iteration order is the same. 663 InEdgeIt(const UndirGraph&, const Edge&) { } 664 /// Next incoming edge 665 666 /// Assign the iterator to the next inedge of the corresponding node. 667 /// 668 InEdgeIt& operator++() { return *this; } 669 }; 670 671 /// \brief Read write map of the nodes to type \c T. 672 /// 673 /// ReadWrite map of the nodes to type \c T. 674 /// \sa Reference 675 /// \warning Making maps that can handle bool type (NodeMap<bool>) 676 /// needs some extra attention! 677 template<class T> 678 class NodeMap : public ReadWriteMap< Node, T > 679 { 680 public: 681 682 ///\e 683 NodeMap(const UndirGraph&) { } 684 ///\e 685 NodeMap(const UndirGraph&, T) { } 686 687 ///Copy constructor 688 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } 689 ///Assignment operator 690 NodeMap& operator=(const NodeMap&) { return *this; } 691 // \todo fix this concept 692 }; 693 694 /// \brief Read write map of the directed edges to type \c T. 695 /// 696 /// Reference map of the directed edges to type \c T. 697 /// \sa Reference 698 /// \warning Making maps that can handle bool type (EdgeMap<bool>) 699 /// needs some extra attention! 700 template<class T> 701 class EdgeMap : public ReadWriteMap<Edge,T> 702 { 703 public: 704 705 ///\e 706 EdgeMap(const UndirGraph&) { } 707 ///\e 708 EdgeMap(const UndirGraph&, T) { } 709 ///Copy constructor 710 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { } 711 ///Assignment operator 712 EdgeMap& operator=(const EdgeMap&) { return *this; } 713 // \todo fix this concept 714 }; 715 378 716 /// Read write map of the undirected edges to type \c T. 379 717 … … 392 730 UndirEdgeMap(const UndirGraph&, T) { } 393 731 ///Copy constructor 394 UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { 732 UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) {} 395 733 ///Assignment operator 396 734 UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; } … … 398 736 }; 399 737 400 /// Is the Edge oriented "forward"? 401 738 /// \brief Direct the given undirected edge. 739 /// 740 /// Direct the given undirected edge. The returned edge source 741 /// will be the given edge. 742 Edge direct(const UndirEdge&, const Node&) const { 743 return INVALID; 744 } 745 746 /// \brief Direct the given undirected edge. 747 /// 748 /// Direct the given undirected edge. The returned edge source 749 /// will be the source of the undirected edge if the given bool 750 /// is true. 751 Edge direct(const UndirEdge&, bool) const { 752 return INVALID; 753 } 754 755 /// \brief Returns true if the edge has default orientation. 756 /// 402 757 /// Returns whether the given directed edge is same orientation as 403 758 /// the corresponding undirected edge. 404 /// 405 /// \todo "What does the direction of an undirected edge mean?" 406 bool forward(Edge) const { return true; } 407 408 /// Opposite node on an edge 409 759 bool direction(Edge) const { return true; } 760 761 /// \brief Returns the opposite directed edge. 762 /// 763 /// Returns the opposite directed edge. 764 Edge oppositeEdge(Edge) const { return INVALID; } 765 766 /// \brief Opposite node on an edge 767 /// 410 768 /// \return the opposite of the given Node on the given Edge 411 ///412 /// \todo What should we do if given Node and Edge are not incident?413 769 Node oppositeNode(Node, UndirEdge) const { return INVALID; } 414 770 415 /// First node of the undirected edge.416 771 /// \brief First node of the undirected edge. 772 /// 417 773 /// \return the first node of the given UndirEdge. 418 774 /// … … 421 777 /// to query the two endnodes of the edge. The direction of the edge 422 778 /// which arises this way is called the inherent direction of the 423 /// undirected edge, and is used to define the " forward" direction779 /// undirected edge, and is used to define the "default" direction 424 780 /// of the directed versions of the edges. 425 /// \sa forward781 /// \sa direction 426 782 Node source(UndirEdge) const { return INVALID; } 427 783 428 /// Second node of the undirected edge.784 /// \brief Second node of the undirected edge. 429 785 Node target(UndirEdge) const { return INVALID; } 430 786 431 /// Source node of the directed edge.787 /// \brief Source node of the directed edge. 432 788 Node source(Edge) const { return INVALID; } 433 789 434 /// Target node of the directed edge.790 /// \brief Target node of the directed edge. 435 791 Node target(Edge) const { return INVALID; } 436 792 437 /// First node of the graph438 793 /// \brief First node of the graph 794 /// 439 795 /// \note This method is part of so called \ref 440 796 /// developpers_interface "Developpers' interface", so it shouldn't 441 797 /// be used in an enduser program. 442 798 void first(Node&) const {} 443 /// Next node of the graph444 799 /// \brief Next node of the graph 800 /// 445 801 /// \note This method is part of so called \ref 446 802 /// developpers_interface "Developpers' interface", so it shouldn't … … 448 804 void next(Node&) const {} 449 805 450 /// First undirected edge of the graph451 806 /// \brief First undirected edge of the graph 807 /// 452 808 /// \note This method is part of so called \ref 453 809 /// developpers_interface "Developpers' interface", so it shouldn't 454 810 /// be used in an enduser program. 455 811 void first(UndirEdge&) const {} 456 /// Next undirected edge of the graph457 812 /// \brief Next undirected edge of the graph 813 /// 458 814 /// \note This method is part of so called \ref 459 815 /// developpers_interface "Developpers' interface", so it shouldn't … … 461 817 void next(UndirEdge&) const {} 462 818 463 /// First directed edge of the graph464 819 /// \brief First directed edge of the graph 820 /// 465 821 /// \note This method is part of so called \ref 466 822 /// developpers_interface "Developpers' interface", so it shouldn't 467 823 /// be used in an enduser program. 468 824 void first(Edge&) const {} 469 /// Next directed edge of the graph470 825 /// \brief Next directed edge of the graph 826 /// 471 827 /// \note This method is part of so called \ref 472 828 /// developpers_interface "Developpers' interface", so it shouldn't … … 474 830 void next(Edge&) const {} 475 831 476 /// First outgoing edge from a given node477 832 /// \brief First outgoing edge from a given node 833 /// 478 834 /// \note This method is part of so called \ref 479 835 /// developpers_interface "Developpers' interface", so it shouldn't 480 836 /// be used in an enduser program. 481 837 void firstOut(Edge&, Node) const {} 482 /// Next outgoing edge to a node483 838 /// \brief Next outgoing edge to a node 839 /// 484 840 /// \note This method is part of so called \ref 485 841 /// developpers_interface "Developpers' interface", so it shouldn't … … 487 843 void nextOut(Edge&) const {} 488 844 489 /// First incoming edge to a given node490 845 /// \brief First incoming edge to a given node 846 /// 491 847 /// \note This method is part of so called \ref 492 848 /// developpers_interface "Developpers' interface", so it shouldn't 493 849 /// be used in an enduser program. 494 850 void firstIn(Edge&, Node) const {} 495 /// Next incoming edge to a node496 851 /// \brief Next incoming edge to a node 852 /// 497 853 /// \note This method is part of so called \ref 498 854 /// developpers_interface "Developpers' interface", so it shouldn't … … 501 857 502 858 503 /// Base node of the iterator859 /// \brief Base node of the iterator 504 860 /// 505 861 /// Returns the base node (the source in this case) of the iterator … … 507 863 return source(e); 508 864 } 509 /// Running node of the iterator865 /// \brief Running node of the iterator 510 866 /// 511 867 /// Returns the running node (the target in this case) of the … … 515 871 } 516 872 517 /// Base node of the iterator873 /// \brief Base node of the iterator 518 874 /// 519 875 /// Returns the base node (the target in this case) of the iterator … … 521 877 return target(e); 522 878 } 523 /// Running node of the iterator879 /// \brief Running node of the iterator 524 880 /// 525 881 /// Returns the running node (the source in this case) of the … … 529 885 } 530 886 531 /// Base node of the iterator887 /// \brief Base node of the iterator 532 888 /// 533 889 /// Returns the base node of the iterator … … 535 891 return INVALID; 536 892 } 537 /// Running node of the iterator 893 894 /// \brief Running node of the iterator 538 895 /// 539 896 /// Returns the running node of the iterator … … 541 898 return INVALID; 542 899 } 543 544 900 545 901 template <typename Graph> … … 554 910 }; 555 911 912 /// \brief An empty nonstatic undirected graph class. 913 /// 914 /// This class provides everything that \ref UndirGraph does. 915 /// Additionally it enables building graphs from scratch. 556 916 class ExtendableUndirGraph : public UndirGraph { 557 917 public: 918 919 /// \brief Add a new node to the graph. 920 /// 921 /// Add a new node to the graph. 922 /// \return the new node. 923 Node addNode(); 924 925 /// \brief Add a new undirected edge to the graph. 926 /// 927 /// Add a new undirected edge to the graph. 928 /// \return the new edge. 929 UndirEdge addEdge(const Node& from, const Node& to); 930 931 /// \brief Resets the graph. 932 /// 933 /// This function deletes all undirected edges and nodes of the graph. 934 /// It also frees the memory allocated to store them. 935 void clear() { } 558 936 559 937 template <typename Graph> … … 572 950 }; 573 951 952 /// \brief An empty erasable undirected graph class. 953 /// 954 /// This class is an extension of \ref ExtendableUndirGraph. It makes it 955 /// possible to erase undirected edges or nodes. 574 956 class ErasableUndirGraph : public ExtendableUndirGraph { 575 957 public: 958 959 /// \brief Deletes a node. 960 /// 961 /// Deletes a node. 962 /// 963 void erase(Node) { } 964 /// \brief Deletes an undirected edge. 965 /// 966 /// Deletes an undirected edge. 967 /// 968 void erase(UndirEdge) { } 576 969 577 970 template <typename Graph>
Note: See TracChangeset
for help on using the changeset viewer.