[BGL] Extending Floyd Warshall (was: All-pairs SP algorithms -> Determine the path)
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.
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? 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?
-- Jeremiah Willcock
Thank you. Best regards, Nicholas
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
On 5 May 2011 02:11, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
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
Thanks for your answer, Jeremiah. This means that I have to play around more with the configuration before the "customised" Floyd Warshall is operational. I'll get back when it is up and working. Best regards, Nicholas
On Thu, 5 May 2011, Nicholas Mario Wardhana wrote:
On 5 May 2011 02:11, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
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
Thanks for your answer, Jeremiah. This means that I have to play around more with the configuration before the "customised" Floyd Warshall is operational. I'll get back when it is up and working.
Remember that you can also just read the paths from the distance matrix (assuming roundoff errors are not too much of a problem with your weights and distances). That will be much simpler than keeping predecessors around. Just look for graph edges that satisfy d(i,j) + w(j,k) == d(i,k) for all vertices i, j, and k (where d is the distance matrix and w are your edge weights). -- Jeremiah Willcock
participants (2)
-
Jeremiah Willcock -
Nicholas Mario Wardhana