Changeset 1982:f0eb6b79dcdf in lemon0.x for lemon/list_graph.h
 Timestamp:
 02/23/06 16:10:45 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2575
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/list_graph.h
r1979 r1982 637 637 }; 638 638 639 640 class ListBpUGraphBase { 641 public: 642 643 class NodeSetError : public LogicError { 644 virtual const char* exceptionName() const { 645 return "lemon::ListBpUGraph::NodeSetError"; 646 } 647 }; 648 649 protected: 650 651 struct NodeT { 652 int first_edge, next_node; 653 }; 654 655 struct EdgeT { 656 int aNode, prev_out, next_out; 657 int bNode, prev_in, next_in; 658 }; 659 660 std::vector<NodeT> aNodes; 661 std::vector<NodeT> bNodes; 662 663 std::vector<EdgeT> edges; 664 665 int first_anode; 666 int first_free_anode; 667 668 int first_bnode; 669 int first_free_bnode; 670 671 int first_free_edge; 672 673 public: 674 675 class Node { 676 friend class ListBpUGraphBase; 677 protected: 678 int id; 679 680 Node(int _id) : id(_id) {} 681 public: 682 Node() {} 683 Node(Invalid) { id = 1; } 684 bool operator==(const Node i) const {return id==i.id;} 685 bool operator!=(const Node i) const {return id!=i.id;} 686 bool operator<(const Node i) const {return id<i.id;} 687 }; 688 689 class Edge { 690 friend class ListBpUGraphBase; 691 protected: 692 int id; 693 694 Edge(int _id) { id = _id;} 695 public: 696 Edge() {} 697 Edge (Invalid) { id = 1; } 698 bool operator==(const Edge i) const {return id==i.id;} 699 bool operator!=(const Edge i) const {return id!=i.id;} 700 bool operator<(const Edge i) const {return id<i.id;} 701 }; 702 703 ListBpUGraphBase() 704 : first_anode(1), first_free_anode(1), 705 first_bnode(1), first_free_bnode(1), 706 first_free_edge(1) {} 707 708 void firstANode(Node& node) const { 709 node.id = first_anode != 1 ? (first_anode << 1) : 1; 710 } 711 void nextANode(Node& node) const { 712 node.id = aNodes[node.id >> 1].next_node; 713 } 714 715 void firstBNode(Node& node) const { 716 node.id = first_bnode != 1 ? (first_bnode << 1) + 1 : 1; 717 } 718 void nextBNode(Node& node) const { 719 node.id = aNodes[node.id >> 1].next_node; 720 } 721 722 void first(Node& node) const { 723 if (first_anode != 1) { 724 node.id = (first_anode << 1); 725 } else if (first_bnode != 1) { 726 node.id = (first_bnode << 1) + 1; 727 } else { 728 node.id = 1; 729 } 730 } 731 void next(Node& node) const { 732 if (aNode(node)) { 733 node.id = aNodes[node.id >> 1].next_node; 734 if (node.id == 1) { 735 if (first_bnode != 1) { 736 node.id = (first_bnode << 1) + 1; 737 } 738 } 739 } else { 740 node.id = bNodes[node.id >> 1].next_node; 741 } 742 } 743 744 void first(Edge& edge) const { 745 int aNodeId = first_anode; 746 while (aNodeId != 1 && aNodes[aNodeId].first_edge == 1) { 747 aNodeId = aNodes[aNodeId].next_node != 1 ? 748 aNodes[aNodeId].next_node >> 1 : 1; 749 } 750 if (aNodeId != 1) { 751 edge.id = aNodes[aNodeId].first_edge; 752 } else { 753 edge.id = 1; 754 } 755 } 756 void next(Edge& edge) const { 757 int aNodeId = edges[edge.id].aNode >> 1; 758 edge.id = edges[edge.id].next_out; 759 if (edge.id == 1) { 760 aNodeId = aNodes[aNodeId].next_node != 1 ? 761 aNodes[aNodeId].next_node >> 1 : 1; 762 while (aNodeId != 1 && aNodes[aNodeId].first_edge == 1) { 763 aNodeId = aNodes[aNodeId].next_node != 1 ? 764 aNodes[aNodeId].next_node >> 1 : 1; 765 } 766 if (aNodeId != 1) { 767 edge.id = aNodes[aNodeId].first_edge; 768 } else { 769 edge.id = 1; 770 } 771 } 772 } 773 774 void firstOut(Edge& edge, const Node& node) const { 775 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 776 edge.id = aNodes[node.id >> 1].first_edge; 777 } 778 void nextOut(Edge& edge) const { 779 edge.id = edges[edge.id].next_out; 780 } 781 782 void firstIn(Edge& edge, const Node& node) const { 783 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 784 edge.id = bNodes[node.id >> 1].first_edge; 785 } 786 void nextIn(Edge& edge) const { 787 edge.id = edges[edge.id].next_in; 788 } 789 790 static int id(const Node& node) { 791 return node.id; 792 } 793 static Node nodeFromId(int id) { 794 return Node(id); 795 } 796 int maxNodeId() const { 797 return aNodes.size() > bNodes.size() ? 798 aNodes.size() * 2  2 : bNodes.size() * 2  1; 799 } 800 801 static int id(const Edge& edge) { 802 return edge.id; 803 } 804 static Edge edgeFromId(int id) { 805 return Edge(id); 806 } 807 int maxEdgeId() const { 808 return edges.size(); 809 } 810 811 static int aNodeId(const Node& node) { 812 return node.id >> 1; 813 } 814 static Node fromANodeId(int id, Node) { 815 return Node(id << 1); 816 } 817 int maxANodeId() const { 818 return aNodes.size(); 819 } 820 821 static int bNodeId(const Node& node) { 822 return node.id >> 1; 823 } 824 static Node fromBNodeId(int id) { 825 return Node((id << 1) + 1); 826 } 827 int maxBNodeId() const { 828 return bNodes.size(); 829 } 830 831 Node aNode(const Edge& edge) const { 832 return Node(edges[edge.id].aNode); 833 } 834 Node bNode(const Edge& edge) const { 835 return Node(edges[edge.id].bNode); 836 } 837 838 static bool aNode(const Node& node) { 839 return (node.id & 1) == 0; 840 } 841 842 static bool bNode(const Node& node) { 843 return (node.id & 1) == 1; 844 } 845 846 Node addANode() { 847 int aNodeId; 848 if (first_free_anode == 1) { 849 aNodeId = aNodes.size(); 850 aNodes.push_back(NodeT()); 851 } else { 852 aNodeId = first_free_anode; 853 first_free_anode = aNodes[first_free_anode].next_node; 854 } 855 aNodes[aNodeId].next_node = 856 first_anode != 1 ? (first_anode << 1) : 1; 857 first_anode = aNodeId; 858 aNodes[aNodeId].first_edge = 1; 859 return Node(aNodeId << 1); 860 } 861 862 Node addBNode() { 863 int bNodeId; 864 if (first_free_anode == 1) { 865 bNodeId = bNodes.size(); 866 bNodes.push_back(NodeT()); 867 } else { 868 bNodeId = first_free_bnode; 869 first_free_bnode = bNodes[first_free_bnode].next_node; 870 } 871 bNodes[bNodeId].next_node = 872 first_bnode != 1 ? (first_bnode << 1) + 1 : 1; 873 first_bnode = bNodeId; 874 bNodes[bNodeId].first_edge = 1; 875 return Node((bNodeId << 1) + 1); 876 } 877 878 Edge addEdge(const Node& source, const Node& target) { 879 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); 880 int edgeId; 881 if (first_free_edge != 1) { 882 edgeId = first_free_edge; 883 first_free_edge = edges[edgeId].next_out; 884 } else { 885 edgeId = edges.size(); 886 edges.push_back(EdgeT()); 887 } 888 if ((source.id & 1) == 0) { 889 edges[edgeId].aNode = source.id; 890 edges[edgeId].bNode = target.id; 891 } else { 892 edges[edgeId].aNode = target.id; 893 edges[edgeId].bNode = source.id; 894 } 895 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge; 896 edges[edgeId].prev_out = 1; 897 if (aNodes[edges[edgeId].aNode >> 1].first_edge != 1) { 898 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId; 899 } 900 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId; 901 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge; 902 edges[edgeId].prev_in = 1; 903 if (bNodes[edges[edgeId].bNode >> 1].first_edge != 1) { 904 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; 905 } 906 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; 907 return Edge(edgeId); 908 } 909 910 void erase(const Node& node) { 911 if (aNode(node)) { 912 int aNodeId = node.id >> 1; 913 aNodes[aNodeId].next_node = first_free_anode; 914 first_free_anode = aNodeId; 915 } else { 916 int bNodeId = node.id >> 1; 917 bNodes[bNodeId].next_node = first_free_bnode; 918 first_free_bnode = bNodeId; 919 } 920 } 921 922 void erase(const Edge& edge) { 923 if (edges[edge.id].prev_out != 1) { 924 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; 925 } else { 926 aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out; 927 } 928 if (edges[edge.id].next_out != 1) { 929 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; 930 } 931 if (edges[edge.id].prev_in != 1) { 932 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; 933 } else { 934 bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in; 935 } 936 if (edges[edge.id].next_in != 1) { 937 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; 938 } 939 edges[edge.id].next_out = first_free_edge; 940 first_free_edge = edge.id; 941 } 942 943 void clear() { 944 aNodes.clear(); 945 bNodes.clear(); 946 edges.clear(); 947 first_anode = 1; 948 first_free_anode = 1; 949 first_bnode = 1; 950 first_free_bnode = 1; 951 first_free_edge = 1; 952 } 953 954 }; 955 956 957 typedef BpUGraphExtender< BpUGraphBaseExtender< 958 ListBpUGraphBase> > ExtendedListBpUGraphBase; 959 960 /// \ingroup graphs 961 /// 962 /// \brief A smart bipartite undirected graph class. 963 /// 964 /// This is a bipartite undirected graph implementation. 965 /// Except from this it conforms to 966 /// the \ref concept::BpUGraph "BpUGraph" concept. 967 /// \sa concept::BpUGraph. 968 /// 969 class ListBpUGraph : public ExtendedListBpUGraphBase {}; 970 639 971 640 972 /// @}
Note: See TracChangeset
for help on using the changeset viewer.