Graph Functions#

template<typename vertex_t, typename edge_t, bool multi_gpu>
std::enable_if_t<multi_gpu, std::tuple<rmm::device_uvector<vertex_t>, renumber_meta_t<vertex_t, edge_t, multi_gpu>>> renumber_edgelist(raft::handle_t const &handle, std::optional<rmm::device_uvector<vertex_t>> &&local_vertices, std::vector<vertex_t*> const &edgelist_srcs, std::vector<vertex_t*> const &edgelist_dsts, std::vector<edge_t> const &edgelist_edge_counts, std::optional<std::vector<std::vector<edge_t>>> const &edgelist_intra_partition_segment_offsets, bool store_transposed, bool do_expensive_check = false)#

renumber edgelist (multi-GPU)

This function assumes that vertices are pre-shuffled to their target processes and edges are pre-shuffled to their target processess and edge partitions using compute_gpu_id_from_vertex_t and compute_gpu_id_from_ext_edge_endpoints_t & compute_partition_id_from_ext_edge_endpoints_t functors, respectively.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

local_vertices – If valid, part of the entire set of vertices in the graph to be renumbered. This parameter can be used to include isolated vertices. Applying the compute_gpu_id_from_vertex_t to every vertex should return the local GPU ID for this function to work (vertices should be pre-shuffled).

edgelist_srcs – Pointers (one pointer per local edge partition assigned to this process) to edge source vertex IDs. Source IDs are updated in-place ([INOUT] parameter). Applying the compute_gpu_id_from_ext_edge_endpoints_t functor to every (destination ID, source ID) pair (if store_transposed = true) or (source ID, destination ID) pair (if store_transposed = false) should return the local GPU ID for this function to work (edges should be pre-shuffled). Applying the compute_partition_id_from_ext_edge_endpoints_t to every (destination ID, source ID) pair (if store_transposed = true) or (source ID, destination ID) pair (if store_transposed = false) should also return the corresponding edge partition ID. The best way to enforce this is to use shuffle_ext_vertex_pairs_to_local_gpu_by_edge_partitioning & groupby_and_count_edgelist_by_local_partition_id.

edgelist_dsts – Pointers (one pointer per local edge partition assigned to this process) to edge destination vertex IDs. Destination IDs are updated in-place ([INOUT] parameter).

edgelist_edge_counts – Edge counts (one count per local edge partition assigned to this process).

edgelist_intra_partition_segment_offsets – If valid, store segment offsets within a local edge partition; a local edge partition can be further segmented by applying the compute_gpu_id_from_vertex_t function to edge minor vertex IDs. This optinoal information is used for further memory footprint optimization if provided.

store_transposed – Should be true if renumbered edges will be used to create a graph with store_transposed = true. Should be false if the edges will be used to create a graph with store_transposed = false.

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

std::tuple<rmm::device_uvector<vertex_t>, renumber_meta_t<vertex_t, edge_t, multi_gpu>> Tuple of labels (vertex IDs before renumbering) for the entire set of vertices (assigned to this process in multi-GPU) and meta-data collected while renumbering. The meta-data includes total number of vertices, total number of edges, partition_t object storing graph partitioning information, vertex partition segment offsets (a vertex partition is partitioned to multiple segments based on vertex degrees), and the number of local unique edge major & minor vertex IDs. This meta-data is expected to be used in graph construction & graph primitives.

template<typename vertex_t, typename edge_t, bool multi_gpu>
std::enable_if_t<!multi_gpu, std::tuple<rmm::device_uvector<vertex_t>, renumber_meta_t<vertex_t, edge_t, multi_gpu>>> renumber_edgelist(raft::handle_t const &handle, std::optional<rmm::device_uvector<vertex_t>> &&vertices, vertex_t *edgelist_srcs, vertex_t *edgelist_dsts, edge_t num_edgelist_edges, bool store_transposed, bool do_expensive_check = false)#

renumber edgelist (single-GPU)

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – If valid, vertices in the graph to be renumbered. This parameter can be used to include isolated vertices.

edgelist_srcs – A pointer to edge source vertex IDs. Source IDs are updated in-place ([INOUT] parameter).

edgelist_dsts – A pointer to edge destination vertex IDs. Destination IDs are updated in-place ([INOUT] parameter).

num_edgelist_edges – Number of edges in the edgelist.

store_transposed – Should be true if renumbered edges will be used to create a graph with store_transposed = true. Should be false if the edges will be used to create a graph with store_transposed = false.

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

std::tuple<rmm::device_uvector<vertex_t>, renumber_meta_t<vertex_t, edge_t, multi_gpu>> Tuple of labels (vertex IDs before renumbering) for the entire set of vertices and meta-data collected while renumbering. The meta-data includes vertex partition segment offsets (a vertex partition is partitioned to multiple segments based on vertex degrees). This meta-data is expected to be used in graph construction & graph primitives.

template<typename vertex_t, bool multi_gpu>
void renumber_ext_vertices(raft::handle_t const &handle, vertex_t *vertices, size_t num_vertices, vertex_t const *renumber_map_labels, vertex_t local_int_vertex_first, vertex_t local_int_vertex_last, bool do_expensive_check = false)#

Renumber external vertices to internal vertices based on the provided renumber_map_labels.

Note cugraph::invalid_id<vertex_t>::value remains unchanged.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – Pointer to the vertices to be renumbered. The input external vertices are renumbered to internal vertices in-place.

