遍历

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)

运行广度优先搜索，查找从源顶点开始的距离（和前驱节点）。

此函数计算从源顶点开始的距离（到达该顶点的最少跳数）。如果 predecessors 不是 nullptr，此函数还将计算每个顶点的前驱节点（广度优先搜索树中的父顶点）。

抛出:

cugraph::logic_error – 输入参数错误时。

模板参数:

• vertex_t – 顶点标识符的类型。需要是整数类型。

• edge_t – 边标识符的类型。需要是整数类型。

• multi_gpu – 标志，指示模板实例化是针对单 GPU (false) 还是多 GPU (true)。

参数:

• handle – RAFT 句柄对象，用于封装运行图算法所需的资源（例如 CUDA 流、通信器以及各种 CUDA 库的句柄）。

• graph_view – 图视图对象。

• distances – 指向输出距离数组的指针。

• predecessors – 指向输出前驱节点数组的指针或 nullptr。

• sources – 开始广度优先搜索的源顶点（广度优先搜索树的根顶点）。如果传入多个源顶点，每个连通分量必须只有一个源顶点。在多 GPU 环境中，源顶点应该是此 GPU 本地的。

• n_sources – 源顶点的数量（每个连通分量最多一个源）。

• direction_optimizing – 如果设置为 true，此算法将根据广度优先搜索边界的大小在基于推的广度优先搜索和基于拉的广度优先搜索之间切换（目前不支持）。此选项仅对对称输入图有效。

• depth_limit – 设置广度优先搜索的最大迭代次数。source_vertex 以外距离超过 depth_limit 跳的任何顶点将被标记为不可达。

• do_expensive_check – 一个标志，用于对输入参数进行昂贵检查（如果设置为 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)

从广度优先搜索输出中提取路径。

此函数从 BFS 输出中提取路径。BFS 输出距离和前驱节点。可以通过递归查找前驱节点，直到回到原始源顶点，来提取从顶点 v 返回原始源顶点的路径。

抛出:

cugraph::logic_error – 输入参数错误时。

模板参数:

• vertex_t – 顶点标识符的类型。需要是整数类型。

• edge_t – 边标识符的类型。需要是整数类型。

• multi_gpu – 标志，指示模板实例化是针对单 GPU (false) 还是多 GPU (true)。

参数:

• handle – RAFT 句柄对象，用于封装运行图算法所需的资源（例如 CUDA 流、通信器以及各种 CUDA 库的句柄）。

• graph_view – 图视图对象。

• distances – 指向由 bfs 构建的距离数组的指针。

• predecessors – 指向由 bfs 构建的前驱节点数组的指针。

• destinations – 目标顶点，提取从源到每个目标的路径。在多 GPU 环境中，目标顶点应该是此 GPU 本地的。

• n_destinations – 目标数量。

返回:

std::tuple<rmm::device_uvector<vertex_t>, vertex_t> 对，包含路径作为向量中的密集矩阵以及最大路径长度。路径中未使用的元素将设置为 invalid_vertex_id（对于有符号的 vertex_t 类型为 -1，对于无符号的 vertex_t 类型为 std::numeric_limits<vertex_t>::max()）。

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)

运行单源最短路径算法，计算从源顶点开始的最小距离（和前驱节点）。

此函数计算从源顶点开始的距离（最小边权重总和）。如果 predecessors 不是 nullptr，此函数还将计算最短路径中每个顶点的前驱节点。图的边权重应为非负数。

抛出:

cugraph::logic_error – 输入参数错误时。

模板参数:

• vertex_t – 顶点标识符的类型。需要是整数类型。

• edge_t – 边标识符的类型。需要是整数类型。

• weight_t – 边权重的类型。需要是浮点类型。

• multi_gpu – 标志，指示模板实例化是针对单 GPU (false) 还是多 GPU (true)。

参数:

• handle – RAFT 句柄对象，用于封装运行图算法所需的资源（例如 CUDA 流、通信器以及各种 CUDA 库的句柄）。

• graph_view – 图视图对象。

• edge_weight_view – 包含 graph_view 边权重的视图对象。

• distances – 指向输出距离数组的指针。

• predecessors – 指向输出前驱节点数组的指针或 nullptr。

• source_vertex – 开始单源最短路径的源顶点。在多 GPU 环境中，源顶点应该是此 GPU 本地的。

• cutoff – 如果在 cutoff 距离内没有更多可达顶点，则单源最短路径终止。距离超过 cutoff 的任何顶点将被标记为不可达。

• do_expensive_check – 一个标志，用于对输入参数进行昂贵检查（如果设置为 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)

计算从给定起点到所有给定目标的最短距离。

.*

此算法专为大直径图设计。对于小直径图，在顺序执行的循环中运行 cugraph::sssp 函数可能更快。此算法目前仅适用于单 GPU（我们不知道有无法容纳在单个 GPU 中的大直径图）。

抛出:

cugraph::logic_error – 输入参数错误时。

模板参数:

• vertex_t – 顶点标识符的类型。需要是整数类型。

• edge_t – 边标识符的类型。需要是整数类型。

• weight_t – 边权重的类型。需要是浮点类型。

• multi_gpu – 标志，指示模板实例化是针对单 GPU (false) 还是多 GPU (true)。

参数:

• handle – RAFT 句柄对象，用于封装运行图算法所需的资源（例如 CUDA 流、通信器以及各种 CUDA 库的句柄）。

• graph_view – 图视图对象。

• edge_weight_view – 包含 graph_view 边权重的视图对象。

• origins – 起点（起始顶点）数组，用于查找最短距离。origins 中不应有重复项。

• destinations – 目标（终点）数组，用于查找最短距离。destinations 中不应有重复项。

• cutoff – 距离超过 cutoff 的任何目标将被标记为不可达。

• do_expensive_check – 一个标志，用于对输入参数进行昂贵检查（如果设置为 true）。

返回:

一个大小为 origins.size() * destinations.size() 的向量。返回向量的第 i 个元素是从第 (i / destinations.size()) 个起点到第 (i % destinations.size()) 个目标的最短距离。