Is this page helpful?

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>

Warning

doxygenfunction: Unable to resolve function “raft::sparse::solver::mst” with arguments None in doxygen xml output for project “RAFT” from directory: ../../cpp/doxygen/_xml/. Potential matches: 

- template<typename vertex_t, typename edge_t, typename weight_t, typename alteration_t = weight_t> Graph_COO<vertex_t, edge_t, weight_t> 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, bool symmetrize_output = true, bool initialize_colors = true, int iterations = 0)
- template<typename vertex_t, typename edge_t, typename weight_t, typename alteration_t = weight_t> Graph_COO<vertex_t, edge_t, weight_t> 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)