
Boost : 
Subject: Re: [boost] [BGL] To customize the graph traversing
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 20090720 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:
>
> ABCDEFGHLMN
>
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk