为什么 BGL A* 需要隐式图来建模 VertexListGraph？
我之前的一个更具体的后续问题隐式图的 BGL 内部属性
Boost BGL 有一个版本的 A* 算法，应该可以处理隐式图，即 astar_search_no_init() 函数。隐式图可以建模为 IncidenceGraph。 A* 的文档 说“请请注意，astar_search_no_init() 必须用于隐式图；基本的 astar_search() 函数需要一个对顶点列表图概念进行建模的图，这两个版本还需要图类型来对顶点列表图进行建模。发生率图概念”。
这是否意味着该图不必必须对顶点列表图概念进行建模？如果是这种情况，我是否遗漏了一些东西，因为我无法找到使用 IncidenceGraphs 的函数 astar_search_no_init() 的任何版本？有两个版本的 astar_search_no_init() 可用，并且它们似乎都适用于 VertexListGraphs。我使用的是 Boost 1.48，A* 位于文件 astar_search.hpp 中。
我不明白首先要求隐式图对顶点列表图进行建模有什么意义。该文档对我来说非常混乱和误导。有什么想法吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
2009 年 1 月 27 日在 r50803 中添加了对隐式图的支持，以修复 < a href="https://svn.boost.org/trac/boost/ticket/829" rel="nofollow">错误#829。修复方法是不依赖 num_vertices 或利用图形类型建模的任何其他要求 VertexListGraph 概念。
因此，即使模板类型参数名为
VertexListGraph，它也应该只适用于仅对 IncidenceGraph 概念。Support for implicit graphs was added in r50803 on January 27, 2009, to fix Bug #829. The fix was not to rely on
num_verticesor 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.图概念本身是有序的；这是一个很好的图形概念图 ;)
正如您所看到的，事实上，
发生率概念与astar_search_no_init()所需的图顶点列表图概念无关。即每个概念都可以独立建模。因此，您的图表仅对第一个概念进行建模就足够了。请注意，只为
astar_search_no_init()建模顶点列表图是不的，尽管它看起来可行。顶点列表图概念不是关联图的特例。 可以对双向图进行建模；这是关联图的一个特例`The graph concepts are ordered themselves; here's a nice graph of graph concepts ;)
As you can see, the fact that the the
Incidence Graphconcept required byastar_search_no_init()is unrelated toVertex List Graphconcept. I.e. each concept can be modelled independently. So, it's sufficient for your graph to model only the first concept.Note that it's not OK to only model
Vertex List Graphforastar_search_no_init(), even though it may seem to work. TheVertex List Graphconcept is not a special case ofIncidence Graph. It would be OK to modelBidirectional Graph; that is a special case of Incidence Graph`