- cugraph.dense_hungarian(costs, num_rows, num_columns, epsilon=None)#
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.
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.
Number of rows in the matrix
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.
- costmatches costs.dtype
The cost of the overall assignment
- assignment[i] gives the vertex id of the task assigned to the
>>> 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)