lemon/johnson.h
changeset 2337 9c3d44ac39fb
parent 2263 9273fe7d850c
child 2376 0ed45a6c74b1
equal deleted inserted replaced
22:8ee68cc74bf1 23:8ea53cac779f
    26 
    26 
    27 #include <lemon/list_graph.h>
    27 #include <lemon/list_graph.h>
    28 #include <lemon/graph_utils.h>
    28 #include <lemon/graph_utils.h>
    29 #include <lemon/dijkstra.h>
    29 #include <lemon/dijkstra.h>
    30 #include <lemon/bellman_ford.h>
    30 #include <lemon/bellman_ford.h>
       
    31 #include <lemon/bits/path_dump.h>
    31 #include <lemon/bits/invalid.h>
    32 #include <lemon/bits/invalid.h>
    32 #include <lemon/error.h>
    33 #include <lemon/error.h>
    33 #include <lemon/maps.h>
    34 #include <lemon/maps.h>
    34 #include <lemon/matrix_maps.h>
    35 #include <lemon/matrix_maps.h>
    35 
    36 
   627     /// Before the use of these functions,
   628     /// Before the use of these functions,
   628     /// either run() or start() must be called.
   629     /// either run() or start() must be called.
   629     
   630     
   630     ///@{
   631     ///@{
   631 
   632 
   632     /// \brief Copies the shortest path to \c t into \c p
   633     typedef PredMatrixMapPath<Graph, PredMap> Path;
   633     ///    
   634 
   634     /// This function copies the shortest path to \c t into \c p.
   635     ///Gives back the shortest path.
   635     /// If it \c t is a source itself or unreachable, then it does not
   636     
   636     /// alter \c p.
   637     ///Gives back the shortest path.
   637     /// \return Returns \c true if a path to \c t was actually copied to \c p,
   638     ///\pre The \c t should be reachable from the \c t.
   638     /// \c false otherwise.
   639     Path path(Node s, Node t) 
   639     /// \sa DirPath
   640     {
   640     template <typename Path>
   641       return Path(*graph, *_pred, s, t);
   641     bool getPath(Path &p, Node source, Node target) {
       
   642       if (connected(source, target)) {
       
   643 	p.clear();
       
   644 	typename Path::Builder b(target);
       
   645 	for(b.setStartNode(target); predEdge(source, target) != INVALID;
       
   646 	    target = predNode(target)) {
       
   647 	  b.pushFront(predEdge(source, target));
       
   648 	}
       
   649 	b.commit();
       
   650 	return true;
       
   651       }
       
   652       return false;
       
   653     }
   642     }
   654 	  
   643 	  
   655     /// \brief The distance between two nodes.
   644     /// \brief The distance between two nodes.
   656     ///
   645     ///
   657     /// Returns the distance between two nodes.
   646     /// Returns the distance between two nodes.