havoqgt::upper_triangle_edge_generator Class Reference

#include <upper_triangle_edge_generator.hpp>

Classes
class	input_iterator_type
	InputIterator class for upper_triangle_edge_generator. More...

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

Public Member Functions
uint64_t	find_max_vertex (uint64_t num_edges)
	upper_triangle_edge_generator (uint64_t total_edges, int rank, int size, bool undirected)
void	sanity_check ()
input_iterator_type	begin ()
	Returns the begin of the input iterator. More...
input_iterator_type	end ()
	Returns the end of the input iterator. More...
uint64_t	max_vertex_id ()
size_t	size ()

Public Attributes
uint64_t	m_upper_edge_id
uint64_t	m_lower_edge_id
const uint64_t	m_total_edges
const bool	m_undirected
const uint64_t	m_max_vertex
uint64_t	m_i
uint64_t	m_j

Detailed Description

Definition at line 63 of file upper_triangle_edge_generator.hpp.

Member Typedef Documentation

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

Definition at line 66 of file upper_triangle_edge_generator.hpp.

Constructor & Destructor Documentation

havoqgt::upper_triangle_edge_generator::upper_triangle_edge_generator ( uint64_t  total_edges, int  rank, int  size, bool  undirected  )

inline

Definition at line 186 of file upper_triangle_edge_generator.hpp.

      : m_total_edges(total_edges)
      , m_undirected(undirected)
      , m_max_vertex(find_max_vertex(total_edges)) {
    // Determine the max_vertex id
    m_lower_edge_id = (total_edges / size) * rank;
    m_upper_edge_id = (total_edges / size) * (rank + 1);
    m_upper_edge_id = std::min(total_edges, m_upper_edge_id);

    uint64_t start_count = (total_edges / size) * rank;

    uint64_t count = 0;
    for (m_i = 0; count < start_count && m_i < m_max_vertex; m_i++) {
      for (m_j = m_i; count < start_count && m_j < m_max_vertex; m_j++) {
        count++;
      }
    }
    sanity_check();
  }

Here is the call graph for this function:

Member Function Documentation

input_iterator_type havoqgt::upper_triangle_edge_generator::begin ( )

inline

Returns the begin of the input iterator.

Definition at line 222 of file upper_triangle_edge_generator.hpp.

                              {
    const uint64_t num_edges = m_upper_edge_id - m_lower_edge_id;
    return input_iterator_type(m_max_vertex, num_edges, m_undirected, m_i, m_j);
  }

Here is the caller graph for this function:

input_iterator_type havoqgt::upper_triangle_edge_generator::end ( )

inline

Returns the end of the input iterator.

Definition at line 228 of file upper_triangle_edge_generator.hpp.

                            {
    const uint64_t num_edges = m_upper_edge_id - m_lower_edge_id;
    return input_iterator_type(m_max_vertex, num_edges, m_undirected);
  }

Here is the caller graph for this function:

uint64_t havoqgt::upper_triangle_edge_generator::find_max_vertex ( uint64_t  num_edges )

inline

Definition at line 166 of file upper_triangle_edge_generator.hpp.

                                               {
    // (1/2)(x)(x+1) <= num_edges.
    uint64_t x = 0, y = 0;
    num_edges *= 2;
    while (y < num_edges) {
      x++;
      y = x * (x + 1);
    }

    uint64_t count = 0;
    for (uint64_t i = 0; i < x; i++) {
      for (uint64_t j = i; j < x; j++) {
        count++;
      }
    }
    assert(count * 2 >= num_edges);

    return x + 1; // +1 because we skip 0 vertex
  };

uint64_t havoqgt::upper_triangle_edge_generator::max_vertex_id ( )

inline

Definition at line 233 of file upper_triangle_edge_generator.hpp.

                           {
    return m_max_vertex;
  }

void havoqgt::upper_triangle_edge_generator::sanity_check ( )

inline

Definition at line 207 of file upper_triangle_edge_generator.hpp.

                      {
    auto itr1 = begin();
    auto itr2 = begin();
    auto itr_end = end();
    while (itr1 != itr_end) {
      assert(itr1 == itr2);
      assert(*itr1 == *itr2);
      itr1++;
      itr2++;
    }

  }

Here is the call graph for this function:

Here is the caller graph for this function:

size_t havoqgt::upper_triangle_edge_generator::size ( )

inline

Definition at line 237 of file upper_triangle_edge_generator.hpp.

                {
    const uint64_t num_edges = m_upper_edge_id - m_lower_edge_id;
    return num_edges;
  }

Here is the caller graph for this function:

Member Data Documentation

uint64_t havoqgt::upper_triangle_edge_generator::m_i

Definition at line 247 of file upper_triangle_edge_generator.hpp.

uint64_t havoqgt::upper_triangle_edge_generator::m_j

Definition at line 247 of file upper_triangle_edge_generator.hpp.

uint64_t havoqgt::upper_triangle_edge_generator::m_lower_edge_id

Definition at line 242 of file upper_triangle_edge_generator.hpp.

const uint64_t havoqgt::upper_triangle_edge_generator::m_max_vertex

Definition at line 246 of file upper_triangle_edge_generator.hpp.

const uint64_t havoqgt::upper_triangle_edge_generator::m_total_edges

Definition at line 243 of file upper_triangle_edge_generator.hpp.

const bool havoqgt::upper_triangle_edge_generator::m_undirected

Definition at line 244 of file upper_triangle_edge_generator.hpp.

uint64_t havoqgt::upper_triangle_edge_generator::m_upper_edge_id

Definition at line 242 of file upper_triangle_edge_generator.hpp.

---

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

• include/havoqgt/upper_triangle_edge_generator.hpp