[Boost-users] [Graph] How to do multi source shortest path
Leo Hidd
I have a graph and multiple sources (please read this thread:
http://thread.gmane.org/gmane.comp.lib.boost.user/73084/focus=73086
first paragraph, for the characteristics of the graph, if it matters).
So, instead of running the single source shortest path (SSSP) algorithm
(e.g., dijkstra_shortest_paths()) multiple times, what I do is that I
specify several sources instead of only one (so all the sources are
initialized with distance 0 and put into the queue) and than I run
Dijkstra as one usually does for SSSP. Doing so, the multi source runs
almost as fast as a single source instead of running
NbOfSouces*ElapsedTimeForSingleSource. Then, I'd like to know if it's
possible to use boost algorithms for multi-source shortest path, like
specifying several sources or anything alike. And, in the case it is
possible, it would be possible to have an array with the index of the
source the closest to a given node?
All pairs is not a solution because the number of sources is way less
than the number of nodes in the graph and because all sources use lots
of memory for storing the distances (for a 4 million nodes graph I'd
need a 4*10^12 elements table, don't?)
thx for your time,
leo
_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Jeremiah Willcock
> Hi all,
>
> I have a graph and multiple sources (please read this thread:
> http://thread.gmane.org/gmane.comp.lib.boost.user/73084/focus=73086 first
> paragraph, for the characteristics of the graph, if it matters). So, instead
> of running the single source shortest path (SSSP) algorithm (e.g.,
> dijkstra_shortest_paths()) multiple times, what I do is that I specify
> several sources instead of only one (so all the sources are initialized with
> distance 0 and put into the queue) and than I run Dijkstra as one usually
> does for SSSP. Doing so, the multi source runs almost as fast as a single
> source instead of running NbOfSouces*ElapsedTimeForSingleSource. Then, I'd
> like to know if it's possible to use boost algorithms for multi-source
> shortest path, like specifying several sources or anything alike. And, in the
> case it is possible, it would be possible to have an array with the index of
> the source the closest to a given node?
It looks like that functionality is missing; to do it, you'd need a
multi-source version of breadth_first_visit as well as one for
dijkstra_shortest_paths{,_no_init}. It would not be hard to implement
most likely, but it would preferably mean refactoring some of the existing
single-source code to take a queue and use all elements initially in it.
> All pairs is not a solution because the number of sources is way less than
> the number of nodes in the graph and because all sources use lots of memory
> for storing the distances (for a 4 million nodes graph I'd need a 4*10^12
> elements table, don't?)
You'd need a 16*10^12 element table, so that is impractical.
-- Jeremiah Willcock
Leo Hidd
> On Tue, 6 Mar 2012, Leo Hidd wrote:
>
>> Hi all,
>>
>> I have a graph and multiple sources (please read this thread:
>> http://thread.gmane.org/gmane.comp.lib.boost.user/73084/focus=73086
>> first paragraph, for the characteristics of the graph, if it
>> matters). So, instead of running the single source shortest path
>> (SSSP) algorithm (e.g., dijkstra_shortest_paths()) multiple times,
>> what I do is that I specify several sources instead of only one (so
>> all the sources are initialized with distance 0 and put into the
>> queue) and than I run Dijkstra as one usually does for SSSP. Doing
>> so, the multi source runs almost as fast as a single source instead
>> of running NbOfSouces*ElapsedTimeForSingleSource. Then, I'd like to
>> know if it's possible to use boost algorithms for multi-source
>> shortest path, like specifying several sources or anything alike.
>> And, in the case it is possible, it would be possible to have an
>> array with the index of the source the closest to a given node?
>
> It looks like that functionality is missing; to do it, you'd need a
> multi-source version of breadth_first_visit as well as one for
> dijkstra_shortest_paths{,_no_init}. It would not be hard to implement
> most likely, but it would preferably mean refactoring some of the
> existing single-source code to take a queue and use all elements
> initially in it.
>
Boost, so that SSSP would be a particular case of MSSP when only one
source is given in the input parameters? It would really be nice. As for
me to implement it myself, I fear I don't have enough skills to get into
the code and make those changes properly.
>> All pairs is not a solution because the number of sources is way less
>> than the number of nodes in the graph and because all sources use
>> lots of memory for storing the distances (for a 4 million nodes graph
>> I'd need a 4*10^12 elements table, don't?)
>
> You'd need a 16*10^12 element table, so that is impractical.
Gordon Woodhull
On Mar 6, 2012, at 12:37 PM, Leo Hidd <leo...@gmail.com> wrote:
> Le 06/03/2012 17:45, Jeremiah Willcock a écrit :
>> On Tue, 6 Mar 2012, Leo Hidd wrote:
>>
>>> Hi all,
>>>
>>> I have a graph and multiple sources (please read this thread: http://thread.gmane.org/gmane.comp.lib.boost.user/73084/focus=73086 first paragraph, for the characteristics of the graph, if it matters). So, instead of running the single source shortest path (SSSP) algorithm (e.g., dijkstra_shortest_paths()) multiple times, what I do is that I specify several sources instead of only one (so all the sources are initialized with distance 0 and put into the queue) and than I run Dijkstra as one usually does for SSSP. Doing so, the multi source runs almost as fast as a single source instead of running NbOfSouces*ElapsedTimeForSingleSource. Then, I'd like to know if it's possible to use boost algorithms for multi-source shortest path, like specifying several sources or anything alike. And, in the case it is possible, it would be possible to have an array with the index of the source the closest to a given node?
>>
>> It looks like that functionality is missing; to do it, you'd need a multi-source version of breadth_first_visit as well as one for dijkstra_shortest_paths{,_no_init}. It would not be hard to implement most likely, but it would preferably mean refactoring some of the existing single-source code to take a queue and use all elements initially in it.
>>
> do you think it could be implemented in a (near?) future version of Boost, so that SSSP would be a particular case of MSSP when only one source is given in the input parameters? It would really be nice. As for me to implement it myself, I fear I don't have enough skills to get into the code and make those changes properly.
Why not just create a "super source" vertex with zero-weight edges to all the sources you want?
Cheers,
Gordon
Leo Hidd
dijkstra_shortest_paths function takes only one vertex_descriptor, not
an array of it (isn't it?).
Gordon Woodhull
On Mar 7, 2012, at 8:27 AM, Leo Hidd <leo...@gmail.com> wrote:
> and how do I create this "super source" vertex? The dijkstra_shortest_paths function takes only one vertex_descriptor, not an array of it (isn't it?).
I meant, just add a special vertex to your graph and connect it with zero-weight edges to all the sources you want, and specify that as the source. Requires a little bit of detective work at the end to see which source a path goes through, but it should get you your answer.
Jeremiah Willcock
>
>
> On Mar 7, 2012, at 8:27 AM, Leo Hidd <leo...@gmail.com> wrote:
>
>> and how do I create this "super source" vertex? The
>> dijkstra_shortest_paths function takes only one vertex_descriptor, not
>> an array of it (isn't it?).
>
> I meant, just add a special vertex to your graph and connect it with
> zero-weight edges to all the sources you want, and specify that as the
> source. Requires a little bit of detective work at the end to see which
> source a path goes through, but it should get you your answer.
Even that isn't too hard -- keep a predecessor map, then walk up it from
each vertex until you reach one of the source vertices; that will be the
closest one.
-- Jeremiah Willcock
Leo Cacciari
>
>
> On Mar 7, 2012, at 8:27 AM, Leo Hidd <leo...@gmail.com> wrote:
>
>> and how do I create this "super source" vertex? The dijkstra_shortest_paths function takes only one vertex_descriptor, not an array of it (isn't it?).
>
> I meant, just add a special vertex to your graph and connect it with zero-weight edges to all the sources you want, and specify that as the source. Requires a little bit of detective work at the end to see which source a path goes through, but it should get you your answer.
>
your problem _and_ becomes your idea of putting all the source vertices
into the queue at the start, as _this_ is _exactly_ what would do the
djikstra algorithm upon finding a source connected with 0-length edges
to a bunch of other vertices. (just my 5¢)
L.C.
--
Leo Cacciari
Aliae nationes servitutem pati possunt populi romani est propria libertas
Leo Hidd
> Il 03/07/2012 04:22 PM, Gordon Woodhull ha scritto:
>>
>> On Mar 7, 2012, at 8:27 AM, Leo Hidd<leo...@gmail.com> wrote:
>>
>>> and how do I create this "super source" vertex? The dijkstra_shortest_paths function takes only one vertex_descriptor, not an array of it (isn't it?).
>> I meant, just add a special vertex to your graph and connect it with zero-weight edges to all the sources you want, and specify that as the source. Requires a little bit of detective work at the end to see which source a path goes through, but it should get you your answer.
>>
> This, by the way, is the "classical" graph-theoretical way to address
> your problem _and_ becomes your idea of putting all the source vertices
> into the queue at the start, as _this_ is _exactly_ what would do the
> djikstra algorithm upon finding a source connected with 0-length edges
> to a bunch of other vertices. (just my 5¢)
>
> L.C.
>
to dijkstra_shortest_paths whose size is the number of nodes of the
graph and this array would be filed with the index of the closest
source. By the way, the distance and path arrays are relative to the
closest source. The idea of tracking back through the path is always a
solution to it, but it is more computational complex than storing the
result direct to an array.
I'll try Gordon's suggestion. I come back with results. In the mean time
I'm also trying to create a test case for Jeremiah on the other topic
"[Graph] How to do multi source shortest path".
thx guys, leo
Leo Hidd
>> and how do I create this "super source" vertex? The dijkstra_shortest_paths function takes only one vertex_descriptor, not an array of it (isn't it?).
> I meant, just add a special vertex to your graph and connect it with zero-weight edges to all the sources you want, and specify that as the source. Requires a little bit of detective work at the end to see which source a path goes through, but it should get you your answer.
>
> Cheers,
> Gordon
>
just fine ;)
However, it would be nice to avoid the Sherlock Holmes part of the job.
In my case, I actually don't need the path as long as I have the index
of the closest source. For a small number of sources, the source search
through the path for all nodes takes a non negligible time compared to
the MSSP search:
example with 3 million nodes, 9 million edges (undirected graph,
dijkstra_shortest_paths_no_color_map)
0- 1 source: SSSP 4800ms
1- 60 sources: MSSP 6309 ms, source search 1778 ms
2- 600 sources: MSSP 7494 ms, source search 634 ms
3- 6000 sources: MSSP 8408 ms, source search 289 ms
4- 60000 sources: MSSP 9292 ms, source search 130 ms
(of coarse, more sources you have, smaller will be the average path,
thus the source search)
So it would be nice if there was a way to return a table with the index
of the closest source for each node (i.e., the source to which the
distance_map corresponds). The additional MSSP run-time to keep track of
the closest source would be negligible.
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.
Jeremiah Willcock
That can be done with a visitor: have closest_source as a property map,
then on each edge_relaxed event, copy the closest source property from the
edge's source to its target.
> 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.
-- Jeremiah Willcock
Leo Hidd
>> 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.
>
distributed/parallel version of it, like for the
delta_stepping_shortest_paths()?
leo
Jeremiah Willcock
>
>>> 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
Leo Hidd
> 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.
Jeremiah Willcock
> 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
trunk):
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