Boost logo

Boost :

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




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