On Wed, 27 Apr 2011, Nicholas Mario Wardhana wrote:
On 16 April 2011 02:42, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
Hi Jeremiah,
My apology for digging up an old post. I'd like to ask how Boost's Floyd Warshall can extended to provide further functionality. I cannot find any notion of visitor for Floyd Warshall, unlike Dijkstra and A*, and I am a bit confused about the types of the arguments that have to be passed to the function.
One thing you can do in BGL is to compute the paths using the distances; look for edges where the source and target distances from a particular starting node differ by the edge's weight, and that will be in the SSSP tree for that starting node. You can also change the distances to <distance, predecessor> pairs (just by changing the types being passed into the algorithm);
Will that be a variable of type std::vector<std::vector<std::pair<float, boost::vertex_descriptor>>> ? I tried this and the code failed to compile.
Your weight map will also need to have elements of that type, and you will need customized compare, combine, inf, and zero arguments. Are you providing all of those?
you would still compare just the distances, and the weight of an edge would be a pair <actual_weight, source>.
Will that be a std::pair<float, vertex_descriptor> variable?
Yes.
Additionally, is it also possible to know the number of nodes in a shortest path between two vertices in the graph by using Boost's Floyd-Warshall implementation?
The easiest way to do that would be to compute the path itself using one of the methods I described; the length information is not recorded directly. -- Jeremiah Willcock