lemon/bfs.h
changeset 2347 0aaa7ada5395
parent 2307 558cc308a4bd
child 2350 eb371753e814
equal deleted inserted replaced
22:0ecdafb12357 23:e2d86439ed51
    23 ///\file
    23 ///\file
    24 ///\brief Bfs algorithm.
    24 ///\brief Bfs 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 namespace lemon {
    33 namespace lemon {
   674     ///Before the use of these functions,
   675     ///Before the use of these functions,
   675     ///either run() or start() must be calleb.
   676     ///either run() or start() must be calleb.
   676     
   677     
   677     ///@{
   678     ///@{
   678 
   679 
   679     ///Copies the shortest path to \c t into \c p
   680     typedef PredMapPath<Graph, PredMap> Path;
   680     
   681 
   681     ///This function copies the shortest path to \c t into \c p.
   682     ///Gives back the shortest path.
   682     ///If \c t is a source itself or unreachable, then it does not
   683     
   683     ///alter \c p.
   684     ///Gives back the shortest path.
   684     ///\return Returns \c true if a path to \c t was actually copied to \c p,
   685     ///\pre The \c t should be reachable from the source.
   685     ///\c false otherwise.
   686     Path path(Node t) 
   686     ///\sa DirPath
   687     {
   687     template<class P>
   688       return Path(*G, *_pred, t);
   688     bool getPath(P &p,Node t) 
       
   689     {
       
   690       if(reached(t)) {
       
   691 	p.clear();
       
   692 	typename P::Builder b(p);
       
   693 	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
       
   694 	  b.pushFront(predEdge(t));
       
   695 	b.commit();
       
   696 	return true;
       
   697       }
       
   698       return false;
       
   699     }
   689     }
   700 
   690 
   701     ///The distance of a node from the root(s).
   691     ///The distance of a node from the root(s).
   702 
   692 
   703     ///Returns the distance of a node from the root(s).
   693     ///Returns the distance of a node from the root(s).