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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-05-04 14:11:12

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