306 nodes[n.id].first_out = e.id; |
306 nodes[n.id].first_out = e.id; |
307 } |
307 } |
308 |
308 |
309 }; |
309 }; |
310 |
310 |
311 typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase; |
|
312 typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase; |
|
313 typedef MappableGraphExtender<IterableListGraphBase> MappableListGraphBase; |
|
314 typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase; |
|
315 typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase; |
|
316 typedef ErasableGraphExtender< |
311 typedef ErasableGraphExtender< |
317 ClearableGraphExtender< |
312 ClearableGraphExtender< |
318 ExtendableGraphExtender< |
313 ExtendableGraphExtender< |
319 MappableGraphExtender< |
314 MappableGraphExtender< |
320 IterableGraphExtender< |
315 IterableGraphExtender< |
321 AlterableGraphExtender<ListGraphBase> > > > > > ExtendedListGraphBase; |
316 AlterableGraphExtender<ListGraphBase> > > > > > ExtendedListGraphBase; |
322 |
317 |
323 /// \addtogroup graphs |
318 /// \addtogroup graphs |
324 /// @{ |
319 /// @{ |
325 |
320 |
326 ///A list graph class. |
321 ///A list graph class. |
327 |
322 |
328 ///This is a simple and fast erasable graph implementation. |
323 ///This is a simple and fast erasable graph implementation. |
329 /// |
324 /// |
340 /// Changes the target of \c e to \c n |
335 /// Changes the target of \c e to \c n |
341 /// |
336 /// |
342 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
337 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
343 ///referencing the changed edge remain |
338 ///referencing the changed edge remain |
344 ///valid. However <tt>InEdge</tt>'s are invalidated. |
339 ///valid. However <tt>InEdge</tt>'s are invalidated. |
345 void changeTarget(Edge e, Node n) { _changeTarget(e,n); } |
340 void changeTarget(Edge e, Node n) { |
|
341 getNotifier(Edge()).signalChange(e); |
|
342 _changeTarget(e,n); |
|
343 getNotifier(Edge()).commitChange(e); |
|
344 } |
346 /// Changes the source of \c e to \c n |
345 /// Changes the source of \c e to \c n |
347 |
346 |
348 /// Changes the source of \c e to \c n |
347 /// Changes the source of \c e to \c n |
349 /// |
348 /// |
350 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
349 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
351 ///referencing the changed edge remain |
350 ///referencing the changed edge remain |
352 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
351 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
353 void changeSource(Edge e, Node n) { _changeSource(e,n); } |
352 void changeSource(Edge e, Node n) { |
|
353 getNotifier(Edge()).signalChange(e); |
|
354 _changeSource(e,n); |
|
355 getNotifier(Edge()).commitChange(e); |
|
356 } |
354 |
357 |
355 /// Invert the direction of an edge. |
358 /// Invert the direction of an edge. |
356 |
359 |
357 ///\note The <tt>Edge</tt>'s |
360 ///\note The <tt>Edge</tt>'s |
358 ///referencing the changed edge remain |
361 ///referencing the changed edge remain |
359 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated. |
362 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated. |
360 void reverseEdge(Edge e) { |
363 void reverseEdge(Edge e) { |
361 Node t=target(e); |
364 Node t=target(e); |
|
365 getNotifier(Edge()).signalChange(e); |
362 _changeTarget(e,source(e)); |
366 _changeTarget(e,source(e)); |
363 _changeSource(e,t); |
367 _changeSource(e,t); |
|
368 getNotifier(Edge()).commitChange(e); |
364 } |
369 } |
365 |
370 |
366 ///Using this it possible to avoid the superfluous memory allocation. |
371 ///Using this it possible to avoid the superfluous memory allocation. |
367 |
372 |
368 ///Using this it possible to avoid the superfluous memory allocation. |
373 ///Using this it possible to avoid the superfluous memory allocation. |
380 /// |
385 /// |
381 ///\note The <tt>Edge</tt>s |
386 ///\note The <tt>Edge</tt>s |
382 ///referencing a moved edge remain |
387 ///referencing a moved edge remain |
383 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
388 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
384 ///may be invalidated. |
389 ///may be invalidated. |
385 void contract(Node a,Node b,bool r=true) |
390 void contract(Node a, Node b, bool r = true) |
386 { |
391 { |
387 for(OutEdgeIt e(*this,b);e!=INVALID;) { |
392 for(OutEdgeIt e(*this,b);e!=INVALID;) { |
388 OutEdgeIt f=e; |
393 OutEdgeIt f=e; |
389 ++f; |
394 ++f; |
390 if(r && target(e)==a) erase(e); |
395 if(r && target(e)==a) erase(e); |
560 MappableUndirGraphExtender< |
565 MappableUndirGraphExtender< |
561 IterableUndirGraphExtender< |
566 IterableUndirGraphExtender< |
562 AlterableUndirGraphExtender< |
567 AlterableUndirGraphExtender< |
563 UndirGraphExtender<ListGraphBase> > > > > > > ExtendedUndirListGraphBase; |
568 UndirGraphExtender<ListGraphBase> > > > > > > ExtendedUndirListGraphBase; |
564 |
569 |
565 /// \addtogroup graphs |
570 /// \addtogroup graphs |
566 /// @{ |
571 /// @{ |
567 |
572 |
568 ///An undirected list graph class. |
573 ///An undirected list graph class. |
569 |
574 |
570 ///This is a simple and fast erasable undirected graph implementation. |
575 ///This is a simple and fast erasable undirected graph implementation. |
571 /// |
576 /// |
576 /// |
581 /// |
577 ///\todo SnapShot, reverseEdge(), changeTarget(), changeSource(), contract() |
582 ///\todo SnapShot, reverseEdge(), changeTarget(), changeSource(), contract() |
578 ///haven't been implemented yet. |
583 ///haven't been implemented yet. |
579 /// |
584 /// |
580 class UndirListGraph : public ExtendedUndirListGraphBase { |
585 class UndirListGraph : public ExtendedUndirListGraphBase { |
|
586 public: |
|
587 typedef ExtendedUndirListGraphBase Parent; |
|
588 /// \brief Changes the target of \c e to \c n |
|
589 /// |
|
590 /// Changes the target of \c e to \c n |
|
591 /// |
|
592 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
|
593 /// referencing the changed edge remain |
|
594 /// valid. However <tt>InEdge</tt>'s are invalidated. |
|
595 void changeTarget(UndirEdge e, Node n) { |
|
596 getNotifier(UndirEdge()).signalChange(e); |
|
597 getNotifier(Edge()).signalChange(direct(e, true)); |
|
598 getNotifier(Edge()).signalChange(direct(e, false)); |
|
599 _changeTarget(e,n); |
|
600 getNotifier(UndirEdge()).commitChange(e); |
|
601 getNotifier(Edge()).commitChange(direct(e, true)); |
|
602 getNotifier(Edge()).commitChange(direct(e, false)); |
|
603 } |
|
604 /// Changes the source of \c e to \c n |
|
605 /// |
|
606 /// Changes the source of \c e to \c n |
|
607 /// |
|
608 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
|
609 ///referencing the changed edge remain |
|
610 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
|
611 void changeSource(UndirEdge e, Node n) { |
|
612 getNotifier(UndirEdge()).signalChange(e); |
|
613 getNotifier(Edge()).signalChange(direct(e, true)); |
|
614 getNotifier(Edge()).signalChange(direct(e, false)); |
|
615 _changeSource(e,n); |
|
616 getNotifier(UndirEdge()).commitChange(e); |
|
617 getNotifier(Edge()).commitChange(direct(e, true)); |
|
618 getNotifier(Edge()).commitChange(direct(e, false)); |
|
619 } |
|
620 /// \brief Contract two nodes. |
|
621 /// |
|
622 /// This function contracts two nodes. |
|
623 /// |
|
624 /// Node \p b will be removed but instead of deleting |
|
625 /// its neighboring edges, they will be joined to \p a. |
|
626 /// The last parameter \p r controls whether to remove loops. \c true |
|
627 /// means that loops will be removed. |
|
628 /// |
|
629 /// \note The <tt>Edge</tt>s |
|
630 /// referencing a moved edge remain |
|
631 /// valid. |
|
632 void contract(Node a, Node b, bool r = true) { |
|
633 for(IncEdgeIt e(*this, b); e!=INVALID;) { |
|
634 IncEdgeIt f = e; ++f; |
|
635 if (r && runningNode(e) == a) { |
|
636 erase(e); |
|
637 } else if (source(e) == b) { |
|
638 changeSource(e, a); |
|
639 } else { |
|
640 changeTarget(e, a); |
|
641 } |
|
642 e = f; |
|
643 } |
|
644 erase(b); |
|
645 } |
581 }; |
646 }; |
582 |
647 |
583 |
648 |
584 /// @} |
649 /// @} |
585 } //namespace lemon |
650 } //namespace lemon |