Changeset 937:d4e911acef3d in lemon0.x for src/lemon/list_graph.h
 Timestamp:
 10/04/04 19:13:21 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1264
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/list_graph.h
r921 r937 30 30 #include <lemon/array_map.h> 31 31 32 #include <lemon/sym_map.h>33 34 32 #include <lemon/map_defines.h> 35 33 … … 105 103 first_free_edge(_g.first_free_edge) {} 106 104 105 /// \bug In the vector can be hole if a node is erased from the graph. 107 106 ///Number of nodes. 108 107 int nodeNum() const { return nodes.size(); } … … 439 438 ///\todo this date structure need some reconsiderations. Maybe it 440 439 ///should be implemented independently from ListGraph. 441 440 /* 442 441 class SymListGraph : public ListGraph 443 442 { … … 484 483 ListGraph::erase(e); 485 484 } 485 };*/ 486 487 class SymListGraph : public ListGraph { 488 typedef ListGraph Parent; 489 public: 490 491 typedef SymListGraph Graph; 492 493 typedef ListGraph::Node Node; 494 typedef ListGraph::NodeIt NodeIt; 495 496 class SymEdge; 497 class SymEdgeIt; 498 499 class Edge; 500 class EdgeIt; 501 class OutEdgeIt; 502 class InEdgeIt; 503 504 template <typename Value> 505 class NodeMap : public Parent::NodeMap<Value> { 506 public: 507 NodeMap(const SymListGraph& g) 508 : SymListGraph::Parent::NodeMap<Value>(g) {} 509 NodeMap(const SymListGraph& g, Value v) 510 : SymListGraph::Parent::NodeMap<Value>(g, v) {} 511 template<typename TT> 512 NodeMap(const NodeMap<TT>& copy) 513 : SymListGraph::Parent::NodeMap<Value>(copy) { } 514 }; 515 516 template <typename Value> 517 class SymEdgeMap : public Parent::EdgeMap<Value> { 518 public: 519 typedef SymEdge KeyType; 520 521 SymEdgeMap(const SymListGraph& g) 522 : SymListGraph::Parent::EdgeMap<Value>(g) {} 523 SymEdgeMap(const SymListGraph& g, Value v) 524 : SymListGraph::Parent::EdgeMap<Value>(g, v) {} 525 template<typename TT> 526 SymEdgeMap(const SymEdgeMap<TT>& copy) 527 : SymListGraph::Parent::EdgeMap<Value>(copy) { } 528 529 }; 530 531 // Create edge map registry. 532 CREATE_EDGE_MAP_REGISTRY; 533 // Create edge maps. 534 CREATE_EDGE_MAP(ArrayMap); 535 536 class Edge { 537 friend class SymListGraph; 538 friend class SymListGraph::EdgeIt; 539 friend class SymListGraph::OutEdgeIt; 540 friend class SymListGraph::InEdgeIt; 541 542 protected: 543 int id; 544 545 Edge(int pid) { id = pid; } 546 547 public: 548 /// An Edge with id \c n. 549 550 Edge() { } 551 Edge (Invalid) { id = 1; } 552 553 operator SymEdge(){ return SymEdge(id >> 1);} 554 555 bool operator==(const Edge i) const {return id == i.id;} 556 bool operator!=(const Edge i) const {return id != i.id;} 557 bool operator<(const Edge i) const {return id < i.id;} 558 // ///Validity check 559 // operator bool() { return n!=1; } 560 }; 561 562 class SymEdge : public ListGraph::Edge { 563 friend class SymListGraph; 564 friend class SymListGraph::Edge; 565 typedef ListGraph::Edge Parent; 566 567 protected: 568 SymEdge(int pid) : Parent(pid) {} 569 public: 570 571 SymEdge() { } 572 SymEdge(const ListGraph::Edge& i) : Parent(i) {} 573 SymEdge (Invalid) : Parent(INVALID) {} 574 575 }; 576 577 class OutEdgeIt { 578 Parent::OutEdgeIt out; 579 Parent::InEdgeIt in; 580 public: 581 OutEdgeIt() {} 582 OutEdgeIt(const SymListGraph& g, Edge e) { 583 if ((e.id & 1) == 0) { 584 out = Parent::OutEdgeIt(g, SymEdge(e)); 585 in = Parent::InEdgeIt(g, g.tail(e)); 586 } else { 587 out = Parent::OutEdgeIt(INVALID); 588 in = Parent::InEdgeIt(g, SymEdge(e)); 589 } 590 } 591 OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 592 593 OutEdgeIt(const SymListGraph& g, const Node v) 594 : out(g, v), in(g, v) {} 595 OutEdgeIt &operator++() { 596 if (out != INVALID) { 597 ++out; 598 } else { 599 ++in; 600 } 601 return *this; 602 } 603 604 operator Edge() const { 605 if (out == INVALID && in == INVALID) return INVALID; 606 return out != INVALID ? forward(out) : backward(in); 607 } 608 609 bool operator==(const Edge i) const {return Edge(*this) == i;} 610 bool operator!=(const Edge i) const {return Edge(*this) != i;} 611 bool operator<(const Edge i) const {return Edge(*this) < i;} 612 }; 613 614 class InEdgeIt { 615 Parent::OutEdgeIt out; 616 Parent::InEdgeIt in; 617 public: 618 InEdgeIt() {} 619 InEdgeIt(const SymListGraph& g, Edge e) { 620 if ((e.id & 1) == 0) { 621 out = Parent::OutEdgeIt(g, SymEdge(e)); 622 in = Parent::InEdgeIt(g, g.tail(e)); 623 } else { 624 out = Parent::OutEdgeIt(INVALID); 625 in = Parent::InEdgeIt(g, SymEdge(e)); 626 } 627 } 628 InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 629 630 InEdgeIt(const SymListGraph& g, const Node v) 631 : out(g, v), in(g, v) {} 632 633 InEdgeIt &operator++() { 634 if (out != INVALID) { 635 ++out; 636 } else { 637 ++in; 638 } 639 return *this; 640 } 641 642 operator Edge() const { 643 if (out == INVALID && in == INVALID) return INVALID; 644 return out != INVALID ? backward(out) : forward(in); 645 } 646 647 bool operator==(const Edge i) const {return Edge(*this) == i;} 648 bool operator!=(const Edge i) const {return Edge(*this) != i;} 649 bool operator<(const Edge i) const {return Edge(*this) < i;} 650 }; 651 652 class SymEdgeIt : public Parent::EdgeIt { 653 654 public: 655 SymEdgeIt() {} 656 657 SymEdgeIt(const SymListGraph& g) 658 : SymListGraph::Parent::EdgeIt(g) {} 659 660 SymEdgeIt(const SymListGraph& g, SymEdge e) 661 : SymListGraph::Parent::EdgeIt(g, e) {} 662 663 SymEdgeIt(Invalid i) 664 : SymListGraph::Parent::EdgeIt(INVALID) {} 665 666 SymEdgeIt& operator++() { 667 SymListGraph::Parent::EdgeIt::operator++(); 668 return *this; 669 } 670 671 operator SymEdge() const { 672 return SymEdge 673 (static_cast<const SymListGraph::Parent::EdgeIt&>(*this)); 674 } 675 bool operator==(const SymEdge i) const {return SymEdge(*this) == i;} 676 bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;} 677 bool operator<(const SymEdge i) const {return SymEdge(*this) < i;} 678 }; 679 680 class EdgeIt { 681 SymEdgeIt it; 682 bool fw; 683 public: 684 EdgeIt(const SymListGraph& g) : it(g), fw(true) {} 685 EdgeIt (Invalid i) : it(i) { } 686 EdgeIt(const SymListGraph& g, Edge e) 687 : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { } 688 EdgeIt() { } 689 EdgeIt& operator++() { 690 fw = !fw; 691 if (fw) ++it; 692 return *this; 693 } 694 operator Edge() const { 695 if (it == INVALID) return INVALID; 696 return fw ? forward(it) : backward(it); 697 } 698 bool operator==(const Edge i) const {return Edge(*this) == i;} 699 bool operator!=(const Edge i) const {return Edge(*this) != i;} 700 bool operator<(const Edge i) const {return Edge(*this) < i;} 701 702 }; 703 704 ///Number of nodes. 705 int nodeNum() const { return Parent::nodeNum(); } 706 ///Number of edges. 707 int edgeNum() const { return 2*Parent::edgeNum(); } 708 ///Number of symmetric edges. 709 int symEdgeNum() const { return Parent::edgeNum(); } 710 711 ///Set the expected maximum number of edges. 712 713 ///With this function, it is possible to set the expected number of edges. 714 ///The use of this fasten the building of the graph and makes 715 ///it possible to avoid the superfluous memory allocation. 716 void reserveSymEdge(int n) { Parent::reserveEdge(n); }; 717 718 /// Maximum node ID. 719 720 /// Maximum node ID. 721 ///\sa id(Node) 722 int maxNodeId() const { return Parent::maxNodeId(); } 723 /// Maximum edge ID. 724 725 /// Maximum edge ID. 726 ///\sa id(Edge) 727 int maxEdgeId() const { return 2*Parent::maxEdgeId(); } 728 /// Maximum symmetric edge ID. 729 730 /// Maximum symmetric edge ID. 731 ///\sa id(SymEdge) 732 int maxSymEdgeId() const { return Parent::maxEdgeId(); } 733 734 735 Node tail(Edge e) const { 736 return (e.id & 1) == 0 ? 737 Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); 738 } 739 740 Node head(Edge e) const { 741 return (e.id & 1) == 0 ? 742 Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); 743 } 744 745 Node tail(SymEdge e) const { 746 return Parent::tail(e); 747 } 748 749 Node head(SymEdge e) const { 750 return Parent::head(e); 751 } 752 753 NodeIt& first(NodeIt& v) const { 754 v=NodeIt(*this); return v; } 755 EdgeIt& first(EdgeIt& e) const { 756 e=EdgeIt(*this); return e; } 757 SymEdgeIt& first(SymEdgeIt& e) const { 758 e=SymEdgeIt(*this); return e; } 759 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 760 e=OutEdgeIt(*this,v); return e; } 761 InEdgeIt& first(InEdgeIt& e, const Node v) const { 762 e=InEdgeIt(*this,v); return e; } 763 764 /// Node ID. 765 766 /// The ID of a valid Node is a nonnegative integer not greater than 767 /// \ref maxNodeId(). The range of the ID's is not surely continuous 768 /// and the greatest node ID can be actually less then \ref maxNodeId(). 769 /// 770 /// The ID of the \ref INVALID node is 1. 771 ///\return The ID of the node \c v. 772 static int id(Node v) { return Parent::id(v); } 773 /// Edge ID. 774 775 /// The ID of a valid Edge is a nonnegative integer not greater than 776 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 777 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 778 /// 779 /// The ID of the \ref INVALID edge is 1. 780 ///\return The ID of the edge \c e. 781 static int id(Edge e) { return e.id; } 782 783 /// The ID of a valid SymEdge is a nonnegative integer not greater than 784 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous 785 /// and the greatest edge ID can be actually less then \ref maxSymEdgeId(). 786 /// 787 /// The ID of the \ref INVALID symmetric edge is 1. 788 ///\return The ID of the edge \c e. 789 static int id(SymEdge e) { return Parent::id(e); } 790 791 /// Adds a new node to the graph. 792 793 /// \warning It adds the new node to the front of the list. 794 /// (i.e. the lastly added node becomes the first.) 795 Node addNode() { 796 return Parent::addNode(); 797 } 798 799 SymEdge addEdge(Node u, Node v) { 800 SymEdge se = Parent::addEdge(u, v); 801 edge_maps.add(forward(se)); 802 edge_maps.add(backward(se)); 803 return se; 804 } 805 806 /// Finds an edge between two nodes. 807 808 /// Finds an edge from node \c u to node \c v. 809 /// 810 /// If \c prev is \ref INVALID (this is the default value), then 811 /// It finds the first edge from \c u to \c v. Otherwise it looks for 812 /// the next edge from \c u to \c v after \c prev. 813 /// \return The found edge or INVALID if there is no such an edge. 814 Edge findEdge(Node u, Node v, Edge prev = INVALID) 815 { 816 if (prev == INVALID  id(prev) & 1 == 0) { 817 SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 818 if (se != INVALID) return forward(se); 819 } else { 820 SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 821 if (se != INVALID) return backward(se); 822 } 823 return INVALID; 824 } 825 826 // /// Finds an symmetric edge between two nodes. 827 828 // /// Finds an symmetric edge from node \c u to node \c v. 829 // /// 830 // /// If \c prev is \ref INVALID (this is the default value), then 831 // /// It finds the first edge from \c u to \c v. Otherwise it looks for 832 // /// the next edge from \c u to \c v after \c prev. 833 // /// \return The found edge or INVALID if there is no such an edge. 834 835 // SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) 836 // { 837 // if (prev == INVALID  id(prev) & 1 == 0) { 838 // SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 839 // if (se != INVALID) return se; 840 // } else { 841 // SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 842 // if (se != INVALID) return se; 843 // } 844 // return INVALID; 845 // } 846 847 public: 848 849 void erase(Node n) { 850 for (OutEdgeIt it(*this, n); it != INVALID; ++it) { 851 edge_maps.erase(it); 852 edge_maps.erase(opposite(it)); 853 } 854 Parent::erase(n); 855 } 856 857 void erase(SymEdge e) { 858 edge_maps.erase(forward(e)); 859 edge_maps.erase(backward(e)); 860 Parent::erase(e); 861 }; 862 863 void clear() { 864 edge_maps.clear(); 865 Parent::clear(); 866 } 867 868 static Edge opposite(Edge e) { 869 return Edge(id(e) ^ 1); 870 } 871 872 static Edge forward(SymEdge e) { 873 return Edge(id(e) << 1); 874 } 875 876 static Edge backward(SymEdge e) { 877 return Edge((id(e) << 1)  1); 878 } 879 486 880 }; 487 488 881 489 882 ///A graph class containing only nodes.
Note: See TracChangeset
for help on using the changeset viewer.