[Graph] How to do multi source shortest path
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? 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
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.
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
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.
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. y, true my bad xD
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mar 6, 2012, at 12:37 PM, Leo Hidd <leohidd@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
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?). Le 07/03/2012 06:53, Gordon Woodhull a écrit :
On Mar 6, 2012, at 12:37 PM, Leo Hidd<leohidd@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
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mar 7, 2012, at 8:27 AM, Leo Hidd <leohidd@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. Cheers, Gordon
On Wed, 7 Mar 2012, Gordon Woodhull wrote:
On Mar 7, 2012, at 8:27 AM, Leo Hidd <leohidd@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
Il 03/07/2012 04:22 PM, Gordon Woodhull ha scritto:
On Mar 7, 2012, at 8:27 AM, Leo Hidd <leohidd@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. -- Leo Cacciari Aliae nationes servitutem pati possunt populi romani est propria libertas
Le 07/03/2012 16:44, Leo Cacciari a écrit :
Il 03/07/2012 04:22 PM, Gordon Woodhull ha scritto:
On Mar 7, 2012, at 8:27 AM, Leo Hidd<leohidd@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.
y, yes, but what i meant was, like, pass an array (or vecS) as argument 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
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
thx Gordon, the extra vertex and additional zero-weight edges do the job 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.
On Fri, 9 Mar 2012, Leo Hidd 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.
Cheers, Gordon
thx Gordon, the extra vertex and additional zero-weight edges do the job 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.
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
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()? leo
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
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.
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 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
participants (4)
-
Gordon Woodhull -
Jeremiah Willcock -
Leo Cacciari -
Leo Hidd