更改Boost Graph库中顶点的迭代顺序

Question

我需要对图形顶点进行N次迭代，其中在每次迭代中，我希望每个顶点的出现顺序不同。我知道如何通过创建顶点描述符向量来做到这一点：

...
VertexIter itG1=boost::vertices(g).first;
VertexIter itG1End=boost::vertices(g).second;

while(itG1!=itG1End)
    vID.push_back(*itG1)
    itG1++

for (i=0; i< N; i++){
    shuffle(vID.begin(),vID.end(),RNG)
    vector<vertexDesc>::iterator idIterator;
    idIterator idIT = vID.begin();
    idIterator idEND = vID.end();

    while(idIT!=idEND){

        do_something_with(*idIT);
        idIT++;

   }
}

我想实现这样的目标：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/random/linear_congruential.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/graph_utility.hpp>
#include <random>

int main(int argc, char *argv[])
{
  boost::minstd_rand gen;
  struct Vertex{ int foo;};
  struct Edge{std::string blah;};

  typedef boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, Vertex, Edge > Graph;
  typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
  typedef boost::graph_traits<Graph>::edge_descriptor edge_t;
  typedef boost::graph_traits<Graph>::vertex_iterator vertexIter;
  typedef boost::graph_traits<Graph>::edge_iterator edgeIter;

  Graph g;

  boost::generate_random_graph<Graph,boost::minstd_rand>(g, 10,20, gen);
std::shuffle(boost::vertices(g).first,boost::vertices(g).second,std::default_random_engine(time(NULL)));

  return 0;

}

但是编译器抱怨std :: swap有问题。

Answer 1

您为什么要从具有描述符向量的地方改变？这绝对是更有效的方法。

即使您实际上能够交换顶点（您已经发现，也无法交换邻接列表），由于在这种情况下描述符are顶点ID，您实际上只是将边缘进行混洗（保持图同构）。

所以，如果那是您真正想要的，请参阅

• How to efficiently shuffle edges in a graph

[如果确实要像使用boost::vertices时那样控制内部库功能的遍历顺序，则需要custom vertex container by defining your own container generator。可以在此处找到一个示例，但是您仍然愿意对图模型进行实质性修改以获取所需的行为，并且我怀疑您会从中获得重大利益（因此我在开幕词中发言）。