为什么图形的C++数据结构隐藏了连续的整数索引？

Question

有向图和无向图的数据结构具有根本重要性.公知和广泛使用的实现方式中,如Boost图库和柠檬被设计为使得节点和边的连续整数索引不暴露于经由接口用户.

相反,用户通过(小)代表对象识别节点和边缘.一个优点是当节点和边缘的索引由于从图形中移除边缘或节点而改变时,这些对象被自动更新.

在我看来(!),这个优势被高估了.用户通常将节点和/或边缘的代表性对象存储在容器中,例如,std::vector.现在,如果从图形中移除节点或边缘并且它们的代表对象变得无效,则用户需要忽略该向量或重新排列向量以便保持有效的整数索引连续,即,完全执行设计所应的簿记.做不必要的.

因此,我的问题是:设计选择(隐藏用户的节点和边缘的连续整数索引)是否还有其他优点？

Answer 1

我不能代表柠檬图，但对于增强图，我认为主要目标是通用的。因此，抽象出顶点（边）访问有助于实现该目标。

\n\n

文档中指出，boost graph 基于 Dietmar K\xc3\xbchl\ 的关于通用图算法的硕士论文。（请参阅我对 BGL 是否仍需要属性映射？的回答）。因此，该库的主要目标是通用和可扩展。封装访问的选择是从图形表示中抽象算法的一部分。对我来说，连续整数索引是一个实现细节。

\n\n

Boost 不会对您将如何使用图表或哪些性能权衡对您很重要做出任何假设。它允许您选择（或实施）最适合您需求的容器。

\n\n

如果你想打破这个封装，你可以随意这样做。事实上，我最常见的 boost graph 用法涉及vecS容器和 a vectorof structs。我通常使用尺寸固定的图表。我可以轻松地使用 a mapof vertex_descriptors （或edge_descriptors） 来实现相同的目标。

\n\n

总而言之，我想说，这与其说是一种设计选择，不如说是实现通用这一更广泛目标的结果。因此，隐藏访问权限的好处是更通用。

\n