围绕 Boost Graph 库中的捆绑属性进行设计
Designing around bundled properties in the Boost Graph Library
我正在将一些图形代码从 Python (networkx) 移植到 C++ (BGL) 中。在我的 Python 代码中，图的顶点和边是实现已建立接口的客户端定义对象；我继续对它们调用一堆方法。一切都很好。
天真地，BGL 似乎是为了支持与 "bundled properties." 类似的设计模式。这些基本上允许通过传递某些模板参数来定义顶点和边的自定义类型：
adjacency_list<OutEdgeList, VertexList,
Directed, VertexProperties,
EdgeProperties, GraphProperties,
EdgeList>
此处的自定义顶点和边类型由VertexProperties和EdgeProperties给出。
在处理这个端口时，我注意到一些事情让我觉得也许 BGL 的捆绑属性接口实际上只是为了支持（或多或少）不可变类型：
边和顶点"descriptors"
如果您将某些内容放入图表中，您会得到一个 "descriptor"，您必须使用它从那里引用它。有边和顶点的描述符，它们是图的 "keys"——实现为不可变的。所以如果你有一个顶点并且你想找到相邻的顶点，你必须（a）获取当前顶点描述符，（b）使用 BGL 方法找到它的邻居的描述符，最后（c）引用每个邻居通过他们各自的描述符。
所有这些簿记的最终结果是显然需要额外的容器——std::map，比如说——提供从顶点和边的反向查找（同样，类型 VertexProperty 和 EdgeProperty) 到他们的描述符。
"BGL isn't meant to store pointers."
我在 a similar SO question 中发现了这一说法，但无法在任何地方的 Boost 文档中对其进行验证。从随后的讨论中，我只能推测约束实际上可能更强一些："BGL isn't meant to directly reference the heap." 不过，这似乎并不完全合理，因为容器类型是可配置的（OutEdgeList 和 VertexList, above) 和默认的标准东西，比如向量。
我是 BGL n00b，我无法理解捆绑属性的意图。 （而且，坦率地说，我对一般的编程模型感到有点不知所措——"properties"、"concepts"、"traits"、"descriptors"、AHHHH！) 问题：
BGL 图是否有效地 支持 VertexProperty 和 EdgeProperty 的复杂且可能是堆绑定类型？或者这些是不可变数据的轻量级容器？
如果是前者，有没有办法绕过所有的描述符记账？
如果是后者，那么 "right way" 处理我们可能想要粘贴在 BGL 图中的大型、复杂的东西是什么？
- Do BGL graphs efficiently support complex and possibly heap-bound types for VertexProperty and EdgeProperty? Or are these meant to be lightweight containers for immutable data?
当然可以。你可以随心所欲地做。以防万一：您可以使捆绑包包含一个（不可变或可变）指针，指向分配给堆的 "complex" 类型，当然，它是完全可变的。现在，
我建议使用您首选的所有权适配器（unique_ptr、scoped_ptr、shared_ptr，等等）。看看 std::string：它也是 "heap based"，但您从不担心在 属性 捆绑包中使用它，对吗？
- If the former, is there any way to get around all the descriptor bookkeeping?
没有严格意义上的 "descriptor bookkeeping"。 可能取决于图形模型。但总的来说，描述符实际上是底层容器迭代器模型的抽象（并不是说这可能是跨多个容器的迭代器，例如 edges(EdgeListgraph) 而不是 out_edges(v, IncidenceGraph) adjacency_list<>.
重点是将逻辑与存储模型的假设分离开来。即使有一些非常难看的 void* 传递，编译器也应该将其编译为与直接迭代器访问相同的代码。从这个意义上说，"bookkeeping" 通常是 感知的 ，并且您可能会接受具有额外概念层的 心理负担 。
- If the latter, what's the "right way" to deal with large, complicated things that we might want to stick in a BGL graph?
糟糕。我想我不小心在 1 下解决了这个问题。最简单的使用方法可能是引用共享。您的具体情况可能允许更有效的解决方案。
大写字母选择
- "BGL isn't meant to store pointers."
好吧，也许不是捆绑包。即使在这里，它完全取决于你如何管理足尖 ownership/lifetime。
我认为链接的答案非常好。和我上面说的有共鸣。
- So if you have a vertex and you want to find neighboring vertices, you have to (a) get the current vertex descriptor, (b) use BGL methods to find the descriptors of its neighbors, and finally (c) reference each of the neighbors via their respective descriptors.
大多数 BGL 算法依赖于 vertex_index_t 属性 的存在（或要求将一个指定为参数）以确保这些是低成本操作。事实上，如果你使用 vecS 那么顶点索引就是顶点向量的索引，所以反向和正向查找非常简单。 （您可以随时查看启用优化后生成的程序集，看看是否有任何惊喜）。
这个答案可能会鼓舞人心：Boost Graph Library: possible to combine Bundled Properties with Interior Properties?
TL;DR/摘要
我有一种来自 Python 的感觉，您可能低估了在模板繁多的通用库代码中优化 C++ 的编译器。
当你在实践中筛选通用机制层时冒出的东西在编译时蒸发了。当然，这样做的缺点是很难看穿抽象。但这也意味着功能和抽象级别不会受到影响。
BGL 是一个库，您只需更改很少的代码即可切换到完全不同的图形模型、存储布局等。这里的目标不是 "ease of use" 或 "do what I mean"（为此使用 Java 或 python）。
我们的目标是选择 C++/不/通过将每个实现细节硬编码到整个代码库中来消除所有敏捷性。相反，在库概念的层面上工作，并受益于你保留的自由 experiment/change 随着需求的发展你的方法。
我正在将一些图形代码从 Python (networkx) 移植到 C++ (BGL) 中。在我的 Python 代码中，图的顶点和边是实现已建立接口的客户端定义对象；我继续对它们调用一堆方法。一切都很好。
天真地，BGL 似乎是为了支持与 "bundled properties." 类似的设计模式。这些基本上允许通过传递某些模板参数来定义顶点和边的自定义类型：
adjacency_list<OutEdgeList, VertexList,
Directed, VertexProperties,
EdgeProperties, GraphProperties,
EdgeList>
此处的自定义顶点和边类型由VertexProperties和EdgeProperties给出。
在处理这个端口时，我注意到一些事情让我觉得也许 BGL 的捆绑属性接口实际上只是为了支持（或多或少）不可变类型：
边和顶点"descriptors"
如果您将某些内容放入图表中，您会得到一个 "descriptor"，您必须使用它从那里引用它。有边和顶点的描述符，它们是图的 "keys"——实现为不可变的。所以如果你有一个顶点并且你想找到相邻的顶点，你必须（a）获取当前顶点描述符，（b）使用 BGL 方法找到它的邻居的描述符，最后（c）引用每个邻居通过他们各自的描述符。
所有这些簿记的最终结果是显然需要额外的容器——
std::map，比如说——提供从顶点和边的反向查找（同样，类型VertexProperty和EdgeProperty) 到他们的描述符。"BGL isn't meant to store pointers."
我在 a similar SO question 中发现了这一说法，但无法在任何地方的 Boost 文档中对其进行验证。从随后的讨论中，我只能推测约束实际上可能更强一些："BGL isn't meant to directly reference the heap." 不过，这似乎并不完全合理，因为容器类型是可配置的（
OutEdgeList和VertexList, above) 和默认的标准东西，比如向量。
我是 BGL n00b，我无法理解捆绑属性的意图。 （而且，坦率地说，我对一般的编程模型感到有点不知所措——"properties"、"concepts"、"traits"、"descriptors"、AHHHH！) 问题：
BGL 图是否有效地 支持
VertexProperty和EdgeProperty的复杂且可能是堆绑定类型？或者这些是不可变数据的轻量级容器？如果是前者，有没有办法绕过所有的描述符记账？
如果是后者，那么 "right way" 处理我们可能想要粘贴在 BGL 图中的大型、复杂的东西是什么？
- Do BGL graphs efficiently support complex and possibly heap-bound types for VertexProperty and EdgeProperty? Or are these meant to be lightweight containers for immutable data?
当然可以。你可以随心所欲地做。以防万一：您可以使捆绑包包含一个（不可变或可变）指针，指向分配给堆的 "complex" 类型，当然，它是完全可变的。现在，
我建议使用您首选的所有权适配器（unique_ptr、scoped_ptr、shared_ptr，等等）。看看 std::string：它也是 "heap based"，但您从不担心在 属性 捆绑包中使用它，对吗？
- If the former, is there any way to get around all the descriptor bookkeeping?
没有严格意义上的 "descriptor bookkeeping"。 可能取决于图形模型。但总的来说，描述符实际上是底层容器迭代器模型的抽象（并不是说这可能是跨多个容器的迭代器，例如 edges(EdgeListgraph) 而不是 out_edges(v, IncidenceGraph) adjacency_list<>.
重点是将逻辑与存储模型的假设分离开来。即使有一些非常难看的 void* 传递，编译器也应该将其编译为与直接迭代器访问相同的代码。从这个意义上说，"bookkeeping" 通常是 感知的 ，并且您可能会接受具有额外概念层的 心理负担 。
- If the latter, what's the "right way" to deal with large, complicated things that we might want to stick in a BGL graph?
糟糕。我想我不小心在 1 下解决了这个问题。最简单的使用方法可能是引用共享。您的具体情况可能允许更有效的解决方案。
大写字母选择
- "BGL isn't meant to store pointers."
好吧，也许不是捆绑包。即使在这里，它完全取决于你如何管理足尖 ownership/lifetime。
我认为链接的答案非常好。和我上面说的有共鸣。
- So if you have a vertex and you want to find neighboring vertices, you have to (a) get the current vertex descriptor, (b) use BGL methods to find the descriptors of its neighbors, and finally (c) reference each of the neighbors via their respective descriptors.
大多数 BGL 算法依赖于 vertex_index_t 属性 的存在（或要求将一个指定为参数）以确保这些是低成本操作。事实上，如果你使用 vecS 那么顶点索引就是顶点向量的索引，所以反向和正向查找非常简单。 （您可以随时查看启用优化后生成的程序集，看看是否有任何惊喜）。
这个答案可能会鼓舞人心：Boost Graph Library: possible to combine Bundled Properties with Interior Properties?
TL;DR/摘要
我有一种来自 Python 的感觉，您可能低估了在模板繁多的通用库代码中优化 C++ 的编译器。
当你在实践中筛选通用机制层时冒出的东西在编译时蒸发了。当然，这样做的缺点是很难看穿抽象。但这也意味着功能和抽象级别不会受到影响。
BGL 是一个库，您只需更改很少的代码即可切换到完全不同的图形模型、存储布局等。这里的目标不是 "ease of use" 或 "do what I mean"（为此使用 Java 或 python）。
我们的目标是选择 C++/不/通过将每个实现细节硬编码到整个代码库中来消除所有敏捷性。相反，在库概念的层面上工作，并受益于你保留的自由 experiment/change 随着需求的发展你的方法。