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

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