Hungarian.H File Reference

Hungarian (Kuhn-Munkres) algorithm for the optimal assignment problem. More...

#include <cmath>
#include <limits>
#include <type_traits>
#include <utility>
#include <initializer_list>
#include <tpl_dynMat.H>
#include <tpl_array.H>
#include <htlist.H>
#include <ah-errors.H>
#include <ahFunction.H>

Include dependency graph for Hungarian.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Hungarian_Result< Cost_Type >
	Result of the Hungarian assignment algorithm. More...
class	Aleph::Hungarian_Assignment< Cost_Type >
	Implementation of the Hungarian (Munkres) algorithm. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<typename Cost_Type >
Hungarian_Result< Cost_Type >	Aleph::hungarian_assignment (const DynMatrix< Cost_Type > &cost)
	Compute minimum-cost assignment (free function).
template<typename Cost_Type >
Hungarian_Result< Cost_Type >	Aleph::hungarian_max_assignment (const DynMatrix< Cost_Type > &cost)
	Compute maximum-profit assignment (free function).

Detailed Description

Hungarian (Kuhn-Munkres) algorithm for the optimal assignment problem.

This file implements the Hungarian algorithm, also known as the Kuhn-Munkres algorithm, for solving the linear assignment problem: given an \(m \times n\)cost matrix, find a minimum-cost matching of rows to columns.

Complexity

Algorithm	Time	Space
Hungarian	O(max(m,n)^3)	O(m*n)

Example

// Suppose we have a cost matrix for 3 tasks and 3 workers:
//          Task 1  Task 2  Task 3
// Worker 1:  10      20      30
// Worker 2:  40      50      10
// Worker 3:  20      10      60
DynMatrix<double> costs(3, 3);
costs(0,0)=10; costs(0,1)=20; costs(0,2)=30;
costs(1,0)=40; costs(1,1)=50; costs(1,2)=10;
costs(2,0)=20; costs(2,1)=10; costs(2,2)=60;
 
// Find minimum weight assignment
auto res = Aleph::hungarian_assignment(costs);
// res.total_cost = 30.0 (10 + 10 + 10)
// res.row_to_col = {0, 2, 1}

Definition in file Hungarian.H.