num_vertices – Number of vertices to be renumbered.

renumber_map_labels – Pointer to the external vertices corresponding to the internal vertices in the range [local_int_vertex_first, local_int_vertex_last).

local_int_vertex_first – The first local internal vertex (inclusive, assigned to this process in multi-GPU).

local_int_vertex_last – The last local internal vertex (exclusive, assigned to this process in multi-GPU).

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

template<typename vertex_t>
void unrenumber_local_int_vertices(raft::handle_t const &handle, vertex_t *vertices, size_t num_vertices, vertex_t const *renumber_map_labels, vertex_t local_int_vertex_first, vertex_t local_int_vertex_last, bool do_expensive_check = false)#

Unrenumber local internal vertices to external vertices based on the providied renumber_map_labels.

Note cugraph::invalid_id<vertex_t>::value remains unchanged.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – Pointer to the local internal vertices to be unrenumbered. Each input element should be in [local_int_vertex_first, local_int_vertex_last). The input internal vertices are renumbered to external vertices in-place.

num_vertices – Number of vertices to be unrenumbered.

renumber_map_labels – Pointer to the external vertices corresponding to the internal vertices in the range [local_int_vertex_first, local_int_vertex_last).

local_int_vertex_first – The first local internal vertex (inclusive, assigned to this process in multi-GPU).

local_int_vertex_last – The last local internal vertex (exclusive, assigned to this process in multi-GPU).

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

template<typename vertex_t, bool multi_gpu>
void unrenumber_int_vertices(raft::handle_t const &handle, vertex_t *vertices, size_t num_vertices, vertex_t const *renumber_map_labels, std::vector<vertex_t> const &vertex_partition_range_lasts, bool do_expensive_check = false)#

Unrenumber (possibly non-local) internal vertices to external vertices based on the providied renumber_map_labels.

Note cugraph::invalid_id<vertex_t>::value remains unchanged.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – Pointer to the internal vertices to be unrenumbered. The input internal vertices are renumbered to external vertices in-place.

num_vertices – Number of vertices to be unrenumbered.

renumber_map_labels – Pointer to the external vertices corresponding to the internal vertices in the range [local_int_vertex_first, local_int_vertex_last).

vertex_partition_range_lasts – Last local internal vertices (exclusive, assigned to each process in multi-GPU).

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

template<typename vertex_t, bool store_transposed, bool multi_gpu>
std::enable_if_t<multi_gpu, void> unrenumber_local_int_edges(raft::handle_t const &handle, std::vector<vertex_t*> const &edgelist_srcs, std::vector<vertex_t*> const &edgelist_dsts, std::vector<size_t> const &edgelist_edge_counts, vertex_t const *renumber_map_labels, std::vector<vertex_t> const &vertex_partition_range_lasts, std::optional<std::vector<std::vector<size_t>>> const &edgelist_intra_partition_segment_offsets, bool do_expensive_check = false)#

Unrenumber local edges’ internal source & destination IDs to external IDs based on the provided renumber_map_labels (multi-GPU).

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms. @params edgelist_srcs Pointers (one pointer per local edge partition assigned to this process) to the local internal source vertex IDs to be unrenumbered. The input source vertex IDs are renumbered to external IDs in-place. @params edgelist_dsts Pointers (one pointer per local edge partition assigned to this process) to the local internal destination vertex IDs to be unrenumbered. The input destination vertex IDs are renumbered to external IDs in-place.

edgelist_edge_counts – Edge counts (one count per local edge partition assigned to this process).

renumber_map_labels – Pointer to the external vertices corresponding to the internal vertices in the range assigned to this process.

vertex_partition_range_lasts – Last local internal vertices (exclusive, assigned to each process in multi-GPU).

edgelist_intra_partition_segment_offsets – If valid, store segment offsets within a local edge partition; a local edge partition can be further segmented by applying the compute_gpu_id_from_vertex_t function to edge minor vertex IDs. This optinoal information is used for further memory footprint optimization if provided.

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

template<typename vertex_t, bool store_transposed, bool multi_gpu>
std::enable_if_t<!multi_gpu, void> unrenumber_local_int_edges(raft::handle_t const &handle, vertex_t *edgelist_srcs, vertex_t *edgelist_dsts, size_t num_edgelist_edges, vertex_t const *renumber_map_labels, vertex_t num_vertices, bool do_expensive_check = false)#

Unrenumber local edges’ internal source & destination IDs to external IDs based on the provided renumber_map_labels (single-GPU).

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms. @params edgelist_srcs Pointer to the local internal source vertex IDs to be unrenumbered. The input source vertex IDs are renumbered to external IDs in-place. @params edgelist_dsts Pointer to the local internal destination vertex IDs to be unrenumbered. The input destination vertex IDs are renumbered to external IDs in-place.

num_edgelist_edges – Number of edges in the edge list.

renumber_map_labels – Pointer to the external vertices corresponding to the internal vertices.

num_vertices – Number of vertices to be unrenumbered.

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

template<typename vertex_t, bool multi_gpu>
void renumber_local_ext_vertices(raft::handle_t const &handle, vertex_t *vertices, size_t num_vertices, vertex_t const *renumber_map_labels, vertex_t local_int_vertex_first, vertex_t local_int_vertex_last, bool do_expensive_check = false)#

