在Boost Graph Library中选择给定顶点的随机进出邻居的有效方法？

Question

我需要使用 Boost Graph Library 从我的图形中的给定顶点选择一个随机的外邻或内邻。我从 RNG 收到一个索引 i 并需要选择第 i 个出边（它们可以按任何顺序排列，只需要在调用之间保持一致）。为此，我像这样使用了 std::advance :

typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
Graph g; // Given graph
int i;
int v; // Given vertex
//
// Code to generate random index (guaranteed to be valid) and store it in i
//
typename graph_traits < graph_t >::in_edge_iterator ei, ei_end;
tie(ei,ei_end) = in_edges(v,g);
std::advance(ei,i);
// Now ei points to the ith out edge, and is ready to use
// Return the corresponding in-neighbor
return source(*ei,g);

现在一切正常，我得到了正确的输出。但是我需要知道这是否有效，也就是说 std::advance 会在恒定时间内工作，而不管 i 的值如何，因为我已经使用 vecS 来存储邻接列表？如果没有，有没有有效的方法？

我应该提到我只需要 select 一个随机的近邻或外邻，所以如果你有办法做到这一点而不处理边缘，那也很好。

Answer 1

如果你想确保 advance(ei. i) 是 o(1)，你可以简单地添加一个 static_assert:

 static_assert( 
     std:::is_base_of<
          std::random_access_iterator_tag,
          typename std:::iterator_traits< decltype(ei) >::iterator_category
     >::value,
     "Not a random access iterator!" )

如果 ei 不是随机访问迭代器，编译将失败。

至于实际问题，OutEdgeList（adjacency_list 中的第一个模板参数）= vecS 足以进行随机访问 out_edges。我相信没有指定 in_edges 返回的迭代器是否是随机访问的。

Answer 2

我尝试将迭代器作为指针递增，它起作用了。我替换了

std::advance(ei,i);

和

ei+=i;

并且它现在在 i 中以固定时间运行，用于输入和输出边缘迭代器。然而，前者需要时间线性 i.

出于某种原因，尽管我可以像上面那样进行随机访问，但另一个答案中描述的检查迭代器是否是随机访问的检查失败了。

在Boost Graph Library中选择给定顶点的随机进出邻居的有效方法？

Efficient way to choose random in or out neighbours of a given vertex in Boost Graph Library?

c++

boost

boost-graph