c++ - 如何使用 `ListS` 而不是 `VecS` 作为底层容器并能够做同样的事情？

Question

我通常vecS作为容器工作boost::adjacency_list：

struct myVertexType { std::vector<Stuff> vec; /* and more */ };
struct myEdgeType { /* some data too */ };
using Graph = boost::adjacency_list<
        boost::vecS,
        boost::vecS,
        boost::directedS,
        myVertexType,
        myEdgeType
    >;

但是，我遇到了一个引发问题的情况：我引用了一些存储为顶点的捆绑属性的数据，当我创建另一个顶点时，这似乎使我的引用无效 (1)。

至少这是我从阅读此页面（“迭代器和描述符稳定性/无效”部分）中了解到的。

所以我切换到listS，一切顺利：

using Graph = boost::adjacency_list<
        boost::listS,
        boost::listS,
        boost::directedS,
        myVertexType,
        myEdgeType
    >;

直到...

直到我注意到 with listS,boost::target( e1, g )无法编译！：

Graph g;
auto e1 = boost::add_edge(1, 0, g).first;
auto t = boost::target( e1, g );

这也无法构建：（参见 coliru）

Graph g;
boost::add_edge(1, 0, g);
write_graphviz(std::cout, g );

所以我搜索了一下，找到了 Sehe 的答案，指出

vecS有一个隐式顶点索引。 listS没有。因此它使用内部property vertex_index_t

但是，给定的答案使用内部属性（？）（或者它是动态属性？），并且我使用自己的数据类型作为顶点和边。

所以我的问题是：

如何构建一个基于列表的图形类型，使我能够做所有允许的“常规事情” VecS？

（1）要清楚，我引用了一个顶点中的向量，当我创建另一个顶点时，向量突然变空了！

编辑：澄清了我的节点内的内容。

标签： c++boostboost-graph

Answer 1

背景

“当我创建另一个顶点时，这似乎使我的参考无效（1）。”

是的，这是可能的。

您必须意识到，在您选择容器选择器的基础上，存在更大的性能权衡。许多算法可以获得非常不同的效率特性。

此外，一些语义发生了微妙的变化（例如，当setS用作边缘容器选择器时，您自然不能再有重复的边缘；这也是add_edge返回 a 的原因pair<descriptor, bool>）。

还要意识到通常您不需要引用甚至迭代器稳定性。BGL 中的典型编码模式不是传递/保存对属性（包）的引用，而是按值传递属性映射。

属性映射抽象了对（可变）属性的访问。

您通常可以传递通常稳定的描述符（除非您要删除 中“中间”vecS的顶点，因为隐含的顶点索引显然会针对所有后续顶点发生变化）。

也就是说，让我们继续解决您的问题：

问题

直到我注意到使用 listS 时， boost::target( e1, g ) 无法编译！

没有。这编译得很好。

不好的是你add_edge用整数参数调用。顶点描述符不与列表/集合（基于节点的容器）集成。

更糟糕的是，不会为非 vecS adjacency_list 自动添加顶点，因此无论如何您都会引用超出范围的顶点。

引用这些的一般方法是：

V v0 = add_vertex(g);
V v1 = add_vertex(g);
auto [e1, inserted] = boost::add_edge(v0, v1, g);
assert(inserted);
[[maybe_unused]] V t = boost::target(e1, g);

graphviz 调用也很好，但由于同样的原因在add_edge...上失败了

此外，您需要添加一个顶点索引。作为内部属性或将属性映射传递给算法函数。

这是一个完整的测试演示，显示了所有三种风格：

住在科利鲁

#include <boost/algorithm/string.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/core/demangle.hpp>
#include <iostream>
#include <numeric>
using boost::core::demangle;
using boost::algorithm::replace_all_copy;

struct myVertexType { /* some data */ };
struct myEdgeType { /* some data too */ };

template <typename containerS> void tests() {
    using Graph = boost::adjacency_list<
        containerS, containerS,
        boost::directedS,
        myVertexType,
        myEdgeType>;

    using V = typename Graph::vertex_descriptor;

    std::cout << "\n"
              << std::boolalpha << "tests() with "
              << demangle(typeid(containerS).name()) << " - "
              << "vertex_descriptor integral? " << std::is_integral<V>()
              << "\n";
    Graph g;

    V v0 = add_vertex(g);
    V v1 = add_vertex(g);
    auto [e1, inserted] = boost::add_edge(v0, v1, g);
    assert(inserted);
    [[maybe_unused]] V t = boost::target(e1, g);

    std::ostringstream dot;
    if constexpr (std::is_same<boost::vecS, containerS>()) {
        boost::write_graphviz(dot, g);
    } else {
        std::map<V, int> index;
        for (auto v : boost::make_iterator_range(vertices(g)))
            index.emplace(v, index.size());

        auto index_map = boost::make_assoc_property_map(index);

        boost::dynamic_properties dp;
        dp.property("node_id", index_map); // get(boost::vertex_index, g)

        boost::write_graphviz_dp(dot, g, dp);
    }

    std::cout << "dot: " << replace_all_copy(dot.str(), "\n", "") << "\n";
}

int main() {
    tests<boost::vecS>();
    tests<boost::setS>();
    tests<boost::listS>();
}

印刷

tests() with boost::vecS - vertex_descriptor integral? true
dot: digraph G {0;1;0->1 ;}

tests() with boost::setS - vertex_descriptor integral? false
dot: digraph G {0;1;0->1 ;}

tests() with boost::listS - vertex_descriptor integral? false
dot: digraph G {0;1;0->1 ;}