| .. Copyright (C) 2004-2009 The Trustees of Indiana University. |
| Use, modification and distribution is subject to the Boost Software |
| License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| |
| ==================================== |
| |Logo| 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; |
| }; |
| |
| This class template implements a generator for R-MAT graphs [CZF04]_, |
| suitable for initializing an adjacency_list or other graph structure |
| with iterator-based initialization. An R-MAT graph has a scale-free |
| distribution w.r.t. vertex degree and is implemented using |
| Recursive-MATrix partitioning. The output of this generator is sorted |
| for use with a `compressed sparse row graph`_. The edge list produced by |
| this iterator is guaranteed not to contain parallel edges. |
| |
| Where Defined |
| ------------- |
| <``boost/graph/rmat_graph_generator.hpp``> |
| |
| Constructors |
| ------------ |
| |
| :: |
| |
| sorted_unique_rmat_iterator(); |
| |
| Constructs a past-the-end 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()); |
| |
| Constructs an R-MAT generator iterator that creates a graph with ``n`` |
| vertices and ``m`` edges. ``a``, ``b``, ``c``, and ``d`` represent |
| the probability that a generated edge is placed of each of the 4 |
| quadrants of the partitioned adjacency matrix. Probabilities are |
| drawn from the random number generator ``gen``. Vertex indices are |
| permuted to eliminate locality when ``permute_vertices`` is true. |
| When ``bidirectional`` is ``true`` for every edge s-t, the |
| corresponding anti-edge t-s is added as well, these anti-edges are not |
| counted towards ``m``. ``ep`` allows the user to specify which edges |
| are retained, this is useful in the case where the user wishes to |
| refrain from storing remote edges locally during generation to reduce |
| memory consumption. |
| |
| 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, and C Faloutsos. R-MAT: A Recursive |
| Model for Graph Mining. In Proceedings of 4th International Conference |
| on Data Mining, pages 442--446, 2004. |
| |
| ----------------------------------------------------------------------------- |
| |
| Copyright (C) 2009 The Trustees of Indiana University. |
| |
| Authors: Nick Edmonds and Andrew Lumsdaine |
| |
| .. |Logo| image:: pbgl-logo.png |
| :align: middle |
| :alt: Parallel BGL |
| :target: http://www.osl.iu.edu/research/pbgl |
| |
| .. _compressed sparse row graph: http://www.boost.org/libs/graph/doc/compressed_sparse_row.html |