Renumber local external vertices to internal vertices based on the provided renumber_map_labels.

Note cugraph::invalid_id<vertex_t>::value remains unchanged.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – Pointer to the vertices to be renumbered. The input external vertices are renumbered to internal vertices in-place.

num_vertices – Number of vertices to be renumbered.

renumber_map_labels – Pointer to the external vertices corresponding to the internal vertices in the range [local_int_vertex_first, local_int_vertex_last).

local_int_vertex_first – The first local internal vertex (inclusive, assigned to this process in multi-GPU).

local_int_vertex_last – The last local internal vertex (exclusive, assigned to this process in multi-GPU).

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

template<typename vertex_t, typename edge_t, typename weight_t, typename edge_type_t, bool store_transposed, bool multi_gpu>
std::tuple<rmm::device_uvector<vertex_t>, rmm::device_uvector<vertex_t>, std::optional<rmm::device_uvector<weight_t>>, std::optional<rmm::device_uvector<edge_t>>, std::optional<rmm::device_uvector<edge_type_t>>> decompress_to_edgelist(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, std::optional<edge_property_view_t<edge_t, weight_t const*>> edge_weight_view, std::optional<edge_property_view_t<edge_t, edge_t const*>> edge_id_view, std::optional<edge_property_view_t<edge_t, edge_type_t const*>> edge_type_view, std::optional<raft::device_span<vertex_t const>> renumber_map, bool do_expensive_check = false)#

Construct the edge list from the graph view object.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

edge_type_t – Type of edge types. Needs to be an integral type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph_view – Graph view object of the graph to be decompressed.

edge_weight_view – Optional view object holding edge weights for graph_view.

edge_id_view – Optional view object holding edge ids for graph_view.

edge_type_view – Optional view object holding edge types for graph_view.

renumber_map – If valid, return the renumbered edge list based on the provided renumber_map

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Tuple of edge sources, destinations, (optional) edge weights (if edge_weight_view.has_value() is true) and (optional) edge ids (if edge_id_view.has_value() is true).

template<typename vertex_t, typename edge_t, typename weight_t, typename edge_type_t, typename edge_time_t, bool multi_gpu>
std::tuple<rmm::device_uvector<vertex_t>, rmm::device_uvector<vertex_t>, std::optional<rmm::device_uvector<weight_t>>, std::optional<rmm::device_uvector<edge_t>>, std::optional<rmm::device_uvector<edge_type_t>>, std::optional<rmm::device_uvector<edge_time_t>>, std::optional<rmm::device_uvector<edge_time_t>>> symmetrize_edgelist(raft::handle_t const &handle, rmm::device_uvector<vertex_t> &&edgelist_srcs, rmm::device_uvector<vertex_t> &&edgelist_dsts, std::optional<rmm::device_uvector<weight_t>> &&edgelist_weights, std::optional<rmm::device_uvector<edge_t>> &&edgelist_edge_ids, std::optional<rmm::device_uvector<edge_type_t>> &&edgelist_edge_types, std::optional<rmm::device_uvector<edge_time_t>> &&edgelist_edge_start_times, std::optional<rmm::device_uvector<edge_time_t>> &&edgelist_edge_end_times, bool reciprocal)#

Symmetrize edgelist.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

edge_type_t – Type of edge type identifiers. Needs to be an integral type.

edge_time_t – Type of edge time. Needs to be an integral type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

edgelist_srcs – Vector of edge source vertex IDs. If multi-GPU, applying the compute_gpu_id_from_ext_edge_endpoints_t to every edge should return the local GPU ID for this function to work (edges should be pre-shuffled).

edgelist_dsts – Vector of edge destination vertex IDs.

edgelist_weights – Vector of edge weights.

edgelist_edge_ids – Vector of edge ids

edgelist_edge_types – Vector of edge types

edgelist_edge_start_times – Vector of edge start times

edgelist_edge_end_times – Vector of edge end times

reciprocal – Flag indicating whether to keep (if set to false) or discard (if set to true) edges that appear only in one direction.

Returns:

Tuple of symmetrized sources, destinations, optional weights, optional edge ids, optional edge types, optional edge start times and optional edge end times

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
std::tuple<graph_t<vertex_t, edge_t, store_transposed, multi_gpu>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>>, std::optional<rmm::device_uvector<vertex_t>>> symmetrize_graph(raft::handle_t const &handle, graph_t<vertex_t, edge_t, store_transposed, multi_gpu> &&graph, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>> &&edge_weights, std::optional<rmm::device_uvector<vertex_t>> &&renumber_map, bool reciprocal = false, bool do_expensive_check = false)#

Symmetrize the input graph.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph – Graph object to be symmetrized.

edge_weights – Optional owning object holding edge weights for graph.

renumber_map – Renumber map to recover the original vertex IDs from the renumbered vertex IDs. This should be valid if multi-GPU.

reciprocal – If true, an edge is kept only when the reversed edge also exists. If false, keep (and symmetrize) all the edges that appear only in one direction.

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Return a symmetrized graph, an owning object holding edge weights (if edge_weights.has_value() is true) and a new renumber map (to recover the original vertex IDs, if renumber_map.has_value() is true).

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
std::tuple<graph_t<vertex_t, edge_t, store_transposed, multi_gpu>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>>, std::optional<rmm::device_uvector<vertex_t>>> transpose_graph(raft::handle_t const &handle, graph_t<vertex_t, edge_t, store_transposed, multi_gpu> &&graph, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>> &&edge_weights, std::optional<rmm::device_uvector<vertex_t>> &&renumber_map, bool do_expensive_check = false)#

