Re: [boost] [BGL] To customize the graph traversing

Subject: Re: [boost] [BGL] To customize the graph traversing
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2009-07-20 09:40:15

Cosimo Calabrese wrote:
> 
>>
>> You may try to specialize out_edges() function.
>> See attached example.
>>
> 
> Dmitry,
> 
> thank you very much for the code. If I correctly understand it:
> 
> - "pv" vertex property is the predecessor vertex;
> - "outel" edge property is the list of the edges in which I can continue 
> the exploration;
Yep.
> - the redefined out_edges returns all the outer edges if I've discovered 
> the vertex for the first time, and only the "authorized" edges (outel) 
> if the vertex has already been discovered.
> 
> Right?

No. All the outer edges are return only for the START vertex of the BFS, 
because it does not have any predecessor info.
> 
> To focalize the problem, take a look at the attached image ( no more 
> ascii sketch... ). Suppose that A is the start vertex, and I want reach 
> the N vertex; suppose that I can't go in LM if I'm in CL. So the path 
> should be:
> 
> A-B-C-D-E-F-G-H-L-M-N
> 
> But the BFD algorithm, when it condiders the C vertex, discovers the L 
> vertex; so the outer edge of L is only LH, because LM is forbidden from 
> CL. So L becames a explored vertex, in other words a black vertex. So 
> the BFS doesn't consider the L vertex never more. So I can't obtain the 
> attended path.
> 
> In your example, when I reach the L vertex for the first time, the 
> out_edges function returns ALL the outer edges, included the forbidden 
> LM, because the original boost::out_edges is called.

Should work fine for this example.
> 
> 

Dmitry