ブースト・グラフ・ライブラリの特定の頂点のランダムまたはイン・ネイバーを効率的に選択できますか？

Question

ブーストグラフライブラリを使用して、グラフ内の特定の頂点からランダムなアウトネイバーまたはインネイバーを選択する必要があります。私は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); 

は今、これは正常に動作し、私は正しい出力を取得しています。しかし、私がvecSを使用して隣接リストを保存して以来、iの値にかかわらず、std::advanceは一定時間で動作するのが効率的かどうかを知る必要がありますか？そうでない場合は、効率的な方法がありますか？

私は、隣接する隣接ノードまたは隣接ノードをランダムに選択する必要があることを言及する必要があります。エッジを処理せずに行う方法がある場合は、それも素晴らしい方法です。

Answer 1

イテレータをポインタとしてインクリメントしてみましたが、動作しました。私は

ei+=i; 

で

std::advance(ei,i); 

を交換し、それは今のエッジイテレータ内と外の両方のためにiに一定の時間で実行されます。しかし、前者はiで時間が線形である。

何らかの理由で、上記のようなランダムアクセスが可能であるにもかかわらず、イテレータがランダムアクセスであるかどうかを確認するためのもう1つの答えに記載されているチェックが失敗します。

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によって返されたイテレータがランダムアクセスであるかどうかは指定されていません。