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

How to configure boost::graph to use my own (stable) index for vertices?

最简单的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_decriptor 会稳定。

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 时，我似乎无法控制它 returns 的确切 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];

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

Can this be achieved using boost::graph?

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

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

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

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

备注：

  • 查找的时间复杂度为 O(1)，因为 name-vertex 查找基于无序（散列）索引
  • 如果你不小心使 id 类型与 vertex_descriptor 类型相同（或者如果你的论点两者都有同样“远”的转换。
  • 据我所知，内部名称 属性 是 而不是 自动选择为 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只是为了显示when/how它是默认构造的
  • 选择 listS 因为它
    • 一个。提供 reference/descriptor 稳定性（移除的顶点除外）
    • b.导致不透明 vertex_descriptor (void*) 与重载解析中的 id 类型 (size_t) 不冲突

第 2 步：命名特征

接下来我们向 BGL 介绍我们的内部顶点名称。

This is purely parameterized by Vertex bundle, so keep in mind that different graphs using the same bundle would use the same name traits.

// 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};
        }
    };
};

备注

  • 我们当然可以hard-code第二专业的知识：

     template <> struct boost::graph::internal_vertex_constructor<Vertex> {
     struct type {
         Vertex operator()(size_t id) const { return {id}; }
     };
 };

  • 它非常重要return id 引用。否则会导致 UB 没有来自 library/compiler

    的诊断

步骤 #3 Adding/Finding 顶点

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

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

或者您在问题中预期的 old-fashioned 方式：

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

重复添加无效：

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

存在不同的查找。 vertex_by_property return 是一个 optional<vertex_descriptor> 给定的顶点束。

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

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

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

虽然感觉像一个实现细节，但实际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

#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<void*, hash<void*>, equal_to<void*>, allocator<void*>> 作为 m_vertices 类型。