273 nodes.clear(); |
273 nodes.clear(); |
274 first_node = first_free_node = first_free_edge = -1; |
274 first_node = first_free_node = first_free_edge = -1; |
275 } |
275 } |
276 |
276 |
277 protected: |
277 protected: |
278 void _moveTarget(Edge e, Node n) |
278 void _changeTarget(Edge e, Node n) |
279 { |
279 { |
280 if(edges[e.id].next_in != -1) |
280 if(edges[e.id].next_in != -1) |
281 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; |
281 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; |
282 if(edges[e.id].prev_in != -1) |
282 if(edges[e.id].prev_in != -1) |
283 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; |
283 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; |
285 edges[e.id].target = n.id; |
285 edges[e.id].target = n.id; |
286 edges[e.id].prev_in = -1; |
286 edges[e.id].prev_in = -1; |
287 edges[e.id].next_in = nodes[n.id].first_in; |
287 edges[e.id].next_in = nodes[n.id].first_in; |
288 nodes[n.id].first_in = e.id; |
288 nodes[n.id].first_in = e.id; |
289 } |
289 } |
290 void _moveSource(Edge e, Node n) |
290 void _changeSource(Edge e, Node n) |
291 { |
291 { |
292 if(edges[e.id].next_out != -1) |
292 if(edges[e.id].next_out != -1) |
293 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; |
293 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; |
294 if(edges[e.id].prev_out != -1) |
294 if(edges[e.id].prev_out != -1) |
295 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; |
295 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; |
322 ///\sa concept::ErasableGraph. |
322 ///\sa concept::ErasableGraph. |
323 |
323 |
324 class ListGraph : public ErasableListGraphBase |
324 class ListGraph : public ErasableListGraphBase |
325 { |
325 { |
326 public: |
326 public: |
327 /// Moves the target of \c e to \c n |
327 /// Changes the target of \c e to \c n |
328 |
328 |
329 /// Moves the target of \c e to \c n |
329 /// Changes the target of \c e to \c n |
330 /// |
330 /// |
331 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
331 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
332 ///referencing the moved edge remain |
332 ///referencing the changed edge remain |
333 ///valid. However <tt>InEdge</tt>'s are invalidated. |
333 ///valid. However <tt>InEdge</tt>'s are invalidated. |
334 void moveTarget(Edge e, Node n) { _moveTarget(e,n); } |
334 void changeTarget(Edge e, Node n) { _changeTarget(e,n); } |
335 /// Moves the source of \c e to \c n |
335 /// Changes the source of \c e to \c n |
336 |
336 |
337 /// Moves the source of \c e to \c n |
337 /// Changes the source of \c e to \c n |
338 /// |
338 /// |
339 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
339 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
340 ///referencing the moved edge remain |
340 ///referencing the changed edge remain |
341 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
341 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
342 void moveSource(Edge e, Node n) { _moveSource(e,n); } |
342 void changeSource(Edge e, Node n) { _changeSource(e,n); } |
343 |
343 |
344 /// Invert the direction of an edge. |
344 /// Invert the direction of an edge. |
345 |
345 |
346 ///\note The <tt>Edge</tt>'s |
346 ///\note The <tt>Edge</tt>'s |
347 ///referencing the moved edge remain |
347 ///referencing the changed edge remain |
348 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated. |
348 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated. |
349 void reverseEdge(Edge e) { |
349 void reverseEdge(Edge e) { |
350 Node t=target(e); |
350 Node t=target(e); |
351 _moveTarget(e,source(e)); |
351 _changeTarget(e,source(e)); |
352 _moveSource(e,t); |
352 _changeSource(e,t); |
353 } |
353 } |
354 |
354 |
355 ///Using this it possible to avoid the superfluous memory allocation. |
355 ///Using this it possible to avoid the superfluous memory allocation. |
356 |
356 |
357 ///Using this it possible to avoid the superfluous memory allocation. |
357 ///Using this it possible to avoid the superfluous memory allocation. |
375 { |
375 { |
376 for(OutEdgeIt e(*this,b);e!=INVALID;) { |
376 for(OutEdgeIt e(*this,b);e!=INVALID;) { |
377 OutEdgeIt f=e; |
377 OutEdgeIt f=e; |
378 ++f; |
378 ++f; |
379 if(r && target(e)==a) erase(e); |
379 if(r && target(e)==a) erase(e); |
380 else moveSource(e,a); |
380 else changeSource(e,a); |
381 e=f; |
381 e=f; |
382 } |
382 } |
383 for(InEdgeIt e(*this,b);e!=INVALID;) { |
383 for(InEdgeIt e(*this,b);e!=INVALID;) { |
384 InEdgeIt f=e; |
384 InEdgeIt f=e; |
385 ++f; |
385 ++f; |
386 if(r && source(e)==a) erase(e); |
386 if(r && source(e)==a) erase(e); |
387 else moveTarget(e,a); |
387 else changeTarget(e,a); |
388 e=f; |
388 e=f; |
389 } |
389 } |
390 erase(b); |
390 erase(b); |
391 } |
391 } |
392 |
392 |
557 ///It conforms to the |
557 ///It conforms to the |
558 ///\ref concept::UndirGraph "UndirGraph" concept. |
558 ///\ref concept::UndirGraph "UndirGraph" concept. |
559 /// |
559 /// |
560 ///\sa concept::UndirGraph. |
560 ///\sa concept::UndirGraph. |
561 /// |
561 /// |
562 ///\todo SnapShot, reverseEdge(), moveTarget(), moveSource(), contract() |
562 ///\todo SnapShot, reverseEdge(), changeTarget(), changeSource(), contract() |
563 ///haven't been implemented yet. |
563 ///haven't been implemented yet. |
564 /// |
564 /// |
565 class UndirListGraph : public ErasableUndirListGraphBase { |
565 class UndirListGraph : public ErasableUndirListGraphBase { |
566 }; |
566 }; |
567 |
567 |