Re: [Boost-users] [BGL] dijkstra_shortest_path fails to call initialize_vertex

From: Michael Barrientos (michael_barrientos_at_[hidden])
Date: 2006-08-09 19:45:56

Doug Gregor wrote:
> On Aug 9, 2006, at 12:07 AM, Michael Barrientos wrote:
>> I did some digging into the source, and found that when the Dijkstra's
>> algorithm delegates to the Breadth First Search algorithm, it calls
>> breadth_first_visit. However, only breadth_first_search calls
>> initialize_vertex. Thus initialize vertex is never called.
> 
> Yep, you're right.
> 
>> For now, I've decided to work around it without patching BGL, but can
>> this be fixed in a future version?
> 
> It's been fixed for 1.34.0.
> 
> 	Doug

Reminder to self for the future: check the CVS to see if it's already 
fixed in the next release. However, it's not fixed the way I had hoped 
it would be.

I had hoped that the fix would place the initialize_vertex call after 
the initialization of the color/distance/predecessor maps, like it is in 
1.33.1 for BFS. I noticed that the fix in CVS places the initialize call 
before the initialization, and that the BFS/Astar/etc. have similarly 
moved the initialize_vertex call to before the color map initialization.

What I'm trying to do (which I admit is very non-standard) is to set the 
  color of vertices that I do not want visited to black on graph 
initialization. My visitor would have access to an external color map, 
and sets the vertex color to black during initialize_vertex. The way it 
is now, the vertex color is unconditionally set to white after the 
initialize_vertex call, overwriting any changes I make.

I know a similar thing can be accomplished by setting edge weights to 
infinite or by using a filtered graph, but both of these solutions end 
up costing more in performance because the function is called multiple 
times (the blacking out/filtering function is a pretty expensive operation).

What are the chances of moving the initialize_vertex call to a point 
after the vertex color is initialized? Or will the only recourse be to 
call the internal function dijkstra_shortest_paths_no_init directly?
--
Mike Barrientos - michael_barrientos_at_[hidden]