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-21 11:03:26

Cosimo Calabrese wrote:
> Dmitry Bufistov ha scritto:
>> 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.
> 
> You're 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.
>>
>> Should work fine for this example.
> 
> Unfortunately this doesn't resolve the problem.
> 
> I've modified your code to implement the example's picture (you can find 
> it with numbered vertexes in attach, like the code implements). All the 
> edges can follow all their outer edges, except the 2-9 edge that can't 
> follow the 9-10 edge.
> 
> The result is that, for example, the "11" is not reachable. From 2-9, I 
> examine the 9 vertex; then I follow to the 9-7 (that is authorized), but 
> I consider the 9-10 edge never more, because the 9 vertex is explored 
> (black). So the 10, 11 and 12 vertexes are not reachable.
> 
> But it isn't true, because the path to reach the 11 vertex exists:
> 
> 0-1-2-3-4-5-6-7-9-10-11
> 
> I also attach the modified code.

Ok. Does the attached patch work?
We add a property "degree of exploration" for each vertex (m_vo in the 
code).
> 
> 
> Best regards,
> Cosimo Calabrese

Best,
Dmitry