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