我如何使用 `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).

至少这是我从 reading this page 中了解到的（“迭代器和描述符 Stability/Invalidation”部分）。

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

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

直到...

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

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

这也无法构建：(see on coliru)

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

所以我搜索了一下，发现，说明

vecS has an implicit vertex index. listS doesn't. Therefore it uses the internal property vertex_index_t

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

所以我的问题是：

如何构建基于列表的图形类型，使我能够执行 VecS 允许的所有“常规操作”？

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

编辑：阐明了我的节点中的内容。

Answer 1

背景

"when I created another vertex, that seemed to make my reference invalid (1)."

是的，这是可能的。

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

此外，一些语义发生了微妙的变化（例如，当使用 setS 作为边缘容器选择器时，你自然不能再有重复的边缘；这也是为什么 add_edge returns a pair<descriptor, bool>).

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

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

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

话虽如此，让我们继续解决您的问题：

问题

Until I noticed that with listS, boost::target( e1, g ) fails to compile!

没有。编译得很好。

您调用 add_edge 时使用整数参数是不好的。顶点描述符不与 lists/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...

上由于同样的原因失败

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

这是一个完整的测试演示，展示了所有三种口味：

Live On Coliru

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

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

How can I use `ListS` instead of `VecS` as underlying container and be able to do the same thing?

c++

boost

boost-graph

背景

问题