Re: [Boost-users] [BGL] Extending Floyd Warshall (was: All-pairs SP algorithms -> Determine the path)

Subject: Re: [Boost-users] [BGL] Extending Floyd Warshall (was: All-pairs SP algorithms -> Determine the path)
From: Nicholas Mario Wardhana (mario.wardhana_at_[hidden])
Date: 2011-05-04 14:22:26

On 5 May 2011 02:11, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> On Wed, 27 Apr 2011, Nicholas Mario Wardhana wrote:
>
>> On 16 April 2011 02:42, Jeremiah Willcock <jewillco_at_[hidden]> 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