lemon/floyd_warshall.h
changeset 2335 27aa03cd3121
parent 2260 4274224f8a7d
child 2376 0ed45a6c74b1
equal deleted inserted replaced
17:9d58bf554e45 18:f3cf7f3edfde
    24 /// \brief FloydWarshall algorithm.
    24 /// \brief FloydWarshall algorithm.
    25 ///
    25 ///
    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/bits/path_dump.h>
    29 #include <lemon/bits/invalid.h>
    30 #include <lemon/bits/invalid.h>
    30 #include <lemon/error.h>
    31 #include <lemon/error.h>
    31 #include <lemon/matrix_maps.h>
    32 #include <lemon/matrix_maps.h>
    32 #include <lemon/maps.h>
    33 #include <lemon/maps.h>
    33 
    34 
   478     /// Before the use of these functions,
   479     /// Before the use of these functions,
   479     /// either run() or start() must be called.
   480     /// either run() or start() must be called.
   480     
   481     
   481     ///@{
   482     ///@{
   482 
   483 
   483     /// \brief Copies the shortest path to \c t into \c p
   484     typedef PredMatrixMapPath<Graph, PredMap> Path;
   484     ///    
   485 
   485     /// This function copies the shortest path to \c t into \c p.
   486     ///Gives back the shortest path.
   486     /// If it \c t is a source itself or unreachable, then it does not
   487     
   487     /// alter \c p.
   488     ///Gives back the shortest path.
   488     /// \return Returns \c true if a path to \c t was actually copied to \c p,
   489     ///\pre The \c t should be reachable from the \c t.
   489     /// \c false otherwise.
   490     Path path(Node s, Node t) 
   490     /// \sa DirPath
   491     {
   491     template <typename Path>
   492       return Path(*graph, *_pred, s, t);
   492     bool getPath(Path &p, Node source, Node target) {
       
   493       if (connected(source, target)) {
       
   494 	p.clear();
       
   495 	typename Path::Builder b(target);
       
   496 	for(b.setStartNode(target); predEdge(source, target) != INVALID;
       
   497 	    target = predNode(target)) {
       
   498 	  b.pushFront(predEdge(source, target));
       
   499 	}
       
   500 	b.commit();
       
   501 	return true;
       
   502       }
       
   503       return false;
       
   504     }
   493     }
   505 	  
   494 	  
   506     /// \brief The distance between two nodes.
   495     /// \brief The distance between two nodes.
   507     ///
   496     ///
   508     /// Returns the distance between two nodes.
   497     /// Returns the distance between two nodes.