Traversal

Traversal#

2025-05-20

4 min read time

Applies to Linux

Breadth First Search (BFS)#

rocgraph_status rocgraph_bfs(
const rocgraph_handle_t *handle,
rocgraph_graph_t *graph,
rocgraph_type_erased_device_array_view_t *sources,
rocgraph_bool direction_optimizing,
size_t depth_limit,
rocgraph_bool compute_predecessors,
rocgraph_bool do_expensive_check,
rocgraph_paths_result_t **result,
rocgraph_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 ROCGRAPH_SUCCESS

Returns:

error code

Single-Source Shortest-Path (SSSP)#

rocgraph_status rocgraph_sssp(
const rocgraph_handle_t *handle,
rocgraph_graph_t *graph,
size_t source,
double cutoff,
rocgraph_bool compute_predecessors,
rocgraph_bool do_expensive_check,
rocgraph_paths_result_t **result,
rocgraph_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 ROCGRAPH_SUCCESS

Returns:

error code

Path Extraction#

rocgraph_status rocgraph_extract_paths(
const rocgraph_handle_t *handle,
rocgraph_graph_t *graph,
const rocgraph_type_erased_device_array_view_t *sources,
const rocgraph_paths_result_t *paths_result,
const rocgraph_type_erased_device_array_view_t *destinations,
rocgraph_extract_paths_result_t **result,
rocgraph_error_t **error,
)#

Extract BFS or SSSP paths from a rocgraph_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

  • paths_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 ROCGRAPH_SUCCESS

Returns:

error code

Traversal Support Functions#

size_t rocgraph_extract_paths_result_get_max_path_length(
rocgraph_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

rocgraph_type_erased_device_array_view_t *rocgraph_extract_paths_result_get_paths(
rocgraph_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 rocgraph_extract_paths_result_free(
rocgraph_extract_paths_result_t *result,
)#

Free extract_paths result.

Parameters:

result – [in] The result from extract_paths

struct rocgraph_extract_paths_result_t#
#include <rocgraph_extract_paths_result_t.h>

Opaque extract_paths result type.

Public Members

int32_t align_#

alignment variable

Contents