vertex_frontier.cuh

namespace cugraph

Functions

template<typename vertex_t, typename KeyIterator>
KeyIterator compute_key_lower_bound(

KeyIterator sorted_unique_key_first,

KeyIterator sorted_unique_key_last,

vertex_t v_threshold,

rmm::cuda_stream_view stream_view

)

template<typename vertex_t, typename KeyIterator>
std::vector<size_t> compute_key_segment_offsets(

KeyIterator sorted_key_first,

KeyIterator sorted_key_last,

raft::host_span<vertex_t const> segment_offsets,

vertex_t vertex_range_first,

rmm::cuda_stream_view stream_view

)

template<typename VertexIterator>
rmm::device_uvector<uint32_t> compute_vertex_list_bitmap_info(

VertexIterator sorted_unique_vertex_first,

VertexIterator sorted_unique_vertex_last,

typename thrust::iterator_traits<VertexIterator>::value_type vertex_range_first,

typename thrust::iterator_traits<VertexIterator>::value_type vertex_range_last,

rmm::cuda_stream_view stream_view

)

template<typename InputVertexIterator, typename OutputVertexIterator>
void device_bcast_vertex_list(

raft::comms::comms_t const &comm,

std::variant<raft::device_span<uint32_t const>, InputVertexIterator> v_list,

OutputVertexIterator output_v_first,

typename thrust::iterator_traits<InputVertexIterator>::value_type vertex_range_first,

typename thrust::iterator_traits<InputVertexIterator>::value_type vertex_range_last,

size_t v_list_size,

int root,

rmm::cuda_stream_view stream_view

)

template<typename OutputVertexIterator>
void retrieve_vertex_list_from_bitmap(

raft::device_span<uint32_t const> bitmap,

OutputVertexIterator output_v_first,

raft::device_span<size_t> count,

typename thrust::iterator_traits<OutputVertexIterator>::value_type vertex_range_first,

typename thrust::iterator_traits<OutputVertexIterator>::value_type vertex_range_last,

rmm::cuda_stream_view stream_view

)

template<typename vertex_t, typename idx_t>
struct index_to_repeated_vertex_tuple_t

Public Functions

inline __device__ cuda::std::tuple< vertex_t, idx_t > operator() (size_t i) const

Public Members

raft::device_span<vertex_t const> vertices = {}

idx_t repeat_count = {}

template<typename vertex_t, typename tag_t = void, bool multi_gpu = false, bool sorted_unique = false>
class key_bucket_t

Public Types

using key_type = std::conditional_t<std::is_same_v<tag_t, void>, vertex_t, cuda::std::tuple<vertex_t, tag_t>>

using optional_tag_type = std::conditional_t<std::is_same_v<tag_t, void>, std::byte, rmm::device_uvector<tag_t>>

Public Functions

key_bucket_t() = delete

key_bucket_t(key_bucket_t const &other) = delete

key_bucket_t(key_bucket_t &&other) = default

template<typename tag_type = tag_t, std::enable_if_t<std::is_same_v<tag_type, void>>* = nullptr>
inline key_bucket_t(

raft::handle_t const &handle

)

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline key_bucket_t(

raft::handle_t const &handle

)

template<typename tag_type = tag_t, std::enable_if_t<std::is_same_v<tag_type, void>>* = nullptr>
inline key_bucket_t(

raft::handle_t const &handle,

rmm::device_uvector<vertex_t> &&vertices

)

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline key_bucket_t(

raft::handle_t const &handle,

rmm::device_uvector<vertex_t> &&vertices,

rmm::device_uvector<tag_t> &&tags

)

key_bucket_t &operator=(key_bucket_t const &other) = delete

key_bucket_t &operator=(key_bucket_t &&other) = default

template<typename tag_type = tag_t, std::enable_if_t<std::is_same_v<tag_type, void>>* = nullptr>
inline void insert(

vertex_t vertex

)

@ brief insert a vertex to the bucket

Parameters:

vertex – vertex to insert

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline void insert(

cuda::std::tuple<vertex_t, tag_type> key

)

@ brief insert a (vertex, tag) pair to the bucket

Parameters:

• vertex – vertex of the (vertex, tag) pair to insert

• tag – tag of the (vertex, tag) pair to insert

template<typename VertexIterator, typename tag_type = tag_t, std::enable_if_t<std::is_same_v<tag_type, void>>* = nullptr>
inline void insert(

VertexIterator vertex_first,

VertexIterator vertex_last

)

@ brief insert a list of vertices to the bucket

Parameters:

• vertex_first – Iterator pointing to the first (inclusive) element of the vertices stored in device memory.

• vertex_last – Iterator pointing to the last (exclusive) element of the vertices stored in device memory.

template<typename KeyIterator, typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline void insert(

KeyIterator key_first,

KeyIterator key_last

)

@ brief insert a list of (vertex, tag) pairs to the bucket

Parameters:

• key_first – Iterator pointing to the first (inclusive) element of the (vertex,tag) pairs stored in device memory.

• key_last – Iterator pointing to the last (exclusive) element of the (vertex,tag) pairs stored in device memory.

inline size_t size() const

template<bool do_aggregate = multi_gpu>
inline std::enable_if_t<do_aggregate, size_t> aggregate_size(

) const

template<bool do_aggregate = multi_gpu>
inline std::enable_if_t<!do_aggregate, size_t> aggregate_size(

) const

inline void resize(size_t size)

inline void clear()

inline void shrink_to_fit()

inline auto begin()

