Time complexity/performance of edge and vertex properties in Boost Graph

Solution 1:

is it guaranteed that access to the name of a vertex and weight of an edge are efficient and fast under random access like so:

Yes. The properties are actually stored inline with the vertex/edge node. A descriptor is effectively a type erased pointer to that node. name_map[*vi] ends up inlining to something like get<N>(*static_cast<storage_node*>(vi)) if you imagine the property storage as a kind of tuple with a get<> accessor¹.

Part of my confusion comes from general std::map characteristic that it too does not support random access

Property maps are not like std::map; They may be consecutive, they may be node-based, ordered, unordered, or even calculated. In fact Boost Property Map maybe closer to the concept of a Lense in some functional programming languages. It is a set of functions that can be used to model (mutable) projections for a given key type.

See also:

• map set/get requests into C++ class/structure changes
• examples like Is it possible to have several edge weight property maps for one graph?, and Boost set default edge weight to one

Curiosity Wins... Code Gen

Let's see what code gets generated:

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <fmt/format.h>

using G =
    boost::adjacency_list<boost::listS, // out edges stored as list
                        boost::listS, // vertices stored as list
                        boost::directedS,
                        boost::property<boost::vertex_name_t, std::string>,
                        boost::property<boost::edge_weight_t, double>>;

using V = G::vertex_descriptor;
using E = G::edge_descriptor;

void test(V v, E e, G const& g) {
    auto name   = get(boost::vertex_name, g);
    auto weight = get(boost::edge_weight, g);

    fmt::print("{} {}\n", name[v], weight[e]);
}

int main()
{
    G g;
    E e = add_edge(add_vertex({"foo"}, g), add_vertex({"bar"}, g), {42}, g).first;

    test(vertex(0, g), e, g);
}

Prints

foo 42

But more interestingly, the codegen:

test(void*, boost::detail::edge_desc_impl<boost::directed_tag, void*>, boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::property<boost::edge_weight_t, double, boost::no_property>, boost::no_property, boost::listS> const&): # @test(void*, boost::detail::edge_desc_impl<boost::directed_tag, void*>, boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::property<boost::edge_weight_t, double, boost::no_property>, boost::no_property, boost::listS> const&)
  sub rsp, 40
  mov rax, qword ptr [rsp + 64]
  movups xmm0, xmmword ptr [rdi + 24]
  mov rax, qword ptr [rax]
  movaps xmmword ptr [rsp], xmm0
  mov qword ptr [rsp + 16], rax
  mov rcx, rsp
  mov edi, offset .L.str
  mov esi, 6
  mov edx, 173
  call fmt::v7::vprint(fmt::v7::basic_string_view<char>, fmt::v7::format_args)
  add rsp, 40
  ret

You see, no algorithmic overhead, just dereferences.

¹ In reality, the properties are stored in a kind of Lisp-like list type that end up behaving similarly to a tuple. Boost Graph predates tuples by considerable time margin. I suppose if you want one can compare it closely to Boost Fusion's map type (which also has a type key).