c++ - 为什么 BGL A* 需要隐式图来对 VertexListGraph 进行建模？

Question

我之前的一个更具体的后续问题 BGL Interior properties for implicit graph

Boost BGL 有一个 A* 算法的版本，它应该与隐式图一起工作，即 astar_search_no_init() 函数。隐式图可以建模为 IncidenceGraphs。 documentation of A*说“请注意 astar_search_no_init() 必须用于隐式图；基本的 astar_search() 函数需要一个模拟顶点列表图概念的图。两个版本还需要图类型来模拟关联图概念”。

这是否意味着该图不必必须对顶点列表图概念建模？如果是这种情况，我是否遗漏了什么，因为我无法找到 任何 版本的函数 astar_search_no_init() 将使用 IncidenceGraphs？有两个版本的 astar_search_no_init() 可用，它们似乎都适用于 VertexListGraphs。我使用的是 Boost 1.48，A* 在文件 astar_search.hpp 中。

我不明白要求隐式图首先对顶点列表图建模有什么意义。该文档对我来说非常困惑和误导。有什么想法吗？

Answer 1

在 r50803 中添加了对隐式图的支持2009 年 1 月 27 日修复Bug #829 .解决方法是不依赖于 num_vertices 或利用对 VertexListGraph 建模的图形类型的任何其他要求。概念。

因此，即使模板类型参数名为 VertexListGraph，它也应该只适用于仅对 IncidenceGraph 建模的图形类型概念。