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

Subject: Re: [boost] [BGL] To customize the graph traversing
From: Benoit . (trasfract_at_[hidden])
Date: 2009-07-20 09:41:15

Hi Cosimo,

I am not sure i understand what's preventing you from using a
filtered_graph. It uses a property which can be dynamically modified
thus making it possible to hide an edge at some point, and show it
later on.
You just need a trigger to inform the filter property of the last edge
that has been explored.

How have you stored the constraints on allowed paths ?

Benoît Casoetto

On Mon, Jul 20, 2009 at 3:00 PM, Cosimo
Calabrese<cosimo.calabrese_at_[hidden]> 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;
> - 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?
>
> 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.
>
>
> Best,
> Cosimo Calabrese.
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>