2

对我之前的隐式图的 BGL 内部属性的一个更具体的后续问题

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

这不是说图不必建模Vertex List Graph 的概念吗？如果是这种情况，我是否遗漏了一些东西，因为我无法找到将使用 IncidenceGraphs 的函数 astar_search_no_init() 的任何版本？有两个版本的 astar_search_no_init() 可用，它们似乎都适用于 VertexListGraphs。我正在使用 Boost 1.48 并且 A* 在文件 astar_search.hpp 中。

我看不出首先要求隐式图对顶点列表图进行建模有什么意义。该文档对我来说非常混乱和误导。有任何想法吗？

4

2 回答 2

2

图概念本身是有序的；这是一个很好的图形概念图；）

提升图概念

如您所见，Incidence Graph所需的概念与概念astar_search_no_init()无关Vertex List Graph。即每个概念都可以独立建模。因此，您的图表仅对第一个概念进行建模就足够了。

请注意，仅对 建模是不可行的，即使它似乎可行。这个概念不是. 可以建模；_ 这是 Incidence Graph 的一个特例`Vertex List Graphastar_search_no_init()Vertex List GraphIncidence GraphBidirectional Graph

于 2011-12-29T09:49:50.670 回答
2

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

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

于 2011-12-29T13:10:00.993 回答