BGL, shortest path between two nearby nodes in a huge graph
Dear list, I am a happy user of BGL, but recently I got stuck in a strange problem. I think I am missing the obvious, so I'll be happy to read the fine manual if it's the case. Just point me to the right direction. I need to find the shortest path between two nodes, for doing so I am using dijkstra with a custom visitor that stops the search (throwing an exception) when examine_vertex is called on the destination node. It worked fine, but it run strangely slow. After some profiling, it is clear that most of the time is used in the initialize_vertex function. The graph is fairly large, but the path I am looking for are fairly small (10 edges tops usually). It is possible to skip the initialize phase? Cheers, Paolo
Dear list,
I am a happy user of BGL, but recently I got stuck in a strange problem. I think I am missing the obvious, so I'll be happy to read the fine manual if it's the case. Just point me to the right direction.
I need to find the shortest path between two nodes, for doing so I am using dijkstra with a custom visitor that stops the search (throwing an exception) when examine_vertex is called on the destination node.
It worked fine, but it run strangely slow. After some profiling, it is clear that most of the time is used in the initialize_vertex function. The graph is fairly large, but the path I am looking for are fairly small (10 edges tops usually).
It is possible to skip the initialize phase?
There are a number of (undocumented) dijkstra_shortest_paths_no_init(...) functions in dijkstra_shortest_paths.hpp. I think you need the one with the signature listed below, because it is the only one that does not initialize the color map. A strategy can be to use a visitor to keep a list of all discovered vertices and re-initialize those (predecessor, distance, color) after each path is found. // Call breadth first search template <class Graph, class SourceInputIter, class DijkstraVisitor, class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, class Compare, class Combine, class DistZero, class ColorMap> inline void dijkstra_shortest_paths_no_init (const Graph& g, SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color)
This exact use-case is described in the breadth_first_visit (note: not breadth_first_search) documentation:
Also, this difference allows for more flexibility in the color property map. For example, one could use a map that only implements a partial function on the vertices, which could be more space efficient when the search only reaches a small portion of the graph.
http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/breadth_first_visit.html On 01/21/2016 10:06 AM, alex wrote:
Dear list,
I am a happy user of BGL, but recently I got stuck in a strange problem. I think I am missing the obvious, so I'll be happy to read the fine manual if it's the case. Just point me to the right direction.
I need to find the shortest path between two nodes, for doing so I am using dijkstra with a custom visitor that stops the search (throwing an exception) when examine_vertex is called on the destination node.
It worked fine, but it run strangely slow. After some profiling, it is clear that most of the time is used in the initialize_vertex function. The graph is fairly large, but the path I am looking for are fairly small (10 edges tops usually).
It is possible to skip the initialize phase?
There are a number of (undocumented) dijkstra_shortest_paths_no_init(...) functions in dijkstra_shortest_paths.hpp. I think you need the one with the signature listed below, because it is the only one that does not initialize the color map.
A strategy can be to use a visitor to keep a list of all discovered vertices and re-initialize those (predecessor, distance, color) after each path is found.
// Call breadth first search template <class Graph, class SourceInputIter, class DijkstraVisitor, class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, class Compare, class Combine, class DistZero, class ColorMap> inline void dijkstra_shortest_paths_no_init (const Graph& g, SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color)
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
At the moment I was using the _no_color_map version (I have no infinity edges), but the idea sounds fairly good. Thanks a lot. On Thu, Jan 21, 2016 at 7:50 PM, Daniel Hofmann <daniel@trvx.org> wrote:
This exact use-case is described in the breadth_first_visit (note: not breadth_first_search) documentation:
Also, this difference allows for more flexibility in the color property map. For example, one could use a map that only implements a partial function on the vertices, which could be more space efficient when the search only reaches a small portion of the graph.
http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/breadth_first_visit.html
On 01/21/2016 10:06 AM, alex wrote:
Dear list,
I am a happy user of BGL, but recently I got stuck in a strange problem. I think I am missing the obvious, so I'll be happy to read the fine manual if it's the case. Just point me to the right direction.
I need to find the shortest path between two nodes, for doing so I am using dijkstra with a custom visitor that stops the search (throwing an exception) when examine_vertex is called on the destination node.
It worked fine, but it run strangely slow. After some profiling, it is clear that most of the time is used in the initialize_vertex function. The graph is fairly large, but the path I am looking for are fairly small (10 edges tops usually).
It is possible to skip the initialize phase?
There are a number of (undocumented) dijkstra_shortest_paths_no_init(...) functions in dijkstra_shortest_paths.hpp. I think you need the one with the signature listed below, because it is the only one that does not initialize the color map.
A strategy can be to use a visitor to keep a list of all discovered vertices and re-initialize those (predecessor, distance, color) after each path is found.
// Call breadth first search template <class Graph, class SourceInputIter, class DijkstraVisitor, class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, class Compare, class Combine, class DistZero, class ColorMap> inline void dijkstra_shortest_paths_no_init (const Graph& g, SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color)
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Finally I could try the idea out and it works fine. I just passed a reference to the distance_map to the visitor and setup the distance to the neighbor to "infinity" in the vis.examine_edge call. I did so only if the vertex was not already in the map. On Thu, Jan 21, 2016 at 7:58 PM, Paolo Bolzoni <paolo.bolzoni.brown@gmail.com> wrote:
At the moment I was using the _no_color_map version (I have no infinity edges), but the idea sounds fairly good. Thanks a lot.
On Thu, Jan 21, 2016 at 7:50 PM, Daniel Hofmann <daniel@trvx.org> wrote:
This exact use-case is described in the breadth_first_visit (note: not breadth_first_search) documentation:
Also, this difference allows for more flexibility in the color property map. For example, one could use a map that only implements a partial function on the vertices, which could be more space efficient when the search only reaches a small portion of the graph.
http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/breadth_first_visit.html
On 01/21/2016 10:06 AM, alex wrote:
Dear list,
I am a happy user of BGL, but recently I got stuck in a strange problem. I think I am missing the obvious, so I'll be happy to read the fine manual if it's the case. Just point me to the right direction.
I need to find the shortest path between two nodes, for doing so I am using dijkstra with a custom visitor that stops the search (throwing an exception) when examine_vertex is called on the destination node.
It worked fine, but it run strangely slow. After some profiling, it is clear that most of the time is used in the initialize_vertex function. The graph is fairly large, but the path I am looking for are fairly small (10 edges tops usually).
It is possible to skip the initialize phase?
There are a number of (undocumented) dijkstra_shortest_paths_no_init(...) functions in dijkstra_shortest_paths.hpp. I think you need the one with the signature listed below, because it is the only one that does not initialize the color map.
A strategy can be to use a visitor to keep a list of all discovered vertices and re-initialize those (predecessor, distance, color) after each path is found.
// Call breadth first search template <class Graph, class SourceInputIter, class DijkstraVisitor, class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, class Compare, class Combine, class DistZero, class ColorMap> inline void dijkstra_shortest_paths_no_init (const Graph& g, SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color)
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
It's more a curiosity than an immediate need, but the function breadth_first_visit only needs the model of an Incidence Graph instead of a Vertex List Graph. Is it the same for dijkstra_shortest_paths_no_color_map_no_init ? On Mon, Jan 25, 2016 at 2:28 PM, Paolo Bolzoni <paolo.bolzoni.brown@gmail.com> wrote:
Finally I could try the idea out and it works fine. I just passed a reference to the distance_map to the visitor and setup the distance to the neighbor to "infinity" in the vis.examine_edge call. I did so only if the vertex was not already in the map.
On Thu, Jan 21, 2016 at 7:58 PM, Paolo Bolzoni <paolo.bolzoni.brown@gmail.com> wrote:
At the moment I was using the _no_color_map version (I have no infinity edges), but the idea sounds fairly good. Thanks a lot.
On Thu, Jan 21, 2016 at 7:50 PM, Daniel Hofmann <daniel@trvx.org> wrote:
This exact use-case is described in the breadth_first_visit (note: not breadth_first_search) documentation:
Also, this difference allows for more flexibility in the color property map. For example, one could use a map that only implements a partial function on the vertices, which could be more space efficient when the search only reaches a small portion of the graph.
http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/breadth_first_visit.html
On 01/21/2016 10:06 AM, alex wrote:
Dear list,
I am a happy user of BGL, but recently I got stuck in a strange problem. I think I am missing the obvious, so I'll be happy to read the fine manual if it's the case. Just point me to the right direction.
I need to find the shortest path between two nodes, for doing so I am using dijkstra with a custom visitor that stops the search (throwing an exception) when examine_vertex is called on the destination node.
It worked fine, but it run strangely slow. After some profiling, it is clear that most of the time is used in the initialize_vertex function. The graph is fairly large, but the path I am looking for are fairly small (10 edges tops usually).
It is possible to skip the initialize phase?
There are a number of (undocumented) dijkstra_shortest_paths_no_init(...) functions in dijkstra_shortest_paths.hpp. I think you need the one with the signature listed below, because it is the only one that does not initialize the color map.
A strategy can be to use a visitor to keep a list of all discovered vertices and re-initialize those (predecessor, distance, color) after each path is found.
// Call breadth first search template <class Graph, class SourceInputIter, class DijkstraVisitor, class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, class Compare, class Combine, class DistZero, class ColorMap> inline void dijkstra_shortest_paths_no_init (const Graph& g, SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color)
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (1)
-
alex -
Daniel Hofmann -
Paolo Bolzoni