Boost logo

Boost Users :

Subject: Re: [Boost-users] [Graph] How to do multi source shortest path
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-03-12 22:18:22

On Tue, 13 Mar 2012, Leo Hidd wrote:

> Le 09/03/2012 19:04, Jeremiah Willcock a écrit :
>> On Fri, 9 Mar 2012, Leo Hidd wrote:
>>>>> An additional question, is there a way to modify the target or the
>>>>> source vertex of an edge? It would be useful to me because I run several
>>>>> iterations of MSSP with a different set of sources for each iteration
>>>>> (but the number of the sources is the same). Modifying the source/targe
>>>>> of an edge would avoid delete/re-add the zero-weight edges.
>>>> No, there isn't. A direct implementation of MSSP will solve your
>>>> problem, though, and I am working on one. It will probably be committed
>>>> to the Boost trunk next week.
>>> wow, nice, thank you sir! Do you plan to also implement the
>>> distributed/parallel version of it, like for the
>>> delta_stepping_shortest_paths()?
>> I was planning on just doing the sequential version.
>> -- Jeremiah Willcock
> it would be so nice to have the distributed MSSP, but I ignore how time
> consuming it would be to implement it in boost. A priori it should be as
> difficult (or easy) as for single source. Please let me know if you consider
> to implement distributed MSSP.

A version like you are asking about (starting from all of them in parallel
and finding the closest to each vertex) is only a small change to the
interface to SSSP; it is for the sequential code, too. Here are what are
probably the only changes to need to be made (in
<boost/graph/distributed/delta_stepping_shortest_paths.hpp> in the Boost

1. Add a new version of delta_stepping_impl::run that takes a range of
vertices, and processes each of them like it does to s right now (set
distances to 0 on local ones and put them into buckets).

2. Add a new version of delta_stepping_shortest_paths that takes an
iterator range of sources and calls the new impl function instead of the
single-source version.

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at