注意
RAFT 中的向量搜索和聚类算法正在迁移到一个名为 cuVS 的新库，该库专门用于向量搜索。在此迁移期间，我们将继续支持 RAFT 中的向量搜索算法，但在 RAPIDS 24.06（六月）版本之后将不再更新它们。我们计划在 RAPIDS 24.10（十月）版本之前完成迁移，并在 24.12（十二月）版本中将其完全从 RAFT 中移除。
求解器#
本页提供迭代和组合求解器包中公开元素的 C++ 类参考。
线性分配问题#
#include <raft/solver/linear_assignment.cuh>
-
template<typename vertex_t, typename weight_t>
class LinearAssignmentProblem# O(n^3) 交替树匈牙利算法的 CUDA 实现。
另请参阅
Date, Ketan, and Rakesh Nagi. “GPU-accelerated Hungarian algorithms
for the Linear Assignment Problem.” Parallel Computing 57 (2016): 52-72.
注意
这是从原作者 Ketan Date 和 Rakesh Nagi 移植到 RAFT 的版本
- 模板参数:
vertex_t –
weight_t –
公共函数
-
inline LinearAssignmentProblem(raft::resources const &handle, vertex_t size, vertex_t batchsize, weight_t epsilon)#
构造函数。
- 参数:
handle – 用于管理资源的 raft 句柄
size – 方阵的大小
batchsize –
epsilon –
-
inline void solve(weight_t const *d_cost_matrix, vertex_t *d_row_assignment, vertex_t *d_col_assignment)#
在输入代价矩阵上执行匈牙利算法。
- 参数:
d_cost_matrix –
d_row_assignment –
d_col_assignment –
-
inline std::pair<const weight_t*, vertex_t> getRowDualVector(int spId) const#
获取子问题 spId 的最优行对偶向量的函数。
- 参数:
spId –
- 返回:
最小生成树#
#include <raft/sparse/solver/mst.cuh>
-
template<typename vertex_t, typename edge_t, typename weight_t, typename alteration_t = weight_t>
Graph_COO<vertex_t, edge_t, weight_t> raft::sparse::solver::mst(raft::resources const &handle, edge_t const *offsets, vertex_t const *indices, weight_t const *weights, vertex_t const v, edge_t const e, vertex_t *color, cudaStream_t stream, bool symmetrize_output = true, bool initialize_colors = true, int iterations = 0)# 根据给定图的连通分量计算最小生成树（MST）或最小生成森林（MSF）。
- 模板参数:
vertex_t – 用于顶点索引精度的整型类型
edge_t – 用于边索引精度的整型类型
weight_t – 权重数组的类型
alteration_t – 用于随机修改的类型
- 参数:
handle –
offsets – 行偏移的 csr inptr 数组（大小 v+1）
indices – 列索引的 csr 数组（大小 e）
weights – 权重的 csr 数组（大小 e）
v – 图中的顶点数
e – 图中的边数
color – 存储 MSF 结果颜色的数组
stream – 用于排序操作的 cuda 流
symmetrize_output – 结果输出边列表是否应该对称化？
initialize_colors – 颜色数组是否应该在 MST 内部初始化？
iterations – 执行的最大迭代次数
- 返回:
包含 mst 的边列表（或当遇到 msf 时，保证位于 mst 中的边的子集）