havoqgt::rmat_edge_generator Class Reference

#include <rmat_edge_generator.hpp>

Classes
class	input_iterator_type
	InputIterator class for rmat_edge_generator. More...

Public Types
typedef uint64_t	vertex_descriptor
typedef std::pair< uint64_t, uint64_t >	edge_type

Public Member Functions
	rmat_edge_generator (uint64_t seed, uint64_t vertex_scale, uint64_t edge_count, double a, double b, double c, double d, bool scramble, bool undirected)
	seed used to be 5489 More...
input_iterator_type	begin ()
	Returns the begin of the input iterator. More...
input_iterator_type	end ()
	Returns the end of the input iterator. More...
void	sanity_max_vertex_id ()
uint64_t	max_vertex_id ()
size_t	size ()

Protected Member Functions
edge_type	generate_edge ()
	Generates a new RMAT edge. This function was adapted from the Boost Graph Library. More...
edge_type	generate_edge (boost::uniform_01< boost::mt19937 > &gen)

Protected Attributes
const uint64_t	m_seed
boost::mt19937	m_rng
boost::uniform_01< boost::mt19937 >	m_gen
const uint64_t	m_vertex_scale
const uint64_t	m_edge_count
const bool	m_scramble
const bool	m_undirected
const double	m_rmat_a
const double	m_rmat_b
const double	m_rmat_c
const double	m_rmat_d

Detailed Description

RMAT edge generator, based on Boost Graph's RMAT generator

Options include scrambling vertices based on a hash funciton, and symmetrizing the list. Generated edges are not sorted. May contain duplicate and self edges.

Definition at line 68 of file rmat_edge_generator.hpp.

Member Typedef Documentation

typedef std::pair<uint64_t, uint64_t> havoqgt::rmat_edge_generator::edge_type

Definition at line 72 of file rmat_edge_generator.hpp.

typedef uint64_t havoqgt::rmat_edge_generator::vertex_descriptor

Definition at line 71 of file rmat_edge_generator.hpp.

Constructor & Destructor Documentation

havoqgt::rmat_edge_generator::rmat_edge_generator ( uint64_t  seed, uint64_t  vertex_scale, uint64_t  edge_count, double  a, double  b, double  c, double  d, bool  scramble, bool  undirected  )

inline

seed used to be 5489

Definition at line 150 of file rmat_edge_generator.hpp.

                : m_seed(seed)
                , m_rng(seed)
        , m_gen(m_rng)
      , m_vertex_scale(vertex_scale)
      , m_edge_count(edge_count)
      , m_scramble(scramble)
      , m_undirected(undirected)
      , m_rmat_a(a)
      , m_rmat_b(b)
      , m_rmat_c(c)
      , m_rmat_d(d) {

      //  sanity_max_vertex_id();

        // #ifdef DEBUG
        //   auto itr1 = begin();
        //   auto itr2 = begin();
        //   while (itr1 != end()) {
        //     assert(itr2 != end());
        //     assert(*itr1 == *itr2);
        //     assert(itr1 == itr2);
        //     itr1++;
        //     itr2++;
        //   }
        // #endif
      }

Member Function Documentation

input_iterator_type havoqgt::rmat_edge_generator::begin ( )

inline

Returns the begin of the input iterator.

Definition at line 182 of file rmat_edge_generator.hpp.

                              {
    return input_iterator_type(this, 0);
  }

Here is the caller graph for this function:

input_iterator_type havoqgt::rmat_edge_generator::end ( )

inline

Returns the end of the input iterator.

Definition at line 187 of file rmat_edge_generator.hpp.

                            {
    return input_iterator_type(this, m_edge_count);
  }

Here is the caller graph for this function:

edge_type havoqgt::rmat_edge_generator::generate_edge ( )

inlineprotected

Generates a new RMAT edge. This function was adapted from the Boost Graph Library.

Definition at line 215 of file rmat_edge_generator.hpp.

                            {
        return generate_edge(m_gen);
  }

Here is the caller graph for this function:

edge_type havoqgt::rmat_edge_generator::generate_edge ( boost::uniform_01< boost::mt19937 > &  gen )

inlineprotected

