Boost Graph Library에서 주어진 꼭지점의 임의의 안팎을 랜덤하게 선택하는 효율적인 방법은 무엇입니까?

Question

부스트 그래프 라이브러리를 사용하여 그래프의 주어진 버텍스에서 임의의 아웃 이웃 또는 이웃을 선택해야합니다. RNG에서 인덱스 i를 받고 i 번째 에지를 선택할 필요가 있습니다 (순서에 관계없이 호출간에 일관성이 있어야합니다).

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의 사용을했습니다. 그러나 이것이 효율적인지 알 필요가 있습니다. adjacency list를 저장하기 위해 vecS을 사용했기 때문에 i의 값에 관계없이 일정 시간에 std::advance이 작동합니까? 그렇지 않다면 효과적인 방법이 있습니까?

나는 이웃이나 이웃을 무작위로 선택해야한다는 것을 언급해야한다. 가장자리를 처리하지 않고 그렇게 할 수있는 방법이 있다면 그것은 또한 좋을 것이다.

Answer 1

반복기를 포인터로 증가 시키려고 시도했지만 작동합니다. 나는

ei+=i; 

와

std::advance(ei,i); 

교체 그리고 지금과 에지 반복자 밖으로 모두 i에 일정 시간에 실행됩니다. 그러나 전자는 i에서 시간을 선형으로 취합니다.

위와 같은 임의 액세스를 할 수 있다는 사실에도 불구하고 반복자가 임의 액세스인지 확인하기위한 다른 대답에 설명 된 검사가 실패합니다.

Answer 2

당신이 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에 의해 반환 된 반복자가 임의 액세스인지 여부는 지정되어 있지 않습니다.