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)