Sorted unique R-MAT generator

 template<typename RandomGenerator, typename Graph,
          typename EdgePredicate = keep_all_edges>
 class sorted_unique_rmat_iterator
 {
 public:
   typedef std::input_iterator_tag iterator_category;
   typedef std::pair<vertices_size_type, vertices_size_type> value_type;
   typedef const value_type& reference;
   typedef const value_type* pointer;
   typedef void difference_type;
   sorted_unique_rmat_iterator();
   sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
                               edges_size_type m, double a, double b, double c,
                               double d, bool bidirectional = true,
                               bool permute_vertices = true,
                               EdgePredicate ep = keep_all_edges());
   // Iterator operations
   reference operator*() const;
   pointer operator->() const;
   sorted_unique_rmat_iterator& operator++();
   sorted_unique_rmat_iterator operator++(int);
   bool operator==(const sorted_unique_rmat_iterator& other) const;
   bool operator!=(const sorted_unique_rmat_iterator& other) const;
};

Этот шаблон класса реализует генератор для графов R-MAT [CZF04], подходящий для инициализации списка смежности или другой структуры графа с инициализацией на основе итератора. График R-MAT имеет степень безмасштабного распределения w.r.t. и реализуется с использованием разбиения Recursive-MATrix. Выход этого генератора отсортирован для использования с графом сжатого разреженного ряда . Список краев, создаваемый этим итератором, гарантированно не содержит параллельных краев.

Where Defined

<boost/graph/rmat_graph_generator.hpp>

Constructors

sorted_unique_rmat_iterator();

Создает итератор прошлого-конца.

sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
                            edges_size_type m, double a, double b, double c,
                            double d, bool bidirectional = false,
                            bool permute_vertices = true,
                            EdgePredicate ep = keep_all_edges());

Конструирует итератор генератора R-MAT, который создает граф с вершинами n и краями m. a, b, c и d представляют вероятность размещения генерируемого края каждого из 4 квадрантов разделённой матрицы смежности. Вероятности взяты из генератора случайных чисел gen. Индексы Vertex изменяются для устранения локальности, когда permute_vertices соответствует действительности. Когда bidirectional является true для каждого края s-t добавляется соответствующий антикрай t-s, эти антикрая не учитываются в сторону m. ep позволяет пользователю указать, какие края сохраняются, это полезно в том случае, когда пользователь желает воздерживаться от хранения удаленных краев локально во время генерации для снижения потребления памяти.

Example

#include <boost/graph/distributed/mpi_process_group.hpp>
#include <boost/graph/compressed_sparse_row_graph.hpp>
#include <boost/graph/rmat_graph_generator.hpp>
#include <boost/random/linear_congruential.hpp>
using boost::graph::distributed::mpi_process_group;
typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
                                    distributedS<mpi_process_group> > Graph;
typedef keep_local_edges<boost::parallel::variant_distribution<mpi_process_group>,
                         mpi_process_group::process_id_type> EdgeFilter;
typedef boost::sorted_unique_rmat_iterator<boost::minstd_rand, Graph> RMATGen;
int main()
{
  boost::minstd_rand gen;
  mpi_process_group pg;
  int N = 100;
  boost::parallel::variant_distribution<ProcessGroup> distrib
    = boost::parallel::block(pg, N);
  mpi_process_group::process_id_type id = process_id(pg);
  // Create graph with 100 nodes and 400 edges
  Graph g(RMATGen(gen, N, 400, 0.57, 0.19, 0.19, 0.05, true,
                  true, EdgeFilter(distrib, id)),
          RMATGen(), N, pg, distrib);
  return 0;
}

Bibliography

[CZF04]

D Chakrabarti, Y Zhan и C Faloutsos. R-MAT: Рекурсивная модель для графического майнинга. Proceedings of 4th International Conference on Data Mining, pages 442--446, 2004.

Авторы: Ник Эдмондс и Эндрю Ламсдейн

Статья Parallel BGL Sorted unique R-MAT generator раздела может быть полезна для разработчиков на c++ и boost.

Parallel BGL Sorted unique R-MAT generator

Boost , ,

Boost C++ Libraries

Sorted unique R-MAT generator

Where Defined

Constructors

Example

Bibliography