Changeset 1187:4c89e925cfe2 in lemon for lemon/smart_graph.h
- Timestamp:
- 11/14/10 20:06:23 (13 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/smart_graph.h
r956 r1187 406 406 std::vector<ArcT> arcs; 407 407 408 int first_free_arc;409 410 408 public: 411 409 … … 812 810 }; 813 811 812 class SmartBpGraphBase { 813 814 protected: 815 816 struct NodeT { 817 int first_out; 818 int partition_next; 819 int partition_index; 820 bool red; 821 }; 822 823 struct ArcT { 824 int target; 825 int next_out; 826 }; 827 828 std::vector<NodeT> nodes; 829 std::vector<ArcT> arcs; 830 831 int first_red, first_blue; 832 833 public: 834 835 typedef SmartBpGraphBase Graph; 836 837 class Node; 838 class Arc; 839 class Edge; 840 841 class Node { 842 friend class SmartBpGraphBase; 843 protected: 844 845 int _id; 846 explicit Node(int id) { _id = id;} 847 848 public: 849 Node() {} 850 Node (Invalid) { _id = -1; } 851 bool operator==(const Node& node) const {return _id == node._id;} 852 bool operator!=(const Node& node) const {return _id != node._id;} 853 bool operator<(const Node& node) const {return _id < node._id;} 854 }; 855 856 class Edge { 857 friend class SmartBpGraphBase; 858 protected: 859 860 int _id; 861 explicit Edge(int id) { _id = id;} 862 863 public: 864 Edge() {} 865 Edge (Invalid) { _id = -1; } 866 bool operator==(const Edge& arc) const {return _id == arc._id;} 867 bool operator!=(const Edge& arc) const {return _id != arc._id;} 868 bool operator<(const Edge& arc) const {return _id < arc._id;} 869 }; 870 871 class Arc { 872 friend class SmartBpGraphBase; 873 protected: 874 875 int _id; 876 explicit Arc(int id) { _id = id;} 877 878 public: 879 operator Edge() const { 880 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 881 } 882 883 Arc() {} 884 Arc (Invalid) { _id = -1; } 885 bool operator==(const Arc& arc) const {return _id == arc._id;} 886 bool operator!=(const Arc& arc) const {return _id != arc._id;} 887 bool operator<(const Arc& arc) const {return _id < arc._id;} 888 }; 889 890 891 892 SmartBpGraphBase() 893 : nodes(), arcs(), first_red(-1), first_blue(-1) {} 894 895 typedef True NodeNumTag; 896 typedef True EdgeNumTag; 897 typedef True ArcNumTag; 898 899 int nodeNum() const { return nodes.size(); } 900 int redNum() const { 901 return first_red == -1 ? 0 : nodes[first_red].partition_index + 1; 902 } 903 int blueNum() const { 904 return first_blue == -1 ? 0 : nodes[first_blue].partition_index + 1; 905 } 906 int edgeNum() const { return arcs.size() / 2; } 907 int arcNum() const { return arcs.size(); } 908 909 int maxNodeId() const { return nodes.size()-1; } 910 int maxRedId() const { 911 return first_red == -1 ? -1 : nodes[first_red].partition_index; 912 } 913 int maxBlueId() const { 914 return first_blue == -1 ? -1 : nodes[first_blue].partition_index; 915 } 916 int maxEdgeId() const { return arcs.size() / 2 - 1; } 917 int maxArcId() const { return arcs.size()-1; } 918 919 bool red(Node n) const { return nodes[n._id].red; } 920 bool blue(Node n) const { return !nodes[n._id].red; } 921 922 Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); } 923 Node target(Arc a) const { return Node(arcs[a._id].target); } 924 925 Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); } 926 Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); } 927 928 Node u(Edge e) const { return redNode(e); } 929 Node v(Edge e) const { return blueNode(e); } 930 931 static bool direction(Arc a) { 932 return (a._id & 1) == 1; 933 } 934 935 static Arc direct(Edge e, bool d) { 936 return Arc(e._id * 2 + (d ? 1 : 0)); 937 } 938 939 void first(Node& node) const { 940 node._id = nodes.size() - 1; 941 } 942 943 static void next(Node& node) { 944 --node._id; 945 } 946 947 void firstRed(Node& node) const { 948 node._id = first_red; 949 } 950 951 void nextRed(Node& node) const { 952 node._id = nodes[node._id].partition_next; 953 } 954 955 void firstBlue(Node& node) const { 956 node._id = first_blue; 957 } 958 959 void nextBlue(Node& node) const { 960 node._id = nodes[node._id].partition_next; 961 } 962 963 void first(Arc& arc) const { 964 arc._id = arcs.size() - 1; 965 } 966 967 static void next(Arc& arc) { 968 --arc._id; 969 } 970 971 void first(Edge& arc) const { 972 arc._id = arcs.size() / 2 - 1; 973 } 974 975 static void next(Edge& arc) { 976 --arc._id; 977 } 978 979 void firstOut(Arc &arc, const Node& v) const { 980 arc._id = nodes[v._id].first_out; 981 } 982 void nextOut(Arc &arc) const { 983 arc._id = arcs[arc._id].next_out; 984 } 985 986 void firstIn(Arc &arc, const Node& v) const { 987 arc._id = ((nodes[v._id].first_out) ^ 1); 988 if (arc._id == -2) arc._id = -1; 989 } 990 void nextIn(Arc &arc) const { 991 arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1); 992 if (arc._id == -2) arc._id = -1; 993 } 994 995 void firstInc(Edge &arc, bool& d, const Node& v) const { 996 int de = nodes[v._id].first_out; 997 if (de != -1) { 998 arc._id = de / 2; 999 d = ((de & 1) == 1); 1000 } else { 1001 arc._id = -1; 1002 d = true; 1003 } 1004 } 1005 void nextInc(Edge &arc, bool& d) const { 1006 int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); 1007 if (de != -1) { 1008 arc._id = de / 2; 1009 d = ((de & 1) == 1); 1010 } else { 1011 arc._id = -1; 1012 d = true; 1013 } 1014 } 1015 1016 static int id(Node v) { return v._id; } 1017 int redId(Node v) const { 1018 LEMON_DEBUG(nodes[v._id].red, "Node has to be red"); 1019 return nodes[v._id].partition_index; 1020 } 1021 int blueId(Node v) const { 1022 LEMON_DEBUG(nodes[v._id].red, "Node has to be blue"); 1023 return nodes[v._id].partition_index; 1024 } 1025 static int id(Arc e) { return e._id; } 1026 static int id(Edge e) { return e._id; } 1027 1028 static Node nodeFromId(int id) { return Node(id);} 1029 static Arc arcFromId(int id) { return Arc(id);} 1030 static Edge edgeFromId(int id) { return Edge(id);} 1031 1032 bool valid(Node n) const { 1033 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 1034 } 1035 bool valid(Arc a) const { 1036 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 1037 } 1038 bool valid(Edge e) const { 1039 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 1040 } 1041 1042 Node addRedNode() { 1043 int n = nodes.size(); 1044 nodes.push_back(NodeT()); 1045 nodes[n].first_out = -1; 1046 nodes[n].red = true; 1047 if (first_red == -1) { 1048 nodes[n].partition_index = 0; 1049 } else { 1050 nodes[n].partition_index = nodes[first_red].partition_index + 1; 1051 } 1052 nodes[n].partition_next = first_red; 1053 first_red = n; 1054 1055 return Node(n); 1056 } 1057 1058 Node addBlueNode() { 1059 int n = nodes.size(); 1060 nodes.push_back(NodeT()); 1061 nodes[n].first_out = -1; 1062 nodes[n].red = false; 1063 if (first_blue == -1) { 1064 nodes[n].partition_index = 0; 1065 } else { 1066 nodes[n].partition_index = nodes[first_blue].partition_index + 1; 1067 } 1068 nodes[n].partition_next = first_blue; 1069 first_blue = n; 1070 1071 return Node(n); 1072 } 1073 1074 Edge addEdge(Node u, Node v) { 1075 int n = arcs.size(); 1076 arcs.push_back(ArcT()); 1077 arcs.push_back(ArcT()); 1078 1079 arcs[n].target = u._id; 1080 arcs[n | 1].target = v._id; 1081 1082 arcs[n].next_out = nodes[v._id].first_out; 1083 nodes[v._id].first_out = n; 1084 1085 arcs[n | 1].next_out = nodes[u._id].first_out; 1086 nodes[u._id].first_out = (n | 1); 1087 1088 return Edge(n / 2); 1089 } 1090 1091 void clear() { 1092 arcs.clear(); 1093 nodes.clear(); 1094 first_red = -1; 1095 first_blue = -1; 1096 } 1097 1098 }; 1099 1100 typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase; 1101 1102 /// \ingroup graphs 1103 /// 1104 /// \brief A smart undirected graph class. 1105 /// 1106 /// \ref SmartBpGraph is a simple and fast graph implementation. 1107 /// It is also quite memory efficient but at the price 1108 /// that it does not support node and edge deletion 1109 /// (except for the Snapshot feature). 1110 /// 1111 /// This type fully conforms to the \ref concepts::Graph "Graph concept" 1112 /// and it also provides some additional functionalities. 1113 /// Most of its member functions and nested classes are documented 1114 /// only in the concept class. 1115 /// 1116 /// This class provides constant time counting for nodes, edges and arcs. 1117 /// 1118 /// \sa concepts::Graph 1119 /// \sa SmartDigraph 1120 class SmartBpGraph : public ExtendedSmartBpGraphBase { 1121 typedef ExtendedSmartBpGraphBase Parent; 1122 1123 private: 1124 /// Graphs are \e not copy constructible. Use GraphCopy instead. 1125 SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {}; 1126 /// \brief Assignment of a graph to another one is \e not allowed. 1127 /// Use GraphCopy instead. 1128 void operator=(const SmartBpGraph &) {} 1129 1130 public: 1131 1132 /// Constructor 1133 1134 /// Constructor. 1135 /// 1136 SmartBpGraph() {} 1137 1138 /// \brief Add a new red node to the graph. 1139 /// 1140 /// This function adds a red new node to the graph. 1141 /// \return The new node. 1142 Node addRedNode() { return Parent::addRedNode(); } 1143 1144 /// \brief Add a new blue node to the graph. 1145 /// 1146 /// This function adds a blue new node to the graph. 1147 /// \return The new node. 1148 Node addBlueNode() { return Parent::addBlueNode(); } 1149 1150 /// \brief Add a new edge to the graph. 1151 /// 1152 /// This function adds a new edge to the graph between nodes 1153 /// \c u and \c v with inherent orientation from node \c u to 1154 /// node \c v. 1155 /// \return The new edge. 1156 Edge addEdge(Node red, Node blue) { 1157 LEMON_DEBUG(Parent::red(red) && Parent::blue(blue), 1158 "Edge has to be formed by a red and a blue nodes"); 1159 return Parent::addEdge(red, blue); 1160 } 1161 1162 /// \brief Node validity check 1163 /// 1164 /// This function gives back \c true if the given node is valid, 1165 /// i.e. it is a real node of the graph. 1166 /// 1167 /// \warning A removed node (using Snapshot) could become valid again 1168 /// if new nodes are added to the graph. 1169 bool valid(Node n) const { return Parent::valid(n); } 1170 1171 /// \brief Edge validity check 1172 /// 1173 /// This function gives back \c true if the given edge is valid, 1174 /// i.e. it is a real edge of the graph. 1175 /// 1176 /// \warning A removed edge (using Snapshot) could become valid again 1177 /// if new edges are added to the graph. 1178 bool valid(Edge e) const { return Parent::valid(e); } 1179 1180 /// \brief Arc validity check 1181 /// 1182 /// This function gives back \c true if the given arc is valid, 1183 /// i.e. it is a real arc of the graph. 1184 /// 1185 /// \warning A removed arc (using Snapshot) could become valid again 1186 /// if new edges are added to the graph. 1187 bool valid(Arc a) const { return Parent::valid(a); } 1188 1189 ///Clear the graph. 1190 1191 ///This function erases all nodes and arcs from the graph. 1192 /// 1193 void clear() { 1194 Parent::clear(); 1195 } 1196 1197 /// Reserve memory for nodes. 1198 1199 /// Using this function, it is possible to avoid superfluous memory 1200 /// allocation: if you know that the graph you want to build will 1201 /// be large (e.g. it will contain millions of nodes and/or edges), 1202 /// then it is worth reserving space for this amount before starting 1203 /// to build the graph. 1204 /// \sa reserveEdge() 1205 void reserveNode(int n) { nodes.reserve(n); }; 1206 1207 /// Reserve memory for edges. 1208 1209 /// Using this function, it is possible to avoid superfluous memory 1210 /// allocation: if you know that the graph you want to build will 1211 /// be large (e.g. it will contain millions of nodes and/or edges), 1212 /// then it is worth reserving space for this amount before starting 1213 /// to build the graph. 1214 /// \sa reserveNode() 1215 void reserveEdge(int m) { arcs.reserve(2 * m); }; 1216 1217 public: 1218 1219 class Snapshot; 1220 1221 protected: 1222 1223 void saveSnapshot(Snapshot &s) 1224 { 1225 s._graph = this; 1226 s.node_num = nodes.size(); 1227 s.arc_num = arcs.size(); 1228 } 1229 1230 void restoreSnapshot(const Snapshot &s) 1231 { 1232 while(s.arc_num<arcs.size()) { 1233 int n=arcs.size()-1; 1234 Edge arc=edgeFromId(n/2); 1235 Parent::notifier(Edge()).erase(arc); 1236 std::vector<Arc> dir; 1237 dir.push_back(arcFromId(n)); 1238 dir.push_back(arcFromId(n-1)); 1239 Parent::notifier(Arc()).erase(dir); 1240 nodes[arcs[n-1].target].first_out=arcs[n].next_out; 1241 nodes[arcs[n].target].first_out=arcs[n-1].next_out; 1242 arcs.pop_back(); 1243 arcs.pop_back(); 1244 } 1245 while(s.node_num<nodes.size()) { 1246 int n=nodes.size()-1; 1247 Node node = nodeFromId(n); 1248 if (Parent::red(node)) { 1249 first_red = nodes[n].partition_next; 1250 Parent::notifier(RedNode()).erase(node); 1251 } else { 1252 first_blue = nodes[n].partition_next; 1253 Parent::notifier(BlueNode()).erase(node); 1254 } 1255 Parent::notifier(Node()).erase(node); 1256 nodes.pop_back(); 1257 } 1258 } 1259 1260 public: 1261 1262 ///Class to make a snapshot of the graph and to restore it later. 1263 1264 ///Class to make a snapshot of the graph and to restore it later. 1265 /// 1266 ///The newly added nodes and edges can be removed using the 1267 ///restore() function. This is the only way for deleting nodes and/or 1268 ///edges from a SmartBpGraph structure. 1269 /// 1270 ///\note After a state is restored, you cannot restore a later state, 1271 ///i.e. you cannot add the removed nodes and edges again using 1272 ///another Snapshot instance. 1273 /// 1274 ///\warning The validity of the snapshot is not stored due to 1275 ///performance reasons. If you do not use the snapshot correctly, 1276 ///it can cause broken program, invalid or not restored state of 1277 ///the graph or no change. 1278 class Snapshot 1279 { 1280 SmartBpGraph *_graph; 1281 protected: 1282 friend class SmartBpGraph; 1283 unsigned int node_num; 1284 unsigned int arc_num; 1285 public: 1286 ///Default constructor. 1287 1288 ///Default constructor. 1289 ///You have to call save() to actually make a snapshot. 1290 Snapshot() : _graph(0) {} 1291 ///Constructor that immediately makes a snapshot 1292 1293 /// This constructor immediately makes a snapshot of the given graph. 1294 /// 1295 Snapshot(SmartBpGraph &gr) { 1296 gr.saveSnapshot(*this); 1297 } 1298 1299 ///Make a snapshot. 1300 1301 ///This function makes a snapshot of the given graph. 1302 ///It can be called more than once. In case of a repeated 1303 ///call, the previous snapshot gets lost. 1304 void save(SmartBpGraph &gr) 1305 { 1306 gr.saveSnapshot(*this); 1307 } 1308 1309 ///Undo the changes until the last snapshot. 1310 1311 ///This function undos the changes until the last snapshot 1312 ///created by save() or Snapshot(SmartBpGraph&). 1313 void restore() 1314 { 1315 _graph->restoreSnapshot(*this); 1316 } 1317 }; 1318 }; 1319 814 1320 } //namespace lemon 815 1321
Note: See TracChangeset
for help on using the changeset viewer.