Изменить порядок итерации по вершине в библиотеке графов ускорения - PullRequest
Новая
       88

Изменить порядок итерации по вершине в библиотеке графов ускорения

0 голосов
/ 18 марта 2020

Мне нужно итерировать вершины графа 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 :: своп.

1 Ответ

1 голос
/ 21 марта 2020

Почему вы хотите отказаться от наличия вектора дескрипторов? Это, безусловно, более эффективный способ.

Даже если вы действительно могли поменять местами вершины (что, как вы уже обнаружили, невозможно для списков смежности), поскольку дескрипторы являются вершинами id в этом сценарии, вы фактически просто перетасовали бы ребра (поддерживая изоморфизм графа).

Итак, если это то, что вам действительно нравится, см.

Если на самом деле вы хотите контролировать порядок обхода внутренних библиотечных объектов, как при использовании boost::vertices, то вам нужен пользовательский контейнер вершин, определив собственный контейнерный генератор . Пример можно найти здесь, но вы можете внести существенные изменения в модель графа, чтобы получить желаемое поведение, и я сомневаюсь, что вы получите значительные преимущества (отсюда и мое вступительное заявление).

...