cugraph.dense_hungarian#

cugraph.dense_hungarian(costs, num_rows, num_columns, epsilon=None)[source]#

Execute the Hungarian algorithm against a dense bipartite graph representation.

NOTE: This API is unstable and subject to change

The Hungarian algorithm identifies the lowest cost matching of vertices such that all workers that can be assigned work are assigned exactly on job.

Parameters:

costscudf.Series: A dense representation (row major order) of the bipartite graph. Each row represents a worker, each column represents a task, cost[i][j] represents the cost of worker i performing task j.
num_rowsint: Number of rows in the matrix
num_columnsint: Number of columns in the matrix
epsilonfloat or double (matching weight type in graph): Used for determining when value is close enough to zero to consider 0. Defaults (if not specified) to 1e-6 in the C++ code. Unused for integer weight types.

Returns:

costmatches costs.dtype

The cost of the overall assignment

assignmentcudf.Series

assignment[i] gives the vertex id of the task assigned to the: worker i

Examples

>>> workers, G, costs = cugraph.utils.create_random_bipartite(5, 5,
...                                                           100, float)
>>> costs_flattened = cudf.Series(costs.flatten())
>>> cost, assignment = cugraph.dense_hungarian(costs_flattened, 5, 5)