首页 文章

设计Boost图库中的捆绑属性

提问于
浏览 次
8

我正在从Python（networkx）和C（BGL）中移植一些图形代码 . 在我的Python代码中，图的顶点和边是实现已 Build 接口的客户端定义的对象;我继续在他们身上调用一堆方法 . 一切都好 .

天真地看来，BGL似乎意味着支持具有“捆绑属性”的类似设计模式 . 这些基本上允许通过传递某些模板参数来定义顶点和边的自定义类型：

adjacency_list<OutEdgeList, VertexList,
               Directed, VertexProperties,
               EdgeProperties, GraphProperties,
               EdgeList>

这里的自定义顶点和边类型由 VertexProperties 和 EdgeProperties 给出 .

在这个端口上工作时我注意到了一些让我觉得可能BGL的捆绑属性接口实际上只是支持（或多或少）不可变类型的东西：

  • Edge and vertex "descriptors"

如果你把某些东西放到图表中，你会得到一个“描述符”，你必须用它来从那里引用它 . 有边和顶点的描述符，它们是图中的“键” - 实现为不可变的 . 因此，如果您有一个顶点并且想要找到相邻顶点，则必须（a）获取当前顶点描述符，（b）使用BGL方法查找其邻居的描述符，最后（c）引用每个邻居通过各自的描述符 .

所有这些簿记的最终结果显然需要额外的容器 - 比如说 - 提供从顶点和边缘（类型 VertexProperty 和 EdgeProperty ）到其描述符的反向查找 .

  • "BGL isn't meant to store pointers."

我在a similar SO question中发现了这个说法，但是因为容器类型是可配置的（ OutEdgeList 和 VertexList ，上面）和默认标准的东西，比如矢量，所以看起来完全合理 .

我'm a BGL n00b and am having trouble understanding what'用于捆绑属性 . （而且，坦率地说，我对编程模型感到有些不知所措 - "properties"，"concepts"，"traits"，"descriptors"，AHHHH！）问题：

  • BGL图是否有效地支持 VertexProperty 和 EdgeProperty 的复杂和可能的堆绑定类型？或者这些是不可变数据的轻量级容器？

  • 如果是前者，有没有办法解决所有描述符簿记？

  • 如果是后者，处理大型复杂事物的“正确方法”是什么，我们可能想要坚持BGL图？

c++ boost graph boost-graph

1 回答

  • 6

    BGL图是否有效地支持VertexProperty和EdgeProperty的复杂和可能的堆绑定类型？或者这些是不可变数据的轻量级容器？

    当然 . 无论如何你都可以做到 . 以防万一：你可以让bundle拥有一个（不可变的或可变的）指向堆分配的“复杂”类型的指针 - 当然 - 它是完全可变的 . 现在，

    我建议使用您首选的所有权适配器（unique_ptr，scoped_ptr，shared_ptr，什么不是） . 看看 std::string ：它也是"heap based"，但你并不担心在一个属性包中使用它，是吗？

    如果是前者，有没有办法绕过所有描述符簿记？

    没有严格的"descriptor bookkeeping" . 可能取决于图模型 . 但一般来说，描述符实际上是底层容器迭代器模型的抽象（并不是说这可能是跨多个容器的迭代器，例如 edges(EdgeListgraph) 而不是 out_edges(v, IncidenceGraph) for adjacency_list<> .

    关键是要将逻辑与存储模型的假设分离 . 即使有一些非常难看的 void* 传递，编译器也应该将其编译为与直接迭代器访问相同的代码 . 在这个意义上，"bookkeeping"通常是感性的，你很可能会接受额外的概念层 .

    如果是后者，那么处理大型复杂事物的“正确方法”是什么？我们可能希望将这些事物放在BGL图中？

    哎呀 . 我想我在1下意外地解决了这个问题 . 使用绝对最简单的事情可能是refcounted sharing . 您的具体情况可能会提供更有效的解决方案 .

    CAPITA SELECTA

    “BGL并不意味着存储指针 . ”

    好吧，也许不是捆绑 . 即使在这里，它也完全取决于你如何管理所有者/所有人的生命 .

    我认为相关的答案非常好 . 它与我上面所说的相矛盾 .

    因此，如果您有一个顶点并且想要找到相邻顶点，则必须（a）获取当前顶点描述符，（b）使用BGL方法查找其邻居的描述符，最后（c）引用每个顶点描述符 . 邻居通过各自的描述符 .

    大多数BGL算法依赖于 vertex_index_t 属性的存在（或者需要指定一个属性作为参数）以确保这些是低成本操作 . 实际上，如果使用 vecS ，则顶点索引是顶点向量的索引，因此反向和正向查找非常简单 . （您始终可以查看生成的程序集，并启用优化以查看是否有任何意外） .

    这个答案可能是鼓舞人心的：Boost Graph Library: possible to combine Bundled Properties with Interior Properties?

    TL; DR /摘要

    我有一种来自Python的感觉，你可能会在模板繁重的通用库代码中低估C优化编译器 .

    当你在实践中筛选通用机械层时，在编译时蒸发的东西会蒸发掉 . 当然，这样做的缺点是难以看清抽象 . 但这也意味着功率和抽象级别不会受到影响 .

    BGL是一个库，允许您切换到完全不同的图形模型，存储布局等，只需很少的代码更改 . 这里的目标不是“易用性”或“做我的意思”（使用Java或python） .

    目标是通过将每个实现细节硬编码到整个代码库中来选择C / not /删除所有敏捷性 . 相反，在图书馆概念层面工作，并从您保留的自由中获益，以便随着需求的变化来尝试/改变您的方法 .

    回复于

相关问题