How to use vertex dentifiers in Boost graph of size int64_t

Question

I am trying to add edges to a Boost undirected graph using boost::add_edge(...). The graph is defined as:

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;

I do not get compile errors. My code works fine, if the vertices are ints (e.g. boost::add_edge(1, 2, g)). However, as soon as I add vertices as int64_t, I get a "terminate called after throwing an instance of '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);
    ...

I guess I have to specify somehow the size of the vertex numbers - but I just do not understand how to do it. Note: I do not want to add extra properties to the vertices - I just need large numbers for the vertices (because they are identifiers from OpenStreetMap).

Answer 1

Using vecS the vertex index is implicit. They correspond to the index in the vertex storage container, which is vector.

This means that using vertex index 1810014749 on g would be Undefined Behaviour if you have fewer than 1810014750 vertices. "Luckily" (?) for you add_edge is smart enough to detect this and resize the vector in the case of vecS container selector, so it tries to allocate enough storage for the highest vertex id mentioned before adding the edge, which fails because your program doesn't have access to that much memory:

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

Here, 1810014750 * sizeof(_Tp) is 14,48 GB.

Other than that, 64 bits is no problem, since the vertex descriptor would already be 64 (albeit unsigned):

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));

So as long as you don't actually use negative osm_id_t there was no technical barrier to using osm_id_t as the index.

"Sparse" vertex index

If your vertex index isn't dense then vecS might be less suited for your storage. Consider using something else:

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

Prints

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