# 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.

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)