Bri*_*ion 8 c++ boost graph boost-graph
我正在从Python(networkx)和C++(BGL)中移植一些图形代码.在我的Python代码中,图的顶点和边是实现已建立接口的客户端定义的对象; 我继续在他们身上调用一堆方法.一切都好.
天真地看来,BGL似乎是为了支持具有"捆绑属性"的类似设计模式.这些基本上允许通过传递某些模板参数来定义顶点和边的自定义类型:
adjacency_list<OutEdgeList, VertexList,
Directed, VertexProperties,
EdgeProperties, GraphProperties,
EdgeList>
这里的自定义顶点和边类型由VertexProperties和给出EdgeProperties.
在这个端口上工作时我注意到一些事情让我觉得BGL的捆绑属性接口实际上只是为了支持(或多或少)不可变类型:
边和顶点"描述符"
如果你把某些东西放到图表中,你会得到一个"描述符",你必须用它来从那里引用它.有边和顶点的描述符,它们是图中的"键" - 实现为不可变的.因此,如果您有一个顶点并且想要找到相邻顶点,则必须(a)获取当前顶点描述符,(b)使用BGL方法查找其邻居的描述符,最后(c)引用每个邻居通过各自的描述符.
所有这些簿记的最终结果是显然需要额外的容器 - std::map比如说 - 提供从顶点和边缘(再次,类型VertexProperty和EdgeProperty)到它们的描述符的反向查找.
"BGL并不意味着存储指针."
我在一个类似的SO问题中发现了这个主张,但是无法在任何地方的Boost文档中对其进行验证.从随后的讨论中我可以推测,约束实际上可能更强一些:"BGL并不意味着直接引用堆." 但这似乎并不完全合理,因为容器类型是可配置的(OutEdgeList以及VertexList上面的)和默认的标准内容,如矢量.
我是一个BGL的n00b和我无法理解有什么打算捆绑特性.(坦率地说,我觉得编程模型有点不知所措 - "属性","概念","特征","描述符",AHHHH!)问题:
不要BGL图有效地支持复杂和可能堆结合的类型VertexProperty和EdgeProperty？或者这些是不可变数据的轻量级容器？
如果是前者,有没有办法绕过所有描述符簿记？
如果是后者,处理大型复杂事物的"正确方法"是什么,我们可能想要坚持BGL图？
- BGL图是否有效地支持VertexProperty和EdgeProperty的复杂和可能的堆绑定类型？或者这些是不可变数据的轻量级容器？
当然.无论如何你都可以做到.以防万一:你可以让bundle拥有一个(不可变的或可变的)指向堆分配的"复杂"类型的指针 - 当然 - 它是完全可变的.现在,
我建议使用您首选的所有权适配器(unique_ptr,scoped_ptr,shared_ptr,什么不是).看看std::string:它也是"基于堆的",但你不担心在属性包中使用它,是吗？
- 如果是前者,有没有办法绕过所有描述符簿记？
没有严格的"描述符簿记".有可能视图模型是.但在一般情况下,描述符实际上是一个抽象的基础容器迭代器模式(不,这可能是跨多个容器迭代器,例如,edges(EdgeListgraph)而不是out_edges(v, IncidenceGraph)为adjacency_list<>.
关键是要将逻辑与存储模型的假设分离.即使有一些非常难看的void*传递,编译器应该将其编译为与直接迭代器访问相同的代码.在这个意义上的"簿记"通常感性,你就可能捡心理负荷有额外的概念层.
- 如果是后者,处理大型复杂事物的"正确方法"是什么,我们可能想要坚持BGL图？
哎呀.我想我在1下意外地解决了这个问题.使用的绝对最简单的事情可能是refcounted sharing.您的具体情况可能会提供更有效的解决方案.
- "BGL并不意味着存储指针."
好吧,也许不是捆绑.即使在这里,它也完全取决于你如何管理指定者的所有权/生命周期.
我认为相关的答案非常好.它与我上面所说的相矛盾.
- 因此,如果您有一个顶点并且想要找到相邻顶点,则必须(a)获取当前顶点描述符,(b)使用BGL方法查找其邻居的描述符,最后(c)引用每个邻居通过各自的描述符.
大多数BGL算法依赖于vertex_index_t属性的存在(或者需要指定一个属性作为参数)以确保这些是低成本操作.事实上,如果你使用vecS那么顶点索引是顶点向量的索引,所以反向和正向查找非常简单.(您始终可以查看生成的程序集,并启用优化以查看是否有任何意外).
这个答案可能是鼓舞人心的:Boost Graph Library:可以将Bundled Properties与Interior Properties结合起来吗？
我有一种来自Python的感觉,你可能会在模板繁重的通用库代码中低估C++优化编译器.
当你在实践中筛选通用机械层时,在编译时蒸发的东西会蒸发掉.当然,这样做的缺点是难以看清抽象.但这也意味着功率和抽象级别不会受到影响.
BGL是一个库,允许您切换到完全不同的图形模型,存储布局等,只需很少的代码更改.这里的目标不是"易用性"或"做我的意思"(使用Java或python).
目标是通过将每个实现细节硬编码到整个代码库中来选择C++/not /删除所有敏捷性.相反,在图书馆概念层面工作,并从您保留的自由中获益,以便随着需求的变化尝试/改变您的方法.