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@tellus.it> 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