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