Minimal boost adjacency_list with non-contiguous storage (i.e. != vecS) and add_edge()

Question

I want to create a graph for an algorithm which requires graph concepts only provided by an adjacency_list. The vertex ids themselves are random size_t's and non-contiguous, so using a vector as the underlying storage is impossible, but this does not compile:

#include <boost/graph/adjacency_list.hpp>

int main()
{
  using namespace boost;
  using out_edge_storage = setS;
//  using vertex_storage = vecS; // compiles Ok
  using vertex_storage = setS; // error: no matching function for call to 'add_edge'
  using graph = adjacency_list<out_edge_storage, vertex_storage, undirectedS>;
  graph g;
  add_edge(3, 44, g);
  add_edge(1024102400, 3, g); // uses too much space (bad_alloc) with vecS
}

I do not need any extra custom vertex properties nor do I need to modify the graph after creating it. Reading through the documentation [1] I could not find a reason what the extra requirements for add_edge() are.

How would I construct a graph using a set or hash set datatype, and where in the documentation can I find the details I have missed?

1: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html + http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/adjacency_list.html

(The other stackoverflow questions regarding adjacency_list+vecS (e.g. here) are far from minimal and did not help.)

Answer 1

I do not need any extra custom vertex properties nor do I need to modify the graph after creating it.

Well, maybe not in your mind, but since the vector index no longer "doubles" as vertex id, you want somewhere to attach these numbers to the vertex descriptors.

This happens to be your reason to require/desire a property. I'd suggest a internal property if you want the algorithms also automatically know how to use that number to identify your indices.

Live On Coliru

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

using graph = boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, 
    boost::property<boost::vertex_index_t, size_t> >;

int main() {
    graph g;
    auto A = add_vertex(3, g);
    auto B = add_vertex(44, g);
    auto C = add_vertex(1024102400, g);
    add_edge(A, B, g);
    add_edge(C, A, g);

    print_graph(g);
}

Printing:

3 <--> 44 1024102400 
44 <--> 3 
1024102400 <--> 3