Boost logo

Boost :

Subject: Re: [boost] [BGL] To customize the graph traversing
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-07-21 06:39:39

Hi Benoît,

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

the constraints are stored in a edge property, that is a list of
"authorized" edgeDescriptors. If I understand that you propose, I should
apply a parametrized predicate to a filtered graph. During the
exploration, when I explore a vertex, I can take the predecessor vertex,
and get the edge predecessor of the examined vertex. So I can
reconfigure the predicate with that edge, including the "authorized"
edges and excluding the other outer edges from the graph view. So the
exploration can continue only on the locally authorized edges.

If I correctly understand, I think that it doesn't work. The situation
returned to the Dmitry's proposal. Referring to the same attached graph
(look to the Dmitry mail), when the exploration reachs the "9" vertex
from "2" vertex, so the predecessor edge is 2-9. If I pass the 2-9 edge
to the predicate, it excludes the 9-10 from the view, and the
exploration continue to the 9-7 edge. But now the 9 vertex is
"explored", so it is black, and so I consider the 9 vertex never more.
So the 10, 11 and 12 vertexes aren't reachable.

The problem is that the "9" vertex becomes black "prematurely", and it
dipends only from the traversing algorithm (BFS in this case). So even
if I apply a filter to the graph, or select the right outer edges like
Dmitry's proposal, this doesn't change this fact. When the "9" vertex
becomes black, it becomes inexplorable, like BFS wants. IMO, a BFS
hypothesis is that the graph is immutable during all the traversing.

I'm searching a method to customize the traversing algorithm, but I'm
pessimist. The coloration method is cabled in the algorithm. So I think
I must modify BFS so that it colors vertexes in different way. Or to
find another exploration algorithm.

Best regards,
Cosimo Calabrese.

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