lemon/dfs.h
changeset 2373 134639e6ea45
parent 2260 4274224f8a7d
child 2376 0ed45a6c74b1
equal deleted inserted replaced
33:30902fa23d27 34:f18c014f67c2
    23 ///\file
    23 ///\file
    24 ///\brief Dfs algorithm.
    24 ///\brief Dfs algorithm.
    25 
    25 
    26 #include <lemon/list_graph.h>
    26 #include <lemon/list_graph.h>
    27 #include <lemon/graph_utils.h>
    27 #include <lemon/graph_utils.h>
       
    28 #include <lemon/bits/path_dump.h>
    28 #include <lemon/bits/invalid.h>
    29 #include <lemon/bits/invalid.h>
    29 #include <lemon/error.h>
    30 #include <lemon/error.h>
    30 #include <lemon/maps.h>
    31 #include <lemon/maps.h>
    31 
    32 
    32 #include <lemon/concept_check.h>
    33 #include <lemon/concept_check.h>
   650     ///Before the use of these functions,
   651     ///Before the use of these functions,
   651     ///either run() or start() must be called.
   652     ///either run() or start() must be called.
   652     
   653     
   653     ///@{
   654     ///@{
   654 
   655 
   655     ///Copies the path to \c t on the DFS tree into \c p
   656     typedef PredMapPath<Graph, PredMap> Path;
   656     
   657 
   657     ///This function copies the path to \c t on the DFS tree  into \c p.
   658     ///Gives back the shortest path.
   658     ///If \c t is a source itself or unreachable, then it does not
   659     
   659     ///alter \c p.
   660     ///Gives back the shortest path.
   660     ///
   661     ///\pre The \c t should be reachable from the source.
   661     ///\return Returns \c true if a path to \c t was actually copied to \c p,
   662     Path path(Node t) 
   662     ///\c false otherwise.
   663     {
   663     ///\sa DirPath
   664       return Path(*G, *_pred, t);
   664     template<class P>
       
   665     bool getPath(P &p,Node t) 
       
   666     {
       
   667       if(reached(t)) {
       
   668 	p.clear();
       
   669 	typename P::Builder b(p);
       
   670 	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
       
   671 	  b.pushFront(predEdge(t));
       
   672 	b.commit();
       
   673 	return true;
       
   674       }
       
   675       return false;
       
   676     }
   665     }
   677 
   666 
   678     ///The distance of a node from the root(s).
   667     ///The distance of a node from the root(s).
   679 
   668 
   680     ///Returns the distance of a node from the root(s).
   669     ///Returns the distance of a node from the root(s).