Traversal Functions

Traversal Functions#

2025-05-20

5 min read time

Applies to Linux

Breadth First Search (BFS)#

hipgraph_error_code_t hipgraph_bfs(
const hipgraph_resource_handle_t *handle,
hipgraph_graph_t *graph,
hipgraph_type_erased_device_array_view_t *sources,
hipgraph_bool_t direction_optimizing,
size_t depth_limit,
hipgraph_bool_t compute_predecessors,
hipgraph_bool_t do_expensive_check,
hipgraph_paths_result_t **result,
hipgraph_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 HIPGRAPH_SUCCESS

Returns:

error code

Single-Source Shortest-Path (SSSP)#

hipgraph_error_code_t hipgraph_sssp(
const hipgraph_resource_handle_t *handle,
hipgraph_graph_t *graph,
size_t source,
double cutoff,
hipgraph_bool_t compute_predecessors,
hipgraph_bool_t do_expensive_check,
hipgraph_paths_result_t **result,
hipgraph_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 HIPGRAPH_SUCCESS

Returns:

error code

Path Extraction#

hipgraph_error_code_t hipgraph_extract_paths(
const hipgraph_resource_handle_t *handle,
hipgraph_graph_t *graph,
const hipgraph_type_erased_device_array_view_t *sources,
const hipgraph_paths_result_t *paths_result,
const hipgraph_type_erased_device_array_view_t *destinations,
hipgraph_extract_paths_result_t **result,
hipgraph_error_t **error,
)#

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

Returns:

error code

Extract Max Path Length#

size_t hipgraph_extract_paths_result_get_max_path_length(
hipgraph_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#

hipgraph_type_erased_device_array_view_t *hipgraph_paths_result_get_vertices(
hipgraph_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

hipgraph_type_erased_device_array_view_t *hipgraph_paths_result_get_distances(
hipgraph_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

hipgraph_type_erased_device_array_view_t *hipgraph_paths_result_get_predecessors(
hipgraph_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 hipgraph_paths_result_free(
hipgraph_paths_result_t *result,
)#

Free paths result.

Parameters:

result – [in] The result from bfs or sssp

hipgraph_type_erased_device_array_view_t *hipgraph_extract_paths_result_get_paths(
hipgraph_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 hipgraph_extract_paths_result_free(
hipgraph_extract_paths_result_t *result,
)#

Free extract_paths result.

Parameters:

result – [in] The result from extract_paths

Contents