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

sehe · Accepted Answer · 2022-01-22T00:42:01.377

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.

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

Out of curiosity, checked the code-gen. https://godbolt.org/z/fEn75h7dK The proof of the pudding is in the eating, as they say — sehe, Jan 22 '22 at 00:43
In line: `test(vertex(0, g), e, g);`, isn't the call to `vertex(0, g)` linear time since we are storing the vertices in `std::list` ? Isn't `0` algorithmically akin to applying `[0]` on a `list` and hence linear and not constant time? — Tryer, Jan 22 '22 at 04:02
Your question is about the property map lookups, right? How you get the descriptors is your concern. In your question you used a loop (linear iteration). I chose an arbitrary valid descriptor just to call the function with. The point is that retrieving the properties from the descriptor is constant time, which was the question. (Also, one cannot apply `[0]` on a `list` so I'm not sure what that meant) — sehe, Jan 22 '22 at 13:44

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

1 Answers1

Curiosity Wins... Code Gen