cugraph.hungarian

cugraph.hungarian(G, workers, epsilon=None)

Execute the Hungarian algorithm against a symmetric, weighted, bipartite graph.

As a bipartite graph, the vertex set of the graph can be partitioned into two disjoint sets such that all edges connect a vertex from one set to a vertex of the other set. The workers variable identifies one of the sets of vertices, the other set is all vertices not in the workers set (V - workers).

The edge weights reflect the cost of assigning a particular job to a worker.

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:

Gcugraph.Graph

cuGraph graph descriptor, should contain the connectivity information as an an edge list. Edge weights are required. If an edge list is not provided then it will be computed.

workerscudf.Series or cudf.DataFrame

A series or column that identifies the vertex ids of the vertices in the workers set. In case of multi-column vertices, it should be a cudf.DataFrame. All vertices in G that are not in the workers set are implicitly assigned to the jobs set.

epsilonfloat/double (matching weight in graph), optional (default=None)

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

dfcudf.DataFrame

df[‘vertex’][i] gives the vertex id of the i’th vertex. Only vertices

in the workers list are defined in this column.

df[‘assignment’][i] gives the vertex id of the “job” assigned to the

corresponding vertex.

Examples

>>> workers, G, costs = cugraph.utils.create_random_bipartite(5, 5,
...                                                           100, float)
>>> cost, df = cugraph.hungarian(G, workers)