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