c++ - 如何配置 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_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 时返回的确切 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 实现吗？

Answer 1

Can this be achieved using boost::graph?

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

---

令我惊讶的是，adjacency_list 的类型层次结构中出现了一些新东西.显然这些天有一个 named_graph mixin(实际上是 maybe_name_graph )，它使用顶点包上的特征来检测“内部名称”。

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

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

注意事项:

• 查找的时间复杂度为 O(1)，因为名称-顶点查找基于无序(哈希)索引
• 如果你制作 add_edge 就会遇到问题(例如 id 的不明确重载)意外键入与 vertex_descriptor 相同的内容类型(或者如果你的论点对任何一个都有同样“远”的转换)。
• 据我所知，内部名称属性不会自动选取为vertex_index_t也不vertex_name_t属性(property)。

第 1 步:图表

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

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

到目前为止没有惊喜。我

• 选择添加第二个成员 other只是为了展示它何时/如何默认构建
• 选择了 listS因为它
  • 一个。提供引用/描述符稳定性(移除顶点除外)
  • 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};
        }
    };
};

注意

• 我们当然可以在第二个特化中对已知信息进行硬编码:

   template <> struct boost::graph::internal_vertex_constructor<Vertex> {
       struct type {
           Vertex operator()(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返回 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类型。