Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/list_graph.h
- Timestamp:
- 06/30/06 14:14:36 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2821
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_graph.h
r2114 r2115 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief ListGraph, ListUGraph classes. 25 26 #include <lemon/bits/base_extender.h> 24 ///\brief ListGraph class. 25 27 26 #include <lemon/bits/graph_extender.h> 28 29 #include <lemon/error.h>30 27 31 28 #include <vector> … … 310 307 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; 311 308 312 /// \addtogroup graphs 313 /// @{ 309 /// \ingroup graphs 314 310 315 311 ///A list graph class. … … 706 702 }; 707 703 708 ///@}709 710 /**************** Undirected List Graph ****************/711 712 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >713 ExtendedListUGraphBase;714 715 /// \addtogroup graphs716 /// @{717 718 ///An undirected list graph class.719 720 ///This is a simple and fast erasable undirected graph implementation.721 ///722 ///It conforms to the723 ///\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 s742 /// 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 n748 ///749 /// Changes the target of \c e to \c n750 ///751 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s752 /// referencing the changed edge remain753 /// 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 n758 ///759 /// Changes the source of \c e to \c n760 ///761 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s762 ///referencing the changed edge remain763 ///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 deleting772 /// its neighboring edges, they will be joined to \p a.773 /// The last parameter \p r controls whether to remove loops. \c true774 /// means that loops will be removed.775 ///776 /// \note The <tt>Edge</tt>s777 /// referencing a moved edge remain778 /// 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 graphs1144 ///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 /// @}1156 704 } //namespace lemon 1157 705
Note: See TracChangeset
for help on using the changeset viewer.