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

Question

Consider:

typedef adjacency_list<
    listS, //out edges stored as std::list
    listS, //verteices stored as std::list
    directedS,
    property<vertex_name_t, std::string>,
    property<edge_weight_t, double>
> user_graph;

Storage of edges and vertices as std::list precludes random access via [index].

Consider further that property maps are defined so.

typedef property_map<user_graph, vertex_name_t>::type name_map_t;
typedef property_map<user_graph, edge_weight_t>::type weight_map_t;

user_graph g;
name_map_t name_map = get(vertex_name, g);
weight_map_t weight_map = get(edge_weight, g);

Even though random access of actual edges/vertices is not possible via [index], 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:

graph_traits<user_graph>::vertex_iterator vi, vi_end;
for(tie(vi, vi_end)=vertices(g); vi != vi_end; ++vi)
    cout<<"Name of vertex is "<<name_map[*vi];//Question is, is this efficient given storage of vertices as std::list

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

Is it the case that whether vertices are stored as std::vector or std::list or std::set, regardless, access to its property maps via vertex descriptors using some_map[vertex_descriptor] or some_map[*vertex_iterator] is always guaranteed to be efficient (constant time)?

Answer 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).