Un moyen efficace de choisir des voisins aléatoires dans ou hors d'un sommet donné dans Boost Graph Library?

Question

J'ai besoin de choisir un voisin externe aléatoire ou un voisin d'un sommet donné dans mon graphique en utilisant la bibliothèque de graphes Boost. Je reçois un index i à partir d'un RNG et j'ai besoin de choisir le «ith out edge» (ils peuvent être dans n'importe quel ordre, il faut juste qu'ils soient cohérents entre les appels). À cette fin, je l'ai fait usage de std::advance comme ceci:

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); 

Maintenant, cela fonctionne très bien, et je reçois une sortie correcte. Cependant j'ai besoin de savoir si c'est efficace, c'est std::advance fonctionnera dans le temps constant indépendamment de la valeur de i puisque j'ai employé vecS pour stocker la liste d'adjacence? Sinon, y a-t-il un moyen efficace?

Je devrais mentionner que je dois seulement sélectionner un voisin in-situ ou un voisin, donc si vous avez un moyen de le faire sans manipuler les bords, ce serait aussi génial.

Answer 1

J'ai essayé d'incrémenter l'itérateur comme un pointeur et cela fonctionne. Je l'ai remplacé

std::advance(ei,i); 

avec

ei+=i; 

Et il fonctionne maintenant à temps constant i à la fois dans et hors itérateurs de bord. Cependant, le premier prend du temps linéaire en i.

Pour une raison quelconque, malgré le fait que je puisse faire un accès aléatoire comme ci-dessus, la vérification décrite dans l'autre réponse pour voir si l'itérateur est un accès aléatoire échoue.

Answer 2

Si vous voulez vous assurer que advance(ei. i) est o(1), vous pouvez simplement ajouter un 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!") 

Cela ne parviendra pas à compiler si ei n'est pas un itérateur d'accès aléatoire.

En ce qui concerne la question réelle, ayant OutEdgeList (le premier paramètre de modèle dans adjacency_list) = vecS est suffisante pour avoir accès aléatoire out_edges. Je crois qu'il n'est pas précisé si les itérateurs retournés par in_edges sont à accès aléatoire.