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.

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

Send feedback about...