Definition at line 218 of file rmat_edge_generator.hpp.

                                                              {
    double rmat_a = m_rmat_a;
    double rmat_b = m_rmat_b;
    double rmat_c = m_rmat_c;
    double rmat_d = m_rmat_d;
    uint64_t u = 0, v = 0;
    uint64_t step = (uint64_t(1) << m_vertex_scale)/2;
    for (unsigned int j = 0; j < m_vertex_scale; ++j) {
      double p = gen();

      if (p < rmat_a)
        ;
      else if (p >= rmat_a && p < rmat_a + rmat_b)
        v += step;
      else if (p >= rmat_a + rmat_b && p < rmat_a + rmat_b + rmat_c)
        u += step;
      else { // p > a + b + c && p < a + b + c + d
        u += step;
        v += step;
      }

      step /= 2;

      // 0.2 and 0.9 are hardcoded in the reference SSCA implementation.
      // The maximum change in any given value should be less than 10%
      rmat_a *= 0.9 + 0.2 * gen();
      rmat_b *= 0.9 + 0.2 * gen();
      rmat_c *= 0.9 + 0.2 * gen();
      rmat_d *= 0.9 + 0.2 * gen();

      double S = rmat_a + rmat_b + rmat_c + rmat_d;

      rmat_a /= S; rmat_b /= S; rmat_c /= S;
      // d /= S;
      // Ensure all values add up to 1, regardless of floating point errors
      rmat_d = 1. - rmat_a - rmat_b - rmat_c;
    }
    if(m_scramble) {
      u = havoqgt::detail::hash_nbits(u, m_vertex_scale);
      v = havoqgt::detail::hash_nbits(v, m_vertex_scale);
    }

    return std::make_pair(u, v);
  }

Here is the call graph for this function:

uint64_t havoqgt::rmat_edge_generator::max_vertex_id ( )

inline

Definition at line 205 of file rmat_edge_generator.hpp.

                           {
    return (uint64_t(1) << uint64_t(m_vertex_scale)) - 1;
  }

Here is the caller graph for this function:

void havoqgt::rmat_edge_generator::sanity_max_vertex_id ( )

inline

Definition at line 191 of file rmat_edge_generator.hpp.

                              {
    auto itr = begin();
    auto itr_end = end();

    uint64_t value = 0;
    while (itr != itr_end) {
      value = std::max(value, (*itr).first);
      value = std::max(value, (*itr).second);
    }

    std::cout << " value: " << value << std::endl;
    assert(max_vertex_id() == value);

  }

Here is the call graph for this function:

size_t havoqgt::rmat_edge_generator::size ( )

inline

Definition at line 209 of file rmat_edge_generator.hpp.

                {
        return m_edge_count;
  }

Member Data Documentation

const uint64_t havoqgt::rmat_edge_generator::m_edge_count

protected

Definition at line 268 of file rmat_edge_generator.hpp.

boost::uniform_01<boost::mt19937> havoqgt::rmat_edge_generator::m_gen

protected

Definition at line 266 of file rmat_edge_generator.hpp.

const double havoqgt::rmat_edge_generator::m_rmat_a

protected

Definition at line 271 of file rmat_edge_generator.hpp.

const double havoqgt::rmat_edge_generator::m_rmat_b

protected

Definition at line 272 of file rmat_edge_generator.hpp.

const double havoqgt::rmat_edge_generator::m_rmat_c

protected

Definition at line 273 of file rmat_edge_generator.hpp.

const double havoqgt::rmat_edge_generator::m_rmat_d

protected

Definition at line 274 of file rmat_edge_generator.hpp.

boost::mt19937 havoqgt::rmat_edge_generator::m_rng

protected

Definition at line 265 of file rmat_edge_generator.hpp.

const bool havoqgt::rmat_edge_generator::m_scramble

protected

Definition at line 269 of file rmat_edge_generator.hpp.

const uint64_t havoqgt::rmat_edge_generator::m_seed

protected

Definition at line 264 of file rmat_edge_generator.hpp.

const bool havoqgt::rmat_edge_generator::m_undirected

protected

Definition at line 270 of file rmat_edge_generator.hpp.

const uint64_t havoqgt::rmat_edge_generator::m_vertex_scale

protected

Definition at line 267 of file rmat_edge_generator.hpp.

---

The documentation for this class was generated from the following file:

• include/havoqgt/rmat_edge_generator.hpp