328 |
328 |
329 /// Changes the target of \c e to \c n |
329 /// Changes the target of \c e to \c n |
330 |
330 |
331 /// Changes the target of \c e to \c n |
331 /// Changes the target of \c e to \c n |
332 /// |
332 /// |
333 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
333 ///\note The <tt>Edge</tt>s and <tt>OutEdge</tt>s |
334 ///referencing the changed edge remain |
334 ///referencing the changed edge remain |
335 ///valid. However <tt>InEdge</tt>'s are invalidated. |
335 ///valid. However <tt>InEdge</tt>s are invalidated. |
336 void changeTarget(Edge e, Node n) { |
336 void changeTarget(Edge e, Node n) { |
337 _changeTarget(e,n); |
337 _changeTarget(e,n); |
338 } |
338 } |
339 /// Changes the source of \c e to \c n |
339 /// Changes the source of \c e to \c n |
340 |
340 |
341 /// Changes the source of \c e to \c n |
341 /// Changes the source of \c e to \c n |
342 /// |
342 /// |
343 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
343 ///\note The <tt>Edge</tt>s and <tt>InEdge</tt>s |
344 ///referencing the changed edge remain |
344 ///referencing the changed edge remain |
345 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
345 ///valid. However <tt>OutEdge</tt>s are invalidated. |
346 void changeSource(Edge e, Node n) { |
346 void changeSource(Edge e, Node n) { |
347 _changeSource(e,n); |
347 _changeSource(e,n); |
348 } |
348 } |
349 |
349 |
350 /// Invert the direction of an edge. |
350 /// Invert the direction of an edge. |
351 |
351 |
352 ///\note The <tt>Edge</tt>'s |
352 ///\note The <tt>Edge</tt>s |
353 ///referencing the changed edge remain |
353 ///referencing the changed edge remain |
354 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated. |
354 ///valid. However <tt>OutEdge</tt>s and <tt>InEdge</tt>s are invalidated. |
355 void reverseEdge(Edge e) { |
355 void reverseEdge(Edge e) { |
356 Node t=target(e); |
356 Node t=target(e); |
357 _changeTarget(e,source(e)); |
357 _changeTarget(e,source(e)); |
358 _changeSource(e,t); |
358 _changeSource(e,t); |
359 } |
359 } |
360 |
360 |
361 ///Using this it possible to avoid the superfluous memory allocation. |
361 ///Using this it is possible to avoid the superfluous memory allocation. |
362 |
362 |
363 ///Using this it possible to avoid the superfluous memory allocation. |
363 ///Using this it is possible to avoid the superfluous memory allocation. |
364 ///\todo more docs... |
364 ///\todo more docs... |
365 void reserveEdge(int n) { edges.reserve(n); }; |
365 void reserveEdge(int n) { edges.reserve(n); }; |
366 |
366 |
367 ///Contract two nodes. |
367 ///Contract two nodes. |
368 |
368 |
369 ///This function contracts two nodes. |
369 ///This function contracts two nodes. |
370 /// |
370 /// |
371 ///Node \p b will be removed but instead of deleting |
371 ///Node \p b will be removed but instead of deleting |
372 ///its neighboring edges, they will be joined to \p a. |
372 ///incident edges, they will be joined to \p a. |
373 ///The last parameter \p r controls whether to remove loops. \c true |
373 ///The last parameter \p r controls whether to remove loops. \c true |
374 ///means that loops will be removed. |
374 ///means that loops will be removed. |
375 /// |
375 /// |
376 ///\note The <tt>Edge</tt>s |
376 ///\note The <tt>Edge</tt>s |
377 ///referencing a moved edge remain |
377 ///referencing a moved edge remain |
378 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
378 ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s |
379 ///may be invalidated. |
379 ///may be invalidated. |
380 void contract(Node a, Node b, bool r = true) |
380 void contract(Node a, Node b, bool r = true) |
381 { |
381 { |
382 for(OutEdgeIt e(*this,b);e!=INVALID;) { |
382 for(OutEdgeIt e(*this,b);e!=INVALID;) { |
383 OutEdgeIt f=e; |
383 OutEdgeIt f=e; |
404 ///from \c n to the newly created node is also added. |
404 ///from \c n to the newly created node is also added. |
405 ///\return The newly created node. |
405 ///\return The newly created node. |
406 /// |
406 /// |
407 ///\note The <tt>Edge</tt>s |
407 ///\note The <tt>Edge</tt>s |
408 ///referencing a moved edge remain |
408 ///referencing a moved edge remain |
409 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
409 ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s |
410 ///may be invalidated. |
410 ///may be invalidated. |
411 ///\warning This functionality cannot be used together with the Snapshot |
411 ///\warning This functionality cannot be used together with the Snapshot |
412 ///feature. |
412 ///feature. |
413 ///\todo It could be implemented in a bit faster way. |
413 ///\todo It could be implemented in a bit faster way. |
414 Node split(Node n, bool connect = true) |
414 Node split(Node n, bool connect = true) |
424 return b; |
424 return b; |
425 } |
425 } |
426 |
426 |
427 ///Split an edge. |
427 ///Split an edge. |
428 |
428 |
429 ///This function splits an edge. First a new node \c b is added to the graph, |
429 ///This function splits an edge. First a new node \c b is added to |
430 ///then the original edge is re-targetes to \c b. Finally an edge |
430 ///the graph, then the original edge is re-targeted to \c |
431 ///from \c b to the original target is added. |
431 ///b. Finally an edge from \c b to the original target is added. |
432 ///\return The newly created node. |
432 ///\return The newly created node. |
433 ///\warning This functionality cannot be used together with the Snapshot |
433 ///\warning This functionality |
434 ///feature. |
434 ///cannot be used together with the Snapshot feature. |
435 Node split(Edge e) |
435 Node split(Edge e) |
436 { |
436 { |
437 Node b = addNode(); |
437 Node b = addNode(); |
438 addEdge(b,target(e)); |
438 addEdge(b,target(e)); |
439 changeTarget(e,b); |
439 changeTarget(e,b); |
440 return b; |
440 return b; |
441 } |
441 } |
442 |
442 |
443 ///Class to make a snapshot of the graph and to restrore to it later. |
443 ///Class to make a snapshot of the graph and to restore it later. |
444 |
444 |
445 ///Class to make a snapshot of the graph and to restrore to it later. |
445 ///Class to make a snapshot of the graph and to restore it later. |
446 /// |
446 /// |
447 ///The newly added nodes and edges can be removed using the |
447 ///The newly added nodes and edges can be removed using the |
448 ///restore() function. |
448 ///restore() function. |
449 /// |
449 /// |
450 ///\warning Edge and node deletions cannot be restored. |
450 ///\warning Edge and node deletions cannot be restored. |