311 |
311 |
312 ///A list graph class. |
312 ///A list graph class. |
313 |
313 |
314 ///This is a simple and fast erasable graph implementation. |
314 ///This is a simple and fast erasable graph implementation. |
315 /// |
315 /// |
316 ///It conforms to the |
316 ///It addition that it conforms to the |
317 ///\ref concept::ErasableGraph "ErasableGraph" concept. |
317 ///\ref concept::ErasableGraph "ErasableGraph" concept, |
|
318 ///it also provides several additional useful extra functionalities. |
318 ///\sa concept::ErasableGraph. |
319 ///\sa concept::ErasableGraph. |
319 |
320 |
320 class ListGraph : public ErasableListGraphBase |
321 class ListGraph : public ErasableListGraphBase |
321 { |
322 { |
322 public: |
323 public: |
323 /// Moves the target of \c e to \c n |
324 /// Moves the target of \c e to \c n |
324 |
325 |
325 /// Moves the target of \c e to \c n |
326 /// Moves the target of \c e to \c n |
326 /// |
327 /// |
|
328 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
|
329 ///referencing the moved edge remain |
|
330 ///valid. However <tt>InEdge</tt>'s are invalidated. |
327 void moveTarget(Edge e, Node n) { _moveTarget(e,n); } |
331 void moveTarget(Edge e, Node n) { _moveTarget(e,n); } |
328 /// Moves the source of \c e to \c n |
332 /// Moves the source of \c e to \c n |
329 |
333 |
330 /// Moves the source of \c e to \c n |
334 /// Moves the source of \c e to \c n |
331 /// |
335 /// |
|
336 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
|
337 ///referencing the moved edge remain |
|
338 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
332 void moveSource(Edge e, Node n) { _moveSource(e,n); } |
339 void moveSource(Edge e, Node n) { _moveSource(e,n); } |
|
340 |
|
341 /// Invert the direction of an edge. |
|
342 |
|
343 ///\note The <tt>Edge</tt>'s |
|
344 ///referencing the moved edge remain |
|
345 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated. |
|
346 void reverseEdge(Edge e) { |
|
347 Node t=target(e); |
|
348 _moveTarget(e,source(e)); |
|
349 _moveSource(e,t); |
|
350 } |
|
351 |
|
352 ///Using this it possible to avoid the superfluous memory allocation. |
333 |
353 |
334 ///Using this it possible to avoid the superfluous memory allocation. |
354 ///Using this it possible to avoid the superfluous memory allocation. |
335 ///\todo more docs... |
355 ///\todo more docs... |
336 void reserveEdge(int n) { edges.reserve(n); }; |
356 void reserveEdge(int n) { edges.reserve(n); }; |
337 |
357 |
|
358 ///Contract two nodes. |
|
359 |
|
360 ///This function contracts two nodes. |
|
361 /// |
|
362 ///Node \p b will be removed but instead of deleting |
|
363 ///its neighboring edges, they will be joined to \p a. |
|
364 ///The last parameter \p r controls whether to remove loops. \c true |
|
365 ///means that loops will be removed. |
|
366 /// |
|
367 ///\note The <tt>Edge</tt>s |
|
368 ///referencing the moved edge remain |
|
369 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
|
370 ///may be invalidated. |
|
371 void contract(Node a,Node b,bool r=true) |
|
372 { |
|
373 for(OutEdgeIt e(*this,b);e!=INVALID;) { |
|
374 OutEdgeIt f=e; |
|
375 ++f; |
|
376 if(r && target(e)==a) erase(e); |
|
377 else moveSource(e,b); |
|
378 e=f; |
|
379 } |
|
380 for(InEdgeIt e(*this,b);e!=INVALID;) { |
|
381 InEdgeIt f=e; |
|
382 ++f; |
|
383 if(r && source(e)==a) erase(e); |
|
384 else moveTarget(e,b); |
|
385 e=f; |
|
386 } |
|
387 erase(b); |
|
388 } |
338 }; |
389 }; |
339 |
390 |
340 /// @} |
391 /// @} |
341 } //namespace lemon |
392 } //namespace lemon |
342 |
393 |