Traversal#

Breadth First Search (BFS)#

cugraph_error_code_t cugraph_bfs(const cugraph_resource_handle_t *handle, cugraph_graph_t *graph, cugraph_type_erased_device_array_view_t *sources, bool_t direction_optimizing, size_t depth_limit, bool_t compute_predecessors, bool_t do_expensive_check, cugraph_paths_result_t **result, cugraph_error_t **error)#

Perform a breadth first search from a set of seed vertices.

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

Parameters:

  • handle – [in] Handle for accessing resources

  • graph – [in] Pointer to graph FIXME: Make this just [in], copy it if I need to temporarily modify internally

  • sources – [inout] Array of source vertices. NOTE: Array might be modified if renumbering is enabled for the graph

  • direction_optimizing – [in] 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.

  • compute_predecessors – [in] A flag to indicate whether to compute the predecessors in the result

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

  • result – [out] Opaque pointer to paths results

  • error – [out] Pointer to an error object storing details of any error. Will be populated if error code is not CUGRAPH_SUCCESS

Returns:

error code

Single-Source Shortest-Path (SSSP)#

cugraph_error_code_t cugraph_sssp(const cugraph_resource_handle_t *handle, cugraph_graph_t *graph, size_t source, double cutoff, bool_t compute_predecessors, bool_t do_expensive_check, cugraph_paths_result_t **result, cugraph_error_t **error)#

Perform 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 NULL, this function calculates the predecessor of each vertex (parent vertex in the breadth-first search tree) as well.

Parameters:

  • handle – [in] Handle for accessing resources

  • graph – [in] Pointer to graph

  • source – [in] Source vertex id

  • cutoff – [in] Maximum edge weight sum to consider

  • compute_predecessors – [in] A flag to indicate whether to compute the predecessors in the result

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

  • result – [out] Opaque pointer to paths results

  • error – [out] Pointer to an error object storing details of any error. Will be populated if error code is not CUGRAPH_SUCCESS

Returns:

error code

Path Extraction#

cugraph_error_code_t cugraph_extract_paths(const cugraph_resource_handle_t *handle, cugraph_graph_t *graph, const cugraph_type_erased_device_array_view_t *sources, const cugraph_paths_result_t *paths_result, const cugraph_type_erased_device_array_view_t *destinations, cugraph_extract_paths_result_t **result, cugraph_error_t **error)#

Extract BFS or SSSP paths from a cugraph_paths_result_t.

This function extracts paths from the BFS or SSSP output. BFS and SSSP output 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.

Parameters:

  • handle – [in] Handle for accessing resources

  • graph – [in] Pointer to graph. NOTE: Graph might be modified if the storage needs to be transposed

  • sources – [in] Array of source vertices

  • result – [in] Output from the BFS call

  • destinations – [in] Array of destination vertices.

  • result – [out] Opaque pointer to extract_paths results

  • error – [out] Pointer to an error object storing details of any error. Will be populated if error code is not CUGRAPH_SUCCESS

Returns:

error code

Extract Max Path Length#

size_t cugraph_extract_paths_result_get_max_path_length(cugraph_extract_paths_result_t *result)#

Get the max path length from extract_paths result.

Parameters:

result – [in] The result from extract_paths

Returns:

maximum path length

Traversal Support Functions#

cugraph_type_erased_device_array_view_t *cugraph_paths_result_get_vertices(cugraph_paths_result_t *result)#

Get the vertex ids from the paths result.

Parameters:

result – [in] The result from bfs or sssp

Returns:

type erased array of vertex ids

cugraph_type_erased_device_array_view_t *cugraph_paths_result_get_distances(cugraph_paths_result_t *result)#

Get the distances from the paths result.

Parameters:

result – [in] The result from bfs or sssp

Returns:

type erased array of distances

cugraph_type_erased_device_array_view_t *cugraph_paths_result_get_predecessors(cugraph_paths_result_t *result)#

Get the predecessors from the paths result.

Parameters:

result – [in] The result from bfs or sssp

Returns:

type erased array of predecessors. Value will be NULL if compute_predecessors was FALSE in the call to bfs or sssp that produced this result.

void cugraph_paths_result_free(cugraph_paths_result_t *result)#

Free paths result.

Parameters:

result – [in] The result from bfs or sssp

cugraph_type_erased_device_array_view_t *cugraph_extract_paths_result_get_paths(cugraph_extract_paths_result_t *result)#

Get the matrix (row major order) of paths.

Parameters:

result – [in] The result from extract_paths

Returns:

type erased array pointing to the matrix in device memory

void cugraph_extract_paths_result_free(cugraph_extract_paths_result_t *result)#

Free extract_paths result.

Parameters:

result – [in] The result from extract_paths

On this page
Show Source