c++ - Boost 图形库的性能 vertex_descriptor

Question

我对用于访问图中顶点的 vertex_descriptor 有疑问。在我自己之前的一个实现中，我在顶点上使用了指针，就像一种直接访问顶点的方法。如果我想通过整数或其他方式访问 IDVertex，我可以实现一个映射。

但是在 BGL 中，我不明白为什么 vertex_descriptor 是一个整数？我知道它对 vector 有意义。但是如果我想使用像 10^6 这样的大量顶点并且能够删除集合中的任何顶点，我会使用 map 。另外，在我的游戏中，我希望能够通过更符合逻辑的指针整数来引用每个节点？

BGL 如何将整数与 no_random_access_container 中的顶点链接起来，例如 std::set ？访问方法总是 log(n) 否？如果有一种机制可以在不保留 vertex_descirptor 的情况下直接在顶点上保留句柄，您能解释一下吗？

抱歉我的英语不好;)

Answer 1

当顶点容器策略定义为vecS、setS或listS时，vertex_descriptor成为相应容器中的[“value_type”指向的]迭代器。 vertex_iterator 类型通常是此容器中的迭代器类型。

这意味着对顶点的访问始终是 O(1)。在 setS 的情况下添加和删除一个新顶点将花费 O(logN)，在 listS 或 vecS 的情况下为 O(1)。对于 vecS 而不是 listS 或 setS 的情况，删除一个顶点将使其他一些顶点无效。有关详细信息，请参阅 adjacency graph page 中的迭代器和描述符稳定性/失效部分.

关于您的其他问题。如果您想直接在顶点上保留指向数据的(指针)，可以将其添加为顶点属性。

您经常需要在数据和图形顶点之间建立某种一对一的映射。将直接映射保留为例如 boost::unordered_set 并将逆映射作为每个顶点的属性会很方便。