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