如何在大小为 int64_t 的 Boost 图中使用顶点标识符

Question

我正在尝试使用 boost::add_edge(...) 向 Boost 无向图添加边。该图定义为：

using osm_id_t = int64_t;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
        // vertex properties
        boost::property<boost::vertex_index_t, osm_id_t,
        boost::property<boost::vertex_color_t, boost::default_color_type> >,
        // edge properties
        boost::no_property> UndirectedOSMIdGraph;

我没有遇到编译错误。如果顶点是整数（例如 boost::add_edge(1, 2, g)），我的代码工作正常。但是，一旦我将顶点添加为 int64_t，我就会得到一个“在抛出 'std::bad_alloc'

实例后调用的终止

    UndirectedOSMIdGraph g;
    osm_id_t large {1810014749};
    boost::add_edge (large, 2, g);  //if instead large is just 1 it works
    boost::add_edge (2, 3, g);
    ...

我想我必须以某种方式指定顶点数的大小 - 但我只是不知道该怎么做。注意：我不想向顶点添加额外的属性 - 我只需要大量的顶点（因为它们是来自 OpenStreetMap 的标识符）。

Answer 1

使用vecS 顶点索引是隐式的。它们对应于顶点存储容器中的索引，即vector。

这意味着如果顶点数少于 1810014750，则在 g 上使用顶点索引 1810014749 将是未定义的行为。 “幸运的是”（？）对你来说 add_edge 足够聪明，可以检测到这一点并在 vecS 容器选择器的情况下调整向量的大小，因此它会尝试为添加之前提到的最高顶点 ID 分配足够的存储空间边缘，失败是因为您的程序无法访问那么多内存：

    at /usr/include/c++/10/ext/new_allocator.h:115
115             return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));

此处，1810014750 * sizeof(_Tp) 为 14,48 GB。

除此之外，64 位没有问题，因为顶点描述符已经是 64（尽管未签名）：

using V = UndirectedOSMIdGraph::vertex_descriptor;

static_assert(not std::is_same_v<osm_id_t, V>);
static_assert(std::is_same_v<std::make_unsigned_t<osm_id_t>, V>);
static_assert(sizeof(osm_id_t) == sizeof(V));

因此，只要您实际上不使用负数 osm_id_t，使用 osm_id_t 作为索引就没有技术障碍。

“稀疏”顶点索引

如果您的顶点索引不密集，那么 vecS 可能不太适合您的存储。考虑使用其他东西：

Live On Compiler Exlorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

using osm_id_t = int64_t;

using UndirectedOSMIdGraph = boost::adjacency_list<
    boost::vecS, boost::listS, boost::undirectedS,
    boost::property<
        boost::vertex_index_t, osm_id_t,
        boost::property<boost::vertex_color_t, boost::default_color_type>>,
    boost::no_property>;

using V = UndirectedOSMIdGraph::vertex_descriptor;

static_assert(not std::is_same_v<std::make_unsigned_t<osm_id_t>, V>);

int main() {
    UndirectedOSMIdGraph g;

    osm_id_t large{1810014749};
    auto     v2 = add_vertex(2, g);
    add_edge(add_vertex(large, g), v2, g);
    add_edge(v2, add_vertex(3, g), g);

    print_graph(g);
}

版画

2 <--> 1810014749 3 
1810014749 <--> 2 
3 <--> 2

如何在大小为 int64_t 的 Boost 图中使用顶点标识符

How to use vertex dentifiers in Boost graph of size int64_t

c++

boost

boost-graph

“稀疏”顶点索引