为什么图的C ++数据结构隐藏连续的整数索引? [英] Why do C++ data structures for graphs hide contiguous integer indices?

问题描述

有向图和无向图的数据结构至关重要.众所周知且广泛使用的实现，例如 Boost Graph库和柠檬的设计使得结点和边的连续整数索引不会通过该界面向用户公开.

Data structures for directed and undirected graphs are of fundamental importance. Well-known and widely-used implementations such as the Boost Graph Library and Lemon are designed such that the contiguous integer indices of nodes and edges are not exposed to the user via the interface.

相反，用户通过(小的)代表性对象识别节点和边缘.优点之一是，由于从图中删除了边或节点，当节点和边的索引改变时，这些对象会自动更新.

Instead, the user identifies nodes and edges by (small) representative objects. One advantage is that these objects are updated automatically when the indices of nodes and edges change due to the removal of edges or nodes from the graph.

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

In my opinion (!), this advantage is overrated. Users will typically store the representative objects of nodes and/or edges in a container, e.g., an std::vector. Now, if nodes or edges are removed from the graph and their representative objects become invalid, the user needs to either ignore this or rearrange the vector so as to keep valid integer indices contiguous, i.e., do exactly the bookkeeping that the design was supposed to make unnecessary.

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

Hence, my question is: Does the design choice (of hiding the contiguous integer indices of nodes and edges from the user) have other advantages?

推荐答案

我不能说柠檬图，但是对于提升图，我认为主要目标是通用.因此，抽象出顶点(边缘)访问权限有助于实现该目标.

I can't speak for Lemon graph, but for boost graph I think the main goal is to be generic. So abstracting away the vertex (edge) access helps to achieve that goal.

文档中指出，升压图基于DietmarKühl关于通用图算法的硕士论文. (请参阅我对 BGL是否仍然需要属性映射的回答?).因此，库背后的主要目标是通用且可扩展.封装访问的选择是从图形表示中抽象算法的一部分.对我来说，连续整数索引是一个实现细节.

It is stated in the documentation that boost graph is based on Dietmar Kühl's Masters Thesis on generic graph algorithms. (See my answer to Do property maps remain necessary for BGL?). So the main goal behind the library is to be generic and extensible. The choice of encapsulating access is part of abstracting the algorithms from the graph representation. To me, continuous integer indices are an implementation detail.

Boost不会对您如何使用图表或哪些性能折衷对您很重要进行任何假设.它使您可以选择(或实现)最适合您需求的容器.

Boost doesn't make any assumptions on how you will use the graph or what performance trade offs are important to you. It lets you choose (or implement) the container that will best fit your needs.

如果您想破坏此封装，则可以随意这样做.实际上，我最常用的升压图使用vecS容器和vector of struct s.我通常使用固定大小的图.我可以轻松地对对象使用vertex_descriptor(或edge_descriptor s)的map来实现相同的目标.

If you want to break this encapsulation, you are free to do so. In fact, my most common use of boost graph involves vecS containers and a vector of structs. I usually work with graphs where the size is fixed. I could just as easily use a map of vertex_descriptors (or edge_descriptors) to objects to achieve the same goal.

因此，总而言之，我要说的不是设计选择，而是实现通用性这一更广泛目标的结果.因此，隐藏访问权限具有更通用的优势.

So in summary, I would say that this not so much a design choice, but rather a consequence of achieving the broader goal of being generic. So the hiding of access has the benefit of being more generic.

这篇关于为什么图的C ++数据结构隐藏连续的整数索引?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！