如何配置 boost::graph 以使用我自己的（稳定）顶点索引？

Question

最简单的 boost::adjacency_list 使用 std::size_t 作为底层 vertex_descriptor（索引）。

boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS,
    boost::no_property,
    boost::no_property
>  graph;

一旦我知道了顶点描述符，我就可以快速访问所需的顶点。

auto vertex = graph[idx]; // idx is the veretx descriptor

但是，当图发生变异时，无法保证 vertex_descriptor 保持稳定。

auto v0 = boost::add_vertex(graph);
auto v1 = boost::add_vertex(graph);
auto v2 = boost::add_vertex(graph);

boost::remove_vertex(v0, graph); // v1 and v2 are no longer valid

我希望能够快速找到特定的顶点 - 这意味着我希望避免遍历图结构来搜索我知道存在的顶点。

我的想法是，我可以使用 VertexListS 模板参数的不同选择器以某种方式调整 boost::adjacency_list ，这将允许我使用我自己提供的 vertex_descripor （索引）。

我探索了使用关联容器选择器（例如内置 boost::hash_mapS）的可能性，但似乎我无法控制它在调用 add_vertex 时返回的确切 id。 我希望能够为每个顶点使用我自己的 id (vertex_descriptor)。

我会尝试用我希望能够工作的代码更清楚一点：

// the following type will serve as the vertex_descriptor:
using my_id_type = std::size_t;

struct MyVertex
{
    my_id_type id;
    // some other fields
}

// add vertices with unique identifiers that will also serve as the vertex_descriptors
boost::add_vertex(MyVertex{1111}, graph); // I expect this to return 1111
boost::add_vertex(MyVertex{2222}, graph);
boost::add_vertex(MyVertex{1234}, graph);


boost::remove_vertex(1111, graph); // I expect this to remove the first vertex

// access a specific vertex using its unique, stable descriptor:
auto vertex = graph[1234];

Can this be returned using boost::graph?

Answer 1

这可以使用 boost::graph 来实现吗？

对于 BGL，答案几乎总是“是”。它是现存最深刻的通用图书馆设计之一。

---

令我惊讶的是，adjacency_list 的类型层次结构中出现了一些新内容。显然，现在有一个 named_graph mixin（实际上是 maybe_name_graph），它使用顶点束上的特征来检测“内部名称”。

这意味着你可以接近。尽管顶点描述符不会成为您的 ID，但您可以进行 O(1) 查找。并且该接口有一些便利，因此您可以编写：

add_edge(1111, 2222, g);
add_edge(2222, 1111, g);

注意：

• 查找的摊销时间为 O(1)，因为名称顶点查找基于无序（散列）索引，
• 您会遇到问题（例如如果您意外地使 id 类型与 vertex_descriptor 类型相同（或者如果您的参数具有同样“远”的转换，则 add_edge 的不明确重载）到任一）。
• 据我所知，内部 name 属性不会自动选取为 vertex_index_t 或 vertex_name_t 属性。

步骤#1：图表

struct Vertex {
    size_t      id;
    std::string other = "default-constructed";
};

using Graph =
    boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, Vertex>;

到目前为止，没有什么意外。我

• 选择添加第二个成员 other 只是为了显示它何时/如何获得默认构造的
• opted listS 因为它
  • a.提供参考/描述符稳定性（已删除的顶点除外）
  • b.导致不透明的 vertex_descriptor (void*)，它与重载决策中的 id 类型 (size_t) 不冲突

步骤#2：名称特征

接下来我们向 BGL 教授内部顶点名称。

这纯粹由 Vertex 捆绑包参数化，因此请记住，使用同一捆绑包的不同图形将使用相同名称的特征。

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = size_t;
        result_type const& operator()(Vertex const& bundle) const {
            return bundle.id;
        }
    };
};

template <> struct boost::graph::internal_vertex_constructor<Vertex> {
    struct type {
      private:
        using extract_name_type = typename internal_vertex_name<Vertex>::type;

        using vertex_name_type = typename remove_cv<typename remove_reference<
            typename extract_name_type::result_type>::type>::type;

      public:
        using argument_type = vertex_name_type;
        using result_type = Vertex;

        result_type operator()(const vertex_name_type& id) const {
            return {id};
        }
    };
};

注意

