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