在Boost图库中给定顶点的邻居的随机选择或随机选择的有效方法？

我需要使用Boost Graph Library从我的图中给定的顶点中选择一个随机的邻居或邻居。我从一个RNG收到一个索引i，并且需要选择第i个边缘（它们可以是任意顺序，只需要在呼叫间保持一致）。为此，我利用了std::advance像这样：在Boost图库中给定顶点的邻居的随机选择或随机选择的有效方法？

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来存储邻接列表了？如果不是，有没有一种有效的方法？

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

来源

2017-02-25 NILobachevsky

我试着增加迭代器作为指针，它的工作原理。我换成

std::advance(ei,i);

与

ei+=i;

现在它运行在固定的时间在i对进出边迭代两者。然而，前者在i中需要时间线性。

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

来源

2017-02-27 12:58:10 NILobachevsky

如果你想确保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返回的迭代器是否是随机访问。

来源

2017-02-25 14:36:15 sbabbi

感谢您的回答。有趣的是，assert在_both_ out和边缘失败。如果考虑到边缘显然应该是随机访问？有没有另一种方法来有效地选择一个随机的邻居（不必涉及迭代边缘）？ – NILobachevsky

我刚刚通过一个简单的基准确认了两种迭代器都不是随机访问;该访问在索引中需要时间线性。即使当我尝试使用adjacency_iterator（assert也不存在）时，这似乎是真的 – NILobachevsky

那么[documentation]（http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/adjacency_list.html ）'out_edges'明确指出，如果你使用'vecS'，返回的迭代器应该是随机访问..所以现在我感到困惑。 – sbabbi

在Boost图库中给定顶点的邻居的随机选择或随机选择的有效方法？

回答

相关问题