Time complexity of Boost Graph function vertex() on adjacency_list

I am confused about the time complexity of the Boost Graph function vertex() when operating on an adjacency_list.

This page in the manual appears to claim that the function vertex() runs in constant time even when template parameter VertexList is listS.

vertex() This operation is constant time for vecS and for listS.

However, it is a mystery to me how the function can achieve constant time operation when the underlying data structure is a std::list. I have looked at the generated object code and it looks like the function vertex() compiles to an iterative loop when VertexList=listS, versus a constant lookup when VertexList=vecS.

Finally, I created a small test program which confirms that the run time scales with the value of the index passed to vertex() when using listS.

How does this add up? Is there some special way to make vertex() run in constant time, or did I misunderstand the documentation, or is the documentation simply wrong?

// Sample code showing non-constant run time of vertex()
boost::adjacency_list<
    boost::vecS,
    boost::listS,  // program is fast when I change this to vecS
    boost::undirectedS> g;

// Generate random graph with 10000 vertices.
std::mt19937 rng(1234);
boost::generate_random_graph(g, 10000, 20000, rng, false);

// Repeated lookup of vertex in graph
//   takes 10 seconds for listS, 0.02 seconds for vecS
int result = 0;
std::uniform_int_distribution vdist{0, int(boost::num_vertices(g) - 1)};
for (int i = 0; i < 1000000; ++i) {
    int v = vdist(rng);
    result += boost::out_degree(boost::vertex(v, g), g);
}
std::cout << result << std::endl;

Solution

The documentation is just wrong. The relevant overload is correctly commented O(V):

// O(V)
template < class Derived, class Config, class Base >
inline typename Config::vertex_descriptor vertex(
    typename Config::vertices_size_type n,
    const adj_list_impl< Derived, Config, Base >& g_)
{
    const Derived& g = static_cast< const Derived& >(g_);
    typename Config::vertex_iterator i = vertices(g).first;
    while (n--)
        ++i; // std::advance(i, n); (not VC++ portable)
    return *i;
}

You can emulate the constant-time lookup using an external index, but I'm sure you know how to.

Here's the example simplified and made self-contained:

Live On Coliru

// Compile: g++ -std=c++17 -O3 -o test test.cpp
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <iostream>
#include <random>
#include <chrono>
using namespace std::chrono_literals;
static inline auto now() { return std::chrono::high_resolution_clock::now(); };

template <typename VertexContainerSelector, size_t Seed = 1234> void bench_mark(size_t N = 1'000'000) {
    using G = boost::adjacency_list<boost::vecS, VertexContainerSelector, boost::undirectedS>;
    using V = G::vertex_descriptor;
    G g;

    std::mt19937 rng{Seed};
    generate_random_graph(g, 10'000, 20'000, rng, false);

    auto get = [&] { return [&g](size_t n) { return vertex(n, g); }; }();

    size_t result = 0;
    auto   vdist  = bind(std::uniform_int_distribution{0ul, num_vertices(g) - 1}, ref(rng));

    auto s = now();
    for (size_t i = 0; i < N; ++i) {
        int  n  = vdist();
        auto u  = get(n);
        result += out_degree(u, g);
    }
    std::cout << __PRETTY_FUNCTION__ << " " << result << " " << (now() - s) / 1.s << "s" << std::endl;
}

int main() {
    bench_mark<boost::vecS>();
    bench_mark<boost::listS>();
}

Printing (on my machine):

void bench_mark(size_t) [with VertexContainerSelector = boost::vecS...] 4000918 0.0035862s
void bench_mark(size_t) [with VertexContainerSelector = boost::listS...] 4000918 5.23695s

Workaround

Possible implementation of the suggested workaround:

std::vector<V> index; // only used for listS
auto  get = [&] {
    if constexpr (std::is_same_v<VertexContainerSelector, boost::vecS>) {
        return [&g](size_t n) { return vertex(n, g); };
    } else {
        auto [b, e] = vertices(g);
        index.assign(b, e);
        return [&index](size_t n) { return index[n]; };
    }
}();

Prints (compare Live On Coliru)

void bench_mark(size_t) [with VertexContainerSelector = boost::vecS...] 4000918 0.00360215s
void bench_mark(size_t) [with VertexContainerSelector = boost::listS...] 4000918 0.00436193s