如果BGL中的add_vertex检查顶点的存在 [英] if add_vertex in BGL checks for the existence of the vertex

问题描述

在BGL中，add_edge检查边是否已存在. add_vertex是否有相同的机制? 例如，如果我们有一个包含某些bundled_properties的顶点，然后将其添加到图形中，然后将其连接到一条边，那么如果存在相似的顶点，该顶点是否会被复制?

In BGL, add_edge checks if the edge already exists. Is there the same mechanism for add_vertex? For example, if we have a vertex with some bundled_properties, and then we add it to the graph, and then connect an edge to it, would be this vertex duplicated if there was a similar vertex?

推荐答案

当两个顶点具有相似的属性(内部或捆绑)时，它们是相同的顶点，并且add_vertex而不是将其与新索引添加在一起，不应该只是将索引返回到现有的那个吗? – Bruce 11分钟前

如果您有两个具有相似属性"的顶点，则您决定是否要添加具有这些属性的另一个顶点.

If you have two vertices with "similar properties", you decide whether you want to add another vertex with those properties or not.

如果我们有一个具有一些bundled_properties的顶点，然后将其添加到图形中，然后将其连接到一条边，如果存在相似的顶点，该顶点是否会重复?

if we have a vertex with some bundled_properties, and then we add it to the graph, and then connect an edge to it, would be this vertex duplicated if there was a similar vertex?

您可以通过引用vertex_descriptor来添加边.没有办法将边连接到顶点属性".因此，add_edge不能使用某些属性意外地创建新顶点.

You add edges by referring to vertex_descriptors. There is no way to "connect an edge to vertex properties". So, add_edge cannot accidentally create a new vertex using some property.

注意:可能会有混淆，因为将vectorS²用于顶点容器选择器使您可以通过引用可能不存在的顶点描述符来添加边.实际上，它并没有像扩展顶点ID/描述符的有效域"那样添加顶点".例如:

Note: There might be confusion because using vectorS² for vertex container selector lets you add edges by referring to potentially non-existing vertex descriptors. Really, that doesn't "add vertices" as much as it "extends the valid domain for vertex ids/descriptors". E.g.:

adjacency_list<> g;
add_edge(10, 11, g);

并没有真正添加12个顶点.它将顶点id域扩展为包含值11. 在Coliru上直播

doesn't really add 12 vertices. It extends the vertex id domain to encompass the value 11. Live On Coliru

让我们看一下add_vertex:

调用为add_vertex，它添加了一个顶点.实际上，通常不为它们插入属性，这只是一种方便.

Let's look at add_vertex:

The call is add_vertex and it adds a vertex. In fact, you don't usually insert properties for them, that's merely a convenience.

之间没有根本区别:

vertex_descriptor v = add_vertex(g);

g[v] = vertexProperties;

还有

vertex_descriptor v = add_vertex(vertexProperties, g);

在两种情况下，您都会总是获得一个新的，唯一的顶点描述符，并将其属性设置为特定值.

In both cases you will always get a new, unique, vertex descriptor, and have its properties set to a specific value.

add_edge真的不同吗?与add_vertex一样，两者之间没有区别:

Is add_edge really different? Like with add_vertex there is no difference between:

vertex_descriptor from {/*...*/}, to {/*...*/};
edge_descriptor e = add_edge(from, to, g).first;

g[e] = edgeProperties;

还有

edge_descriptor e = add_edge(from, to, edgeProperties, g).first;

您会注意到，两者(可能)都添加了一条边，返回其描述符，并且都将属性设置为特定值.

You will note that both (possibly) add an edge, returning its descriptor, and both set the properties to specific values.

这里的重点是adjacency_list不会 知道或关心这些属性.它们为您添加信息，或对某些算法有用，但它们与adjacency_list建模的图概念不相关.

The important point here is that adjacency_list does not know or care about the properties. They add information for you, or useful for certain algorithms, but they are not relevant to the graph concept modeled by adjacency_list.

为什么要add_edge 有条件地添加?

这是因为adjacency_list使用的策略隐含需要检查的不变性:

Why does add_edge conditionally add?

That's because the adjacency_list uses strategies that imply invariants that need to be checked:

• 如果您的边缘容器选择恰好是setS，其插入方法可能会或可能不会插入新边； adjacency_lists<>只是将行为¹转发给add_edge
• 如果您的adjacency_list也使用undirected或bidirectional，则会在边上放置更多约束(例如，防止在使用setS作为目标的双向图中添加(a->b)和(b->a))边缘容器选择器).

• if your edge-container selection happens to be e.g. setS, its insertion method may or may not insert a new edge; adjacency_lists<> just forwards the behaviour¹ to add_edge
• if your adjacency_list uses undirected or bidirectional as well, this puts extra contraints on edges (e.g. preventing addition of (a->b) as well as (b->a) in a bidirectional graph that uses setS as the edge container selector).

总结:

• add_vertex不会 不 获取任何标识信息，因此不需要检查约束(实际上不能).

• add_vertex does not take any identifying information, hence it doesn't need to check for constraints (in fact, it cannot).

add_edge 确实获取标识信息(端点顶点)，并且可以对照实例化adjacency_list时选择的策略所产生的约束来检查这些信息.

add_edge does take identifying information (the endpoint vertices) and it can check these against the constraints that arise from the strategies that you chose when instantiating the adjacency_list.

---

¹例如优雅地避免边缘加倍

---

¹ e.g. to elegantly avoid doubled edges

²或其他可能的随机访问顶点容器选择器，它们具有作为隐式顶点ID

² or possibly other Random Access vertex container selectors, that have integral vertex descriptors that act as implicit vertex id

这篇关于如果BGL中的add_vertex检查顶点的存在的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！