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:

inline weight_t getPrimalObjectiveValue(int spId)#

Function for getting optimal primal objective value for subproblem spId.

Parameters:

spId –

Returns:

inline weight_t getDualObjectiveValue(int spId)#

Function for getting optimal dual objective value 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)