equal
deleted
inserted
replaced
470 ///Initializes the internal data structures. |
470 ///Initializes the internal data structures. |
471 |
471 |
472 ///Initializes the internal data structures. |
472 ///Initializes the internal data structures. |
473 /// |
473 /// |
474 ///\todo _heap_map's type could also be in the traits class. |
474 ///\todo _heap_map's type could also be in the traits class. |
|
475 ///\todo The heaps should be able to make themselves empty directly. |
475 void init() |
476 void init() |
476 { |
477 { |
477 create_maps(); |
478 create_maps(); |
478 |
479 while(!_heap.empty()) _heap.pop(); |
479 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
480 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
480 _pred->set(u,INVALID); |
481 _pred->set(u,INVALID); |
481 // _predNode->set(u,INVALID); |
482 // _predNode->set(u,INVALID); |
482 _processed->set(u,false); |
483 _processed->set(u,false); |
483 _heap_map.set(u,Heap::PRE_HEAP); |
484 _heap_map.set(u,Heap::PRE_HEAP); |
582 ///- The distance of \c dest from the root(s). |
583 ///- The distance of \c dest from the root(s). |
583 /// |
584 /// |
584 void start(Node dest) |
585 void start(Node dest) |
585 { |
586 { |
586 while ( !_heap.empty() && _heap.top()!=dest ) processNextNode(); |
587 while ( !_heap.empty() && _heap.top()!=dest ) processNextNode(); |
587 if ( _heap.top()==dest ) finalizeNodeData(_heap.top()); |
588 if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio()); |
588 } |
589 } |
589 |
590 |
590 ///Executes the algorithm until a condition is met. |
591 ///Executes the algorithm until a condition is met. |
591 |
592 |
592 ///Executes the algorithm until a condition is met. |
593 ///Executes the algorithm until a condition is met. |
598 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. |
599 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. |
599 template<class NM> |
600 template<class NM> |
600 void start(const NM &nm) |
601 void start(const NM &nm) |
601 { |
602 { |
602 while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode(); |
603 while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode(); |
603 if ( !_heap.empty() ) finalizeNodeData(_heap.top()); |
604 if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio()); |
604 } |
605 } |
605 |
606 |
606 ///Runs %Dijkstra algorithm from node \c s. |
607 ///Runs %Dijkstra algorithm from node \c s. |
607 |
608 |
608 ///This method runs the %Dijkstra algorithm from a root node \c s |
609 ///This method runs the %Dijkstra algorithm from a root node \c s |
852 // _predNode(0), |
853 // _predNode(0), |
853 _dist(0), _source(s) {} |
854 _dist(0), _source(s) {} |
854 |
855 |
855 }; |
856 }; |
856 |
857 |
857 /// A class to make easier the usage of Dijkstra algorithm |
858 /// A class to make the usage of Dijkstra algorithm easier |
858 |
859 |
859 /// This class is created to make it easier to use Dijkstra algorithm. |
860 /// This class is created to make it easier to use Dijkstra algorithm. |
860 /// It uses the functions and features of the plain \ref Dijkstra, |
861 /// It uses the functions and features of the plain \ref Dijkstra, |
861 /// but it is much simpler to use it. |
862 /// but it is much simpler to use it. |
862 /// |
863 /// |