Transpose the input graph.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph – Graph object to be transposed.

edge_weights – Optional owning object holding edge weights for graph.

renumber_map – Renumber map to recover the original vertex IDs from the renumbered vertex IDs. This should be valid if multi-GPU.

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Return a transposed graph, an owning object holding edge weights (if edge_weights.has_value() is true) and a new renumber map (to recover the original vertex IDs, if renumber_map.has_value() is true).

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
std::tuple<graph_t<vertex_t, edge_t, !store_transposed, multi_gpu>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, !store_transposed, multi_gpu>, weight_t>>, std::optional<rmm::device_uvector<vertex_t>>> transpose_graph_storage(raft::handle_t const &handle, graph_t<vertex_t, edge_t, store_transposed, multi_gpu> &&graph, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>> &&edge_weights, std::optional<rmm::device_uvector<vertex_t>> &&renumber_map, bool do_expensive_check = false)#

Transpose the storage format (no change in an actual graph topology).

In SG, convert between CSR and CSC. In multi-GPU, currently convert between CSR + DCSR hybrid and CSC + DCSC hybrid (but the internal representation in multi-GPU is subject to change).

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph – Graph object to transpose its storage format.

edge_weights – Optional owning object holding edge weights for graph.

renumber_map – Renumber map to recover the original vertex IDs from the renumbered vertex IDs. This should be valid if multi-GPU.

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

std::tuple<graph_t<vertex_t, edge_t, weight_t, !store_transposed, multi_gpu>,

Returns:

Return a storage transposed graph, an owning object holding edge weights (if edge_weights.has_value() is true) and a new renumber map (to recover the original vertex IDs, if renumber_map.has_value() is true).

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
std::tuple<graph_t<vertex_t, edge_t, store_transposed, multi_gpu>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>>, std::optional<rmm::device_uvector<vertex_t>>> coarsen_graph(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, std::optional<edge_property_view_t<edge_t, weight_t const*>> edge_weight_view, vertex_t const *labels, bool renumber, bool do_expensive_check = false)#

Compute the coarsened graph.

Aggregates the vertices with the same label to a new vertex in the output coarsened graph. Multi-edges in the coarsened graph are collapsed to a single edge with its weight equal to the sum of multi-edge weights.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph_view – Graph view object of the input graph to be coarsened.

edge_weight_view – Optional view object holding edge weights for graph_view.

labels – Vertex labels (assigned to this process in multi-GPU) to be used in coarsening.

renumber – Flag indicating whether to renumber vertices or not (must be true if multi_gpu is true). Setting renumber to false is highly discouraged except for testing as this negatively affects the performance and memory footprint. If renumber is set to true, labels should have only non-negative integers and the number of vertices is assumed to be the maximum element in labels (reduced over the entire set of GPUs in multi-GPU) + 1. This may produce many isolated vertices if the number of unique elements (over the entire set of GPUs in multi-GPU) in labels is much smaller than the assumed number of vertices.

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Tuple of the coarsened graph, coarsened graph edge weights (if edge_weight_view.has_value() is true) and the renumber map (if renumber is true).

template<typename vertex_t, bool multi_gpu>
void relabel(raft::handle_t const &handle, std::tuple<vertex_t const*, vertex_t const*> old_new_label_pairs, vertex_t num_label_pairs, vertex_t *labels, vertex_t num_labels, bool skip_missing_labels, bool do_expensive_check = false)#

Relabel old labels to new labels.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

old_new_label_pairs – Pairs of an old label and the corresponding new label (each process holds only part of the entire old labels and the corresponding new labels; partitioning can be arbitrary).

num_label_pairs – Number of (old, new) label pairs.

labels – Labels to be relabeled. This initially holds old labels. Old labels are updated to new labels in-place ([INOUT] parameter).

num_labels – Number of labels to be relabeled.

skip_missing_labels – Flag dictating the behavior on missing labels (labels contains old labels missing in old_new_label_pairs). If set to true, missing elements are skipped (not relabeled). If set to false, undefined behavior (if do_expensive_check is set to true, this function will throw an exception).

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

rmm::device_uvector<vertex_t> New labels corresponding to the old_labels.

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
std::tuple<rmm::device_uvector<vertex_t>, rmm::device_uvector<vertex_t>, std::optional<rmm::device_uvector<weight_t>>, rmm::device_uvector<size_t>> extract_induced_subgraphs(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, std::optional<edge_property_view_t<edge_t, weight_t const*>> edge_weight_view, raft::device_span<size_t const> subgraph_offsets, raft::device_span<vertex_t const> subgraph_vertices, bool do_expensive_check = false)#

extract induced subgraph(s).

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph_view – Graph view object, we extract induced subgraphs from graph_view.

edge_weight_view – Optional view object holding edge weights for graph_view.

subgraph_offsets – Span pointing to subgraph vertex offsets

subgraph_vertices – Span pointing to subgraph vertices. subgraph_offsets and subgraph_vertices provide vertex sets (or local vertex sets in multi-GPU) for subgraph_offsets.size() - 1 subgraphs to extract. For the i’th subgraph to extract, one can extract the (local-)vertex set by accessing a subset of subgraph_vertices, where the range of the subset is [subgraph_offsetes[i], subgraph_offsets[i + 1]). In multi-GPU, the vertex set for each subgraph is distributed in multiple-GPUs and each GPU holds only the vertices that are local to the GPU.

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Quadraplet of edge major (destination if store_transposed is true, source otherwise) vertices, edge minor (source if store_transposed is true, destination otherwise) vertices, edge weights (if edge_weight_view.has_value() is true), and edge offsets for each induced subgraphs (size == num_subgraphs + 1). The sizes of the edge major & minor vertices are edge_offsets[num_subgraphs].

template<typename vertex_t, typename edge_t, typename weight_t, typename edge_type_t, bool store_transposed, bool multi_gpu>
std::tuple<graph_t<vertex_t, edge_t, store_transposed, multi_gpu>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_type_t>>, std::optional<rmm::device_uvector<vertex_t>>> create_graph_from_edgelist(raft::handle_t const &handle, std::optional<rmm::device_uvector<vertex_t>> &&vertices, rmm::device_uvector<vertex_t> &&edgelist_srcs, rmm::device_uvector<vertex_t> &&edgelist_dsts, std::optional<rmm::device_uvector<weight_t>> &&edgelist_weights, std::optional<rmm::device_uvector<edge_t>> &&edgelist_edge_ids, std::optional<rmm::device_uvector<edge_type_t>> &&edgelist_edge_types, graph_properties_t graph_properties, bool renumber, bool do_expensive_check = false)#

create a graph from (the optional vertex list and) the given edge list (with optional edge IDs and types).

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weight. Needs to be floating point type

edge_type_t – Type of edge type. Needs to be an integral type, currently only int32_t is supported

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – If valid, part of the entire set of vertices in the graph to be renumbered. This parameter can be used to include isolated vertices. If renumber is false and vertices is valid, vertices elements should be consecutive integers starting from 0. If multi-GPU, applying the compute_gpu_id_from_vertex_t to every vertex should return the local GPU ID for this function to work (vertices should be pre-shuffled).

edgelist_srcs – Vector of edge source vertex IDs. If multi-GPU, applying the compute_gpu_id_from_ext_edge_endpoints_t to every edge should return the local GPU ID for this function to work (edges should be pre-shuffled).

edgelist_dsts – Vector of edge destination vertex IDs.

edgelist_weights – Vector of weight values for edges

edgelist_edge_ids – Vector of edge_id values for edges

edgelist_edge_types – Vector of edge_type values for edges

graph_properties – Properties of the graph represented by the input (optional vertex list and) edge list.

renumber – Flag indicating whether to renumber vertices or not (must be true if multi_gpu is true).

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Tuple of the generated graph and optional edge_property_t objects storing the provided edge properties and a renumber map (if renumber is true).

template<typename vertex_t, typename edge_t, typename weight_t, typename edge_type_t, typename edge_time_t, bool store_transposed, bool multi_gpu>
std::tuple<graph_t<vertex_t, edge_t, store_transposed, multi_gpu>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_type_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_time_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_time_t>>, std::optional<rmm::device_uvector<vertex_t>>> create_graph_from_edgelist(raft::handle_t const &handle, std::optional<rmm::device_uvector<vertex_t>> &&vertices, rmm::device_uvector<vertex_t> &&edgelist_srcs, rmm::device_uvector<vertex_t> &&edgelist_dsts, std::optional<rmm::device_uvector<weight_t>> &&edgelist_weights, std::optional<rmm::device_uvector<edge_t>> &&edgelist_edge_ids, std::optional<rmm::device_uvector<edge_type_t>> &&edgelist_edge_types, std::optional<rmm::device_uvector<edge_time_t>> &&edgelist_edge_start_times, std::optional<rmm::device_uvector<edge_time_t>> &&edgelist_edge_end_times, graph_properties_t graph_properties, bool renumber, bool do_expensive_check = false)#

create a graph from (the optional vertex list and) the given edge list (with optional edge IDs and types).

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weight. Needs to be floating point type

edge_type_t – Type of edge type. Needs to be an integral type, currently only int32_t is supported

edge_time_t – Type of edge time. Needs to be an integral type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix. transposed.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – If valid, part of the entire set of vertices in the graph to be renumbered. This parameter can be used to include isolated vertices. If renumber is false and vertices is valid, vertices elements should be consecutive integers starting from 0. If multi-GPU, applying the compute_gpu_id_from_vertex_t to every vertex should return the local GPU ID for this function to work (vertices should be pre-shuffled).

edgelist_srcs – Vector of edge source vertex IDs. If multi-GPU, applying the compute_gpu_id_from_ext_edge_endpoints_t to every edge should return the local GPU ID for this function to work (edges should be pre-shuffled).

edgelist_dsts – Vector of edge destination vertex IDs.

edgelist_weights – Vector of weight values for edges

edgelist_edge_ids – Vector of edge_id values for edges

edgelist_edge_types – Vector of edge_type values for edges

edgelist_edge_start_times – Vector of start time values for edges

edgelist_edge_end_times – Vector of end time values for edges

graph_properties – Properties of the graph represented by the input (optional vertex list and) edge list.

renumber – Flag indicating whether to renumber vertices or not (must be true if multi_gpu is true).

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Tuple of the generated graph and optional edge_property_t objects storing the provided edge properties and a renumber map (if renumber is true).

template<typename vertex_t, typename edge_t, typename weight_t, typename edge_type_t, bool store_transposed, bool multi_gpu>
std::tuple<graph_t<vertex_t, edge_t, store_transposed, multi_gpu>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_type_t>>, std::optional<rmm::device_uvector<vertex_t>>> create_graph_from_edgelist(raft::handle_t const &handle, std::optional<rmm::device_uvector<vertex_t>> &&vertices, std::vector<rmm::device_uvector<vertex_t>> &&edgelist_srcs, std::vector<rmm::device_uvector<vertex_t>> &&edgelist_dsts, std::optional<std::vector<rmm::device_uvector<weight_t>>> &&edgelist_weights, std::optional<std::vector<rmm::device_uvector<edge_t>>> &&edgelist_edge_ids, std::optional<std::vector<rmm::device_uvector<edge_type_t>>> &&edgelist_edge_types, graph_properties_t graph_properties, bool renumber, bool do_expensive_check = false)#

create a graph from (the optional vertex list and) the given edge list (with optional edge IDs and types).

This version takes edge list in multiple chunks (e.g. edge data from multiple files).

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weight. Needs to be floating point type

edge_type_t – Type of edge type. Needs to be an integral type, currently only int32_t is supported

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – If valid, part of the entire set of vertices in the graph to be renumbered. This parameter can be used to include isolated vertices. If renumber is false and vertices is valid, vertices elements should be consecutive integers starting from 0. If multi-GPU, applying the compute_gpu_id_from_vertex_t to every vertex should return the local GPU ID for this function to work (vertices should be pre-shuffled).

edgelist_srcs – Vectors of edge source vertex IDs. If multi-GPU, applying the compute_gpu_id_from_ext_edge_endpoints_t to every edge should return the local GPU ID for this function to work (edges should be pre-shuffled).

edgelist_dsts – Vectors of edge destination vertex IDs.

edgelist_weights – Vectors of weight values for edges

edgelist_edge_ids – Vectors of edge_id values for edges

edgelist_edge_types – Vectors of edge_type values for edges

graph_properties – Properties of the graph represented by the input (optional vertex list and) edge list.

renumber – Flag indicating whether to renumber vertices or not (must be true if multi_gpu is true).

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Tuple of the generated graph and optional edge_property_t objects storing the provided edge properties and a renumber map (if renumber is true).

template<typename vertex_t, typename edge_t, typename weight_t, typename edge_type_t, typename edge_time_t, bool store_transposed, bool multi_gpu>
std::tuple<graph_t<vertex_t, edge_t, store_transposed, multi_gpu>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, weight_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_type_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_time_t>>, std::optional<edge_property_t<graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu>, edge_time_t>>, std::optional<rmm::device_uvector<vertex_t>>> create_graph_from_edgelist(raft::handle_t const &handle, std::optional<rmm::device_uvector<vertex_t>> &&vertices, std::vector<rmm::device_uvector<vertex_t>> &&edgelist_srcs, std::vector<rmm::device_uvector<vertex_t>> &&edgelist_dsts, std::optional<std::vector<rmm::device_uvector<weight_t>>> &&edgelist_weights, std::optional<std::vector<rmm::device_uvector<edge_t>>> &&edgelist_edge_ids, std::optional<std::vector<rmm::device_uvector<edge_type_t>>> &&edgelist_edge_types, std::optional<std::vector<rmm::device_uvector<edge_time_t>>> &&edgelist_edge_start_times, std::optional<std::vector<rmm::device_uvector<edge_time_t>>> &&edgelist_edge_end_times, graph_properties_t graph_properties, bool renumber, bool do_expensive_check = false)#

create a graph from (the optional vertex list and) the given edge list (with optional edge IDs, types, start and end times).

This version takes edge list in multiple chunks (e.g. edge data from multiple files).

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weight. Needs to be floating point type

edge_type_t – Type of edge type. Needs to be an integral type, currently only int32_t is supported

edge_time_t – Type of edge time. Needs to be an integral type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix. transposed.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – If valid, part of the entire set of vertices in the graph to be renumbered. This parameter can be used to include isolated vertices. If renumber is false and vertices is valid, vertices elements should be consecutive integers starting from 0. If multi-GPU, applying the compute_gpu_id_from_vertex_t to every vertex should return the local GPU ID for this function to work (vertices should be pre-shuffled).

edgelist_srcs – Vectors of edge source vertex IDs. If multi-GPU, applying the compute_gpu_id_from_ext_edge_endpoints_t to every edge should return the local GPU ID for this function to work (edges should be pre-shuffled).

edgelist_dsts – Vectors of edge destination vertex IDs.

edgelist_weights – Vectors of weight values for edges

edgelist_edge_ids – Vectors of edge_id values for edges

edgelist_edge_types – Vectors of edge_type values for edges

edgelist_edge_start_times – Vector of start time values for edges

edgelist_edge_end_times – Vector of end time values for edges

graph_properties – Properties of the graph represented by the input (optional vertex list and) edge list.

renumber – Flag indicating whether to renumber vertices or not (must be true if multi_gpu is true).

do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Tuple of the generated graph and optional edge_property_t objects storing the provided edge properties and a renumber map (if renumber is true).