inline auto const cbegin() const

inline auto const begin() const

inline auto end()

inline auto const cend() const

inline auto const end() const

inline auto vertex_begin()

inline auto const vertex_cbegin() const

inline auto const vertex_begin() const

inline auto vertex_end()

inline auto const vertex_cend() const

inline auto const vertex_end() const

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto tag_begin(

)

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto tag_cbegin(

) const

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto const tag_begin(

) const

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto tag_end(

)

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto tag_cend(

) const

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto const tag_end(

) const

Public Static Attributes

static bool constexpr is_sorted_unique = sorted_unique

Private Members

raft::handle_t const *handle_ptr_ = {nullptr}

rmm::device_uvector<vertex_t> vertices_

optional_tag_type tags_

template<typename vertex_t, typename tag_t = void, bool multi_gpu = false, bool sorted_unique = false>
class key_bucket_view_t

Public Types

using key_type = std::conditional_t<std::is_same_v<tag_t, void>, vertex_t, cuda::std::tuple<vertex_t, tag_t>>

using optional_tag_type = std::conditional_t<std::is_same_v<tag_t, void>, std::byte, raft::device_span<tag_t const>>

Public Functions

template<typename tag_type = tag_t, std::enable_if_t<std::is_same_v<tag_type, void>>* = nullptr>
inline key_bucket_view_t(

raft::handle_t const &handle,

raft::device_span<vertex_t const> vertices

)

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline key_bucket_view_t(

raft::handle_t const &handle,

raft::device_span<vertex_t const> vertices,

raft::device_span<tag_t const> tags

)

inline size_t size() const

template<bool do_aggregate = multi_gpu>
inline std::enable_if_t<do_aggregate, size_t> aggregate_size(

) const

template<bool do_aggregate = multi_gpu>
inline std::enable_if_t<!do_aggregate, size_t> aggregate_size(

) const

inline auto const cbegin() const

inline auto const begin() const

inline auto const cend() const

inline auto const end() const

inline auto const vertex_cbegin() const

inline auto const vertex_begin() const

inline auto const vertex_cend() const

inline auto const vertex_end() const

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto tag_cbegin(

) const

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto const tag_begin(

) const

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto tag_cend(

) const

template<typename tag_type = tag_t, std::enable_if_t<!std::is_same_v<tag_type, void>>* = nullptr>
inline auto const tag_end(

) const

Public Static Attributes

static bool constexpr is_sorted_unique = sorted_unique

Private Members

raft::handle_t const *handle_ptr_ = {nullptr}

raft::device_span<vertex_t const> vertices_ = {}

optional_tag_type tags_ = {}

template<typename vertex_t, typename idx_t, bool multi_gpu = false, bool sorted_unique = false>
class repeated_vertex_bucket_view_t

Public Types

using key_type = cuda::std::tuple<vertex_t, idx_t>

Public Functions

inline repeated_vertex_bucket_view_t(

raft::handle_t const &handle,

raft::device_span<vertex_t const> vertices,

idx_t repeat_count

)

inline size_t size() const

template<bool do_aggregate = multi_gpu>
inline std::enable_if_t<do_aggregate, size_t> aggregate_size(

) const

template<bool do_aggregate = multi_gpu>
inline std::enable_if_t<!do_aggregate, size_t> aggregate_size(

) const

inline auto const cbegin() const

inline auto const begin() const

inline auto const cend() const

inline auto const end() const

inline auto const vertex_cbegin() const

inline auto const vertex_begin() const

inline auto const vertex_cend() const

inline auto const vertex_end() const

inline auto tag_cbegin() const

inline auto const tag_begin() const

inline auto tag_cend() const

inline auto const tag_end() const

Public Static Attributes

static bool constexpr is_sorted_unique = sorted_unique

Private Members

raft::handle_t const *handle_ptr_ = {nullptr}

raft::device_span<vertex_t const> vertices_ = {}

idx_t repeat_count_ = {}

template<typename vertex_t, typename tag_t = void, bool multi_gpu = false, bool sorted_unique_key_bucket = false>
class vertex_frontier_t

Public Types

using key_type = std::conditional_t<std::is_same_v<tag_t, void>, vertex_t, cuda::std::tuple<vertex_t, tag_t>>

Public Functions

inline vertex_frontier_t(

raft::handle_t const &handle,

size_t num_buckets

)

inline size_t num_buckets() const

inline key_bucket_t<vertex_t, tag_t, multi_gpu, sorted_unique_key_bucket> &bucket(

size_t bucket_idx

)

inline key_bucket_t<vertex_t, tag_t, multi_gpu, sorted_unique_key_bucket> const &bucket(

size_t bucket_idx

) const

inline void swap_buckets(size_t bucket_idx0, size_t bucket_idx1)

template<typename SplitOp>
inline void split_bucket(

size_t this_bucket_idx,

raft::host_span<size_t const> move_to_bucket_indices,

SplitOp split_op

)

template<typename KeyIterator>
inline void insert_to_buckets(

uint8_t *bucket_idx_first,

uint8_t *bucket_idx_last,

KeyIterator key_first,

raft::host_span<size_t const> to_bucket_indices

)

Public Static Attributes

static size_t constexpr kInvalidBucketIdx = {std::numeric_limits<size_t>::max()}

Private Members

raft::handle_t const *handle_ptr_ = {nullptr}

std::vector<key_bucket_t<vertex_t, tag_t, multi_gpu, sorted_unique_key_bucket>> buckets_ = {}