Boost Graph 中边和顶点属性的时间 complexity/performance

Question

考虑：

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;

将边和顶点存储为 std::list 排除通过 [index] 的随机访问。

进一步考虑属性映射是这样定义的。

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

即使通过[index]不可能随机访问实际的edges/vertices，是否可以保证在像这样的随机访问下访问顶点名称和边权重是高效且快速的所以：

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

我的部分困惑来自一般 std::map 特性，即它也不支持随机访问（参见 here）

无论顶点存储为 std::vector 或 std::list 还是 std::set，不管怎样，使用 [= 通过顶点描述符访问其属性映射21=] 或 some_map[*vertex_iterator] 总是保证有效（恒定时间）？

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:

是的。这些属性实际上存储在 inline 和 vertex/edge node 中。描述符实际上是指向该节点的类型擦除指针。如果您将属性存储想象成一种带有 get<> 访问器¹ 的元组，name_map[*vi] 最终会内联到 get<N>(*static_cast<storage_node*>(vi)) 之类的东西。

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

属性地图不像std::map；它们可能是连续的，它们可能是 node-based、有序的、无序的，甚至是计算的。事实上，Boost Property Map 可能更接近某些函数式编程语言中 Lense 的概念。它是一组函数，可用于对给定键类型的（可变）投影进行建模。

另请参阅：

map set/get requests into C++ class/structure changes
例如Is it possible to have several edge weight property maps for one graph?，和 Boost set default edge weight to one

好奇心获胜...代码生成

让我们看看生成了什么代码：

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);
}

版画

foo 42

但更有趣的是，代码生成器：

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

你看，没有算法开销，只是取消引用。

¹ 实际上，属性存储在一种 Lisp-like 列表类型中，最终表现得类似于元组。 Boost Graph 比元组早了相当长的时间。我想如果你想要的话，可以将它与 Boost Fusion 的 map 类型（也有一个类型键）进行比较。

Boost Graph 中边和顶点属性的时间 complexity/performance

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

c++

boost

boost-graph

boost-property-map

好奇心获胜...代码生成