Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk