Changeset 1694:6d81e6f7a88d in lemon-0.x
- Timestamp:
- 10/03/05 12:11:29 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2220
- Location:
- lemon
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r1665 r1694 550 550 ///\return The next node to be processed or INVALID if the queue is 551 551 /// empty. 552 Node NextNode()552 Node nextNode() 553 553 { 554 554 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; -
lemon/dfs.h
r1666 r1694 337 337 /// 338 338 template <class T> 339 class DefProcessedMap : public Dfs< Graph, 340 DefProcessedMapTraits<T> > { }; 339 struct DefProcessedMap : public Dfs< Graph, DefProcessedMapTraits<T> > { 340 typedef Dfs< Graph, DefProcessedMapTraits<T> > Dfs; 341 }; 341 342 342 343 struct DefGraphProcessedMapTraits : public Traits { … … 564 565 ///\return The next edge to be processed or INVALID if the stack is 565 566 /// empty. 566 OutEdgeIt NextEdge()567 OutEdgeIt nextEdge() 567 568 { 568 569 return _stack_head>=0?_stack[_stack_head]:INVALID; 569 570 } 570 571 571 572 ///\brief Returns \c false if there are nodes 572 573 ///to be processed in the queue -
lemon/dijkstra.h
r1665 r1694 79 79 return new PredMap(G); 80 80 } 81 // ///\brief The type of the map that stores the last but one82 // ///nodes of the shortest paths.83 // ///84 // ///The type of the map that stores the last but one85 // ///nodes of the shortest paths.86 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.87 // ///88 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;89 // ///Instantiates a PredNodeMap.90 91 // ///This function instantiates a \ref PredNodeMap.92 // ///\param G is the graph, to which93 // ///we would like to define the \ref PredNodeMap94 // static PredNodeMap *createPredNodeMap(const GR &G)95 // {96 // return new PredNodeMap();97 // }98 81 99 82 ///The type of the map that stores whether a nodes is processed. … … 210 193 ///edges of the shortest paths. 211 194 typedef typename TR::PredMap PredMap; 212 // ///\brief The type of the map that stores the last but one213 // ///nodes of the shortest paths.214 // typedef typename TR::PredNodeMap PredNodeMap;215 195 ///The type of the map indicating if a node is processed. 216 196 typedef typename TR::ProcessedMap ProcessedMap; … … 228 208 ///Indicates if \ref _pred is locally allocated (\c true) or not. 229 209 bool local_pred; 230 // ///Pointer to the map of predecessors nodes.231 // PredNodeMap *_predNode;232 // ///Indicates if \ref _predNode is locally allocated (\c true) or not.233 // bool local_predNode;234 210 ///Pointer to the map of distances. 235 211 DistMap *_dist; … … 241 217 bool local_processed; 242 218 243 // ///The source node of the last execution.244 // Node source;245 246 219 ///Creates the maps if necessary. 247 220 … … 254 227 _pred = Traits::createPredMap(*G); 255 228 } 256 // if(!_predNode) {257 // local_predNode = true;258 // _predNode = Traits::createPredNodeMap(*G);259 // }260 229 if(!_dist) { 261 230 local_dist = true; … … 290 259 LengthMap, 291 260 DefPredMapTraits<T> > { }; 292 293 // template <class T>294 // struct DefPredNodeMapTraits : public Traits {295 // typedef T PredNodeMap;296 // static PredNodeMap *createPredNodeMap(const Graph &G)297 // {298 // throw UninitializedParameter();299 // }300 // };301 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type302 303 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type304 // ///305 // template <class T>306 // class DefPredNodeMap : public Dijkstra< Graph,307 // LengthMap,308 // DefPredNodeMapTraits<T> > { };309 261 310 262 template <class T> … … 376 328 G(&_G), length(&_length), 377 329 _pred(NULL), local_pred(false), 378 // _predNode(NULL), local_predNode(false),379 330 _dist(NULL), local_dist(false), 380 331 _processed(NULL), local_processed(false), … … 386 337 { 387 338 if(local_pred) delete _pred; 388 // if(local_predNode) delete _predNode;389 339 if(local_dist) delete _dist; 390 340 if(local_processed) delete _processed; … … 418 368 } 419 369 420 // ///Sets the map storing the predecessor nodes.421 422 // ///Sets the map storing the predecessor nodes.423 // ///If you don't use this function before calling \ref run(),424 // ///it will allocate one. The destuctor deallocates this425 // ///automatically allocated map, of course.426 // ///\return <tt> (*this) </tt>427 // Dijkstra &predNodeMap(PredNodeMap &m)428 // {429 // if(local_predNode) {430 // delete _predNode;431 // local_predNode=false;432 // }433 // _predNode = &m;434 // return *this;435 // }436 437 370 ///Sets the map storing the distances calculated by the algorithm. 438 371 … … 457 390 _processed->set(v,true); 458 391 _dist->set(v, dst); 459 // if((*_pred)[v]!=INVALID)460 // _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?461 392 } 462 393 … … 486 417 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 487 418 _pred->set(u,INVALID); 488 // _predNode->set(u,INVALID);489 419 _processed->set(u,false); 490 420 _heap_map.set(u,Heap::PRE_HEAP); … … 503 433 void addSource(Node s,Value dst=0) 504 434 { 505 // source = s;506 435 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); 507 436 else if(_heap[s]<dst) { … … 531 460 _heap.push(w,oldvalue+(*length)[e]); 532 461 _pred->set(w,e); 533 // _predNode->set(w,v);534 462 break; 535 463 case Heap::IN_HEAP: … … 537 465 _heap.decrease(w, oldvalue+(*length)[e]); 538 466 _pred->set(w,e); 539 // _predNode->set(w,v);540 467 } 541 468 break; … … 553 480 ///\return The next node to be processed or INVALID if the priority heap 554 481 /// is empty. 555 Node NextNode()482 Node nextNode() 556 483 { 557 484 return _heap.empty()?_heap.top():INVALID; … … 743 670 const PredMap &predMap() const { return *_pred;} 744 671 745 // ///Returns a reference to the map of nodes of shortest paths.746 747 // ///Returns a reference to the NodeMap of the last but one nodes of the748 // ///shortest path tree.749 // ///\pre \ref run() must be called before using this function.750 // const PredNodeMap &predNodeMap() const { return *_predNode;}751 752 672 ///Checks if a node is reachable from the root. 753 673 … … 1102 1022 1103 1023 #endif 1104
Note: See TracChangeset
for help on using the changeset viewer.