有向图和无向图的数据结构至关重要。Boost Graph Library和Lemon等知名且广泛使用的实现的设计使得节点和边的连续整数索引不会通过接口暴露给用户。
相反，用户通过（小）代表对象来识别节点和边。一个优点是，当节点和边的索引由于从图中删除边或节点而发生变化时，这些对象会自动更新。
在我看来（！），这个优势被高估了。用户通常会将节点和/或边的代表对象存储在容器中，例如std::vector. 现在，如果从图中删除节点或边并且它们的代表对象变得无效，则用户需要忽略这一点或重新排列向量以保持有效的整数索引连续，即完全按照设计应该做的簿记使不必要的。
因此，我的问题是：设计选择（对用户隐藏节点和边的连续整数索引）是否有其他优势？
我不能说柠檬图，但对于提升图，我认为主要目标是通用的。因此，抽象出顶点（边）访问有助于实现该目标。
文档中指出，boost graph 是基于 Dietmar Kühl 的关于通用图算法的硕士论文。（请参阅我对 BGL 是否仍然需要属性图的回答？）。所以库背后的主要目标是通用和可扩展的。封装访问的选择是从图形表示中抽象算法的一部分。对我来说，连续整数索引是一个实现细节。
Boost 不会对您将如何使用图表或哪些性能权衡对您很重要做出任何假设。它允许您选择（或实施）最适合您需求的容器。
如果你想打破这种封装，你可以自由地这样做。其实我最常使用的boost graph涉及到vecScontainers和a vectorof structs。我通常使用大小固定的图表。我可以很容易地对对象使用 a mapof vertex_descriptors（或edge_descriptors）来实现相同的目标。
所以总而言之，我想说这与其说是一种设计选择，不如说是实现更广泛的通用目标的结果。所以隐藏访问的好处是更通用。
（我在 Java 世界中很自在，但希望给出一个不关注特定库的答案是可以的）
这种抽象有几个可能的优点。问题中已经提到了最重要的问题之一：当必须维护索引时，在图形中执行修改时的一致性要困难得多。
这可能很难的原因在于不同的可能图形表示：如果内部表示仅（并且总是）由Vertex和Edge对象的随机访问列表组成，则维护一致的索引可能很容易。但对于其他表示，确定索引可能很困难。
这直接关系到第二个主要优点：一个是可以自由使用图形接口的不同实现。boost 文档的Review of Elementary Graph Theory中的“Graph Data Structures”部分列出了 BGL 已经提供的几种数据结构（每个人都可以添加自己的实现）。某些操作的运行时间以 Big-O 表示法给出，并且可以看到它们在不同的数据结构之间有很大差异。
因此可以很容易地想象不同的实现更适合某些任务。例如，考虑一个算法经常需要检查一个特定的顶点是否包含在一个图中。对于索引（即list基于 - 的）顶点存储，每个测试都需要O(n)。使用set基于 - 的顶点存储，这可以在O(1)中完成- 但在这种情况下根本没有合理的“索引”。
此外，如图形概念概述中所述：
事实上，BGL 接口甚至不需要使用数据结构来实现，因为对于某些问题，基于某些函数隐式定义图会更容易或更有效。
因此，即使图形甚至不存在于内存中也建议存在“索引访问”可能会阻碍这种纯粹的功能实现。