1.1 --- a/src/hugo/dijkstra.h Tue Jul 06 09:52:04 2004 +0000
1.2 +++ b/src/hugo/dijkstra.h Tue Jul 06 10:07:48 2004 +0000
1.3 @@ -84,7 +84,7 @@
1.4
1.5 ///Initialize maps
1.6
1.7 - ///\todo Error if \c G or are \c NULL. What about \c length
1.8 + ///\todo Error if \c G or are \c NULL. What about \c length?
1.9 ///\todo Better memory allocation (instead of new).
1.10 void init_maps()
1.11 {
1.12 @@ -196,7 +196,64 @@
1.13 return *this;
1.14 }
1.15
1.16 - void run(Node s);
1.17 + ///Runs %Dijkstra algorithm from node \c s.
1.18 +
1.19 + ///This method runs the %Dijkstra algorithm from a root node \c s
1.20 + ///in order to
1.21 + ///compute the
1.22 + ///shortest path to each node. The algorithm computes
1.23 + ///- The shortest path tree.
1.24 + ///- The distance of each node from the root.
1.25 +
1.26 + void run(Node s) {
1.27 +
1.28 + init_maps();
1.29 +
1.30 + for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
1.31 + predecessor->set(u,INVALID);
1.32 + pred_node->set(u,INVALID);
1.33 + }
1.34 +
1.35 + typename GR::template NodeMap<int> heap_map(*G,-1);
1.36 +
1.37 + typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
1.38 + std::less<ValueType> >
1.39 + HeapType;
1.40 +
1.41 + HeapType heap(heap_map);
1.42 +
1.43 + heap.push(s,0);
1.44 +
1.45 + while ( !heap.empty() ) {
1.46 +
1.47 + Node v=heap.top();
1.48 + ValueType oldvalue=heap[v];
1.49 + heap.pop();
1.50 + distance->set(v, oldvalue);
1.51 +
1.52 +
1.53 + for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
1.54 + Node w=G->bNode(e);
1.55 +
1.56 + switch(heap.state(w)) {
1.57 + case HeapType::PRE_HEAP:
1.58 + heap.push(w,oldvalue+(*length)[e]);
1.59 + predecessor->set(w,e);
1.60 + pred_node->set(w,v);
1.61 + break;
1.62 + case HeapType::IN_HEAP:
1.63 + if ( oldvalue+(*length)[e] < heap[w] ) {
1.64 + heap.decrease(w, oldvalue+(*length)[e]);
1.65 + predecessor->set(w,e);
1.66 + pred_node->set(w,v);
1.67 + }
1.68 + break;
1.69 + case HeapType::POST_HEAP:
1.70 + break;
1.71 + }
1.72 + }
1.73 + }
1.74 + }
1.75
1.76 ///The distance of a node from the root.
1.77
1.78 @@ -263,66 +320,6 @@
1.79 // IMPLEMENTATIONS
1.80 // **********************************************************************
1.81
1.82 - ///Runs %Dijkstra algorithm from node the root.
1.83 -
1.84 - ///This method runs the %Dijkstra algorithm from a root node \c s
1.85 - ///in order to
1.86 - ///compute the
1.87 - ///shortest path to each node. The algorithm computes
1.88 - ///- The shortest path tree.
1.89 - ///- The distance of each node from the root.
1.90 - template <typename GR, typename LM,
1.91 - template<class,class,class,class> class Heap >
1.92 - void Dijkstra<GR,LM,Heap>::run(Node s) {
1.93 -
1.94 - init_maps();
1.95 -
1.96 - for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
1.97 - predecessor->set(u,INVALID);
1.98 - pred_node->set(u,INVALID);
1.99 - }
1.100 -
1.101 - typename GR::template NodeMap<int> heap_map(*G,-1);
1.102 -
1.103 - typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
1.104 - std::less<ValueType> >
1.105 - HeapType;
1.106 -
1.107 - HeapType heap(heap_map);
1.108 -
1.109 - heap.push(s,0);
1.110 -
1.111 - while ( !heap.empty() ) {
1.112 -
1.113 - Node v=heap.top();
1.114 - ValueType oldvalue=heap[v];
1.115 - heap.pop();
1.116 - distance->set(v, oldvalue);
1.117 -
1.118 -
1.119 - for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
1.120 - Node w=G->bNode(e);
1.121 -
1.122 - switch(heap.state(w)) {
1.123 - case HeapType::PRE_HEAP:
1.124 - heap.push(w,oldvalue+(*length)[e]);
1.125 - predecessor->set(w,e);
1.126 - pred_node->set(w,v);
1.127 - break;
1.128 - case HeapType::IN_HEAP:
1.129 - if ( oldvalue+(*length)[e] < heap[w] ) {
1.130 - heap.decrease(w, oldvalue+(*length)[e]);
1.131 - predecessor->set(w,e);
1.132 - pred_node->set(w,v);
1.133 - }
1.134 - break;
1.135 - case HeapType::POST_HEAP:
1.136 - break;
1.137 - }
1.138 - }
1.139 - }
1.140 - }
1.141 -
1.142 /// @}
1.143
1.144 } //END OF NAMESPACE HUGO