r73:c56b7389dc78
Tue, 05 Feb 2008 11:24:57
[Not Reviewed]
0 comments (0 inline)
0
1
0
166
144
| ... | ... |
@@ -112,10 +112,10 @@ |
| 112 | 112 |
|
| 113 | 113 |
|
| 114 |
void first(Arc& |
|
| 114 |
void first(Arc& arc) const {
|
|
| 115 | 115 |
int n; |
| 116 | 116 |
for(n = first_node; |
| 117 | 117 |
n!=-1 && nodes[n].first_in == -1; |
| 118 | 118 |
n = nodes[n].next); |
| 119 |
|
|
| 119 |
arc.id = (n == -1) ? -1 : nodes[n].first_in; |
|
| 120 | 120 |
} |
| 121 | 121 |
|
| ... | ... |
@@ -294,33 +294,35 @@ |
| 294 | 294 |
typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase; |
| 295 | 295 |
|
| 296 |
/// \addtogroup |
|
| 296 |
/// \addtogroup graphs |
|
| 297 | 297 |
/// @{
|
| 298 | 298 |
|
| 299 |
///A |
|
| 299 |
///A general directed graph structure. |
|
| 300 | 300 |
|
| 301 |
/// |
|
| 301 |
///\ref ListDigraph is a simple and fast <em>directed graph</em> |
|
| 302 |
///implementation based on static linked lists that are stored in |
|
| 303 |
///\c std::vector structures. |
|
| 302 | 304 |
/// |
| 303 | 305 |
///It conforms to the \ref concepts::Digraph "Digraph concept" and it |
| 304 |
///also provides several additional useful extra functionalities. |
|
| 305 |
///The most of the member functions and nested classes are |
|
| 306 |
/// |
|
| 306 |
///also provides several useful additional functionalities. |
|
| 307 |
///Most of the member functions and nested classes are documented |
|
| 308 |
///only in the concept class. |
|
| 307 | 309 |
/// |
| 308 | 310 |
///An important extra feature of this digraph implementation is that |
| 309 | 311 |
///its maps are real \ref concepts::ReferenceMap "reference map"s. |
| 310 | 312 |
/// |
| 311 |
///\sa concepts::Digraph |
|
| 313 |
///\sa concepts::Digraph |
|
| 312 | 314 |
|
| 313 | 315 |
class ListDigraph : public ExtendedListDigraphBase {
|
| 314 | 316 |
private: |
| 315 |
///ListDigraph is \e not copy constructible. Use |
|
| 317 |
///ListDigraph is \e not copy constructible. Use copyDigraph() instead. |
|
| 316 | 318 |
|
| 317 |
///ListDigraph is \e not copy constructible. Use |
|
| 319 |
///ListDigraph is \e not copy constructible. Use copyDigraph() instead. |
|
| 318 | 320 |
/// |
| 319 | 321 |
ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
|
| 320 | 322 |
///\brief Assignment of ListDigraph to another one is \e not allowed. |
| 321 |
///Use |
|
| 323 |
///Use copyDigraph() instead. |
|
| 322 | 324 |
|
| 323 | 325 |
///Assignment of ListDigraph to another one is \e not allowed. |
| 324 |
///Use |
|
| 326 |
///Use copyDigraph() instead. |
|
| 325 | 327 |
void operator=(const ListDigraph &) {}
|
| 326 | 328 |
public: |
| ... | ... |
@@ -336,6 +338,6 @@ |
| 336 | 338 |
///Add a new node to the digraph. |
| 337 | 339 |
|
| 338 |
/// \return the new node. |
|
| 339 |
/// |
|
| 340 |
///Add a new node to the digraph. |
|
| 341 |
///\return the new node. |
|
| 340 | 342 |
Node addNode() { return Parent::addNode(); }
|
| 341 | 343 |
|
| ... | ... |
@@ -349,11 +351,12 @@ |
| 349 | 351 |
} |
| 350 | 352 |
|
| 351 |
/// |
|
| 353 |
/// Change the target of \c e to \c n |
|
| 352 | 354 |
|
| 353 |
/// |
|
| 355 |
/// Change the target of \c e to \c n |
|
| 354 | 356 |
/// |
| 355 | 357 |
///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing |
| 356 | 358 |
///the changed arc remain valid. However <tt>InArcIt</tt>s are |
| 357 | 359 |
///invalidated. |
| 360 |
/// |
|
| 358 | 361 |
///\warning This functionality cannot be used together with the Snapshot |
| 359 | 362 |
///feature. |
| ... | ... |
@@ -361,11 +364,12 @@ |
| 361 | 364 |
Parent::changeTarget(e,n); |
| 362 | 365 |
} |
| 363 |
/// |
|
| 366 |
/// Change the source of \c e to \c n |
|
| 364 | 367 |
|
| 365 |
/// |
|
| 368 |
/// Change the source of \c e to \c n |
|
| 366 | 369 |
/// |
| 367 | 370 |
///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing |
| 368 | 371 |
///the changed arc remain valid. However <tt>OutArcIt</tt>s are |
| 369 | 372 |
///invalidated. |
| 373 |
/// |
|
| 370 | 374 |
///\warning This functionality cannot be used together with the Snapshot |
| 371 | 375 |
///feature. |
| ... | ... |
@@ -379,4 +383,5 @@ |
| 379 | 383 |
///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are |
| 380 | 384 |
///invalidated. |
| 385 |
/// |
|
| 381 | 386 |
///\warning This functionality cannot be used together with the Snapshot |
| 382 | 387 |
///feature. |
| ... | ... |
@@ -387,5 +392,7 @@ |
| 387 | 392 |
} |
| 388 | 393 |
|
| 389 |
/// |
|
| 394 |
/// Reserve memory for nodes. |
|
| 395 |
|
|
| 396 |
/// Using this function it is possible to avoid the superfluous memory |
|
| 390 | 397 |
/// allocation: if you know that the digraph you want to build will |
| 391 | 398 |
/// be very large (e.g. it will contain millions of nodes and/or arcs) |
| ... | ... |
@@ -395,8 +402,7 @@ |
| 395 | 402 |
void reserveNode(int n) { nodes.reserve(n); };
|
| 396 | 403 |
|
| 397 |
/// \brief Using this it is possible to avoid the superfluous memory |
|
| 398 |
/// allocation. |
|
| 404 |
/// Reserve memory for arcs. |
|
| 399 | 405 |
|
| 400 |
/// Using this it is possible to avoid the superfluous memory |
|
| 406 |
/// Using this function it is possible to avoid the superfluous memory |
|
| 401 | 407 |
/// allocation: if you know that the digraph you want to build will |
| 402 | 408 |
/// be very large (e.g. it will contain millions of nodes and/or arcs) |
| ... | ... |
@@ -409,5 +415,4 @@ |
| 409 | 415 |
|
| 410 | 416 |
///This function contracts two nodes. |
| 411 |
/// |
|
| 412 | 417 |
///Node \p b will be removed but instead of deleting |
| 413 | 418 |
///incident arcs, they will be joined to \p a. |
| ... | ... |
@@ -415,8 +420,8 @@ |
| 415 | 420 |
///means that loops will be removed. |
| 416 | 421 |
/// |
| 417 |
///\note The <tt>ArcIt</tt>s |
|
| 418 |
///referencing a moved arc remain |
|
| 422 |
///\note The <tt>ArcIt</tt>s referencing a moved arc remain |
|
| 419 | 423 |
///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s |
| 420 | 424 |
///may be invalidated. |
| 425 |
/// |
|
| 421 | 426 |
///\warning This functionality cannot be used together with the Snapshot |
| 422 | 427 |
///feature. |
| ... | ... |
@@ -453,6 +458,7 @@ |
| 453 | 458 |
/// |
| 454 | 459 |
///\warning This functionality cannot be used together with the |
| 455 |
///Snapshot feature. \todo It could be implemented in a bit |
|
| 456 |
///faster way. |
|
| 460 |
///Snapshot feature. |
|
| 461 |
/// |
|
| 462 |
///\todo It could be implemented in a bit faster way. |
|
| 457 | 463 |
Node split(Node n, bool connect = true) {
|
| 458 | 464 |
Node b = addNode(); |
| ... | ... |
@@ -472,7 +478,9 @@ |
| 472 | 478 |
///the digraph, then the original arc is re-targeted to \c |
| 473 | 479 |
///b. Finally an arc from \c b to the original target is added. |
| 474 |
///\return The newly created node. |
|
| 475 |
///\warning This functionality |
|
| 476 |
/// |
|
| 480 |
/// |
|
| 481 |
///\return The newly created node. |
|
| 482 |
/// |
|
| 483 |
///\warning This functionality cannot be used together with the |
|
| 484 |
///Snapshot feature. |
|
| 477 | 485 |
Node split(Arc e) {
|
| 478 | 486 |
Node b = addNode(); |
| ... | ... |
@@ -483,14 +491,14 @@ |
| 483 | 491 |
|
| 484 | 492 |
/// \brief Class to make a snapshot of the digraph and restore |
| 485 |
/// |
|
| 493 |
/// it later. |
|
| 486 | 494 |
/// |
| 487 |
/// Class to make a snapshot of the digraph and to restore it |
|
| 488 |
/// later. |
|
| 495 |
/// Class to make a snapshot of the digraph and restore it later. |
|
| 489 | 496 |
/// |
| 490 | 497 |
/// The newly added nodes and arcs can be removed using the |
| 491 | 498 |
/// restore() function. |
| 492 | 499 |
/// |
| 493 |
/// \warning Arc and node deletions cannot be restored. This |
|
| 494 |
/// events invalidate the snapshot. |
|
| 500 |
/// \warning Arc and node deletions and other modifications (e.g. |
|
| 501 |
/// contracting, splitting, reversing arcs or nodes) cannot be |
|
| 502 |
/// restored. These events invalidate the snapshot. |
|
| 495 | 503 |
class Snapshot {
|
| 496 | 504 |
protected: |
| ... | ... |
@@ -777,7 +785,7 @@ |
| 777 | 785 |
Edge() {}
|
| 778 | 786 |
Edge (Invalid) { id = -1; }
|
| 779 |
bool operator==(const Edge& arc) const {return id == arc.id;}
|
|
| 780 |
bool operator!=(const Edge& arc) const {return id != arc.id;}
|
|
| 781 |
bool operator |
|
| 787 |
bool operator==(const Edge& edge) const {return id == edge.id;}
|
|
| 788 |
bool operator!=(const Edge& edge) const {return id != edge.id;}
|
|
| 789 |
bool operator<(const Edge& edge) const {return id < edge.id;}
|
|
| 782 | 790 |
}; |
| 783 | 791 |
|
| ... | ... |
@@ -910,8 +918,8 @@ |
| 910 | 918 |
|
| 911 | 919 |
void firstInc(Edge &e, bool& d, const Node& v) const {
|
| 912 |
int de = nodes[v.id].first_out; |
|
| 913 |
if (de != -1 ) {
|
|
| 914 |
e.id = de / 2; |
|
| 915 |
d = ((de & 1) == 1); |
|
| 920 |
int a = nodes[v.id].first_out; |
|
| 921 |
if (a != -1 ) {
|
|
| 922 |
e.id = a / 2; |
|
| 923 |
d = ((a & 1) == 1); |
|
| 916 | 924 |
} else {
|
| 917 | 925 |
e.id = -1; |
| ... | ... |
@@ -920,8 +928,8 @@ |
| 920 | 928 |
} |
| 921 | 929 |
void nextInc(Edge &e, bool& d) const {
|
| 922 |
int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); |
|
| 923 |
if (de != -1 ) {
|
|
| 924 |
e.id = de / 2; |
|
| 925 |
d = ((de & 1) == 1); |
|
| 930 |
int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); |
|
| 931 |
if (a != -1 ) {
|
|
| 932 |
e.id = a / 2; |
|
| 933 |
d = ((a & 1) == 1); |
|
| 926 | 934 |
} else {
|
| 927 | 935 |
e.id = -1; |
| ... | ... |
@@ -1009,6 +1017,6 @@ |
| 1009 | 1017 |
} |
| 1010 | 1018 |
|
| 1011 |
void erase(const Edge& arc) {
|
|
| 1012 |
int n = arc.id * 2; |
|
| 1019 |
void erase(const Edge& edge) {
|
|
| 1020 |
int n = edge.id * 2; |
|
| 1013 | 1021 |
|
| 1014 | 1022 |
if (arcs[n].next_out != -1) {
|
| ... | ... |
@@ -1090,38 +1098,38 @@ |
| 1090 | 1098 |
}; |
| 1091 | 1099 |
|
| 1092 |
// typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> > |
|
| 1093 |
// ExtendedListGraphBase; |
|
| 1094 |
|
|
| 1095 | 1100 |
typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; |
| 1096 | 1101 |
|
| 1097 | 1102 |
|
| 1098 |
|
|
| 1099 |
/// \addtogroup digraphs |
|
| 1103 |
/// \addtogroup graphs |
|
| 1100 | 1104 |
/// @{
|
| 1101 | 1105 |
|
| 1102 |
/// |
|
| 1106 |
///A general undirected graph structure. |
|
| 1103 | 1107 |
|
| 1104 |
/// |
|
| 1108 |
///\ref ListGraph is a simple and fast <em>undirected graph</em> |
|
| 1109 |
///implementation based on static linked lists that are stored in |
|
| 1110 |
///\c std::vector structures. |
|
| 1105 | 1111 |
/// |
| 1106 |
/// |
|
| 1112 |
///It conforms to the \ref concepts::Graph "Graph concept" and it |
|
| 1113 |
///also provides several useful additional functionalities. |
|
| 1114 |
///Most of the member functions and nested classes are documented |
|
| 1115 |
///only in the concept class. |
|
| 1116 |
/// |
|
| 1117 |
///An important extra feature of this graph implementation is that |
|
| 1107 | 1118 |
///its maps are real \ref concepts::ReferenceMap "reference map"s. |
| 1108 | 1119 |
/// |
| 1109 |
///It conforms to the |
|
| 1110 |
///\ref concepts::Graph "Graph concept". |
|
| 1111 |
/// |
|
| 1112 |
///\sa concepts::Graph. |
|
| 1113 |
/// |
|
| 1120 |
///\sa concepts::Graph |
|
| 1121 |
|
|
| 1114 | 1122 |
class ListGraph : public ExtendedListGraphBase {
|
| 1115 | 1123 |
private: |
| 1116 |
///ListGraph is \e not copy constructible. Use |
|
| 1124 |
///ListGraph is \e not copy constructible. Use copyGraph() instead. |
|
| 1117 | 1125 |
|
| 1118 |
///ListGraph is \e not copy constructible. Use |
|
| 1126 |
///ListGraph is \e not copy constructible. Use copyGraph() instead. |
|
| 1119 | 1127 |
/// |
| 1120 | 1128 |
ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
|
| 1121 | 1129 |
///\brief Assignment of ListGraph to another one is \e not allowed. |
| 1122 |
///Use |
|
| 1130 |
///Use copyGraph() instead. |
|
| 1123 | 1131 |
|
| 1124 | 1132 |
///Assignment of ListGraph to another one is \e not allowed. |
| 1125 |
///Use |
|
| 1133 |
///Use copyGraph() instead. |
|
| 1126 | 1134 |
void operator=(const ListGraph &) {}
|
| 1127 | 1135 |
public: |
| ... | ... |
@@ -1134,15 +1142,15 @@ |
| 1134 | 1142 |
typedef ExtendedListGraphBase Parent; |
| 1135 | 1143 |
|
| 1136 |
typedef Parent::OutArcIt |
|
| 1144 |
typedef Parent::OutArcIt IncEdgeIt; |
|
| 1137 | 1145 |
|
| 1138 |
/// \brief Add a new node to the |
|
| 1146 |
/// \brief Add a new node to the graph. |
|
| 1139 | 1147 |
/// |
| 1148 |
/// Add a new node to the graph. |
|
| 1140 | 1149 |
/// \return the new node. |
| 1141 |
/// |
|
| 1142 | 1150 |
Node addNode() { return Parent::addNode(); }
|
| 1143 | 1151 |
|
| 1144 |
/// \brief Add a new edge to the |
|
| 1152 |
/// \brief Add a new edge to the graph. |
|
| 1145 | 1153 |
/// |
| 1146 |
/// Add a new |
|
| 1154 |
/// Add a new edge to the graph with source node \c s |
|
| 1147 | 1155 |
/// and target node \c t. |
| 1148 | 1156 |
/// \return the new edge. |
| ... | ... |
@@ -1150,31 +1158,40 @@ |
| 1150 | 1158 |
return Parent::addEdge(s, t); |
| 1151 | 1159 |
} |
| 1152 |
/// \brief |
|
| 1160 |
/// \brief Change the source of \c e to \c n |
|
| 1153 | 1161 |
/// |
| 1154 |
/// |
|
| 1162 |
/// This function changes the source of \c e to \c n. |
|
| 1155 | 1163 |
/// |
| 1156 | 1164 |
///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
| 1157 | 1165 |
///referencing the changed arc remain |
| 1158 | 1166 |
///valid. However <tt>OutArcIt</tt>s are invalidated. |
| 1167 |
/// |
|
| 1168 |
///\warning This functionality cannot be used together with the |
|
| 1169 |
///Snapshot feature. |
|
| 1159 | 1170 |
void changeSource(Edge e, Node n) {
|
| 1160 | 1171 |
Parent::changeSource(e,n); |
| 1161 | 1172 |
} |
| 1162 |
/// \brief |
|
| 1173 |
/// \brief Change the target of \c e to \c n |
|
| 1163 | 1174 |
/// |
| 1164 |
/// |
|
| 1175 |
/// This function changes the target of \c e to \c n. |
|
| 1165 | 1176 |
/// |
| 1166 | 1177 |
/// \note The <tt>ArcIt</tt>s referencing the changed arc remain |
| 1167 | 1178 |
/// valid. However the other iterators may be invalidated. |
| 1179 |
/// |
|
| 1180 |
///\warning This functionality cannot be used together with the |
|
| 1181 |
///Snapshot feature. |
|
| 1168 | 1182 |
void changeTarget(Edge e, Node n) {
|
| 1169 | 1183 |
Parent::changeTarget(e,n); |
| 1170 | 1184 |
} |
| 1171 |
/// \brief |
|
| 1185 |
/// \brief Change the source of \c e to \c n |
|
| 1172 | 1186 |
/// |
| 1173 |
/// Changes the source of \c e to \c n. It changes the proper |
|
| 1174 |
/// node of the represented edge. |
|
| 1187 |
/// This function changes the source of \c e to \c n. |
|
| 1188 |
/// It also changes the proper node of the represented edge. |
|
| 1175 | 1189 |
/// |
| 1176 | 1190 |
///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
| 1177 | 1191 |
///referencing the changed arc remain |
| 1178 | 1192 |
///valid. However <tt>OutArcIt</tt>s are invalidated. |
| 1193 |
/// |
|
| 1194 |
///\warning This functionality cannot be used together with the |
|
| 1195 |
///Snapshot feature. |
|
| 1179 | 1196 |
void changeSource(Arc e, Node n) {
|
| 1180 | 1197 |
if (Parent::direction(e)) {
|
| ... | ... |
@@ -1184,12 +1201,15 @@ |
| 1184 | 1201 |
} |
| 1185 | 1202 |
} |
| 1186 |
/// \brief |
|
| 1203 |
/// \brief Change the target of \c e to \c n |
|
| 1187 | 1204 |
/// |
| 1188 |
/// Changes the target of \c e to \c n. It changes the proper |
|
| 1189 |
/// node of the represented edge. |
|
| 1205 |
/// This function changes the target of \c e to \c n. |
|
| 1206 |
/// It also changes the proper node of the represented edge. |
|
| 1190 | 1207 |
/// |
| 1191 | 1208 |
///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s |
| 1192 | 1209 |
///referencing the changed arc remain |
| 1193 | 1210 |
///valid. However <tt>InArcIt</tt>s are invalidated. |
| 1211 |
/// |
|
| 1212 |
///\warning This functionality cannot be used together with the |
|
| 1213 |
///Snapshot feature. |
|
| 1194 | 1214 |
void changeTarget(Arc e, Node n) {
|
| 1195 | 1215 |
if (Parent::direction(e)) {
|
| ... | ... |
@@ -1202,5 +1222,4 @@ |
| 1202 | 1222 |
/// |
| 1203 | 1223 |
/// This function contracts two nodes. |
| 1204 |
/// |
|
| 1205 | 1224 |
/// Node \p b will be removed but instead of deleting |
| 1206 | 1225 |
/// its neighboring arcs, they will be joined to \p a. |
| ... | ... |
@@ -1210,7 +1229,10 @@ |
| 1210 | 1229 |
/// \note The <tt>ArcIt</tt>s referencing a moved arc remain |
| 1211 | 1230 |
/// valid. |
| 1231 |
/// |
|
| 1232 |
///\warning This functionality cannot be used together with the |
|
| 1233 |
///Snapshot feature. |
|
| 1212 | 1234 |
void contract(Node a, Node b, bool r = true) {
|
| 1213 |
for(IncArcIt e(*this, b); e!=INVALID;) {
|
|
| 1214 |
IncArcIt f = e; ++f; |
|
| 1235 |
for(IncEdgeIt e(*this, b); e!=INVALID;) {
|
|
| 1236 |
IncEdgeIt f = e; ++f; |
|
| 1215 | 1237 |
if (r && runningNode(e) == a) {
|
| 1216 | 1238 |
erase(e); |
| ... | ... |
@@ -1226,15 +1248,15 @@ |
| 1226 | 1248 |
|
| 1227 | 1249 |
|
| 1228 |
/// \brief Class to make a snapshot of the digraph and restore |
|
| 1229 |
/// to it later. |
|
| 1250 |
/// \brief Class to make a snapshot of the graph and restore |
|
| 1251 |
/// it later. |
|
| 1230 | 1252 |
/// |
| 1231 |
/// Class to make a snapshot of the digraph and to restore it |
|
| 1232 |
/// later. |
|
| 1253 |
/// Class to make a snapshot of the graph and restore it later. |
|
| 1233 | 1254 |
/// |
| 1234 | 1255 |
/// The newly added nodes and edges can be removed |
| 1235 | 1256 |
/// using the restore() function. |
| 1236 | 1257 |
/// |
| 1237 |
/// \warning Arc and node deletions cannot be restored. This |
|
| 1238 |
/// events invalidate the snapshot. |
|
| 1258 |
/// \warning Edge and node deletions and other modifications |
|
| 1259 |
/// (e.g. changing nodes of edges, contracting nodes) cannot be |
|
| 1260 |
/// restored. These events invalidate the snapshot. |
|
| 1239 | 1261 |
class Snapshot {
|
| 1240 | 1262 |
protected: |
| ... | ... |
@@ -1304,36 +1326,36 @@ |
| 1304 | 1326 |
protected: |
| 1305 | 1327 |
|
| 1306 |
virtual void add(const Edge& arc) {
|
|
| 1307 |
snapshot.addEdge(arc); |
|
| 1328 |
virtual void add(const Edge& edge) {
|
|
| 1329 |
snapshot.addEdge(edge); |
|
| 1308 | 1330 |
} |
| 1309 |
virtual void add(const std::vector<Edge>& arcs) {
|
|
| 1310 |
for (int i = arcs.size() - 1; i >= 0; ++i) {
|
|
| 1311 |
|
|
| 1331 |
virtual void add(const std::vector<Edge>& edges) {
|
|
| 1332 |
for (int i = edges.size() - 1; i >= 0; ++i) {
|
|
| 1333 |
snapshot.addEdge(edges[i]); |
|
| 1312 | 1334 |
} |
| 1313 | 1335 |
} |
| 1314 |
virtual void erase(const Edge& arc) {
|
|
| 1315 |
snapshot.eraseEdge(arc); |
|
| 1336 |
virtual void erase(const Edge& edge) {
|
|
| 1337 |
snapshot.eraseEdge(edge); |
|
| 1316 | 1338 |
} |
| 1317 |
virtual void erase(const std::vector<Edge>& arcs) {
|
|
| 1318 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
|
| 1319 |
|
|
| 1339 |
virtual void erase(const std::vector<Edge>& edges) {
|
|
| 1340 |
for (int i = 0; i < int(edges.size()); ++i) {
|
|
| 1341 |
snapshot.eraseEdge(edges[i]); |
|
| 1320 | 1342 |
} |
| 1321 | 1343 |
} |
| 1322 | 1344 |
virtual void build() {
|
| 1323 |
Edge arc; |
|
| 1324 |
std::vector<Edge> arcs; |
|
| 1325 |
for (notifier()->first(arc); arc != INVALID; |
|
| 1326 |
notifier()->next(arc)) {
|
|
| 1327 |
|
|
| 1345 |
Edge edge; |
|
| 1346 |
std::vector<Edge> edges; |
|
| 1347 |
for (notifier()->first(edge); edge != INVALID; |
|
| 1348 |
notifier()->next(edge)) {
|
|
| 1349 |
edges.push_back(edge); |
|
| 1328 | 1350 |
} |
| 1329 |
for (int i = arcs.size() - 1; i >= 0; --i) {
|
|
| 1330 |
snapshot.addEdge(arcs[i]); |
|
| 1351 |
for (int i = edges.size() - 1; i >= 0; --i) {
|
|
| 1352 |
snapshot.addEdge(edges[i]); |
|
| 1331 | 1353 |
} |
| 1332 | 1354 |
} |
| 1333 | 1355 |
virtual void clear() {
|
| 1334 |
Edge arc; |
|
| 1335 |
for (notifier()->first(arc); arc != INVALID; |
|
| 1336 |
notifier()->next(arc)) {
|
|
| 1337 |
snapshot.eraseEdge(arc); |
|
| 1356 |
Edge edge; |
|
| 1357 |
for (notifier()->first(edge); edge != INVALID; |
|
| 1358 |
notifier()->next(edge)) {
|
|
| 1359 |
snapshot.eraseEdge(edge); |
|
| 1338 | 1360 |
} |
| 1339 | 1361 |
} |
| ... | ... |
@@ -1341,12 +1363,12 @@ |
| 1341 | 1363 |
Snapshot& snapshot; |
| 1342 | 1364 |
}; |
| 1343 |
|
|
| 1344 |
ListGraph *digraph; |
|
| 1365 |
|
|
| 1366 |
ListGraph *graph; |
|
| 1345 | 1367 |
|
| 1346 | 1368 |
NodeObserverProxy node_observer_proxy; |
| 1347 |
EdgeObserverProxy |
|
| 1369 |
EdgeObserverProxy edge_observer_proxy; |
|
| 1348 | 1370 |
|
| 1349 | 1371 |
std::list<Node> added_nodes; |
| 1350 |
std::list<Edge> |
|
| 1372 |
std::list<Edge> added_edges; |
|
| 1351 | 1373 |
|
| 1352 | 1374 |
|
| ... | ... |
@@ -1359,5 +1381,5 @@ |
| 1359 | 1381 |
if (it == added_nodes.end()) {
|
| 1360 | 1382 |
clear(); |
| 1361 |
|
|
| 1383 |
edge_observer_proxy.detach(); |
|
| 1362 | 1384 |
throw NodeNotifier::ImmediateDetach(); |
| 1363 | 1385 |
} else {
|
| ... | ... |
@@ -1366,28 +1388,28 @@ |
| 1366 | 1388 |
} |
| 1367 | 1389 |
|
| 1368 |
void addEdge(const Edge& arc) {
|
|
| 1369 |
added_arcs.push_front(arc); |
|
| 1390 |
void addEdge(const Edge& edge) {
|
|
| 1391 |
added_edges.push_front(edge); |
|
| 1370 | 1392 |
} |
| 1371 |
void eraseEdge(const Edge& |
|
| 1393 |
void eraseEdge(const Edge& edge) {
|
|
| 1372 | 1394 |
std::list<Edge>::iterator it = |
| 1373 |
std::find(added_arcs.begin(), added_arcs.end(), arc); |
|
| 1374 |
if (it == added_arcs.end()) {
|
|
| 1395 |
std::find(added_edges.begin(), added_edges.end(), edge); |
|
| 1396 |
if (it == added_edges.end()) {
|
|
| 1375 | 1397 |
clear(); |
| 1376 | 1398 |
node_observer_proxy.detach(); |
| 1377 | 1399 |
throw EdgeNotifier::ImmediateDetach(); |
| 1378 | 1400 |
} else {
|
| 1379 |
added_arcs.erase(it); |
|
| 1380 |
} |
|
| 1401 |
added_edges.erase(it); |
|
| 1402 |
} |
|
| 1381 | 1403 |
} |
| 1382 | 1404 |
|
| 1383 |
void attach(ListGraph &_digraph) {
|
|
| 1384 |
digraph = &_digraph; |
|
| 1385 |
node_observer_proxy.attach(digraph->notifier(Node())); |
|
| 1386 |
arc_observer_proxy.attach(digraph->notifier(Edge())); |
|
| 1405 |
void attach(ListGraph &_graph) {
|
|
| 1406 |
graph = &_graph; |
|
| 1407 |
node_observer_proxy.attach(graph->notifier(Node())); |
|
| 1408 |
edge_observer_proxy.attach(graph->notifier(Edge())); |
|
| 1387 | 1409 |
} |
| 1388 | 1410 |
|
| 1389 | 1411 |
void detach() {
|
| 1390 | 1412 |
node_observer_proxy.detach(); |
| 1391 |
|
|
| 1413 |
edge_observer_proxy.detach(); |
|
| 1392 | 1414 |
} |
| 1393 | 1415 |
|
| ... | ... |
@@ -1398,5 +1420,5 @@ |
| 1398 | 1420 |
void clear() {
|
| 1399 | 1421 |
added_nodes.clear(); |
| 1400 |
|
|
| 1422 |
added_edges.clear(); |
|
| 1401 | 1423 |
} |
| 1402 | 1424 |
|
| ... | ... |
@@ -1408,30 +1430,30 @@ |
| 1408 | 1430 |
/// To actually make a snapshot you must call save(). |
| 1409 | 1431 |
Snapshot() |
| 1410 |
: digraph(0), node_observer_proxy(*this), |
|
| 1411 |
arc_observer_proxy(*this) {}
|
|
| 1432 |
: graph(0), node_observer_proxy(*this), |
|
| 1433 |
edge_observer_proxy(*this) {}
|
|
| 1412 | 1434 |
|
| 1413 | 1435 |
/// \brief Constructor that immediately makes a snapshot. |
| 1414 | 1436 |
/// |
| 1415 |
/// This constructor immediately makes a snapshot of the digraph. |
|
| 1416 |
/// \param _digraph The digraph we make a snapshot of. |
|
| 1417 |
|
|
| 1437 |
/// This constructor immediately makes a snapshot of the graph. |
|
| 1438 |
/// \param _graph The graph we make a snapshot of. |
|
| 1439 |
Snapshot(ListGraph &_graph) |
|
| 1418 | 1440 |
: node_observer_proxy(*this), |
| 1419 |
arc_observer_proxy(*this) {
|
|
| 1420 |
attach(_digraph); |
|
| 1441 |
edge_observer_proxy(*this) {
|
|
| 1442 |
attach(_graph); |
|
| 1421 | 1443 |
} |
| 1422 | 1444 |
|
| 1423 | 1445 |
/// \brief Make a snapshot. |
| 1424 | 1446 |
/// |
| 1425 |
/// Make a snapshot of the |
|
| 1447 |
/// Make a snapshot of the graph. |
|
| 1426 | 1448 |
/// |
| 1427 | 1449 |
/// This function can be called more than once. In case of a repeated |
| 1428 | 1450 |
/// call, the previous snapshot gets lost. |
| 1429 |
/// \param _digraph The digraph we make the snapshot of. |
|
| 1430 |
void save(ListGraph &_digraph) {
|
|
| 1451 |
/// \param _graph The graph we make the snapshot of. |
|
| 1452 |
void save(ListGraph &_graph) {
|
|
| 1431 | 1453 |
if (attached()) {
|
| 1432 | 1454 |
detach(); |
| 1433 | 1455 |
clear(); |
| 1434 | 1456 |
} |
| 1435 |
attach( |
|
| 1457 |
attach(_graph); |
|
| 1436 | 1458 |
} |
| 1437 | 1459 |
|
| ... | ... |
@@ -1441,11 +1463,11 @@ |
| 1441 | 1463 |
void restore() {
|
| 1442 | 1464 |
detach(); |
| 1443 |
for(std::list<Edge>::iterator it = added_arcs.begin(); |
|
| 1444 |
it != added_arcs.end(); ++it) {
|
|
| 1445 |
|
|
| 1465 |
for(std::list<Edge>::iterator it = added_edges.begin(); |
|
| 1466 |
it != added_edges.end(); ++it) {
|
|
| 1467 |
graph->erase(*it); |
|
| 1446 | 1468 |
} |
| 1447 | 1469 |
for(std::list<Node>::iterator it = added_nodes.begin(); |
| 1448 | 1470 |
it != added_nodes.end(); ++it) {
|
| 1449 |
|
|
| 1471 |
graph->erase(*it); |
|
| 1450 | 1472 |
} |
| 1451 | 1473 |
clear(); |
0 comments (0 inline)