如何使用“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) 需要明确的是，我引用了一个位于顶点的向量，当我创建另一个顶点时，该向量突然变空了！

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

Answer 1

背景

“当我创建另一个顶点时，这似乎使我的引用无效 (1)。”

是的，这是可能的。

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

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

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

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

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

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

问题

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

没有。编译得很好。

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

更糟糕的是，顶点不会自动添加到非 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 ;}