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:44:05

On Thu, 5 May 2011, Nicholas Mario Wardhana wrote:

> 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.

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