Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: hungarian
Note: 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 |
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[],["This C++ code implements the Hungarian algorithm (Kuhn-Munkres) for solving assignment problems with O(n^4) complexity. It handles both minimizing and maximizing assignments. The algorithm takes a cost matrix, agents, and tasks, producing an optimal assignment. Functions `MaximizeLinearAssignment` and `MinimizeLinearAssignment` compute the assignment and return results through `direct_assignment` and `reverse_assignment`. If the input 'cost' contains NaN, it returns without executing, leaving output parameters unchanged. The code is translated from Java and Python versions.\n"],null,[]]
