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

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

CodePudding user response：

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