I need to choose a random out-neighbor or in-neighbor from a given vertex in my graph using the Boost Graph Library. I receive an index i from an RNG and need to choose the ith out edge (they could be in any order, it just needs to be consistent across calls). To this end, I've made use of std::advance like so :
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);
Now this works fine, and I'm getting correct output. However I need to know if this is efficient, that is will std::advance work in constant time regardless of the value of i since I've used vecS to store the adjacency list ? If not, is there an efficient way ?
I should mention that I only need to select a random in-neighbor or out-neighbor, so if you have a way to do that without handling the edges, that would also be great.
I tried incrementing the iterator as a pointer and it works. I replaced
std::advance(ei,i);
with
ei+=i;
And it now runs in constant time in i for both in and out edge iterators. However, the former takes time linear in i.
For some reason, despite the fact that I can do random access like above, the check described in the other answer to see if the iterator is random access fails.