Boost logo

Boost Users :

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 00:28:14

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.
>> 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]
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at