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
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