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_ = {}