Hungarian.H File Reference

Hungarian (Munkres) algorithm for the assignment problem. More...

#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 >
	Hungarian (Munkres) algorithm for optimal assignment. 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 (Munkres) algorithm for the assignment problem.

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

Algorithm Overview

The implementation uses the shortest augmenting paths variant with dual variables (potentials). For each row, a Dijkstra-like scan finds the shortest augmenting path using reduced costs c[i][j] - u[i] - v[j], then augments and updates potentials. This avoids the classical cover-lines/find-zeros Munkres steps and yields a clean, efficient O(n^3) implementation.

Key Features

• Solves both minimization and maximization assignment problems
• Handles rectangular cost matrices (m != n)
• Works with integer and floating-point cost types
• Supports negative costs
• Query-after-compute API (constructor solves, methods query)

Complexity

Metric	Value
Time	O(n^3) where n = max(rows, cols)
Space	O(n^2) for the padded cost matrix

Usage Example

// Direct construction from initializer list
Hungarian_Assignment<int> ha({
  {10, 5, 13},
  {3,  9, 18},
  {10, 6, 12}
});
 
auto cost = ha.get_total_cost();    // optimal cost
auto pairs = ha.get_assignments();  // list of (row, col) pairs
 
// Or from a DynMatrix
DynMatrix<double> cost_mat(3, 3);
// ... fill cost_mat ...
auto result = hungarian_assignment(cost_mat);

See also

tpl_mincost.H For min-cost flow-based assignment (solve_assignment)

tpl_bipartite.H For bipartite matching

Author

Leandro Rabindranath Leon

Definition in file Hungarian.H.