C++ Reference: hungarian

This documentation is automatically generated.

IMPORTANT NOTE: we advise using the code in graph/linear_assignment.h whose complexity is usually much smaller. TODO(user): base this code on LinearSumAssignment.

For each of the four functions declared in this file, in case the input parameter 'cost' contains NaN, the function will return without invoking the Hungarian algorithm, and the output parameters 'direct_assignment' and 'reverse_assignment' will be left unchanged.

An O(n^4) implementation of the Kuhn-Munkres algorithm (a.k.a. the Hungarian algorithm) for solving the assignment problem. The assignment problem takes a set of agents, a set of tasks and a cost associated with assigning each agent to each task and produces an optimal (i.e., least cost) assignment of agents to tasks. The code also enables computing a maximum assignment by changing the input matrix.

This code is based on (read: translated from) the Java version (read: translated from) the Python version at http://www.clapper.org/software/python/munkres/.
Function Type Arguments Comments
MaximizeLinearAssignment

Return type: void

Arguments: const std::vector<std::vector<double> >& cost, absl::flat_hash_map<int, int>* direct_assignment, absl::flat_hash_map<int, int>* reverse_assignment

MinimizeLinearAssignment

Return type: void

Arguments: const std::vector<std::vector<double> >& cost, absl::flat_hash_map<int, int>* direct_assignment, absl::flat_hash_map<int, int>* reverse_assignment