Boost logo

Boost :

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.


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.


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:


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.

Cosimo Calabrese.


Boost list run by bdawes at, gregod at, cpdaniel at, john at