r239:7b7e3f20bcec
Tue, 29 Jul 2008 14:54:08
[Not Reviewed]
0 comments (0 inline)
0
1
0
30
64
| ... | ... |
@@ -386,49 +386,49 @@ |
| 386 | 386 |
bool valid(Node n) const { return Parent::valid(n); }
|
| 387 | 387 |
|
| 388 | 388 |
/// Arc validity check |
| 389 | 389 |
|
| 390 | 390 |
/// This function gives back true if the given arc is valid, |
| 391 | 391 |
/// ie. it is a real arc of the graph. |
| 392 | 392 |
/// |
| 393 | 393 |
/// \warning An Arc pointing to a removed item |
| 394 | 394 |
/// could become valid again later if new nodes are |
| 395 | 395 |
/// added to the graph. |
| 396 | 396 |
bool valid(Arc a) const { return Parent::valid(a); }
|
| 397 | 397 |
|
| 398 |
/// Change the target of \c |
|
| 398 |
/// Change the target of \c a to \c n |
|
| 399 | 399 |
|
| 400 |
/// Change the target of \c |
|
| 400 |
/// Change the target of \c a to \c n |
|
| 401 | 401 |
/// |
| 402 | 402 |
///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing |
| 403 | 403 |
///the changed arc remain valid. However <tt>InArcIt</tt>s are |
| 404 | 404 |
///invalidated. |
| 405 | 405 |
/// |
| 406 | 406 |
///\warning This functionality cannot be used together with the Snapshot |
| 407 | 407 |
///feature. |
| 408 |
void changeTarget(Arc e, Node n) {
|
|
| 409 |
Parent::changeTarget(e,n); |
|
| 408 |
void changeTarget(Arc a, Node n) {
|
|
| 409 |
Parent::changeTarget(a,n); |
|
| 410 | 410 |
} |
| 411 |
/// Change the source of \c |
|
| 411 |
/// Change the source of \c a to \c n |
|
| 412 | 412 |
|
| 413 |
/// Change the source of \c |
|
| 413 |
/// Change the source of \c a to \c n |
|
| 414 | 414 |
/// |
| 415 |
///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing |
|
| 416 |
///the changed arc remain valid. However <tt>OutArcIt</tt>s are |
|
| 415 |
///\note The <tt>InArcIt</tt>s referencing the changed arc remain |
|
| 416 |
///valid. However the <tt>ArcIt<tt>s and <tt>OutArcIt</tt>s are |
|
| 417 | 417 |
///invalidated. |
| 418 | 418 |
/// |
| 419 | 419 |
///\warning This functionality cannot be used together with the Snapshot |
| 420 | 420 |
///feature. |
| 421 |
void changeSource(Arc e, Node n) {
|
|
| 422 |
Parent::changeSource(e,n); |
|
| 421 |
void changeSource(Arc a, Node n) {
|
|
| 422 |
Parent::changeSource(a,n); |
|
| 423 | 423 |
} |
| 424 | 424 |
|
| 425 | 425 |
/// Invert the direction of an arc. |
| 426 | 426 |
|
| 427 | 427 |
///\note The <tt>ArcIt</tt>s referencing the changed arc remain |
| 428 | 428 |
///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are |
| 429 | 429 |
///invalidated. |
| 430 | 430 |
/// |
| 431 | 431 |
///\warning This functionality cannot be used together with the Snapshot |
| 432 | 432 |
///feature. |
| 433 | 433 |
void reverseArc(Arc e) {
|
| 434 | 434 |
Node t=target(e); |
| ... | ... |
@@ -1107,46 +1107,46 @@ |
| 1107 | 1107 |
arcs[n | 1].prev_out = -2; |
| 1108 | 1108 |
|
| 1109 | 1109 |
} |
| 1110 | 1110 |
|
| 1111 | 1111 |
void clear() {
|
| 1112 | 1112 |
arcs.clear(); |
| 1113 | 1113 |
nodes.clear(); |
| 1114 | 1114 |
first_node = first_free_node = first_free_arc = -1; |
| 1115 | 1115 |
} |
| 1116 | 1116 |
|
| 1117 | 1117 |
protected: |
| 1118 | 1118 |
|
| 1119 |
void |
|
| 1119 |
void changeV(Edge e, Node n) {
|
|
| 1120 | 1120 |
if(arcs[2 * e.id].next_out != -1) {
|
| 1121 | 1121 |
arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; |
| 1122 | 1122 |
} |
| 1123 | 1123 |
if(arcs[2 * e.id].prev_out != -1) {
|
| 1124 | 1124 |
arcs[arcs[2 * e.id].prev_out].next_out = |
| 1125 | 1125 |
arcs[2 * e.id].next_out; |
| 1126 | 1126 |
} else {
|
| 1127 | 1127 |
nodes[arcs[(2 * e.id) | 1].target].first_out = |
| 1128 | 1128 |
arcs[2 * e.id].next_out; |
| 1129 | 1129 |
} |
| 1130 | 1130 |
|
| 1131 | 1131 |
if (nodes[n.id].first_out != -1) {
|
| 1132 | 1132 |
arcs[nodes[n.id].first_out].prev_out = 2 * e.id; |
| 1133 | 1133 |
} |
| 1134 | 1134 |
arcs[(2 * e.id) | 1].target = n.id; |
| 1135 | 1135 |
arcs[2 * e.id].prev_out = -1; |
| 1136 | 1136 |
arcs[2 * e.id].next_out = nodes[n.id].first_out; |
| 1137 | 1137 |
nodes[n.id].first_out = 2 * e.id; |
| 1138 | 1138 |
} |
| 1139 | 1139 |
|
| 1140 |
void |
|
| 1140 |
void changeU(Edge e, Node n) {
|
|
| 1141 | 1141 |
if(arcs[(2 * e.id) | 1].next_out != -1) {
|
| 1142 | 1142 |
arcs[arcs[(2 * e.id) | 1].next_out].prev_out = |
| 1143 | 1143 |
arcs[(2 * e.id) | 1].prev_out; |
| 1144 | 1144 |
} |
| 1145 | 1145 |
if(arcs[(2 * e.id) | 1].prev_out != -1) {
|
| 1146 | 1146 |
arcs[arcs[(2 * e.id) | 1].prev_out].next_out = |
| 1147 | 1147 |
arcs[(2 * e.id) | 1].next_out; |
| 1148 | 1148 |
} else {
|
| 1149 | 1149 |
nodes[arcs[2 * e.id].target].first_out = |
| 1150 | 1150 |
arcs[(2 * e.id) | 1].next_out; |
| 1151 | 1151 |
} |
| 1152 | 1152 |
|
| ... | ... |
@@ -1251,107 +1251,73 @@ |
| 1251 | 1251 |
/// could become valid again later if new edges are |
| 1252 | 1252 |
/// added to the graph. |
| 1253 | 1253 |
bool valid(Arc a) const { return Parent::valid(a); }
|
| 1254 | 1254 |
/// Edge validity check |
| 1255 | 1255 |
|
| 1256 | 1256 |
/// This function gives back true if the given edge is valid, |
| 1257 | 1257 |
/// ie. it is a real arc of the graph. |
| 1258 | 1258 |
/// |
| 1259 | 1259 |
/// \warning A Edge pointing to a removed item |
| 1260 | 1260 |
/// could become valid again later if new edges are |
| 1261 | 1261 |
/// added to the graph. |
| 1262 | 1262 |
bool valid(Edge e) const { return Parent::valid(e); }
|
| 1263 |
/// \brief Change the |
|
| 1263 |
/// \brief Change the end \c u of \c e to \c n |
|
| 1264 | 1264 |
/// |
| 1265 |
/// This function changes the |
|
| 1265 |
/// This function changes the end \c u of \c e to node \c n. |
|
| 1266 | 1266 |
/// |
| 1267 |
///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
|
| 1268 |
///referencing the changed arc remain |
|
| 1269 |
/// |
|
| 1267 |
///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the |
|
| 1268 |
///changed edge are invalidated and if the changed node is the |
|
| 1269 |
///base node of an iterator then this iterator is also |
|
| 1270 |
///invalidated. |
|
| 1270 | 1271 |
/// |
| 1271 | 1272 |
///\warning This functionality cannot be used together with the |
| 1272 | 1273 |
///Snapshot feature. |
| 1273 |
void changeSource(Edge e, Node n) {
|
|
| 1274 |
Parent::changeSource(e,n); |
|
| 1274 |
void changeU(Edge e, Node n) {
|
|
| 1275 |
Parent::changeU(e,n); |
|
| 1275 | 1276 |
} |
| 1276 |
/// \brief Change the |
|
| 1277 |
/// \brief Change the end \c v of \c e to \c n |
|
| 1277 | 1278 |
/// |
| 1278 |
/// This function changes the |
|
| 1279 |
/// This function changes the end \c v of \c e to \c n. |
|
| 1279 | 1280 |
/// |
| 1280 |
/// \note The <tt>ArcIt</tt>s referencing the changed arc remain |
|
| 1281 |
/// valid. However the other iterators may be invalidated. |
|
| 1281 |
///\note The <tt>EdgeIt</tt>s referencing the changed edge remain |
|
| 1282 |
///valid, however <tt>ArcIt</tt>s and if the changed node is the |
|
| 1283 |
///base node of an iterator then this iterator is invalidated. |
|
| 1282 | 1284 |
/// |
| 1283 | 1285 |
///\warning This functionality cannot be used together with the |
| 1284 | 1286 |
///Snapshot feature. |
| 1285 |
void changeTarget(Edge e, Node n) {
|
|
| 1286 |
Parent::changeTarget(e,n); |
|
| 1287 |
} |
|
| 1288 |
/// \brief Change the source of \c e to \c n |
|
| 1289 |
/// |
|
| 1290 |
/// This function changes the source of \c e to \c n. |
|
| 1291 |
/// It also changes the proper node of the represented edge. |
|
| 1292 |
/// |
|
| 1293 |
///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
|
| 1294 |
///referencing the changed arc remain |
|
| 1295 |
///valid. However <tt>OutArcIt</tt>s are invalidated. |
|
| 1296 |
/// |
|
| 1297 |
///\warning This functionality cannot be used together with the |
|
| 1298 |
///Snapshot feature. |
|
| 1299 |
void changeSource(Arc e, Node n) {
|
|
| 1300 |
if (Parent::direction(e)) {
|
|
| 1301 |
Parent::changeSource(e,n); |
|
| 1302 |
} else {
|
|
| 1303 |
Parent::changeTarget(e,n); |
|
| 1304 |
} |
|
| 1305 |
} |
|
| 1306 |
/// \brief Change the target of \c e to \c n |
|
| 1307 |
/// |
|
| 1308 |
/// This function changes the target of \c e to \c n. |
|
| 1309 |
/// It also changes the proper node of the represented edge. |
|
| 1310 |
/// |
|
| 1311 |
///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s |
|
| 1312 |
///referencing the changed arc remain |
|
| 1313 |
///valid. However <tt>InArcIt</tt>s are invalidated. |
|
| 1314 |
/// |
|
| 1315 |
///\warning This functionality cannot be used together with the |
|
| 1316 |
///Snapshot feature. |
|
| 1317 |
void changeTarget(Arc e, Node n) {
|
|
| 1318 |
if (Parent::direction(e)) {
|
|
| 1319 |
Parent::changeTarget(e,n); |
|
| 1320 |
} else {
|
|
| 1321 |
Parent::changeSource(e,n); |
|
| 1322 |
} |
|
| 1287 |
void changeV(Edge e, Node n) {
|
|
| 1288 |
Parent::changeV(e,n); |
|
| 1323 | 1289 |
} |
| 1324 | 1290 |
/// \brief Contract two nodes. |
| 1325 | 1291 |
/// |
| 1326 | 1292 |
/// This function contracts two nodes. |
| 1327 | 1293 |
/// Node \p b will be removed but instead of deleting |
| 1328 | 1294 |
/// its neighboring arcs, they will be joined to \p a. |
| 1329 | 1295 |
/// The last parameter \p r controls whether to remove loops. \c true |
| 1330 | 1296 |
/// means that loops will be removed. |
| 1331 | 1297 |
/// |
| 1332 | 1298 |
/// \note The <tt>ArcIt</tt>s referencing a moved arc remain |
| 1333 | 1299 |
/// valid. |
| 1334 | 1300 |
/// |
| 1335 | 1301 |
///\warning This functionality cannot be used together with the |
| 1336 | 1302 |
///Snapshot feature. |
| 1337 | 1303 |
void contract(Node a, Node b, bool r = true) {
|
| 1338 | 1304 |
for(IncEdgeIt e(*this, b); e!=INVALID;) {
|
| 1339 | 1305 |
IncEdgeIt f = e; ++f; |
| 1340 | 1306 |
if (r && runningNode(e) == a) {
|
| 1341 | 1307 |
erase(e); |
| 1342 |
} else if (source(e) == b) {
|
|
| 1343 |
changeSource(e, a); |
|
| 1308 |
} else if (u(e) == b) {
|
|
| 1309 |
changeU(e, a); |
|
| 1344 | 1310 |
} else {
|
| 1345 |
|
|
| 1311 |
changeV(e, a); |
|
| 1346 | 1312 |
} |
| 1347 | 1313 |
e = f; |
| 1348 | 1314 |
} |
| 1349 | 1315 |
erase(b); |
| 1350 | 1316 |
} |
| 1351 | 1317 |
|
| 1352 | 1318 |
|
| 1353 | 1319 |
/// \brief Class to make a snapshot of the graph and restore |
| 1354 | 1320 |
/// it later. |
| 1355 | 1321 |
/// |
| 1356 | 1322 |
/// Class to make a snapshot of the graph and restore it later. |
| 1357 | 1323 |
/// |
0 comments (0 inline)