Changeset 1709:a323456bf7c8 in lemon-0.x for lemon/bfs.h
- Timestamp:
- 10/05/05 18:45:37 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2236
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r1694 r1709 58 58 return new PredMap(G); 59 59 } 60 // ///\brief The type of the map that stores the last but one61 // ///nodes of the shortest paths.62 // ///63 // ///The type of the map that stores the last but one64 // ///nodes of the shortest paths.65 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.66 // ///67 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;68 // ///Instantiates a PredNodeMap.69 70 // ///This function instantiates a \ref PredNodeMap.71 // ///\param G is the graph, to which72 // ///we would like to define the \ref PredNodeMap73 // static PredNodeMap *createPredNodeMap(const GR &G)74 // {75 // return new PredNodeMap();76 // }77 78 60 ///The type of the map that indicates which nodes are processed. 79 61 … … 180 162 ///edges of the shortest paths. 181 163 typedef typename TR::PredMap PredMap; 182 // ///\brief The type of the map that stores the last but one183 // ///nodes of the shortest paths.184 // typedef typename TR::PredNodeMap PredNodeMap;185 164 ///The type of the map indicating which nodes are reached. 186 165 typedef typename TR::ReachedMap ReachedMap; … … 196 175 ///Indicates if \ref _pred is locally allocated (\c true) or not. 197 176 bool local_pred; 198 // ///Pointer to the map of predecessors nodes.199 // PredNodeMap *_predNode;200 // ///Indicates if \ref _predNode is locally allocated (\c true) or not.201 // bool local_predNode;202 177 ///Pointer to the map of distances. 203 178 DistMap *_dist; … … 216 191 int _queue_head,_queue_tail,_queue_next_dist; 217 192 int _curr_dist; 218 // ///The source node of the last execution.219 // Node source;220 193 221 194 ///Creates the maps if necessary. … … 229 202 _pred = Traits::createPredMap(*G); 230 203 } 231 // if(!_predNode) {232 // local_predNode = true;233 // _predNode = Traits::createPredNodeMap(*G);234 // }235 204 if(!_dist) { 236 205 local_dist = true; … … 266 235 /// 267 236 template <class T> 268 class DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > { }; 269 270 // template <class T> 271 // struct DefPredNodeMapTraits : public Traits { 272 // typedef T PredNodeMap; 273 // static PredNodeMap *createPredNodeMap(const Graph &G) 274 // { 275 // throw UninitializedParameter(); 276 // } 277 // }; 278 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type 279 280 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type 281 // /// 282 // template <class T> 283 // class DefPredNodeMap : public Bfs< Graph, 284 // LengthMap, 285 // DefPredNodeMapTraits<T> > { }; 237 struct DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > { 238 typedef Bfs< Graph, DefPredMapTraits<T> > Create; 239 }; 286 240 287 241 template <class T> … … 298 252 /// 299 253 template <class T> 300 class DefDistMap : public Bfs< Graph, 301 DefDistMapTraits<T> > { }; 254 struct DefDistMap : public Bfs< Graph, DefDistMapTraits<T> > { 255 typedef Bfs< Graph, DefDistMapTraits<T> > Create; 256 }; 302 257 303 258 template <class T> … … 314 269 /// 315 270 template <class T> 316 class DefReachedMap : public Bfs< Graph, 317 DefReachedMapTraits<T> > { }; 318 319 struct DefGraphReachedMapTraits : public Traits { 320 typedef typename Graph::template NodeMap<bool> ReachedMap; 321 static ReachedMap *createReachedMap(const Graph &G) 322 { 323 return new ReachedMap(G); 324 } 325 }; 271 struct DefReachedMap : public Bfs< Graph, DefReachedMapTraits<T> > { 272 typedef Bfs< Graph, DefReachedMapTraits<T> > Create; 273 }; 274 326 275 template <class T> 327 276 struct DefProcessedMapTraits : public Traits { … … 337 286 /// 338 287 template <class T> 339 class DefProcessedMap : public Bfs< Graph, 340 DefProcessedMapTraits<T> > { }; 288 struct DefProcessedMap : public Bfs< Graph, DefProcessedMapTraits<T> > { 289 typedef Bfs< Graph, DefProcessedMapTraits<T> > Create; 290 }; 341 291 342 292 struct DefGraphProcessedMapTraits : public Traits { … … 354 304 ///If you don't set it explicitly, it will be automatically allocated. 355 305 template <class T> 356 class DefProcessedMapToBeDefaultMap : 357 public Bfs< Graph, 358 DefGraphProcessedMapTraits> { }; 306 struct DefProcessedMapToBeDefaultMap : 307 public Bfs< Graph, DefGraphProcessedMapTraits> { 308 typedef Bfs< Graph, DefGraphProcessedMapTraits> Create; 309 }; 359 310 360 311 ///@} … … 369 320 G(&_G), 370 321 _pred(NULL), local_pred(false), 371 // _predNode(NULL), local_predNode(false),372 322 _dist(NULL), local_dist(false), 373 323 _reached(NULL), local_reached(false), … … 379 329 { 380 330 if(local_pred) delete _pred; 381 // if(local_predNode) delete _predNode;382 331 if(local_dist) delete _dist; 383 332 if(local_reached) delete _reached; … … 435 384 return *this; 436 385 } 437 438 // ///Sets the map storing the predecessor nodes.439 440 // ///Sets the map storing the predecessor nodes.441 // ///If you don't use this function before calling \ref run(),442 // ///it will allocate one. The destructor deallocates this443 // ///automatically allocated map, of course.444 // ///\return <tt> (*this) </tt>445 // Bfs &predNodeMap(PredNodeMap &m)446 // {447 // if(local_predNode) {448 // delete _predNode;449 // local_predNode=false;450 // }451 // _predNode = &m;452 // return *this;453 // }454 386 455 387 ///Sets the map storing the distances calculated by the algorithm. … … 495 427 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 496 428 _pred->set(u,INVALID); 497 // _predNode->set(u,INVALID);498 429 _reached->set(u,false); 499 430 _processed->set(u,false); … … 538 469 _reached->set(m,true); 539 470 _pred->set(m,e); 540 // _pred_node->set(m,n);541 471 _dist->set(m,_curr_dist); 542 472 } … … 746 676 const PredMap &predMap() const { return *_pred;} 747 677 748 // ///Returns a reference to the map of nodes of shortest paths.749 750 // ///Returns a reference to the NodeMap of the last but one nodes of the751 // ///shortest path tree.752 // ///\pre \ref run() must be called before using this function.753 // const PredNodeMap &predNodeMap() const { return *_predNode;}754 755 678 ///Checks if a node is reachable from the root. 756 679 … … 795 718 return new PredMap(); 796 719 } 797 // ///\brief The type of the map that stores the last but one798 // ///nodes of the shortest paths.799 // ///800 // ///The type of the map that stores the last but one801 // ///nodes of the shortest paths.802 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.803 // ///804 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;805 // ///Instantiates a PredNodeMap.806 807 // ///This function instantiates a \ref PredNodeMap.808 // ///\param G is the graph, to which809 // ///we would like to define the \ref PredNodeMap810 // static PredNodeMap *createPredNodeMap(const GR &G)811 // {812 // return new PredNodeMap();813 // }814 720 815 721 ///The type of the map that indicates which nodes are processed. … … 892 798 ///Pointer to the map of predecessors edges. 893 799 void *_pred; 894 // ///Pointer to the map of predecessors nodes.895 // void *_predNode;896 800 ///Pointer to the map of distances. 897 801 void *_dist; … … 905 809 /// all of the attributes to default values (0, INVALID). 906 810 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 907 // _predNode(0),908 811 _dist(0), _source(INVALID) {} 909 812 … … 917 820 BfsWizardBase(const GR &g, Node s=INVALID) : 918 821 _g((void *)&g), _reached(0), _processed(0), _pred(0), 919 // _predNode(0),920 822 _dist(0), _source(s) {} 921 823 … … 966 868 ///edges of the shortest paths. 967 869 typedef typename TR::PredMap PredMap; 968 // ///\brief The type of the map that stores the last but one969 // ///nodes of the shortest paths.970 // typedef typename TR::PredNodeMap PredNodeMap;971 870 ///The type of the map that stores the dists of the nodes. 972 871 typedef typename TR::DistMap DistMap; … … 1000 899 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed); 1001 900 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred); 1002 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);1003 901 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist); 1004 902 alg.run(Base::_source); … … 1077 975 } 1078 976 1079 1080 // template<class T>1081 // struct DefPredNodeMapBase : public Base {1082 // typedef T PredNodeMap;1083 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };1084 // DefPredNodeMapBase(const TR &b) : TR(b) {}1085 // };1086 1087 // ///\brief \ref named-templ-param "Named parameter"1088 // ///function for setting PredNodeMap type1089 // ///1090 // /// \ref named-templ-param "Named parameter"1091 // ///function for setting PredNodeMap type1092 // ///1093 // template<class T>1094 // BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)1095 // {1096 // Base::_predNode=(void *)&t;1097 // return BfsWizard<DefPredNodeMapBase<T> >(*this);1098 // }1099 977 1100 978 template<class T>
Note: See TracChangeset
for help on using the changeset viewer.