Re: [Boost-users] [BGL] bundled GraphProperties

Subject: Re: [Boost-users] [BGL] bundled GraphProperties
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-01-22 12:53:11

On Fri, 22 Jan 2010, Damien Maupu wrote:

> Hi,
>
> I ran in a case where it could be useful or at least make the code more 
> clear.
>
> I am searching an implicit graph that is generate as the search proceed.
> I am using A* but I guess this applies to other search algorithms.
> Therefore it might happen that you don't know the goal vertex in advance and 
> you discover it when the search proceed.
>
> Not knowing the goal means that the end test in examine_vertex() is not done 
> on the vertex descriptor anymore but on some other variable for example the 
> distance of a vertex to be below some threshold.
>
> Once the goal is reached the search stops but we need to save the vertex 
> descriptor of the goal vertex in order to retrieve the path we search for 
> (from a predecessor list for example).
>
> The best place (and the only one I found intuitive) is to save such 
> information in the graph properties.
> I think it is impossible to save that info in the visitor because the visitor 
> passed by copy to the algorithm and not by reference.

You can use a reference member in the visitor that points to an external 
variable (possibly even a local variable in the code that calls A*).

> So far I am using property<graph_name_t, int> to save that vertex descriptor 
> (I am using adjacency list so I assumed vertex descriptor are int, otherwise 
> I don't know how to do it because vertex descriptor are only defined once the 
> graph is defined which is done after the graph property is defined. If anyone 
> know how to do it more properly please tell me so).
>
> Instead of using graph_name property I could create one of my own with a more 
> intuitive name.
> Bundled graph property would be even better for clarity reason.

If you are going to store your data as a graph property, I agree, but 
normally graph properties are not used for results.

-- Jeremiah Willcock