Re: [Boost-users] BGL, shortest path between two nearby nodes in a huge graph

Subject: Re: [Boost-users] BGL, shortest path between two nearby nodes in a huge graph
From: Daniel Hofmann (daniel_at_[hidden])
Date: 2016-01-21 05:50:12

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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>