Traversal#

template<typename vertex_t, typename edge_t, bool multi_gpu>
void bfs(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, vertex_t *distances, vertex_t *predecessors, vertex_t const *sources, size_t n_sources = 1, bool direction_optimizing = false, vertex_t depth_limit = std::numeric_limits<vertex_t>::max(), bool do_expensive_check = false)#

Run breadth-first search to find the distances (and predecessors) from the source vertex.

This function computes the distances (minimum number of hops to reach the vertex) from the source vertex. If predecessors is not nullptr, this function calculates the predecessor of each vertex (parent vertex in the breadth-first search tree) as well.

Throws:

cugraph::logic_error – on erroneous input arguments.

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.

  • graph_view – Graph view object.

  • distances – Pointer to the output distance array.

  • predecessors – Pointer to the output predecessor array or nullptr.

  • sources – Source vertices to start breadth-first search (root vertex of the breath-first search tree). If more than one source is passed, there must be a single source per component. In a multi-gpu context the source vertices should be local to this GPU.

  • n_sources – number of sources (one source per component at most).

  • direction_optimizing – If set to true, this algorithm switches between the push based breadth-first search and pull based breadth-first search depending on the size of the breadth-first search frontier (currently unsupported). This option is valid only for symmetric input graphs.

  • depth_limit – Sets the maximum number of breadth-first search iterations. Any vertices farther than depth_limit hops from source_vertex will be marked as unreachable.

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

template<typename vertex_t, typename edge_t, bool multi_gpu>
std::tuple<rmm::device_uvector<vertex_t>, vertex_t> extract_bfs_paths(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, vertex_t const *distances, vertex_t const *predecessors, vertex_t const *destinations, size_t n_destinations)#

Extract paths from breadth-first search output.

This function extracts paths from the BFS output. BFS outputs distances and predecessors. The path from a vertex v back to the original source vertex can be extracted by recursively looking up the predecessor vertex until you arrive back at the original source vertex.

Throws:

cugraph::logic_error – on erroneous input arguments.

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.

  • graph_view – Graph view object.

  • distances – Pointer to the distance array constructed by bfs.

  • predecessors – Pointer to the predecessor array constructed by bfs.

  • destinations – Destination vertices, extract path from source to each of these destinations In a multi-gpu context the destination vertex should be local to this GPU.

  • n_destinations – number of destinations (one source per component at most).

Returns:

std::tuple<rmm::device_uvector<vertex_t>, vertex_t> pair containing the paths as a dense matrix in the vector and the maximum path length. Unused elements in the paths will be set to invalid_vertex_id (-1 for a signed vertex_t, std::numeric_limits<vertex_t>::max() for an unsigned vertex_t type).

template<typename vertex_t, typename edge_t, typename weight_t, bool multi_gpu>
void sssp(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, edge_property_view_t<edge_t, weight_t const*> edge_weight_view, weight_t *distances, vertex_t *predecessors, vertex_t source_vertex, weight_t cutoff = std::numeric_limits<weight_t>::max(), bool do_expensive_check = false)#

Run single-source shortest-path to compute the minimum distances (and predecessors) from the source vertex.

This function computes the distances (minimum edge weight sums) from the source vertex. If predecessors is not nullptr, this function calculates the predecessor of each vertex in the shortest-path as well. Graph edge weights should be non-negative.

Throws:

cugraph::logic_error – on erroneous input arguments.

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.

  • 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.

  • edge_weight_view – View object holding edge weights for graph_view.

  • distances – Pointer to the output distance array.

  • predecessors – Pointer to the output predecessor array or nullptr.

  • source_vertex – Source vertex to start single-source shortest-path. In a multi-gpu context the source vertex should be local to this GPU.

  • cutoff – Single-source shortest-path terminates if no more vertices are reachable within the distance of cutoff. Any vertex farther than cutoff will be marked as unreachable.

  • 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, bool multi_gpu>
rmm::device_uvector<weight_t> od_shortest_distances(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, edge_property_view_t<edge_t, weight_t const*> edge_weight_view, raft::device_span<vertex_t const> origins, raft::device_span<vertex_t const> destinations, weight_t cutoff = std::numeric_limits<weight_t>::max(), bool do_expensive_check = false)#

Compute the shortest distances from the given origins to all the given destinations.

.*

This algorithm is designed for large diameter graphs. For small diameter graphs, running the cugraph::sssp function in a sequentially executed loop might be faster. This algorithms currently works only for single-GPU (we are not aware of large diameter graphs that won’t fit in a single GPU).

Throws:

cugraph::logic_error – on erroneous input arguments.

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.

  • 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.

  • edge_weight_view – View object holding edge weights for graph_view.

  • origins – An array of origins (starting vertices) to find shortest distances. There should be no duplicates in origins.

  • destinations – An array of destinations (end vertices) to find shortest distances. There should be no duplicates in destinations.

  • cutoff – Any destinations farther than cutoff will be marked as unreachable.

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

Returns:

A vector of size origins.size() * destinations.size(). The i’th element of the returned vector is the shortest distance from the (i / destinations.size())’th origin to the (i % destinations.size())’th destination.