A more specific follow-up question to my earlier one BGL Interior properties for implicit graph
The Boost BGL has a version of the A* algorithm that is supposed to work with implicit graphs, namely the astar_search_no_init() function. The implicit graphs can be modeled as IncidenceGraphs. The documentation of A* says "Please note that astar_search_no_init() must be used for implicit graphs; the basic astar_search() function requires a graph that models the Vertex List Graph concept. Both versions also require the graph type to model the Incidence Graph concept".
Doesn't this mean that the graph does not have to model the Vertex List Graph concept? If this is the case, am I missing something since I am unable to find any versions of the function astar_search_no_init() that would use IncidenceGraphs? There are two versions of astar_search_no_init() available, and both of them seem to work with VertexListGraphs. I am using Boost 1.48 and the A* is in the file astar_search.hpp.
I don't see how it would even make sense to require the implicit graph to model the Vertex List Graph in the first place. The documentation is quite confusing and misleading to me. Any ideas?
Support for implicit graphs was added in r50803 on January 27, 2009, to fix Bug #829. The fix was not to rely on num_vertices or utilize any other requirement of graph types modeling the VertexListGraph concept.
So, even though the template type parameter is named VertexListGraph, it should just work with graph types that only model the IncidenceGraph concept.