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: Paolo Bolzoni (paolo.bolzoni.brown_at_[hidden])
Date: 2016-01-25 01:06:55

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