809 _graph->restoreSnapshot(*this); |
807 _graph->restoreSnapshot(*this); |
810 } |
808 } |
811 }; |
809 }; |
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 } //namespace lemon |
1320 } //namespace lemon |
815 |
1321 |
816 |
1322 |
817 #endif //LEMON_SMART_GRAPH_H |
1323 #endif //LEMON_SMART_GRAPH_H |