Re: [boost] [BGL] To customize the graph traversing

Subject: Re: [boost] [BGL] To customize the graph traversing
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-07-20 09:00:10

> 
> 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.