Linear#

template<typename vertex_t, typename edge_t, typename weight_t>
weight_t hungarian(raft::handle_t const &handle, legacy::GraphCOOView<vertex_t, edge_t, weight_t> const &graph, vertex_t num_workers, vertex_t const *workers, vertex_t *assignments)#

Compute Hungarian algorithm on a weighted bipartite graph.

The Hungarian algorithm computes an assigment of “jobs” to “workers”. This function accepts a weighted graph and a vertex list identifying the “workers”. The weights in the weighted graph identify the cost of assigning a particular job to a worker. The algorithm computes a minimum cost assignment and returns the cost as well as a vector identifying the assignment.

Throws:

cugraph::logic_error – when an error occurs.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Supported value : int (signed, 32-bit)

  • edge_t – Type of edge identifiers. Supported value : int (signed, 32-bit)

  • weight_t – Type of edge weights. Supported values : float or double.

Parameters:

  • handle – [in] Library handle (RAFT). If a communicator is set in the handle,

  • graph – [in] cuGRAPH COO graph

  • num_workers – [in] number of vertices in the worker set

  • workers – [in] device pointer to an array of worker vertex ids

  • assignments – [out] device pointer to an array to which the assignment will be written. The array should be num_workers long, and will identify which vertex id (job) is assigned to that worker

template<typename vertex_t, typename edge_t, typename weight_t>
weight_t hungarian(raft::handle_t const &handle, legacy::GraphCOOView<vertex_t, edge_t, weight_t> const &graph, vertex_t num_workers, vertex_t const *workers, vertex_t *assignments, weight_t epsilon)#

Compute Hungarian algorithm on a weighted bipartite graph.

The Hungarian algorithm computes an assigment of “jobs” to “workers”. This function accepts a weighted graph and a vertex list identifying the “workers”. The weights in the weighted graph identify the cost of assigning a particular job to a worker. The algorithm computes a minimum cost assignment and returns the cost as well as a vector identifying the assignment.

Throws:

cugraph::logic_error – when an error occurs.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Supported value : int (signed, 32-bit)

  • edge_t – Type of edge identifiers. Supported value : int (signed, 32-bit)

  • weight_t – Type of edge weights. Supported values : float or double.

Parameters:

  • handle – [in] Library handle (RAFT). If a communicator is set in the handle,

  • graph – [in] cuGRAPH COO graph

  • num_workers – [in] number of vertices in the worker set

  • workers – [in] device pointer to an array of worker vertex ids

  • assignments – [out] device pointer to an array to which the assignment will be written. The array should be num_workers long, and will identify which vertex id (job) is assigned to that worker

  • epsilon – [in] parameter to define precision of comparisons in reducing weights to zero.

template<typename vertex_t, typename weight_t>
weight_t hungarian(raft::handle_t const &handle, weight_t const *costs, vertex_t num_rows, vertex_t num_columns, vertex_t *assignments)#

Compute Hungarian algorithm on a weighted bipartite graph.

The Hungarian algorithm computes an assigment of “jobs” to “workers”. This function accepts a weighted graph and a vertex list identifying the “workers”. The weights in the weighted graph identify the cost of assigning a particular job to a worker. The algorithm computes a minimum cost assignment and returns the cost as well as a vector identifying the assignment.

Throws:

cugraph::logic_error – when an error occurs.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Supported value : int (signed, 32-bit)

  • weight_t – Type of edge weights. Supported values : float or double.

Parameters:

  • handle – [in] Library handle (RAFT). If a communicator is set in the handle,

  • costs – [in] pointer to array of costs, stored in row major order

  • num_rows – [in] number of rows in dense matrix

  • num_cols – [in] number of cols in dense matrix

  • assignments – [out] device pointer to an array to which the assignment will be written. The array should be num_cols long, and will identify which vertex id (job) is assigned to that worker

template<typename vertex_t, typename weight_t>
weight_t hungarian(raft::handle_t const &handle, weight_t const *costs, vertex_t num_rows, vertex_t num_columns, vertex_t *assignments, weight_t epsilon)#

Compute Hungarian algorithm on a weighted bipartite graph.

The Hungarian algorithm computes an assigment of “jobs” to “workers”. This function accepts a weighted graph and a vertex list identifying the “workers”. The weights in the weighted graph identify the cost of assigning a particular job to a worker. The algorithm computes a minimum cost assignment and returns the cost as well as a vector identifying the assignment.

Throws:

cugraph::logic_error – when an error occurs.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Supported value : int (signed, 32-bit)

  • weight_t – Type of edge weights. Supported values : float or double.

Parameters:

  • handle – [in] Library handle (RAFT). If a communicator is set in the handle,

  • costs – [in] pointer to array of costs, stored in row major order

  • num_rows – [in] number of rows in dense matrix

  • num_cols – [in] number of cols in dense matrix

  • assignments – [out] device pointer to an array to which the assignment will be written. The array should be num_cols long, and will identify which vertex id (job) is assigned to that worker

  • epsilon – [in] parameter to define precision of comparisons in reducing weights to zero.