itération d'ordre aléatoire sur les sommets BGL

Question

Voici un exemple de code pour créer un graphe avec bgl et parcourir les sommets. Je voudrais faire cette itération dans un ordre aléatoire - en d'autres termes: la boucle devrait manipuler chaque sommet, mais l'ordre des sommets devrait être aléatoire pour chaque appel de la fonction principale. Comment puis-je atteindre cet objectif? J'ai expérimenté avec succès std::random_shuffle. Je pense qu'il existe différents types de concepts d'itérateur, mais je ne comprends pas encore les différences.

#include <iostream>     
    #include <boost/graph/graph_traits.hpp> 
    #include <boost/graph/adjacency_list.hpp> 

    using namespace boost; 

    // vertex struct to store some properties in vertices 
    struct Vertex { 
    std::string name; 
    }; 

    int main(int,char*[]) { 
    // create a typedef for the graph type 
    typedef adjacency_list<vecS, vecS, undirectedS, Vertex> Graph; 

    // declare a graph object 
    Graph g(3); 

    // prepare iteration 
    typedef graph_traits<Graph>::vertex_iterator vertex_iter; 
    std::pair<vertex_iter, vertex_iter> vp; 

    // add some property data to the vertices 
    vp = vertices(g); 
    g[*vp.first].name = "A"; 
    g[*(++vp.first)].name = "B"; 
    g[*(++vp.first)].name = "C"; 

    // iterate over the vertices 
    for (vp = vertices(g); vp.first != vp.second; ++vp.first)  
     std::cout << g[*vp.first].name << " "; 
    std::cout << std::endl; 

    return 0; 
    } 

Edit: Voici la solution que je suis venu avec grâce à la réponse de @Jay.

#include <iostream>     
    #include <boost/graph/graph_traits.hpp> 
    #include <boost/graph/adjacency_list.hpp> 
    #include <algorithm> // std::random_shuffle 
    #include <vector>  // std::vector 
    #include <ctime>  // std::time 
    #include <cstdlib>  // std::rand, std::srand 

    using namespace boost; 

    // vertex struct to store some properties in vertices 
    struct Vertex { 
    std::string name; 
    }; 

    // random number generator function 
    int myrandom (int i) { 
    return std::rand()%i; 
    } 

    int main(int,char*[]) { 
    // create a typedef for the graph type 
    typedef adjacency_list<vecS, vecS, undirectedS, Vertex> Graph; 

    // declare a graph object 
    Graph g(3); 

    // prepare iteration 
    typedef graph_traits<Graph>::vertex_iterator vertex_iter; 
    std::pair<vertex_iter, vertex_iter> vp; 

    // add some property data to the vertices 
    vp = vertices(g); 
    g[*vp.first].name = "A"; 
    g[*(++vp.first)].name = "B"; 
    g[*(++vp.first)].name = "C"; 

    // initialize pseudo random number generator 
    std::srand(unsigned (std::time(0))); 

    // create offset vector 
    std::vector<int> myvector; 
    for (int i=0; i<3; ++i) { 
     myvector.push_back(i); 
    } 

    // using myrandom to shuffle offset vector 
    std::random_shuffle(myvector.begin(), myvector.end(), myrandom); 

    // keep vp.first at the start 
    vp = vertices(g); 

    // iterate over the vertices effectively shuffled by the offset 
    vertex_iter dummy_iter; 
    for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) { 
     dummy_iter = vp.first + *it; 
     std::cout << g[*dummy_iter].name << " "; 
    } 
    std::cout << std::endl; 

    return 0; 
    } 

Answer 1

Je pense que la chose la plus simple à faire est de mettre en place un vecteur aléatoire d'indices, as outlined here. Vous pouvez ensuite itérer la liste mélangée et l'utiliser comme décalage pour votre itérateur de vertex.

Par exemple

vp = vertices(g); // Keep vp.first at the start 
vertex_iter dummy_iter; 
// Looping on a shuffled vector, values should be 0..N-1 
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) 
{ 
    dummy_iter = vp.first + *it; 
    Vertex* v = *dummy_iter; 
    ... 

Answer 2

Pour créer un nombre aléatoire dans une plage donnée utilisez le code ci-dessous. ctime #include et #include stdlib.h

int getNumberRange(int min, int max) 
    { 
     srand(static_cast<unsigned int>(time(0))); 

     // always call rand(); after srand() on visual vasic; 
     rand(); 

     static const double fraction = 1.0/(static_cast<double>(RAND_MAX) + 1.0); 
     return static_cast<int>(rand() * fraction * (max - min + 1) + min); 
    } 



    getNumberRange(1, 100); //picks number between 1 and 100 

Chaque fois que vous avez besoin d'un nouveau numéro modifier les valeurs de la plage (1, 100) et appeler à nouveau la fonction.