adjacency_list 中的常量顶点 ID

Question

我想保留 adjacency_list 图（以及顶点组）的顶点和边的外部属性。我需要能够通过属性访问顶点。例如，我想遍历分配了一些权重的所有顶点，并获取它们的出边。

但是，我还需要设置我的顶点容器。在此容器中，添加\删除顶点可能会使顶点描述符无效。

问题是外部属性现在可以映射到无效 vertex_descriptors。

    class manage_data {
...
    auto get_interesting(int weight) {
        return ver_by_weight.equal_range(weight);
    }
    void do_stuff (...) {
        auto for_later_use = get_interesting();
        ...
        boost::remove_vertex(unrelated_vertex, graph_);
        ...
        use_vec(for_later_use.front()); //bug
    }
    }

一种方法似乎是添加一个 vertex_index 属性。这是行不通的，因为它是单向的——您可以通过 vertex_descriptor 获得 vertex_index，但反之则不行。这意味着我不能在我只知道其索引的两个顶点之间添加一条边。

另一个有前途的解决方案是使用标记图。该图只能通过标签添加边。通过使用标签 ID 存储外部数据，我本可以走得更远。不幸的是，并不是所有的 adjacency_list 接口都是使用标签重新实现的——例如out_edges。这意味着我仍然需要能够访问顶点描述符，并且不可能（在合理的时间内）仅使用标签，可以看出 here

一个更好的解决方案是结合以上两者 - 有一个 vertex_label 属性。这看起来过于复杂，而且它不起作用（上面的例子）。

顶点与外部数据相关不是很常见吗？你怎么做到的？

Answer 1

您可以使用从顶点描述符到您自己的 ID 的双向映射。

现在，只要您为顶点容器使用任何基于节点的容器选择器，就大功告成了。

查看 BiMap 并可能 transform_value_property_map 以获得最大的便利（尽管您可能不需要所有的幻想，特别是如果图形主要是只读的 - 或仅收缩例如）

另见

BGL indexing a vertex by keys

adjacency_list 中的常量顶点 ID

constant vertex ids in adjacency_list

boost

graph

boost-graph

adjacency-list