Random order iteration over BGL vertices

Question

Here's some example code to create a graph with bgl and iterate over the vertices. I would like to do this iteration in random order - in other words: the loop should manipulate every vertex, but the order of the vertices should be random for every call of the main function. How can I achieve this?

I experimented unsuccessfully with std::random_shuffle. I think there are different kinds of iterator concepts, but I don't understand the differences yet.

  #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: Here's the solution I came up with thanks to the answer of @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

I think the simplest thing to do is set up a random vector of indices, as outlined here. Then you can iterate the shuffled list and use it as an offset for your vertex iterator.

For example

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