• 我们当然可以硬-对第二个专业化中的已知进行编码：

   模板<> struct boost::graph::internal_vertex_constructor<顶点>; {
       结构体类型{
           顶点运算符()(size_t id) const { return {id}; }
       };
   };
  

• 通过引用返回 id非常 很重要。如果不这样做，会导致 UB 没有来自库/编译器的诊断

步骤#3 添加/查找顶点

现在您可以添加顶点。通过“名称”（您的id）：

auto x = add_vertex(1111, g);                // by id

或者您在问题中预期的老式方式：

add_vertex(Vertex{2222, "twotwotwotwo"}, g); // or with full bundle

重复添加没有效果：

assert(add_vertex(1111, g) == x);

存在不同的查找。 vertex_by_property 返回给定顶点束的可选。

assert(x == *g.vertex_by_property(g[x]));

它通过从传递的包中提取“内部名称”来实现这一点，因此包不需要包含 id 之外的任何其他状态：

assert(x == *g.vertex_by_property(Vertex{1111}));

虽然它感觉像一个实现细节，但实际的< code>multi_index_container 实现名称 ->描述符索引也公开了：

assert(x == *g.named_vertices.find(1111));

步骤#4添加边

add_edge(1111, 2222, g);
add_edge(2222, 1111, g);

这借用了上一个问题的一页:)

显然，您仍然可以通过顶点描述符添加边。

步骤＃5其他操作

从之前的答案中借用更多页面：

print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
print_graph(g, get(&Vertex::other, g), std::cout << "---\n");

std::cout << "---\n";
for (auto *v : boost::make_iterator_range(vertices(g))) {
    auto const& [id, other] = g[v];
    std::cout << id << " " << std::quoted(other) << "\n";
}

if (auto v = g.vertex_by_property({1111})) {
    std::cout << "==== removing " << g[*v].id << "\n";
    clear_vertex(*v, g);  // clear edges
    remove_vertex(*v, g); // remove the vertex
}

print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
print_graph(g, get(&Vertex::other, g), std::cout << "---\n");

完整演示

Live On Coliru< /a>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>
#include <iomanip>

struct Vertex {
    size_t      id;
    std::string other = "default-constructed";
};

using Graph =
    boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, Vertex>;

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = size_t;
        result_type const& operator()(Vertex const& bundle) const {
            return bundle.id;
        }
    };
};

template <> struct boost::graph::internal_vertex_constructor<Vertex> {
    struct type {
      private:
        using extractor = typename internal_vertex_name<Vertex>::type;
        using name_t    = std::decay_t<typename extractor::result_type>;

      public:
        using argument_type = name_t;
        using result_type = Vertex;

        result_type operator()(const name_t& id) const { return {id}; }
    };
};

int main() {
    Graph g;

    {
        auto x = add_vertex(1111, g);                // by id
        add_vertex(Vertex{2222, "twotwotwotwo"}, g); // or with full bundle

        // duplicate additions have no effect
        assert(add_vertex(1111, g) == x);

        // different lookups exist
        assert(x == *g.named_vertices.find(1111));
        assert(x == *g.vertex_by_property(Vertex{1111}));
        assert(x == *g.vertex_by_property(g[x]));
    }

    add_edge(1111, 2222, g);
    add_edge(2222, 1111, g);

    print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
    print_graph(g, get(&Vertex::other, g), std::cout << "---\n");

    std::cout << "---\n";
    for (auto *v : boost::make_iterator_range(vertices(g))) {
        auto const& [id, other] = g[v];
        std::cout << id << " " << std::quoted(other) << "\n";
    }

    if (auto v = g.vertex_by_property({1111})) {
        std::cout << "==== removing " << g[*v].id << "\n";
        clear_vertex(*v, g);  // clear edges
        remove_vertex(*v, g); // remove the vertex
    }

    print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
    print_graph(g, get(&Vertex::other, g), std::cout << "---\n");
}

打印

---
1111 --> 2222 
2222 --> 1111 
---
default-constructed --> twotwotwotwo 
twotwotwotwo --> default-constructed 
---
1111 "default-constructed"
2222 "twotwotwotwo"
==== removing 1111
---
2222 --> 
---
twotwotwotwo --> 

旁注：

• 您不能对顶点使用关联容器选择器。指定 hash_mapS 会导致 unordered_set, equal_to, allocator> 作为 m_vertices 类型。