Solvers

Solvers#

2025-10-17

3 min read time

Applies to Linux

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)