equal
deleted
inserted
replaced
82 PredNodeMap *pred_node; |
82 PredNodeMap *pred_node; |
83 bool local_pred_node; |
83 bool local_pred_node; |
84 DistMap *distance; |
84 DistMap *distance; |
85 bool local_distance; |
85 bool local_distance; |
86 |
86 |
|
87 //The source node of the last execution. |
|
88 Node source; |
|
89 |
87 ///Initialize maps |
90 ///Initialize maps |
88 |
91 |
89 ///\todo Error if \c G or are \c NULL. What about \c length? |
92 ///\todo Error if \c G or are \c NULL. What about \c length? |
90 ///\todo Better memory allocation (instead of new). |
93 ///\todo Better memory allocation (instead of new). |
91 void init_maps() |
94 void init_maps() |
210 |
213 |
211 void run(Node s) { |
214 void run(Node s) { |
212 |
215 |
213 init_maps(); |
216 init_maps(); |
214 |
217 |
215 for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) { |
218 source = s; |
|
219 |
|
220 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
216 predecessor->set(u,INVALID); |
221 predecessor->set(u,INVALID); |
217 pred_node->set(u,INVALID); |
222 pred_node->set(u,INVALID); |
218 } |
223 } |
219 |
224 |
220 typename GR::template NodeMap<int> heap_map(*G,-1); |
225 typename GR::template NodeMap<int> heap_map(*G,-1); |
233 ValueType oldvalue=heap[v]; |
238 ValueType oldvalue=heap[v]; |
234 heap.pop(); |
239 heap.pop(); |
235 distance->set(v, oldvalue); |
240 distance->set(v, oldvalue); |
236 |
241 |
237 |
242 |
238 for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) { |
243 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { |
239 Node w=G->bNode(e); |
244 Node w=G->head(e); |
240 |
245 |
241 switch(heap.state(w)) { |
246 switch(heap.state(w)) { |
242 case HeapType::PRE_HEAP: |
247 case HeapType::PRE_HEAP: |
243 heap.push(w,oldvalue+(*length)[e]); |
248 heap.push(w,oldvalue+(*length)[e]); |
244 predecessor->set(w,e); |
249 predecessor->set(w,e); |
308 const PredNodeMap &predNodeMap() const { return *pred_node;} |
313 const PredNodeMap &predNodeMap() const { return *pred_node;} |
309 |
314 |
310 ///Checks if a node is reachable from the root. |
315 ///Checks if a node is reachable from the root. |
311 |
316 |
312 ///Returns \c true if \c v is reachable from the root. |
317 ///Returns \c true if \c v is reachable from the root. |
313 ///\warning the root node is reported to be unreached! |
318 ///\warning the root node is reported to be reached! |
314 ///\todo Is this what we want? |
|
315 ///\pre \ref run() must be called before using this function. |
319 ///\pre \ref run() must be called before using this function. |
316 /// |
320 /// |
317 bool reached(Node v) { return G->valid((*predecessor)[v]); } |
321 bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; } |
318 |
322 |
319 }; |
323 }; |
320 |
324 |
321 |
325 |
322 // ********************************************************************** |
326 // ********************************************************************** |