Changeset 247:f1158744a112 in lemon1.0 for lemon/dfs.h
 Timestamp:
 08/04/08 22:00:36 (11 years ago)
 Branch:
 default
 Parents:
 246:7c67988fca07 (diff), 244:c30731a37f91 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dfs.h
r244 r247 25 25 26 26 #include <lemon/list_graph.h> 27 #include <lemon/graph_utils.h>28 27 #include <lemon/bits/path_dump.h> 29 #include <lemon/ bits/invalid.h>28 #include <lemon/core.h> 30 29 #include <lemon/error.h> 31 30 #include <lemon/assert.h> 
lemon/dfs.h
r220 r247 22 22 ///\ingroup search 23 23 ///\file 24 ///\brief D fsalgorithm.24 ///\brief DFS algorithm. 25 25 26 26 #include <lemon/list_graph.h> … … 28 28 #include <lemon/core.h> 29 29 #include <lemon/error.h> 30 #include <lemon/assert.h> 30 31 #include <lemon/maps.h> 31 32 32 #include <lemon/concept_check.h>33 34 33 namespace lemon { 35 36 34 37 35 ///Default traits class of Dfs class. … … 42 40 struct DfsDefaultTraits 43 41 { 44 ///The digraph typethe algorithm runs on.42 ///The type of the digraph the algorithm runs on. 45 43 typedef GR Digraph; 46 ///\brief The type of the map that stores the last 44 45 ///\brief The type of the map that stores the predecessor 47 46 ///arcs of the %DFS paths. 48 47 /// 49 ///The type of the map that stores the last48 ///The type of the map that stores the predecessor 50 49 ///arcs of the %DFS paths. 51 50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 52 /// 53 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; 54 ///Instantiates a PredMap. 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 ///Instantiates a \ref PredMap. 55 53 56 54 ///This function instantiates a \ref PredMap. 57 ///\param G is the digraph, to which we would like to define the PredMap. 55 ///\param g is the digraph, to which we would like to define the 56 ///\ref PredMap. 58 57 ///\todo The digraph alone may be insufficient to initialize 59 static PredMap *createPredMap(const GR &G)60 { 61 return new PredMap( G);58 static PredMap *createPredMap(const Digraph &g) 59 { 60 return new PredMap(g); 62 61 } 63 62 … … 66 65 ///The type of the map that indicates which nodes are processed. 67 66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 68 /// \todo named parameter to set this type, function to read and write.67 ///By default it is a NullMap. 69 68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 70 ///Instantiates a ProcessedMap.69 ///Instantiates a \ref ProcessedMap. 71 70 72 71 ///This function instantiates a \ref ProcessedMap. … … 74 73 ///we would like to define the \ref ProcessedMap 75 74 #ifdef DOXYGEN 76 static ProcessedMap *createProcessedMap(const GR&g)75 static ProcessedMap *createProcessedMap(const Digraph &g) 77 76 #else 78 static ProcessedMap *createProcessedMap(const GR&)77 static ProcessedMap *createProcessedMap(const Digraph &) 79 78 #endif 80 79 { 81 80 return new ProcessedMap(); 82 81 } 82 83 83 ///The type of the map that indicates which nodes are reached. 84 84 85 85 ///The type of the map that indicates which nodes are reached. 86 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 88 ///Instantiates a \ref ReachedMap. 89 90 ///This function instantiates a \ref ReachedMap. 91 ///\param g is the digraph, to which 92 ///we would like to define the \ref ReachedMap. 93 static ReachedMap *createReachedMap(const Digraph &g) 94 { 95 return new ReachedMap(g); 96 } 97 98 ///The type of the map that stores the distances of the nodes. 99 100 ///The type of the map that stores the distances of the nodes. 86 101 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 87 ///\todo named parameter to set this type, function to read and write.88 typedef typename Digraph::template NodeMap<bool> ReachedMap;89 ///Instantiates a ReachedMap.90 91 ///This function instantiates a \ref ReachedMap.92 ///\param G is the digraph, to which93 ///we would like to define the \ref ReachedMap.94 static ReachedMap *createReachedMap(const GR &G)95 {96 return new ReachedMap(G);97 }98 ///The type of the map that stores the dists of the nodes.99 100 ///The type of the map that stores the dists of the nodes.101 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.102 ///103 102 typedef typename Digraph::template NodeMap<int> DistMap; 104 ///Instantiates a DistMap.103 ///Instantiates a \ref DistMap. 105 104 106 105 ///This function instantiates a \ref DistMap. 107 ///\param G is the digraph, to which we would like to define108 /// the \ref DistMap109 static DistMap *createDistMap(const GR &G)110 { 111 return new DistMap( G);106 ///\param g is the digraph, to which we would like to define the 107 ///\ref DistMap. 108 static DistMap *createDistMap(const Digraph &g) 109 { 110 return new DistMap(g); 112 111 } 113 112 }; … … 118 117 ///This class provides an efficient implementation of the %DFS algorithm. 119 118 /// 120 ///\tparam GR The digraph type the algorithm runs on. The default value is 121 ///\ref ListDigraph. The value of GR is not used directly by Dfs, it 122 ///is only passed to \ref DfsDefaultTraits. 119 ///There is also a \ref dfs() "function type interface" for the DFS 120 ///algorithm, which is convenient in the simplier cases and it can be 121 ///used easier. 122 /// 123 ///\tparam GR The type of the digraph the algorithm runs on. 124 ///The default value is \ref ListDigraph. The value of GR is not used 125 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits. 123 126 ///\tparam TR Traits class to set various data types used by the algorithm. 124 127 ///The default traits class is … … 135 138 class Dfs { 136 139 public: 137 /** 138 * \brief \ref Exception for uninitialized parameters. 139 * 140 * This error represents problems in the initialization 141 * of the parameters of the algorithms. 142 */ 140 ///\ref Exception for uninitialized parameters. 141 142 ///This error represents problems in the initialization of the 143 ///parameters of the algorithm. 143 144 class UninitializedParameter : public lemon::UninitializedParameter { 144 145 public: … … 148 149 }; 149 150 151 ///The type of the digraph the algorithm runs on. 152 typedef typename TR::Digraph Digraph; 153 154 ///\brief The type of the map that stores the predecessor arcs of the 155 ///DFS paths. 156 typedef typename TR::PredMap PredMap; 157 ///The type of the map that stores the distances of the nodes. 158 typedef typename TR::DistMap DistMap; 159 ///The type of the map that indicates which nodes are reached. 160 typedef typename TR::ReachedMap ReachedMap; 161 ///The type of the map that indicates which nodes are processed. 162 typedef typename TR::ProcessedMap ProcessedMap; 163 ///The type of the paths. 164 typedef PredMapPath<Digraph, PredMap> Path; 165 166 ///The traits class. 150 167 typedef TR Traits; 151 ///The type of the underlying digraph. 152 typedef typename TR::Digraph Digraph;153 ///\e 168 169 private: 170 154 171 typedef typename Digraph::Node Node; 155 ///\e156 172 typedef typename Digraph::NodeIt NodeIt; 157 ///\e158 173 typedef typename Digraph::Arc Arc; 159 ///\e160 174 typedef typename Digraph::OutArcIt OutArcIt; 161 175 162 ///\brief The type of the map that stores the last 163 ///arcs of the %DFS paths. 164 typedef typename TR::PredMap PredMap; 165 ///The type of the map indicating which nodes are reached. 166 typedef typename TR::ReachedMap ReachedMap; 167 ///The type of the map indicating which nodes are processed. 168 typedef typename TR::ProcessedMap ProcessedMap; 169 ///The type of the map that stores the dists of the nodes. 170 typedef typename TR::DistMap DistMap; 171 private: 172 /// Pointer to the underlying digraph. 176 //Pointer to the underlying digraph. 173 177 const Digraph *G; 174 // /Pointer to the map of predecessorsarcs.178 //Pointer to the map of predecessor arcs. 175 179 PredMap *_pred; 176 // /Indicates if \ref _pred is locally allocated (\ctrue) or not.180 //Indicates if _pred is locally allocated (true) or not. 177 181 bool local_pred; 178 // /Pointer to the map of distances.182 //Pointer to the map of distances. 179 183 DistMap *_dist; 180 // /Indicates if \ref _dist is locally allocated (\ctrue) or not.184 //Indicates if _dist is locally allocated (true) or not. 181 185 bool local_dist; 182 // /Pointer to the map of reached status of the nodes.186 //Pointer to the map of reached status of the nodes. 183 187 ReachedMap *_reached; 184 // /Indicates if \ref _reached is locally allocated (\ctrue) or not.188 //Indicates if _reached is locally allocated (true) or not. 185 189 bool local_reached; 186 // /Pointer to the map of processed status of the nodes.190 //Pointer to the map of processed status of the nodes. 187 191 ProcessedMap *_processed; 188 // /Indicates if \ref _processed is locally allocated (\ctrue) or not.192 //Indicates if _processed is locally allocated (true) or not. 189 193 bool local_processed; 190 194 … … 193 197 194 198 ///Creates the maps if necessary. 195 196 199 ///\todo Better memory allocation (instead of new). 197 200 void create_maps() … … 230 233 struct DefPredMapTraits : public Traits { 231 234 typedef T PredMap; 232 static PredMap *createPredMap(const Digraph & G)235 static PredMap *createPredMap(const Digraph &) 233 236 { 234 237 throw UninitializedParameter(); … … 236 239 }; 237 240 ///\brief \ref namedtemplparam "Named parameter" for setting 238 /// PredMap type239 /// 240 ///\ref namedtemplparam "Named parameter" for setting PredMap type241 /// 241 ///\ref PredMap type. 242 /// 243 ///\ref namedtemplparam "Named parameter" for setting 244 ///\ref PredMap type. 242 245 template <class T> 243 246 struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > { 244 247 typedef Dfs<Digraph, DefPredMapTraits<T> > Create; 245 248 }; 246 247 249 248 250 template <class T> … … 255 257 }; 256 258 ///\brief \ref namedtemplparam "Named parameter" for setting 257 /// DistMap type258 /// 259 ///\ref namedtemplparam "Named parameter" for setting DistMap260 /// type259 ///\ref DistMap type. 260 /// 261 ///\ref namedtemplparam "Named parameter" for setting 262 ///\ref DistMap type. 261 263 template <class T> 262 struct DefDistMap {264 struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > { 263 265 typedef Dfs<Digraph, DefDistMapTraits<T> > Create; 264 266 }; … … 273 275 }; 274 276 ///\brief \ref namedtemplparam "Named parameter" for setting 275 /// ReachedMap type276 /// 277 ///\ref namedtemplparam "Named parameter" for setting ReachedMap type278 /// 277 ///\ref ReachedMap type. 278 /// 279 ///\ref namedtemplparam "Named parameter" for setting 280 ///\ref ReachedMap type. 279 281 template <class T> 280 282 struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > { … … 291 293 }; 292 294 ///\brief \ref namedtemplparam "Named parameter" for setting 293 /// ProcessedMap type294 /// 295 ///\ref namedtemplparam "Named parameter" for setting ProcessedMap type296 /// 295 ///\ref ProcessedMap type. 296 /// 297 ///\ref namedtemplparam "Named parameter" for setting 298 ///\ref ProcessedMap type. 297 299 template <class T> 298 300 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > { … … 302 304 struct DefDigraphProcessedMapTraits : public Traits { 303 305 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 304 static ProcessedMap *createProcessedMap(const Digraph & G)306 static ProcessedMap *createProcessedMap(const Digraph &g) 305 307 { 306 return new ProcessedMap( G);307 } 308 }; 309 ///\brief \ref namedtemplparam "Named parameter" 310 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.311 /// 312 ///\ref namedtemplparam "Named parameter" 313 /// for setting the ProcessedMap type to be Digraph::NodeMap<bool>.314 ///If you don't set it explicit ely, it will be automatically allocated.308 return new ProcessedMap(g); 309 } 310 }; 311 ///\brief \ref namedtemplparam "Named parameter" for setting 312 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 313 /// 314 ///\ref namedtemplparam "Named parameter" for setting 315 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 316 ///If you don't set it explicitly, it will be automatically allocated. 315 317 template <class T> 316 classDefProcessedMapToBeDefaultMap :318 struct DefProcessedMapToBeDefaultMap : 317 319 public Dfs< Digraph, DefDigraphProcessedMapTraits> { 318 320 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create; … … 325 327 ///Constructor. 326 328 327 /// \param _G the digraph the algorithm will run on.328 /// 329 Dfs(const Digraph & _G) :330 G(& _G),329 ///Constructor. 330 ///\param g The digraph the algorithm runs on. 331 Dfs(const Digraph &g) : 332 G(&g), 331 333 _pred(NULL), local_pred(false), 332 334 _dist(NULL), local_dist(false), … … 344 346 } 345 347 346 ///Sets the map storingthe predecessor arcs.347 348 ///Sets the map storingthe predecessor arcs.348 ///Sets the map that stores the predecessor arcs. 349 350 ///Sets the map that stores the predecessor arcs. 349 351 ///If you don't use this function before calling \ref run(), 350 ///it will allocate one. The dest uctor deallocates this352 ///it will allocate one. The destructor deallocates this 351 353 ///automatically allocated map, of course. 352 354 ///\return <tt> (*this) </tt> … … 361 363 } 362 364 363 ///Sets the map storing the distances calculated by the algorithm.364 365 ///Sets the map storing the distances calculated by the algorithm.365 ///Sets the map that indicates which nodes are reached. 366 367 ///Sets the map that indicates which nodes are reached. 366 368 ///If you don't use this function before calling \ref run(), 367 ///it will allocate one. The destuctor deallocates this 369 ///it will allocate one. The destructor deallocates this 370 ///automatically allocated map, of course. 371 ///\return <tt> (*this) </tt> 372 Dfs &reachedMap(ReachedMap &m) 373 { 374 if(local_reached) { 375 delete _reached; 376 local_reached=false; 377 } 378 _reached = &m; 379 return *this; 380 } 381 382 ///Sets the map that indicates which nodes are processed. 383 384 ///Sets the map that indicates which nodes are processed. 385 ///If you don't use this function before calling \ref run(), 386 ///it will allocate one. The destructor deallocates this 387 ///automatically allocated map, of course. 388 ///\return <tt> (*this) </tt> 389 Dfs &processedMap(ProcessedMap &m) 390 { 391 if(local_processed) { 392 delete _processed; 393 local_processed=false; 394 } 395 _processed = &m; 396 return *this; 397 } 398 399 ///Sets the map that stores the distances of the nodes. 400 401 ///Sets the map that stores the distances of the nodes calculated by 402 ///the algorithm. 403 ///If you don't use this function before calling \ref run(), 404 ///it will allocate one. The destructor deallocates this 368 405 ///automatically allocated map, of course. 369 406 ///\return <tt> (*this) </tt> … … 378 415 } 379 416 380 ///Sets the map indicating if a node is reached.381 382 ///Sets the map indicating if a node is reached.383 ///If you don't use this function before calling \ref run(),384 ///it will allocate one. The destuctor deallocates this385 ///automatically allocated map, of course.386 ///\return <tt> (*this) </tt>387 Dfs &reachedMap(ReachedMap &m)388 {389 if(local_reached) {390 delete _reached;391 local_reached=false;392 }393 _reached = &m;394 return *this;395 }396 397 ///Sets the map indicating if a node is processed.398 399 ///Sets the map indicating if a node is processed.400 ///If you don't use this function before calling \ref run(),401 ///it will allocate one. The destuctor deallocates this402 ///automatically allocated map, of course.403 ///\return <tt> (*this) </tt>404 Dfs &processedMap(ProcessedMap &m)405 {406 if(local_processed) {407 delete _processed;408 local_processed=false;409 }410 _processed = &m;411 return *this;412 }413 414 417 public: 418 415 419 ///\name Execution control 416 420 ///The simplest way to execute the algorithm is to use 417 ///one of the member functions called \ c run(...).421 ///one of the member functions called \ref lemon::Dfs::run() "run()". 418 422 ///\n 419 ///If you need more control on the execution, 420 /// first you must call \ref init(), then you can add a source node421 ///with \ref addSource().422 ///Finally \ref start() will perform the actual path423 /// computation.423 ///If you need more control on the execution, first you must call 424 ///\ref lemon::Dfs::init() "init()", then you can add a source node 425 ///with \ref lemon::Dfs::addSource() "addSource()". 426 ///Finally \ref lemon::Dfs::start() "start()" will perform the 427 ///actual path computation. 424 428 425 429 ///@{ … … 436 440 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 437 441 _pred>set(u,INVALID); 438 // _predNode>set(u,INVALID);439 442 _reached>set(u,false); 440 443 _processed>set(u,false); … … 446 449 ///Adds a new source node to the set of nodes to be processed. 447 450 /// 448 ///\warning dists are wrong (or at least strange) 449 ///in case of multiple sources. 451 ///\pre The stack must be empty. (Otherwise the algorithm gives 452 ///false results.) 453 /// 454 ///\warning Distances will be wrong (or at least strange) in case of 455 ///multiple sources. 450 456 void addSource(Node s) 451 457 { 458 LEMON_DEBUG(emptyQueue(), "The stack is not empty."); 452 459 if(!(*_reached)[s]) 453 460 { … … 472 479 ///\return The processed arc. 473 480 /// 474 ///\pre The stack must not be empty !481 ///\pre The stack must not be empty. 475 482 Arc processNextArc() 476 483 { … … 498 505 return e; 499 506 } 507 500 508 ///Next arc to be processed. 501 509 502 510 ///Next arc to be processed. 503 511 /// 504 ///\return The next arc to be processed or INVALID if the stack is505 /// empty.506 OutArcIt nextArc() 512 ///\return The next arc to be processed or \c INVALID if the stack 513 ///is empty. 514 OutArcIt nextArc() const 507 515 { 508 516 return _stack_head>=0?_stack[_stack_head]:INVALID; … … 510 518 511 519 ///\brief Returns \c false if there are nodes 512 ///to be processed in the queue520 ///to be processed. 513 521 /// 514 522 ///Returns \c false if there are nodes 515 ///to be processed in the queue 516 bool emptyQueue() { return _stack_head<0; } 523 ///to be processed in the queue (stack). 524 bool emptyQueue() const { return _stack_head<0; } 525 517 526 ///Returns the number of the nodes to be processed. 518 527 519 ///Returns the number of the nodes to be processed in the queue .520 int queueSize() { return _stack_head+1; }528 ///Returns the number of the nodes to be processed in the queue (stack). 529 int queueSize() const { return _stack_head+1; } 521 530 522 531 ///Executes the algorithm. … … 524 533 ///Executes the algorithm. 525 534 /// 526 ///\pre init() must be called and at least one node should be added 527 ///with addSource() before using this function. 528 /// 529 ///This method runs the %DFS algorithm from the root node(s) 530 ///in order to 531 ///compute the 532 ///%DFS path to each node. The algorithm computes 533 /// The %DFS tree. 534 /// The distance of each node from the root(s) in the %DFS tree. 535 /// 535 ///This method runs the %DFS algorithm from the root node 536 ///in order to compute the DFS path to each node. 537 /// 538 /// The algorithm computes 539 /// the %DFS tree, 540 /// the distance of each node from the root in the %DFS tree. 541 /// 542 ///\pre init() must be called and a root node should be 543 ///added with addSource() before using this function. 544 /// 545 ///\note <tt>d.start()</tt> is just a shortcut of the following code. 546 ///\code 547 /// while ( !d.emptyQueue() ) { 548 /// d.processNextArc(); 549 /// } 550 ///\endcode 536 551 void start() 537 552 { … … 539 554 } 540 555 541 ///Executes the algorithm until \c dest is reached. 542 543 ///Executes the algorithm until \c dest is reached. 544 /// 545 ///\pre init() must be called and at least one node should be added 546 ///with addSource() before using this function. 547 /// 548 ///This method runs the %DFS algorithm from the root node(s) 549 ///in order to 550 ///compute the 551 ///%DFS path to \c dest. The algorithm computes 552 /// The %DFS path to \c dest. 553 /// The distance of \c dest from the root(s) in the %DFS tree. 554 /// 556 ///Executes the algorithm until the given target node is reached. 557 558 ///Executes the algorithm until the given target node is reached. 559 /// 560 ///This method runs the %DFS algorithm from the root node 561 ///in order to compute the DFS path to \c dest. 562 /// 563 ///The algorithm computes 564 /// the %DFS path to \c dest, 565 /// the distance of \c dest from the root in the %DFS tree. 566 /// 567 ///\pre init() must be called and a root node should be 568 ///added with addSource() before using this function. 555 569 void start(Node dest) 556 570 { … … 563 577 ///Executes the algorithm until a condition is met. 564 578 /// 565 /// \pre init() must be called and at least one node should be added566 /// with addSource() before using this function.567 /// 568 ///\param em must be abool (or convertible) arc map. The algorithm569 ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.570 /// 571 ///\return The reached arc \c e with <tt>em[e]</tt> true or579 ///This method runs the %DFS algorithm from the root node 580 ///until an arc \c a with <tt>am[a]</tt> true is found. 581 /// 582 ///\param am A \c bool (or convertible) arc map. The algorithm 583 ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true. 584 /// 585 ///\return The reached arc \c a with <tt>am[a]</tt> true or 572 586 ///\c INVALID if no such arc was found. 573 587 /// 574 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, 588 ///\pre init() must be called and a root node should be 589 ///added with addSource() before using this function. 590 /// 591 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, 575 592 ///not a node map. 576 template<class EM>577 Arc start(const EM &em)578 { 579 while ( !emptyQueue() && ! em[_stack[_stack_head]] )593 template<class ArcBoolMap> 594 Arc start(const ArcBoolMap &am) 595 { 596 while ( !emptyQueue() && !am[_stack[_stack_head]] ) 580 597 processNextArc(); 581 598 return emptyQueue() ? INVALID : _stack[_stack_head]; 582 599 } 583 600 584 ///Runs %DFS algorithm to visit all nodes in the digraph. 585 586 ///This method runs the %DFS algorithm in order to 587 ///compute the 588 ///%DFS path to each node. The algorithm computes 589 /// The %DFS tree. 590 /// The distance of each node from the root in the %DFS tree. 591 /// 592 ///\note d.run() is just a shortcut of the following code. 601 ///Runs the algorithm from the given node. 602 603 ///This method runs the %DFS algorithm from node \c s 604 ///in order to compute the DFS path to each node. 605 /// 606 ///The algorithm computes 607 /// the %DFS tree, 608 /// the distance of each node from the root in the %DFS tree. 609 /// 610 ///\note <tt>d.run(s)</tt> is just a shortcut of the following code. 593 611 ///\code 594 612 /// d.init(); 595 /// for (NodeIt it(digraph); it != INVALID; ++it) { 596 /// if (!d.reached(it)) { 597 /// d.addSource(it); 613 /// d.addSource(s); 614 /// d.start(); 615 ///\endcode 616 void run(Node s) { 617 init(); 618 addSource(s); 619 start(); 620 } 621 622 ///Finds the %DFS path between \c s and \c t. 623 624 ///This method runs the %DFS algorithm from node \c s 625 ///in order to compute the DFS path to \c t. 626 /// 627 ///\return The length of the <tt>s</tt><tt>t</tt> DFS path, 628 ///if \c t is reachable form \c s, \c 0 otherwise. 629 /// 630 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is 631 ///just a shortcut of the following code. 632 ///\code 633 /// d.init(); 634 /// d.addSource(s); 635 /// d.start(t); 636 ///\endcode 637 int run(Node s,Node t) { 638 init(); 639 addSource(s); 640 start(t); 641 return reached(t)?_stack_head+1:0; 642 } 643 644 ///Runs the algorithm to visit all nodes in the digraph. 645 646 ///This method runs the %DFS algorithm in order to compute the 647 ///%DFS path to each node. 648 /// 649 ///The algorithm computes 650 /// the %DFS tree, 651 /// the distance of each node from the root in the %DFS tree. 652 /// 653 ///\note <tt>d.run()</tt> is just a shortcut of the following code. 654 ///\code 655 /// d.init(); 656 /// for (NodeIt n(digraph); n != INVALID; ++n) { 657 /// if (!d.reached(n)) { 658 /// d.addSource(n); 598 659 /// d.start(); 599 660 /// } … … 610 671 } 611 672 612 ///Runs %DFS algorithm from node \c s.613 614 ///This method runs the %DFS algorithm from a root node \c s615 ///in order to616 ///compute the617 ///%DFS path to each node. The algorithm computes618 /// The %DFS tree.619 /// The distance of each node from the root in the %DFS tree.620 ///621 ///\note d.run(s) is just a shortcut of the following code.622 ///\code623 /// d.init();624 /// d.addSource(s);625 /// d.start();626 ///\endcode627 void run(Node s) {628 init();629 addSource(s);630 start();631 }632 633 ///Finds the %DFS path between \c s and \c t.634 635 ///Finds the %DFS path between \c s and \c t.636 ///637 ///\return The length of the %DFS st path if there exists one,638 ///0 otherwise.639 ///\note Apart from the return value, d.run(s,t) is640 ///just a shortcut of the following code.641 ///\code642 /// d.init();643 /// d.addSource(s);644 /// d.start(t);645 ///\endcode646 int run(Node s,Node t) {647 init();648 addSource(s);649 start(t);650 return reached(t)?_stack_head+1:0;651 }652 653 673 ///@} 654 674 … … 656 676 ///The result of the %DFS algorithm can be obtained using these 657 677 ///functions.\n 658 /// Before the use of these functions,659 /// either run() or start() must be called.678 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start() 679 ///"start()" must be called before using them. 660 680 661 681 ///@{ 662 682 663 typedef PredMapPath<Digraph, PredMap> Path; 664 665 ///Gives back the shortest path. 666 667 ///Gives back the shortest path. 668 ///\pre The \c t should be reachable from the source. 669 Path path(Node t) 670 { 671 return Path(*G, *_pred, t); 672 } 673 674 ///The distance of a node from the root(s). 675 676 ///Returns the distance of a node from the root(s). 677 ///\pre \ref run() must be called before using this function. 678 ///\warning If node \c v is unreachable from the root(s) then the return 679 ///value of this funcion is undefined. 683 ///The DFS path to a node. 684 685 ///Returns the DFS path to a node. 686 /// 687 ///\warning \c t should be reachable from the root. 688 /// 689 ///\pre Either \ref run() or \ref start() must be called before 690 ///using this function. 691 Path path(Node t) const { return Path(*G, *_pred, t); } 692 693 ///The distance of a node from the root. 694 695 ///Returns the distance of a node from the root. 696 /// 697 ///\warning If node \c v is not reachable from the root, then 698 ///the return value of this function is undefined. 699 /// 700 ///\pre Either \ref run() or \ref start() must be called before 701 ///using this function. 680 702 int dist(Node v) const { return (*_dist)[v]; } 681 703 682 ///Returns the 'previous arc' of the %DFS tree .683 684 /// For a node \c v it returns the 'previous arc'685 /// of the %DFS path,686 /// i.e. it returns the last arc of a %DFS path from the root(s) to \c687 /// v. It is \ref INVALID688 /// if \c v is unreachable from the root(s) or \c v is a root. The689 /// %DFS tree used here is equal to the %DFS tree used in704 ///Returns the 'previous arc' of the %DFS tree for a node. 705 706 ///This function returns the 'previous arc' of the %DFS tree for the 707 ///node \c v, i.e. it returns the last arc of a %DFS path from the 708 ///root to \c v. It is \c INVALID 709 ///if \c v is not reachable from the root(s) or if \c v is a root. 710 /// 711 ///The %DFS tree used here is equal to the %DFS tree used in 690 712 ///\ref predNode(). 713 /// 691 714 ///\pre Either \ref run() or \ref start() must be called before using 692 715 ///this function. … … 695 718 ///Returns the 'previous node' of the %DFS tree. 696 719 697 /// For a node \c v it returns the 'previous node'698 /// of the %DFS tree,699 /// i.e. it returns the last but one node from a %DFS path from the700 /// root(s) to \c v.701 /// It is INVALID if \c v is unreachable from the root(s) or702 /// if \c v itself a root.703 /// The %DFS tree used here is equal to the %DFS704 /// tree used in \ref predArc().720 ///This function returns the 'previous node' of the %DFS 721 ///tree for the node \c v, i.e. it returns the last but one node 722 ///from a %DFS path from the root to \c v. It is \c INVALID 723 ///if \c v is not reachable from the root(s) or if \c v is a root. 724 /// 725 ///The %DFS tree used here is equal to the %DFS tree used in 726 ///\ref predArc(). 727 /// 705 728 ///\pre Either \ref run() or \ref start() must be called before 706 729 ///using this function. … … 708 731 G>source((*_pred)[v]); } 709 732 710 ///Returns a reference to the NodeMap of distances. 711 712 ///Returns a reference to the NodeMap of distances. 713 ///\pre Either \ref run() or \ref init() must 714 ///be called before using this function. 733 ///\brief Returns a const reference to the node map that stores the 734 ///distances of the nodes. 735 /// 736 ///Returns a const reference to the node map that stores the 737 ///distances of the nodes calculated by the algorithm. 738 /// 739 ///\pre Either \ref run() or \ref init() 740 ///must be called before using this function. 715 741 const DistMap &distMap() const { return *_dist;} 716 742 717 ///Returns a reference to the %DFS arctree map. 718 719 ///Returns a reference to the NodeMap of the arcs of the 720 ///%DFS tree. 743 ///\brief Returns a const reference to the node map that stores the 744 ///predecessor arcs. 745 /// 746 ///Returns a const reference to the node map that stores the predecessor 747 ///arcs, which form the DFS tree. 748 /// 721 749 ///\pre Either \ref run() or \ref init() 722 750 ///must be called before using this function. 723 751 const PredMap &predMap() const { return *_pred;} 724 752 725 ///Checks if a node is reachable from the root .753 ///Checks if a node is reachable from the root(s). 726 754 727 755 ///Returns \c true if \c v is reachable from the root(s). 728 ///\warning The source nodes are inditated as unreachable.729 756 ///\pre Either \ref run() or \ref start() 730 757 ///must be called before using this function. 731 /// 732 bool reached(Node v) { return (*_reached)[v]; } 758 bool reached(Node v) const { return (*_reached)[v]; } 733 759 734 760 ///@} 735 761 }; 736 762 737 ///Default traits class of Dfsfunction.738 739 ///Default traits class of Dfsfunction.763 ///Default traits class of dfs() function. 764 765 ///Default traits class of dfs() function. 740 766 ///\tparam GR Digraph type. 741 767 template<class GR> 742 768 struct DfsWizardDefaultTraits 743 769 { 744 ///The digraph typethe algorithm runs on.770 ///The type of the digraph the algorithm runs on. 745 771 typedef GR Digraph; 746 ///\brief The type of the map that stores the last 772 773 ///\brief The type of the map that stores the predecessor 747 774 ///arcs of the %DFS paths. 748 775 /// 749 ///The type of the map that stores the last776 ///The type of the map that stores the predecessor 750 777 ///arcs of the %DFS paths. 751 778 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 752 779 /// 753 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;754 ///Instantiates a PredMap.780 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap; 781 ///Instantiates a \ref PredMap. 755 782 756 783 ///This function instantiates a \ref PredMap. 757 ///\param g is the digraph, to which we would like to define the PredMap. 784 ///\param g is the digraph, to which we would like to define the 785 ///\ref PredMap. 758 786 ///\todo The digraph alone may be insufficient to initialize 759 787 #ifdef DOXYGEN 760 static PredMap *createPredMap(const GR&g)788 static PredMap *createPredMap(const Digraph &g) 761 789 #else 762 static PredMap *createPredMap(const GR&)790 static PredMap *createPredMap(const Digraph &) 763 791 #endif 764 792 { … … 770 798 ///The type of the map that indicates which nodes are processed. 771 799 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 772 ///\todo named parameter to set this type, function to read and write.773 800 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 774 ///Instantiates a ProcessedMap.801 ///Instantiates a \ref ProcessedMap. 775 802 776 803 ///This function instantiates a \ref ProcessedMap. 777 804 ///\param g is the digraph, to which 778 ///we would like to define the \ref ProcessedMap 805 ///we would like to define the \ref ProcessedMap. 779 806 #ifdef DOXYGEN 780 static ProcessedMap *createProcessedMap(const GR&g)807 static ProcessedMap *createProcessedMap(const Digraph &g) 781 808 #else 782 static ProcessedMap *createProcessedMap(const GR&)809 static ProcessedMap *createProcessedMap(const Digraph &) 783 810 #endif 784 811 { 785 812 return new ProcessedMap(); 786 813 } 814 787 815 ///The type of the map that indicates which nodes are reached. 788 816 789 817 ///The type of the map that indicates which nodes are reached. 818 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 819 typedef typename Digraph::template NodeMap<bool> ReachedMap; 820 ///Instantiates a \ref ReachedMap. 821 822 ///This function instantiates a \ref ReachedMap. 823 ///\param g is the digraph, to which 824 ///we would like to define the \ref ReachedMap. 825 static ReachedMap *createReachedMap(const Digraph &g) 826 { 827 return new ReachedMap(g); 828 } 829 830 ///The type of the map that stores the distances of the nodes. 831 832 ///The type of the map that stores the distances of the nodes. 790 833 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 791 ///\todo named parameter to set this type, function to read and write.792 typedef typename Digraph::template NodeMap<bool> ReachedMap;793 ///Instantiates a ReachedMap.794 795 ///This function instantiates a \ref ReachedMap.796 ///\param G is the digraph, to which797 ///we would like to define the \ref ReachedMap.798 static ReachedMap *createReachedMap(const GR &G)799 {800 return new ReachedMap(G);801 }802 ///The type of the map that stores the dists of the nodes.803 804 ///The type of the map that stores the dists of the nodes.805 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.806 834 /// 807 835 typedef NullMap<typename Digraph::Node,int> DistMap; 808 ///Instantiates a DistMap.836 ///Instantiates a \ref DistMap. 809 837 810 838 ///This function instantiates a \ref DistMap. … … 812 840 ///the \ref DistMap 813 841 #ifdef DOXYGEN 814 static DistMap *createDistMap(const GR&g)842 static DistMap *createDistMap(const Digraph &g) 815 843 #else 816 static DistMap *createDistMap(const GR&)844 static DistMap *createDistMap(const Digraph &) 817 845 #endif 818 846 { … … 821 849 }; 822 850 823 /// Default traits used by \ref DfsWizard851 /// Default traits class used by \ref DfsWizard 824 852 825 853 /// To make it easier to use Dfs algorithm 826 /// we have created a wizard class.854 /// we have created a wizard class. 827 855 /// This \ref DfsWizard class needs default traits, 828 /// as well as the \ref Dfs class.856 /// as well as the \ref Dfs class. 829 857 /// The \ref DfsWizardBase is a class to be the default traits of the 830 858 /// \ref DfsWizard class. … … 835 863 typedef DfsWizardDefaultTraits<GR> Base; 836 864 protected: 837 // / Type of the nodes in the digraph.865 //The type of the nodes in the digraph. 838 866 typedef typename Base::Digraph::Node Node; 839 867 840 // / Pointer to the underlying digraph.868 //Pointer to the digraph the algorithm runs on. 841 869 void *_g; 842 // /Pointer to the map of reached nodes.870 //Pointer to the map of reached nodes. 843 871 void *_reached; 844 // /Pointer to the map of processed nodes.872 //Pointer to the map of processed nodes. 845 873 void *_processed; 846 // /Pointer to the map of predecessors arcs.874 //Pointer to the map of predecessors arcs. 847 875 void *_pred; 848 // /Pointer to the map of distances.876 //Pointer to the map of distances. 849 877 void *_dist; 850 // /Pointer to the source node.878 //Pointer to the source node. 851 879 Node _source; 852 880 … … 857 885 /// all of the attributes to default values (0, INVALID). 858 886 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 859 887 _dist(0), _source(INVALID) {} 860 888 861 889 /// Constructor. … … 864 892 /// listed in the parameters list. 865 893 /// Others are initiated to 0. 866 /// \param g is the initial value of \ref _g867 /// \param s is the initial value of \ref _source894 /// \param g The digraph the algorithm runs on. 895 /// \param s The source node. 868 896 DfsWizardBase(const GR &g, Node s=INVALID) : 869 897 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), … … 872 900 }; 873 901 874 /// A class to make the usage of the Dfs algorithm easier 875 876 /// This class is created to make it easier to use the Dfs algorithm. 877 /// It uses the functions and features of the plain \ref Dfs, 878 /// but it is much simpler to use it. 902 /// Auxiliary class for the function type interface of DFS algorithm. 903 904 /// This auxiliary class is created to implement the function type 905 /// interface of \ref Dfs algorithm. It uses the functions and features 906 /// of the plain \ref Dfs, but it is much simpler to use it. 907 /// It should only be used through the \ref dfs() function, which makes 908 /// it easier to use the algorithm. 879 909 /// 880 910 /// Simplicity means that the way to change the types defined … … 885 915 /// the original class by using the :: 886 916 /// operator. In the case of \ref DfsWizard only 887 /// a function have to be called and it will917 /// a function have to be called, and it will 888 918 /// return the needed class. 889 919 /// 890 /// It does not have own \ref run method. When its \ref run method is called891 /// i t initiates a plain \ref Dfs object, and calls the \ref Dfs::run892 /// method of it.920 /// It does not have own \ref run() method. When its \ref run() method 921 /// is called, it initiates a plain \ref Dfs object, and calls the 922 /// \ref Dfs::run() method of it. 893 923 template<class TR> 894 924 class DfsWizard : public TR … … 896 926 typedef TR Base; 897 927 898 ///The type of the underlying digraph.928 ///The type of the digraph the algorithm runs on. 899 929 typedef typename TR::Digraph Digraph; 900 //\e 930 901 931 typedef typename Digraph::Node Node; 902 //\e903 932 typedef typename Digraph::NodeIt NodeIt; 904 //\e905 933 typedef typename Digraph::Arc Arc; 906 //\e907 934 typedef typename Digraph::OutArcIt OutArcIt; 908 935 909 ///\brief The type of the map that stores 910 ///the reached nodes 936 ///\brief The type of the map that stores the predecessor 937 ///arcs of the shortest paths. 938 typedef typename TR::PredMap PredMap; 939 ///\brief The type of the map that stores the distances of the nodes. 940 typedef typename TR::DistMap DistMap; 941 ///\brief The type of the map that indicates which nodes are reached. 911 942 typedef typename TR::ReachedMap ReachedMap; 912 ///\brief The type of the map that stores 913 ///the processed nodes 943 ///\brief The type of the map that indicates which nodes are processed. 914 944 typedef typename TR::ProcessedMap ProcessedMap; 915 ///\brief The type of the map that stores the last916 ///arcs of the %DFS paths.917 typedef typename TR::PredMap PredMap;918 ///The type of the map that stores the distances of the nodes.919 typedef typename TR::DistMap DistMap;920 945 921 946 public: 947 922 948 /// Constructor. 923 949 DfsWizard() : TR() {} … … 935 961 ~DfsWizard() {} 936 962 937 ///Runs D fs algorithm from a givennode.938 939 ///Runs D fs algorithm from a givennode.940 ///The node can be given by the \ref sourcefunction.963 ///Runs DFS algorithm from a source node. 964 965 ///Runs DFS algorithm from a source node. 966 ///The node can be given with the \ref source() function. 941 967 void run() 942 968 { … … 954 980 } 955 981 956 ///Runs D fsalgorithm from the given node.957 958 ///Runs D fsalgorithm from the given node.982 ///Runs DFS algorithm from the given node. 983 984 ///Runs DFS algorithm from the given node. 959 985 ///\param s is the given source. 960 986 void run(Node s) … … 962 988 Base::_source=s; 963 989 run(); 990 } 991 992 /// Sets the source node, from which the Dfs algorithm runs. 993 994 /// Sets the source node, from which the Dfs algorithm runs. 995 /// \param s is the source node. 996 DfsWizard<TR> &source(Node s) 997 { 998 Base::_source=s; 999 return *this; 964 1000 } 965 1001 … … 970 1006 DefPredMapBase(const TR &b) : TR(b) {} 971 1007 }; 972 973 1008 ///\brief \ref namedtemplparam "Named parameter" 974 ///function for setting PredMap type 975 /// 976 /// \ref namedtemplparam "Named parameter" 977 ///function for setting PredMap type 978 /// 1009 ///for setting \ref PredMap object. 1010 /// 1011 ///\ref namedtemplparam "Named parameter" 1012 ///for setting \ref PredMap object. 979 1013 template<class T> 980 1014 DfsWizard<DefPredMapBase<T> > predMap(const T &t) … … 983 1017 return DfsWizard<DefPredMapBase<T> >(*this); 984 1018 } 985 986 1019 987 1020 template<class T> … … 991 1024 DefReachedMapBase(const TR &b) : TR(b) {} 992 1025 }; 993 994 1026 ///\brief \ref namedtemplparam "Named parameter" 995 ///f unction for setting ReachedMap1027 ///for setting \ref ReachedMap object. 996 1028 /// 997 1029 /// \ref namedtemplparam "Named parameter" 998 ///function for setting ReachedMap 999 /// 1030 ///for setting \ref ReachedMap object. 1000 1031 template<class T> 1001 1032 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) … … 1004 1035 return DfsWizard<DefReachedMapBase<T> >(*this); 1005 1036 } 1006 1007 1037 1008 1038 template<class T> … … 1012 1042 DefProcessedMapBase(const TR &b) : TR(b) {} 1013 1043 }; 1014 1015 1044 ///\brief \ref namedtemplparam "Named parameter" 1016 ///f unction for setting ProcessedMap1045 ///for setting \ref ProcessedMap object. 1017 1046 /// 1018 1047 /// \ref namedtemplparam "Named parameter" 1019 ///function for setting ProcessedMap 1020 /// 1048 ///for setting \ref ProcessedMap object. 1021 1049 template<class T> 1022 1050 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) … … 1032 1060 DefDistMapBase(const TR &b) : TR(b) {} 1033 1061 }; 1034 1035 1062 ///\brief \ref namedtemplparam "Named parameter" 1036 ///function for setting DistMap type 1037 /// 1038 /// \ref namedtemplparam "Named parameter" 1039 ///function for setting DistMap type 1040 /// 1063 ///for setting \ref DistMap object. 1064 /// 1065 ///\ref namedtemplparam "Named parameter" 1066 ///for setting \ref DistMap object. 1041 1067 template<class T> 1042 1068 DfsWizard<DefDistMapBase<T> > distMap(const T &t) … … 1044 1070 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1045 1071 return DfsWizard<DefDistMapBase<T> >(*this); 1046 }1047 1048 /// Sets the source node, from which the Dfs algorithm runs.1049 1050 /// Sets the source node, from which the Dfs algorithm runs.1051 /// \param s is the source node.1052 DfsWizard<TR> &source(Node s)1053 {1054 Base::_source=s;1055 return *this;1056 1072 } 1057 1073 … … 1083 1099 1084 1100 #ifdef DOXYGEN 1085 /// \brief Visitor class for dfs.1101 /// \brief Visitor class for DFS. 1086 1102 /// 1087 /// It gives a simple interface for a functional interface for dfs1088 /// traversal. The traversal on a linear data structure.1103 /// This class defines the interface of the DfsVisit events, and 1104 /// it could be the base of a real visitor class. 1089 1105 template <typename _Digraph> 1090 1106 struct DfsVisitor { … … 1092 1108 typedef typename Digraph::Arc Arc; 1093 1109 typedef typename Digraph::Node Node; 1094 /// \brief Called when the arc reach a node. 1095 /// 1096 /// It is called when the dfs find an arc which target is not 1097 /// reached yet. 1110 /// \brief Called for the source node of the DFS. 1111 /// 1112 /// This function is called for the source node of the DFS. 1113 void start(const Node& node) {} 1114 /// \brief Called when the source node is leaved. 1115 /// 1116 /// This function is called when the source node is leaved. 1117 void stop(const Node& node) {} 1118 /// \brief Called when a node is reached first time. 1119 /// 1120 /// This function is called when a node is reached first time. 1121 void reach(const Node& node) {} 1122 /// \brief Called when an arc reaches a new node. 1123 /// 1124 /// This function is called when the DFS finds an arc whose target node 1125 /// is not reached yet. 1098 1126 void discover(const Arc& arc) {} 1099 /// \brief Called when the node reached first time. 1100 /// 1101 /// It is Called when the node reached first time. 1102 void reach(const Node& node) {} 1103 /// \brief Called when we step back on an arc. 1104 /// 1105 /// It is called when the dfs should step back on the arc. 1106 void backtrack(const Arc& arc) {} 1107 /// \brief Called when we step back from the node. 1108 /// 1109 /// It is called when we step back from the node. 1110 void leave(const Node& node) {} 1111 /// \brief Called when the arc examined but target of the arc 1127 /// \brief Called when an arc is examined but its target node is 1112 1128 /// already discovered. 1113 1129 /// 1114 /// It called when the arc examined but the target of the arc1130 /// This function is called when an arc is examined but its target node is 1115 1131 /// already discovered. 1116 1132 void examine(const Arc& arc) {} 1117 /// \brief Called for the source node of the dfs. 1118 /// 1119 /// It is called for the source node of the dfs. 1120 void start(const Node& node) {} 1121 /// \brief Called when we leave the source node of the dfs. 1122 /// 1123 /// It is called when we leave the source node of the dfs. 1124 void stop(const Node& node) {} 1125 1133 /// \brief Called when the DFS steps back from a node. 1134 /// 1135 /// This function is called when the DFS steps back from a node. 1136 void leave(const Node& node) {} 1137 /// \brief Called when the DFS steps back on an arc. 1138 /// 1139 /// This function is called when the DFS steps back on an arc. 1140 void backtrack(const Arc& arc) {} 1126 1141 }; 1127 1142 #else … … 1131 1146 typedef typename Digraph::Arc Arc; 1132 1147 typedef typename Digraph::Node Node; 1133 void discover(const Arc&) {}1134 void reach(const Node&) {}1135 void backtrack(const Arc&) {}1136 void leave(const Node&) {}1137 void examine(const Arc&) {}1138 1148 void start(const Node&) {} 1139 1149 void stop(const Node&) {} 1150 void reach(const Node&) {} 1151 void discover(const Arc&) {} 1152 void examine(const Arc&) {} 1153 void leave(const Node&) {} 1154 void backtrack(const Arc&) {} 1140 1155 1141 1156 template <typename _Visitor> … … 1144 1159 Arc arc; 1145 1160 Node node; 1146 visitor.discover(arc);1147 visitor.reach(node);1148 visitor.backtrack(arc);1149 visitor.leave(node);1150 visitor.examine(arc);1151 1161 visitor.start(node); 1152 1162 visitor.stop(arc); 1163 visitor.reach(node); 1164 visitor.discover(arc); 1165 visitor.examine(arc); 1166 visitor.leave(node); 1167 visitor.backtrack(arc); 1153 1168 } 1154 1169 _Visitor& visitor; … … 1160 1175 /// 1161 1176 /// Default traits class of DfsVisit class. 1162 /// \tparam _Digraph Digraph type.1177 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1163 1178 template<class _Digraph> 1164 1179 struct DfsVisitDefaultTraits { 1165 1180 1166 /// \brief The digraph typethe algorithm runs on.1181 /// \brief The type of the digraph the algorithm runs on. 1167 1182 typedef _Digraph Digraph; 1168 1183 … … 1170 1185 /// 1171 1186 /// The type of the map that indicates which nodes are reached. 1172 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. 1173 /// \todo named parameter to set this type, function to read and write. 1187 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1174 1188 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1175 1189 1176 /// \brief Instantiates a ReachedMap.1190 /// \brief Instantiates a \ref ReachedMap. 1177 1191 /// 1178 1192 /// This function instantiates a \ref ReachedMap. … … 1185 1199 }; 1186 1200 1187 /// %DFS Visit algorithm class.1188 1189 1201 /// \ingroup search 1202 /// 1203 /// \brief %DFS algorithm class with visitor interface. 1204 /// 1190 1205 /// This class provides an efficient implementation of the %DFS algorithm 1191 1206 /// with visitor interface. … … 1193 1208 /// The %DfsVisit class provides an alternative interface to the Dfs 1194 1209 /// class. It works with callback mechanism, the DfsVisit object calls 1195 /// on every dfs event the \c Visitor class member functions.1210 /// the member functions of the \c Visitor class on every DFS event. 1196 1211 /// 1197 /// \tparam _Digraph The digraph typethe algorithm runs on.1212 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1198 1213 /// The default value is 1199 /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it1200 /// is only passed to \ref DfsDefaultTraits.1201 /// \tparam _Visitor The Visitor object for the algorithm. The1202 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitorwhich1203 /// does not observe the D fs events. If you want to observe the dfs1204 /// events you should implement your own Visitor class.1214 /// \ref ListDigraph. The value of _Digraph is not used directly by 1215 /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits. 1216 /// \tparam _Visitor The Visitor type that is used by the algorithm. 1217 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which 1218 /// does not observe the DFS events. If you want to observe the DFS 1219 /// events, you should implement your own visitor class. 1205 1220 /// \tparam _Traits Traits class to set various data types used by the 1206 1221 /// algorithm. The default traits class is 1207 1222 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". 1208 1223 /// See \ref DfsVisitDefaultTraits for the documentation of 1209 /// a Dfs visit traits class. 1210 /// 1211 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso 1224 /// a DFS visit traits class. 1212 1225 #ifdef DOXYGEN 1213 1226 template <typename _Digraph, typename _Visitor, typename _Traits> … … 1223 1236 /// 1224 1237 /// This error represents problems in the initialization 1225 /// of the parameters of the algorithm s.1238 /// of the parameters of the algorithm. 1226 1239 class UninitializedParameter : public lemon::UninitializedParameter { 1227 1240 public: … … 1232 1245 }; 1233 1246 1247 ///The traits class. 1234 1248 typedef _Traits Traits; 1235 1249 1250 ///The type of the digraph the algorithm runs on. 1236 1251 typedef typename Traits::Digraph Digraph; 1237 1252 1253 ///The visitor type used by the algorithm. 1238 1254 typedef _Visitor Visitor; 1239 1255 1240 ///The type of the map indicatingwhich nodes are reached.1256 ///The type of the map that indicates which nodes are reached. 1241 1257 typedef typename Traits::ReachedMap ReachedMap; 1242 1258 … … 1248 1264 typedef typename Digraph::OutArcIt OutArcIt; 1249 1265 1250 // /Pointer to the underlying digraph.1266 //Pointer to the underlying digraph. 1251 1267 const Digraph *_digraph; 1252 // /Pointer to the visitor object.1268 //Pointer to the visitor object. 1253 1269 Visitor *_visitor; 1254 // /Pointer to the map of reached status of the nodes.1270 //Pointer to the map of reached status of the nodes. 1255 1271 ReachedMap *_reached; 1256 // /Indicates if \ref _reached is locally allocated (\ctrue) or not.1272 //Indicates if _reached is locally allocated (true) or not. 1257 1273 bool local_reached; 1258 1274 … … 1260 1276 int _stack_head; 1261 1277 1262 /// \brief Creates the maps if necessary. 1263 /// 1264 /// Creates the maps if necessary. 1278 ///Creates the maps if necessary. 1279 ///\todo Better memory allocation (instead of new). 1265 1280 void create_maps() { 1266 1281 if(!_reached) { … … 1289 1304 }; 1290 1305 /// \brief \ref namedtemplparam "Named parameter" for setting 1291 /// ReachedMap type 1292 /// 1293 /// \ref namedtemplparam "Named parameter" for setting ReachedMap type 1306 /// ReachedMap type. 1307 /// 1308 /// \ref namedtemplparam "Named parameter" for setting ReachedMap type. 1294 1309 template <class T> 1295 1310 struct DefReachedMap : public DfsVisit< Digraph, Visitor, … … 1305 1320 /// Constructor. 1306 1321 /// 1307 /// \param digraph the digraph the algorithm will run on. 1308 /// \param visitor The visitor of the algorithm. 1309 /// 1322 /// \param digraph The digraph the algorithm runs on. 1323 /// \param visitor The visitor object of the algorithm. 1310 1324 DfsVisit(const Digraph& digraph, Visitor& visitor) 1311 1325 : _digraph(&digraph), _visitor(&visitor), … … 1313 1327 1314 1328 /// \brief Destructor. 1315 ///1316 /// Destructor.1317 1329 ~DfsVisit() { 1318 1330 if(local_reached) delete _reached; 1319 1331 } 1320 1332 1321 /// \brief Sets the map indicating if a node isreached.1322 /// 1323 /// Sets the map indicating if a node isreached.1333 /// \brief Sets the map that indicates which nodes are reached. 1334 /// 1335 /// Sets the map that indicates which nodes are reached. 1324 1336 /// If you don't use this function before calling \ref run(), 1325 /// it will allocate one. The dest uctor deallocates this1337 /// it will allocate one. The destructor deallocates this 1326 1338 /// automatically allocated map, of course. 1327 1339 /// \return <tt> (*this) </tt> … … 1336 1348 1337 1349 public: 1350 1338 1351 /// \name Execution control 1339 1352 /// The simplest way to execute the algorithm is to use 1340 /// one of the member functions called \c run(...). 1353 /// one of the member functions called \ref lemon::DfsVisit::run() 1354 /// "run()". 1341 1355 /// \n 1342 /// If you need more control on the execution, 1343 /// first you must call \ref init(), then you can adda source node1344 /// with \ref addSource().1345 /// Finally \ref start() will perform the actual path1346 /// computation.1356 /// If you need more control on the execution, first you must call 1357 /// \ref lemon::DfsVisit::init() "init()", then you can add several 1358 /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()". 1359 /// Finally \ref lemon::DfsVisit::start() "start()" will perform the 1360 /// actual path computation. 1347 1361 1348 1362 /// @{ 1363 1349 1364 /// \brief Initializes the internal data structures. 1350 1365 /// 1351 1366 /// Initializes the internal data structures. 1352 ///1353 1367 void init() { 1354 1368 create_maps(); … … 1360 1374 } 1361 1375 1362 /// \brief Adds a new source node. 1363 /// 1364 /// Adds a new source node to the set of nodes to be processed. 1365 void addSource(Node s) { 1376 ///Adds a new source node. 1377 1378 ///Adds a new source node to the set of nodes to be processed. 1379 /// 1380 ///\pre The stack must be empty. (Otherwise the algorithm gives 1381 ///false results.) 1382 /// 1383 ///\warning Distances will be wrong (or at least strange) in case of 1384 ///multiple sources. 1385 void addSource(Node s) 1386 { 1387 LEMON_DEBUG(emptyQueue(), "The stack is not empty."); 1366 1388 if(!(*_reached)[s]) { 1367 1389 _reached>set(s,true); … … 1384 1406 /// \return The processed arc. 1385 1407 /// 1386 /// \pre The stack must not be empty !1408 /// \pre The stack must not be empty. 1387 1409 Arc processNextArc() { 1388 1410 Arc e = _stack[_stack_head]; … … 1418 1440 /// \return The next arc to be processed or INVALID if the stack is 1419 1441 /// empty. 1420 Arc nextArc() {1442 Arc nextArc() const { 1421 1443 return _stack_head >= 0 ? _stack[_stack_head] : INVALID; 1422 1444 } 1423 1445 1424 1446 /// \brief Returns \c false if there are nodes 1425 /// to be processed in the queue1447 /// to be processed. 1426 1448 /// 1427 1449 /// Returns \c false if there are nodes 1428 /// to be processed in the queue 1429 bool emptyQueue() { return _stack_head < 0; }1450 /// to be processed in the queue (stack). 1451 bool emptyQueue() const { return _stack_head < 0; } 1430 1452 1431 1453 /// \brief Returns the number of the nodes to be processed. 1432 1454 /// 1433 /// Returns the number of the nodes to be processed in the queue .1434 int queueSize() { return _stack_head + 1; }1455 /// Returns the number of the nodes to be processed in the queue (stack). 1456 int queueSize() const { return _stack_head + 1; } 1435 1457 1436 1458 /// \brief Executes the algorithm. … … 1438 1460 /// Executes the algorithm. 1439 1461 /// 1440 /// \pre init() must be called and at least one node should be added 1441 /// with addSource() before using this function. 1462 /// This method runs the %DFS algorithm from the root node 1463 /// in order to compute the %DFS path to each node. 1464 /// 1465 /// The algorithm computes 1466 ///  the %DFS tree, 1467 ///  the distance of each node from the root in the %DFS tree. 1468 /// 1469 /// \pre init() must be called and a root node should be 1470 /// added with addSource() before using this function. 1471 /// 1472 /// \note <tt>d.start()</tt> is just a shortcut of the following code. 1473 /// \code 1474 /// while ( !d.emptyQueue() ) { 1475 /// d.processNextArc(); 1476 /// } 1477 /// \endcode 1442 1478 void start() { 1443 1479 while ( !emptyQueue() ) processNextArc(); 1444 1480 } 1445 1481 1446 /// \brief Executes the algorithm until \c dest is reached. 1447 /// 1448 /// Executes the algorithm until \c dest is reached. 1449 /// 1450 /// \pre init() must be called and at least one node should be added 1482 /// \brief Executes the algorithm until the given target node is reached. 1483 /// 1484 /// Executes the algorithm until the given target node is reached. 1485 /// 1486 /// This method runs the %DFS algorithm from the root node 1487 /// in order to compute the DFS path to \c dest. 1488 /// 1489 /// The algorithm computes 1490 ///  the %DFS path to \c dest, 1491 ///  the distance of \c dest from the root in the %DFS tree. 1492 /// 1493 /// \pre init() must be called and a root node should be added 1451 1494 /// with addSource() before using this function. 1452 1495 void start(Node dest) { … … 1459 1502 /// Executes the algorithm until a condition is met. 1460 1503 /// 1461 /// \pre init() must be called and at least one node should be added 1504 /// This method runs the %DFS algorithm from the root node 1505 /// until an arc \c a with <tt>am[a]</tt> true is found. 1506 /// 1507 /// \param am A \c bool (or convertible) arc map. The algorithm 1508 /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true. 1509 /// 1510 /// \return The reached arc \c a with <tt>am[a]</tt> true or 1511 /// \c INVALID if no such arc was found. 1512 /// 1513 /// \pre init() must be called and a root node should be added 1462 1514 /// with addSource() before using this function. 1463 1515 /// 1464 /// \param em must be a bool (or convertible) arc map. The algorithm 1465 /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true. 1466 /// 1467 ///\return The reached arc \c e with <tt>em[e]</tt> true or 1468 ///\c INVALID if no such arc was found. 1469 /// 1470 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, 1516 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, 1471 1517 /// not a node map. 1472 template <typename EM>1473 Arc start(const EM &em) {1474 while ( !emptyQueue() && ! em[_stack[_stack_head]] )1518 template <typename AM> 1519 Arc start(const AM &am) { 1520 while ( !emptyQueue() && !am[_stack[_stack_head]] ) 1475 1521 processNextArc(); 1476 1522 return emptyQueue() ? INVALID : _stack[_stack_head]; 1477 1523 } 1478 1524 1479 /// \brief Runs %DFSVisit algorithm from node \c s. 1480 /// 1481 /// This method runs the %DFS algorithm from a root node \c s. 1482 /// \note d.run(s) is just a shortcut of the following code. 1525 /// \brief Runs the algorithm from the given node. 1526 /// 1527 /// This method runs the %DFS algorithm from node \c s. 1528 /// in order to compute the DFS path to each node. 1529 /// 1530 /// The algorithm computes 1531 ///  the %DFS tree, 1532 ///  the distance of each node from the root in the %DFS tree. 1533 /// 1534 /// \note <tt>d.run(s)</tt> is just a shortcut of the following code. 1483 1535 ///\code 1484 1536 /// d.init(); … … 1492 1544 } 1493 1545 1494 /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph. 1546 /// \brief Finds the %DFS path between \c s and \c t. 1547 1548 /// This method runs the %DFS algorithm from node \c s 1549 /// in order to compute the DFS path to \c t. 1550 /// 1551 /// \return The length of the <tt>s</tt><tt>t</tt> DFS path, 1552 /// if \c t is reachable form \c s, \c 0 otherwise. 1553 /// 1554 /// \note Apart from the return value, <tt>d.run(s,t)</tt> is 1555 /// just a shortcut of the following code. 1556 ///\code 1557 /// d.init(); 1558 /// d.addSource(s); 1559 /// d.start(t); 1560 ///\endcode 1561 int run(Node s,Node t) { 1562 init(); 1563 addSource(s); 1564 start(t); 1565 return reached(t)?_stack_head+1:0; 1566 } 1567 1568 /// \brief Runs the algorithm to visit all nodes in the digraph. 1495 1569 1496 1570 /// This method runs the %DFS algorithm in order to 1497 /// compute the %DFS path to each node. The algorithm computes 1498 ///  The %DFS tree. 1499 ///  The distance of each node from the root in the %DFS tree. 1500 /// 1501 ///\note d.run() is just a shortcut of the following code. 1571 /// compute the %DFS path to each node. 1572 /// 1573 /// The algorithm computes 1574 ///  the %DFS tree, 1575 ///  the distance of each node from the root in the %DFS tree. 1576 /// 1577 /// \note <tt>d.run()</tt> is just a shortcut of the following code. 1502 1578 ///\code 1503 /// d.init();1504 /// for (NodeIt it(digraph); it != INVALID; ++it) {1505 /// if (!d.reached(it)) {1506 /// d.addSource(it);1507 /// d.start();1508 /// }1509 /// }1579 /// d.init(); 1580 /// for (NodeIt n(digraph); n != INVALID; ++n) { 1581 /// if (!d.reached(n)) { 1582 /// d.addSource(n); 1583 /// d.start(); 1584 /// } 1585 /// } 1510 1586 ///\endcode 1511 1587 void run() { … … 1518 1594 } 1519 1595 } 1596 1520 1597 ///@} 1521 1598 … … 1523 1600 /// The result of the %DFS algorithm can be obtained using these 1524 1601 /// functions.\n 1525 /// Before the use of these functions, 1526 /// either run() or start() must be called. 1602 /// Either \ref lemon::DfsVisit::run() "run()" or 1603 /// \ref lemon::DfsVisit::start() "start()" must be called before 1604 /// using them. 1527 1605 ///@{ 1528 /// \brief Checks if a node is reachable from the root. 1606 1607 /// \brief Checks if a node is reachable from the root(s). 1529 1608 /// 1530 1609 /// Returns \c true if \c v is reachable from the root(s). 1531 /// \warning The source nodes are inditated as unreachable.1532 1610 /// \pre Either \ref run() or \ref start() 1533 1611 /// must be called before using this function. 1534 ///1535 1612 bool reached(Node v) { return (*_reached)[v]; } 1613 1536 1614 ///@} 1615 1537 1616 }; 1538 1617 1539 1540 1618 } //END OF NAMESPACE LEMON 1541 1619 1542 1620 #endif 1543
Note: See TracChangeset
for help on using the changeset viewer.