Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon/list_graph.h
- Timestamp:
- 06/30/06 14:15:45 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_graph.h
r2115 r2116 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief ListGraph class. 25 24 ///\brief ListGraph, ListUGraph classes. 25 26 #include <lemon/bits/base_extender.h> 26 27 #include <lemon/bits/graph_extender.h> 28 29 #include <lemon/error.h> 27 30 28 31 #include <vector> … … 307 310 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; 308 311 309 /// \ingroup graphs 312 /// \addtogroup graphs 313 /// @{ 310 314 311 315 ///A list graph class. … … 702 706 }; 703 707 708 ///@} 709 710 /**************** Undirected List Graph ****************/ 711 712 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 713 ExtendedListUGraphBase; 714 715 /// \addtogroup graphs 716 /// @{ 717 718 ///An undirected list graph class. 719 720 ///This is a simple and fast erasable undirected graph implementation. 721 /// 722 ///It conforms to the 723 ///\ref concept::UGraph "UGraph" concept. 724 /// 725 ///\sa concept::UGraph. 726 /// 727 ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract() 728 ///haven't been implemented yet. 729 /// 730 class ListUGraph : public ExtendedListUGraphBase { 731 public: 732 typedef ExtendedListUGraphBase Parent; 733 /// \brief Add a new node to the graph. 734 /// 735 /// \return the new node. 736 /// 737 Node addNode() { return Parent::addNode(); } 738 739 /// \brief Add a new edge to the graph. 740 /// 741 /// Add a new edge to the graph with source node \c s 742 /// and target node \c t. 743 /// \return the new undirected edge. 744 UEdge addEdge(const Node& s, const Node& t) { 745 return Parent::addEdge(s, t); 746 } 747 /// \brief Changes the target of \c e to \c n 748 /// 749 /// Changes the target of \c e to \c n 750 /// 751 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s 752 /// referencing the changed edge remain 753 /// valid. However <tt>InEdge</tt>'s are invalidated. 754 void changeTarget(UEdge e, Node n) { 755 Parent::changeTarget(e,n); 756 } 757 /// Changes the source of \c e to \c n 758 /// 759 /// Changes the source of \c e to \c n 760 /// 761 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s 762 ///referencing the changed edge remain 763 ///valid. However <tt>OutEdge</tt>'s are invalidated. 764 void changeSource(UEdge e, Node n) { 765 Parent::changeSource(e,n); 766 } 767 /// \brief Contract two nodes. 768 /// 769 /// This function contracts two nodes. 770 /// 771 /// Node \p b will be removed but instead of deleting 772 /// its neighboring edges, they will be joined to \p a. 773 /// The last parameter \p r controls whether to remove loops. \c true 774 /// means that loops will be removed. 775 /// 776 /// \note The <tt>Edge</tt>s 777 /// referencing a moved edge remain 778 /// valid. 779 void contract(Node a, Node b, bool r = true) { 780 for(IncEdgeIt e(*this, b); e!=INVALID;) { 781 IncEdgeIt f = e; ++f; 782 if (r && runningNode(e) == a) { 783 erase(e); 784 } else if (source(e) == b) { 785 changeSource(e, a); 786 } else { 787 changeTarget(e, a); 788 } 789 e = f; 790 } 791 erase(b); 792 } 793 }; 794 795 796 class ListBpUGraphBase { 797 public: 798 799 class NodeSetError : public LogicError { 800 virtual const char* exceptionName() const { 801 return "lemon::ListBpUGraph::NodeSetError"; 802 } 803 }; 804 805 protected: 806 807 struct NodeT { 808 int first_edge, prev, next; 809 }; 810 811 struct UEdgeT { 812 int aNode, prev_out, next_out; 813 int bNode, prev_in, next_in; 814 }; 815 816 std::vector<NodeT> aNodes; 817 std::vector<NodeT> bNodes; 818 819 std::vector<UEdgeT> edges; 820 821 int first_anode; 822 int first_free_anode; 823 824 int first_bnode; 825 int first_free_bnode; 826 827 int first_free_edge; 828 829 public: 830 831 class Node { 832 friend class ListBpUGraphBase; 833 protected: 834 int id; 835 836 explicit Node(int _id) : id(_id) {} 837 public: 838 Node() {} 839 Node(Invalid) { id = -1; } 840 bool operator==(const Node i) const {return id==i.id;} 841 bool operator!=(const Node i) const {return id!=i.id;} 842 bool operator<(const Node i) const {return id<i.id;} 843 }; 844 845 class UEdge { 846 friend class ListBpUGraphBase; 847 protected: 848 int id; 849 850 explicit UEdge(int _id) { id = _id;} 851 public: 852 UEdge() {} 853 UEdge (Invalid) { id = -1; } 854 bool operator==(const UEdge i) const {return id==i.id;} 855 bool operator!=(const UEdge i) const {return id!=i.id;} 856 bool operator<(const UEdge i) const {return id<i.id;} 857 }; 858 859 ListBpUGraphBase() 860 : first_anode(-1), first_free_anode(-1), 861 first_bnode(-1), first_free_bnode(-1), 862 first_free_edge(-1) {} 863 864 void firstANode(Node& node) const { 865 node.id = first_anode != -1 ? (first_anode << 1) : -1; 866 } 867 void nextANode(Node& node) const { 868 node.id = aNodes[node.id >> 1].next; 869 } 870 871 void firstBNode(Node& node) const { 872 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1; 873 } 874 void nextBNode(Node& node) const { 875 node.id = bNodes[node.id >> 1].next; 876 } 877 878 void first(Node& node) const { 879 if (first_anode != -1) { 880 node.id = (first_anode << 1); 881 } else if (first_bnode != -1) { 882 node.id = (first_bnode << 1) + 1; 883 } else { 884 node.id = -1; 885 } 886 } 887 void next(Node& node) const { 888 if (aNode(node)) { 889 node.id = aNodes[node.id >> 1].next; 890 if (node.id == -1) { 891 if (first_bnode != -1) { 892 node.id = (first_bnode << 1) + 1; 893 } 894 } 895 } else { 896 node.id = bNodes[node.id >> 1].next; 897 } 898 } 899 900 void first(UEdge& edge) const { 901 int aNodeId = first_anode; 902 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { 903 aNodeId = aNodes[aNodeId].next != -1 ? 904 aNodes[aNodeId].next >> 1 : -1; 905 } 906 if (aNodeId != -1) { 907 edge.id = aNodes[aNodeId].first_edge; 908 } else { 909 edge.id = -1; 910 } 911 } 912 void next(UEdge& edge) const { 913 int aNodeId = edges[edge.id].aNode >> 1; 914 edge.id = edges[edge.id].next_out; 915 if (edge.id == -1) { 916 aNodeId = aNodes[aNodeId].next != -1 ? 917 aNodes[aNodeId].next >> 1 : -1; 918 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { 919 aNodeId = aNodes[aNodeId].next != -1 ? 920 aNodes[aNodeId].next >> 1 : -1; 921 } 922 if (aNodeId != -1) { 923 edge.id = aNodes[aNodeId].first_edge; 924 } else { 925 edge.id = -1; 926 } 927 } 928 } 929 930 void firstFromANode(UEdge& edge, const Node& node) const { 931 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 932 edge.id = aNodes[node.id >> 1].first_edge; 933 } 934 void nextFromANode(UEdge& edge) const { 935 edge.id = edges[edge.id].next_out; 936 } 937 938 void firstFromBNode(UEdge& edge, const Node& node) const { 939 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 940 edge.id = bNodes[node.id >> 1].first_edge; 941 } 942 void nextFromBNode(UEdge& edge) const { 943 edge.id = edges[edge.id].next_in; 944 } 945 946 static int id(const Node& node) { 947 return node.id; 948 } 949 static Node nodeFromId(int id) { 950 return Node(id); 951 } 952 int maxNodeId() const { 953 return aNodes.size() > bNodes.size() ? 954 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; 955 } 956 957 static int id(const UEdge& edge) { 958 return edge.id; 959 } 960 static UEdge uEdgeFromId(int id) { 961 return UEdge(id); 962 } 963 int maxUEdgeId() const { 964 return edges.size(); 965 } 966 967 static int aNodeId(const Node& node) { 968 return node.id >> 1; 969 } 970 static Node fromANodeId(int id) { 971 return Node(id << 1); 972 } 973 int maxANodeId() const { 974 return aNodes.size(); 975 } 976 977 static int bNodeId(const Node& node) { 978 return node.id >> 1; 979 } 980 static Node fromBNodeId(int id) { 981 return Node((id << 1) + 1); 982 } 983 int maxBNodeId() const { 984 return bNodes.size(); 985 } 986 987 Node aNode(const UEdge& edge) const { 988 return Node(edges[edge.id].aNode); 989 } 990 Node bNode(const UEdge& edge) const { 991 return Node(edges[edge.id].bNode); 992 } 993 994 static bool aNode(const Node& node) { 995 return (node.id & 1) == 0; 996 } 997 998 static bool bNode(const Node& node) { 999 return (node.id & 1) == 1; 1000 } 1001 1002 Node addANode() { 1003 int aNodeId; 1004 if (first_free_anode == -1) { 1005 aNodeId = aNodes.size(); 1006 aNodes.push_back(NodeT()); 1007 } else { 1008 aNodeId = first_free_anode; 1009 first_free_anode = aNodes[first_free_anode].next; 1010 } 1011 if (first_anode != -1) { 1012 aNodes[aNodeId].next = first_anode << 1; 1013 aNodes[first_anode].prev = aNodeId << 1; 1014 } else { 1015 aNodes[aNodeId].next = -1; 1016 } 1017 aNodes[aNodeId].prev = -1; 1018 first_anode = aNodeId; 1019 aNodes[aNodeId].first_edge = -1; 1020 return Node(aNodeId << 1); 1021 } 1022 1023 Node addBNode() { 1024 int bNodeId; 1025 if (first_free_bnode == -1) { 1026 bNodeId = bNodes.size(); 1027 bNodes.push_back(NodeT()); 1028 } else { 1029 bNodeId = first_free_bnode; 1030 first_free_bnode = bNodes[first_free_bnode].next; 1031 } 1032 if (first_bnode != -1) { 1033 bNodes[bNodeId].next = (first_bnode << 1) + 1; 1034 bNodes[first_bnode].prev = (bNodeId << 1) + 1; 1035 } else { 1036 bNodes[bNodeId].next = -1; 1037 } 1038 first_bnode = bNodeId; 1039 bNodes[bNodeId].first_edge = -1; 1040 return Node((bNodeId << 1) + 1); 1041 } 1042 1043 UEdge addEdge(const Node& source, const Node& target) { 1044 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); 1045 int edgeId; 1046 if (first_free_edge != -1) { 1047 edgeId = first_free_edge; 1048 first_free_edge = edges[edgeId].next_out; 1049 } else { 1050 edgeId = edges.size(); 1051 edges.push_back(UEdgeT()); 1052 } 1053 if ((source.id & 1) == 0) { 1054 edges[edgeId].aNode = source.id; 1055 edges[edgeId].bNode = target.id; 1056 } else { 1057 edges[edgeId].aNode = target.id; 1058 edges[edgeId].bNode = source.id; 1059 } 1060 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge; 1061 edges[edgeId].prev_out = -1; 1062 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) { 1063 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId; 1064 } 1065 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId; 1066 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge; 1067 edges[edgeId].prev_in = -1; 1068 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) { 1069 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; 1070 } 1071 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; 1072 return UEdge(edgeId); 1073 } 1074 1075 void erase(const Node& node) { 1076 if (aNode(node)) { 1077 int aNodeId = node.id >> 1; 1078 if (aNodes[aNodeId].prev != -1) { 1079 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next; 1080 } else { 1081 first_anode = aNodes[aNodeId].next >> 1; 1082 } 1083 if (aNodes[aNodeId].next != -1) { 1084 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev; 1085 } 1086 aNodes[aNodeId].next = first_free_anode; 1087 first_free_anode = aNodeId; 1088 } else { 1089 int bNodeId = node.id >> 1; 1090 if (bNodes[bNodeId].prev != -1) { 1091 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next; 1092 } else { 1093 first_bnode = bNodes[bNodeId].next >> 1; 1094 } 1095 if (bNodes[bNodeId].next != -1) { 1096 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev; 1097 } 1098 bNodes[bNodeId].next = first_free_bnode; 1099 first_free_bnode = bNodeId; 1100 } 1101 } 1102 1103 void erase(const UEdge& edge) { 1104 1105 if (edges[edge.id].prev_out != -1) { 1106 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; 1107 } else { 1108 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out; 1109 } 1110 if (edges[edge.id].next_out != -1) { 1111 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; 1112 } 1113 1114 if (edges[edge.id].prev_in != -1) { 1115 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; 1116 } else { 1117 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in; 1118 } 1119 if (edges[edge.id].next_in != -1) { 1120 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; 1121 } 1122 1123 edges[edge.id].next_out = first_free_edge; 1124 first_free_edge = edge.id; 1125 } 1126 1127 void clear() { 1128 aNodes.clear(); 1129 bNodes.clear(); 1130 edges.clear(); 1131 first_anode = -1; 1132 first_free_anode = -1; 1133 first_bnode = -1; 1134 first_free_bnode = -1; 1135 first_free_edge = -1; 1136 } 1137 1138 }; 1139 1140 1141 typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase; 1142 1143 /// \ingroup graphs 1144 /// 1145 /// \brief A smart bipartite undirected graph class. 1146 /// 1147 /// This is a bipartite undirected graph implementation. 1148 /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" 1149 /// concept. 1150 /// \sa concept::BpUGraph. 1151 /// 1152 class ListBpUGraph : public ExtendedListBpUGraphBase {}; 1153 1154 1155 /// @} 704 1156 } //namespace lemon 705 1157
Note: See TracChangeset
for help on using the changeset viewer.