template<typename vertex_t, typename edge_t, bool store_transposed, bool multi_gpu>
std::tuple<rmm::device_uvector<vertex_t>, rmm::device_uvector<vertex_t>> get_two_hop_neighbors(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, std::optional<raft::device_span<vertex_t const>> start_vertices)#

Find all 2-hop neighbors in the graph.

Find pairs of vertices in the input graph such that each pair is connected by a path that is two hops in length.

Throws:

cugraph::logic_error – when an error occurs.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph – The input graph object

start_vertices – Optional list of starting vertices to discover two-hop neighbors of

Returns:

tuple containing pairs of vertices that are 2-hops apart.

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
rmm::device_uvector<weight_t> compute_in_weight_sums(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, edge_property_view_t<edge_t, weight_t const*> edge_weight_view)#

Compute per-vertex incoming edge weight sums.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph_view – Graph view object of the input graph to compute per-vertex incoming edge weight sums.

edge_weight_view – View object holding edge weights for graph_view.

Returns:

Incoming edge weight sums for each vertex.

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
rmm::device_uvector<weight_t> compute_out_weight_sums(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, edge_property_view_t<edge_t, weight_t const*> edge_weight_view)#

Compute per-vertex outgoing edge weight sums.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph_view – Graph view object of the input graph to compute per-vertex outgoing edge weight sums.

edge_weight_view – View object holding edge weights for graph_view.

Returns:

Outgoing edge weight sums for each vertex.

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
weight_t compute_max_in_weight_sum(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, edge_property_view_t<edge_t, weight_t const*> edge_weight_view)#

Compute maximum per-vertex incoming edge weight sums.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph_view – Graph view object of the input graph to compute the maximum per-vertex incoming edge weight sums.

edge_weight_view – View object holding edge weights for graph_view.

Returns:

Maximum per-vertex incoming edge weight sums.

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
weight_t compute_max_out_weight_sum(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, edge_property_view_t<edge_t, weight_t const*> edge_weight_view)#

Compute maximum per-vertex outgoing edge weight sums.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph_view – Graph view object of the input graph to compute the maximum per-vertex outgoing edge weight sums.

edge_weight_view – View object holding edge weights for graph_view.

Returns:

Maximum per-vertex outgoing edge weight sums.

template<typename vertex_t, typename edge_t, typename weight_t, bool store_transposed, bool multi_gpu>
weight_t compute_total_edge_weight(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, edge_property_view_t<edge_t, weight_t const*> edge_weight_view)#

Sum the weights of the entire set of edges.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph_view – Graph view object of the input graph to sum the edge weights.

edge_weight_view – View object holding edge weights for graph_view.

Returns:

Sum of the weights of the entire set of edges.

template<typename vertex_t, typename edge_t, bool store_transposed, bool multi_gpu>
rmm::device_uvector<vertex_t> select_random_vertices(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, store_transposed, multi_gpu> const &graph_view, std::optional<raft::device_span<vertex_t const>> given_set, raft::random::RngState &rng_state, size_t select_count, bool with_replacement, bool sort_vertices, bool do_expensive_check = false)#

Select random vertices.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weights. Needs to be a floating point type.

store_transposed – Flag indicating whether to use sources (if false) or destinations (if true) as major indices in storing edges using a 2D sparse matrix.

multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

graph_view – Graph view object of the input graph to select random vertices from.

given_set – Distributed set to sample from. If given_set is not specified, sample from the entire vertex range provided by graph_view.

rng_state – The RngState instance holding pseudo-random number generator state.

select_count – The number of vertices to select from the graph

with_replacement – If true, select with replacement, if false select without replacement

sort_vertices – If true, return the sorted vertices (in the ascending order).

Returns:

Device vector of selected vertices.

template<typename vertex_t, typename edge_t, typename weight_t, typename edge_type_t, typename edge_time_t>
std::tuple<rmm::device_uvector<vertex_t>, rmm::device_uvector<vertex_t>, std::optional<rmm::device_uvector<weight_t>>, std::optional<rmm::device_uvector<edge_t>>, std::optional<rmm::device_uvector<edge_type_t>>, std::optional<rmm::device_uvector<edge_time_t>>, std::optional<rmm::device_uvector<edge_time_t>>> remove_self_loops(raft::handle_t const &handle, rmm::device_uvector<vertex_t> &&edgelist_srcs, rmm::device_uvector<vertex_t> &&edgelist_dsts, std::optional<rmm::device_uvector<weight_t>> &&edgelist_weights, std::optional<rmm::device_uvector<edge_t>> &&edgelist_edge_ids, std::optional<rmm::device_uvector<edge_type_t>> &&edgelist_edge_types, std::optional<rmm::device_uvector<edge_time_t>> &&edgelist_edge_start_times, std::optional<rmm::device_uvector<edge_time_t>> &&edgelist_edge_end_times)#

Remove self loops from an edge list.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weight. Currently float and double are supported.

edge_type_t – Type of edge type. Needs to be an integral type.

edge_time_t – Type of edge time. Needs to be an integral type.

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

edgelist_srcs – List of source vertex ids

edgelist_dsts – List of destination vertex ids

edgelist_weights – Optional list of edge weights

edgelist_edge_ids – Optional list of edge ids

edgelist_edge_types – Optional list of edge types

edgelist_edge_start_times – Optional list of edge start times

