Attention
The vector search and clustering algorithms in RAFT are being migrated to a new library dedicated to vector search called cuVS. We will continue to support the vector search algorithms in RAFT during this move, but will no longer update them after the RAPIDS 24.06 (June) release. We plan to complete the migration by RAPIDS 24.10 (October) release and they will be removed from RAFT altogether in the 24.12 (December) release.
Solvers#
This page provides C++ class references for the publicly-exposed elements of the iterative and combinatorial solvers package.
Linear Assignment Problem#
#include <raft/solver/linear_assignment.cuh>
-
template<typename vertex_t, typename weight_t>
class LinearAssignmentProblem# CUDA Implementation of O(n^3) alternating tree Hungarian Algorithm.
See also
Date, Ketan, and Rakesh Nagi. “GPU-accelerated Hungarian algorithms
for the Linear Assignment Problem.” Parallel Computing 57 (2016): 52-72.
Note
This is a port to RAFT from original authors Ketan Date and Rakesh Nagi
- Template Parameters:
vertex_t –
weight_t –
Public Functions
-
inline LinearAssignmentProblem(raft::resources const &handle, vertex_t size, vertex_t batchsize, weight_t epsilon)#
Constructor.
- Parameters:
handle – raft handle for managing resources
size – size of square matrix
batchsize –
epsilon –
-
inline void solve(weight_t const *d_cost_matrix, vertex_t *d_row_assignment, vertex_t *d_col_assignment)#
Executes Hungarian algorithm on the input cost matrix.
- Parameters:
d_cost_matrix –
d_row_assignment –
d_col_assignment –
-
inline std::pair<const weight_t*, vertex_t> getRowDualVector(int spId) const#
Function for getting optimal row dual vector for subproblem spId.
- Parameters:
spId –
- Returns:
-
inline std::pair<const weight_t*, vertex_t> getColDualVector(int spId)#
Function for getting optimal col dual vector for subproblem spId.
- Parameters:
spId –
- Returns:
Minimum Spanning Tree#
#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)# Compute the minimum spanning tree (MST) or minimum spanning forest (MSF) depending on the connected components of the given graph.
- Template Parameters:
vertex_t – integral type for precision of vertex indexing
edge_t – integral type for precision of edge indexing
weight_t – type of weights array
alteration_t – type to use for random alteration
- Parameters:
handle –
offsets – csr inptr array of row offsets (size v+1)
indices – csr array of column indices (size e)
weights – csr array of weights (size e)
v – number of vertices in graph
e – number of edges in graph
color – array to store resulting colors for MSF
stream – cuda stream for ordering operations
symmetrize_output – should the resulting output edge list should be symmetrized?
initialize_colors – should the colors array be initialized inside the MST?
iterations – maximum number of iterations to perform
- Returns:
a list of edges containing the mst (or a subset of the edges guaranteed to be in the mst when an msf is encountered)