1

考虑：

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]，是否可以保证在随机访问下访问顶点名称和边的权重是高效且快速的，如下所示：

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它也不支持随机访问的一般特征（见这里）

是否顶点存储为std::vectororstd::list或，无论如何，通过使用or的std::set顶点描述符访问其属性映射总是保证有效（恒定时间）？some_map[vertex_descriptor]some_map[*vertex_iterator]

4

1 回答 1

1

是否保证在随机访问下访问顶点的名称和边的权重是高效且快速的，如下所示：

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

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

属性映射不像 std::map；它们可能是连续的，它们可能是基于节点的、有序的、无序的，甚至是计算的。事实上，Boost Property Map在某些函数式编程语言中可能更接近于镜头的概念。它是一组函数，可用于为给定键类型建模（可变）投影。

也可以看看：

好奇心赢了……代码生成

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

Live On 编译器资源管理器

#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

但更有趣的是，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

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

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

于 2022-01-21T23:32:36.137 回答