edgelist_edge_end_times – Optional list of edge end times

Returns:

Tuple of vectors storing edge sources, destinations, optional weights, optional edge ids, optional edge types, optional edge start times and optional edge end times.

template<typename vertex_t, typename edge_t, typename weight_t, typename edge_type_t, typename edge_time_t>
std::tuple<rmm::device_uvector<vertex_t>, rmm::device_uvector<vertex_t>, std::optional<rmm::device_uvector<weight_t>>, std::optional<rmm::device_uvector<edge_t>>, std::optional<rmm::device_uvector<edge_type_t>>, std::optional<rmm::device_uvector<edge_time_t>>, std::optional<rmm::device_uvector<edge_time_t>>> remove_multi_edges(raft::handle_t const &handle, rmm::device_uvector<vertex_t> &&edgelist_srcs, rmm::device_uvector<vertex_t> &&edgelist_dsts, std::optional<rmm::device_uvector<weight_t>> &&edgelist_weights, std::optional<rmm::device_uvector<edge_t>> &&edgelist_edge_ids, std::optional<rmm::device_uvector<edge_type_t>> &&edgelist_edge_types, std::optional<rmm::device_uvector<edge_time_t>> &&edgelist_edge_start_times, std::optional<rmm::device_uvector<edge_time_t>> &&edgelist_edge_edge_times, bool keep_min_value_edge = false)#

Remove all but one edge when a multi-edge exists.

When a multi-edge exists, one of the edges will remain. If keep_min_value_edge is false, an arbitrary edge will be selected among the edges in the multi-edge. If keep_min_value_edge is true, the edge with the minimum value will be selected. The edge weights will be first compared (if edgelist_weights.has_value() is true); edge IDs will be compared next (if edgelist_edge_ids.has_value() is true); and edge types (if edgelist_edge_types.has_value() is true) will compared last.

In an MG context it is assumed that edges have been shuffled to the proper GPU, in which case any multi-edges will be on the same GPU.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weight. Currently float and double are supported.

edge_type_t – Type of edge type. Needs to be an integral type.

edge_time_t – Type of edge time. Needs to be an integral type.

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

edgelist_srcs – List of source vertex ids

edgelist_dsts – List of destination vertex ids

edgelist_weights – Optional list of edge weights

edgelist_edge_ids – Optional list of edge ids

edgelist_edge_types – Optional list of edge types

edgelist_edge_start_times – Optional list of edge start times

edgelist_edge_end_times – Optional list of edge end times

keep_min_value_edge – Flag indicating whether to keep an arbitrary edge (false) or the minimum value edge (true) among the edges in a multi-edge. Relevant only if edgelist_weights.has_value() | edgelist_edge_ids.has_value() | edgelist_edge_types.has_value() is true. Setting this to true incurs performance overhead as this requires more comparisons.

Returns:

Tuple of vectors storing edge sources, destinations, optional weights, optional edge ids, optional edge types, optional edge start times and optional edge end times.

template<typename vertex_t>
rmm::device_uvector<vertex_t> shuffle_external_vertices(raft::handle_t const &handle, rmm::device_uvector<vertex_t> &&vertices)#

Shuffle external vertex ids to the proper GPU.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – List of vertex ids

Returns:

Vector of vertex ids mapped to this GPU.

template<typename vertex_t, typename value_t>
std::tuple<rmm::device_uvector<vertex_t>, rmm::device_uvector<value_t>> shuffle_external_vertex_value_pairs(raft::handle_t const &handle, rmm::device_uvector<vertex_t> &&vertices, rmm::device_uvector<value_t> &&values)#

Shuffle external vertex ids and values to the proper GPU.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

value_t – Type of values. currently supported types are int32_t, int64_t, size_t, float and double.

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

vertices – List of vertex ids

values – List of values

Returns:

Tuple of vectors storing vertex ids and values mapped to this GPU.

template<typename vertex_t, typename edge_t, typename weight_t, typename edge_type_t>
std::tuple<rmm::device_uvector<vertex_t>, rmm::device_uvector<vertex_t>, std::optional<rmm::device_uvector<weight_t>>, std::optional<rmm::device_uvector<edge_t>>, std::optional<rmm::device_uvector<edge_type_t>>, std::vector<size_t>> shuffle_external_edges(raft::handle_t const &handle, rmm::device_uvector<vertex_t> &&edge_srcs, rmm::device_uvector<vertex_t> &&edge_dsts, std::optional<rmm::device_uvector<weight_t>> &&edge_weights, std::optional<rmm::device_uvector<edge_t>> &&edge_ids, std::optional<rmm::device_uvector<edge_type_t>> &&edge_types)#

Shuffle external edges to the proper GPU.

Template Parameters:

vertex_t – Type of vertex identifiers. Needs to be an integral type.

edge_t – Type of edge identifiers. Needs to be an integral type.

weight_t – Type of edge weight. Currently float and double are supported.

Parameters:

handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

edge_srcs – List of source vertex ids

edge_dsts – List of destination vertex ids

edge_weights – Optional list of edge weights

edge_ids – Optional list of edge ids

edge_types – Optional list of edge types

Returns:

Tuple of vectors storing edge sources, destinations, optional weights, optional edge ids, optional edge types mapped to this GPU and a vector storing the number of edges received from each GPU.

Graph Functions#

This Page