Aleph::Hungarian_Assignment< Cost_Type > Class Template Reference

Hungarian (Munkres) algorithm for optimal assignment. More...

#include <Hungarian.H>

Collaboration diagram for Aleph::Hungarian_Assignment< Cost_Type >:

Public Member Functions
	Hungarian_Assignment (const DynMatrix< Cost_Type > &cost)
	Construct and solve from a DynMatrix cost matrix.
	Hungarian_Assignment (std::initializer_list< std::initializer_list< Cost_Type > > rows)
	Construct and solve from an initializer list of rows.
Cost_Type	get_total_cost () const noexcept
	Get the optimal total cost.
long	get_assignment (const size_t row) const
	Get the column assigned to a given row.
DynList< std::pair< size_t, size_t > >	get_assignments () const
	Get all assignment pairs.
const Array< long > &	get_row_assignments () const noexcept
	Get the row-to-column assignment array.
const Array< long > &	get_col_assignments () const noexcept
	Get the column-to-row assignment array.
size_t	dimension () const noexcept
	Get the padded square dimension.
size_t	rows () const noexcept
	Get the original number of rows.
size_t	cols () const noexcept
	Get the original number of columns.

Private Member Functions
void	solve (const DynMatrix< Cost_Type > &cost)
	Core algorithm: shortest augmenting paths with dual variables.

Private Attributes
size_t	n_ = 0
size_t	orig_rows_ = 0
size_t	orig_cols_ = 0
Cost_Type	total_cost_ = Cost_Type{0}
Array< long >	row_to_col_
Array< long >	col_to_row_

Detailed Description

template<typename Cost_Type = double>
class Aleph::Hungarian_Assignment< Cost_Type >

Hungarian (Munkres) algorithm for optimal assignment.

Given an m x n cost matrix, finds the minimum-cost assignment of rows to columns. The constructor computes the solution; query methods retrieve the results.

For rectangular matrices, the smaller dimension is padded with zero-cost rows or columns. Assignments to padded entries are reported as -1.

The algorithm uses the shortest augmenting paths variant with dual variables, running in O(n^3) time where n = max(m, cols).

Template Parameters

Cost_Type

Numeric type for costs (default: double).

Example

Hungarian_Assignment<int> ha({
  {82, 83, 69, 92},
  {77, 37, 49, 92},
  {11, 69, 5,  86},
  {8,  9,  98, 23}
});
 
std::cout << ha.get_total_cost() << "\n";  // 140
for (auto [r, c] : ha.get_assignments())
  std::cout << r << " -> " << c << "\n";

Definition at line 175 of file Hungarian.H.

Constructor & Destructor Documentation

Hungarian_Assignment() [1/2]

template<typename Cost_Type = double>

Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment ( const DynMatrix< Cost_Type > &  cost )

inline

Construct and solve from a DynMatrix cost matrix.

Computes the minimum-cost assignment for the given cost matrix. Rectangular matrices are padded with zeros to form a square.

Parameters

[in]

cost

The m x n cost matrix.

Exceptions

std::invalid_argument

if the matrix is empty.

Definition at line 307 of file Hungarian.H.

References ah_invalid_argument_if, Aleph::DynMatrix< T >::allocate(), Aleph::DynMatrix< T >::cols(), Aleph::divide_and_conquer_partition_dp(), Aleph::Hungarian_Assignment< Cost_Type >::n_, Aleph::Hungarian_Assignment< Cost_Type >::orig_cols_, Aleph::Hungarian_Assignment< Cost_Type >::orig_rows_, Aleph::DynMatrix< T >::read(), Aleph::DynMatrix< T >::rows(), and Aleph::Hungarian_Assignment< Cost_Type >::solve().

Hungarian_Assignment() [2/2]

template<typename Cost_Type = double>

Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment ( std::initializer_list< std::initializer_list< Cost_Type > >  rows )

inline

Construct and solve from an initializer list of rows.

Convenience constructor for inline cost matrices.

Parameters

[in]

rows

Initializer list of rows, each an initializer list of costs. All rows must have the same length.

Exceptions

std::invalid_argument

if rows is empty or rows have different lengths.

Example

Hungarian_Assignment<int> ha({
  {10, 5, 13},
  {3,  9, 18},
  {10, 6, 12}
});

Definition at line 344 of file Hungarian.H.

References ah_invalid_argument_if, Aleph::DynMatrix< T >::allocate(), Aleph::divide_and_conquer_partition_dp(), Aleph::Hungarian_Assignment< Cost_Type >::n_, Aleph::Hungarian_Assignment< Cost_Type >::orig_cols_, Aleph::Hungarian_Assignment< Cost_Type >::orig_rows_, Aleph::Hungarian_Assignment< Cost_Type >::rows(), and Aleph::Hungarian_Assignment< Cost_Type >::solve().

Member Function Documentation

cols()

template<typename Cost_Type = double>

size_t Aleph::Hungarian_Assignment< Cost_Type >::cols ( ) const

inlinenoexcept

Get the original number of columns.

Returns

The number of columns in the input cost matrix.

Definition at line 439 of file Hungarian.H.

References Aleph::Hungarian_Assignment< Cost_Type >::orig_cols_.

dimension()

template<typename Cost_Type = double>

size_t Aleph::Hungarian_Assignment< Cost_Type >::dimension ( ) const

inlinenoexcept

Get the padded square dimension.

Returns

max(original_rows, original_cols).

Definition at line 429 of file Hungarian.H.

References Aleph::Hungarian_Assignment< Cost_Type >::n_.

get_assignment()

template<typename Cost_Type = double>

long Aleph::Hungarian_Assignment< Cost_Type >::get_assignment ( const size_t  row ) const

inline

Get the column assigned to a given row.

Parameters

[in]

row

Row index (0-based, must be < original rows).

Returns

Column index, or -1 if the row is unassigned (dummy).

Exceptions

std::out_of_range

if row >= original number of rows.

Definition at line 384 of file Hungarian.H.

References ah_out_of_range_error_if, Aleph::Hungarian_Assignment< Cost_Type >::orig_rows_, and Aleph::Hungarian_Assignment< Cost_Type >::row_to_col_.

get_assignments()

template<typename Cost_Type = double>

DynList< std::pair< size_t, size_t > > Aleph::Hungarian_Assignment< Cost_Type >::get_assignments ( ) const

inline

Get all assignment pairs.

Returns only the pairs (row, col) where both indices are within the original (non-padded) dimensions.

Returns

List of (row, col) pairs.

Definition at line 399 of file Hungarian.H.

References Aleph::and, Aleph::DynList< T >::append(), Aleph::Hungarian_Assignment< Cost_Type >::orig_cols_, Aleph::Hungarian_Assignment< Cost_Type >::orig_rows_, and Aleph::Hungarian_Assignment< Cost_Type >::row_to_col_.

get_col_assignments()

template<typename Cost_Type = double>

const Array< long > & Aleph::Hungarian_Assignment< Cost_Type >::get_col_assignments ( ) const

inlinenoexcept

Get the column-to-row assignment array.

Returns

Const reference to array where entry j is the row assigned to column j (-1 if dummy).

Definition at line 421 of file Hungarian.H.

References Aleph::Hungarian_Assignment< Cost_Type >::col_to_row_.

get_row_assignments()

template<typename Cost_Type = double>

const Array< long > & Aleph::Hungarian_Assignment< Cost_Type >::get_row_assignments ( ) const

inlinenoexcept

Get the row-to-column assignment array.

Returns

Const reference to array where entry i is the column assigned to row i (-1 if dummy).

Definition at line 412 of file Hungarian.H.

References Aleph::Hungarian_Assignment< Cost_Type >::row_to_col_.

get_total_cost()

template<typename Cost_Type = double>

Cost_Type Aleph::Hungarian_Assignment< Cost_Type >::get_total_cost ( ) const

inlinenoexcept

Get the optimal total cost.

Returns

The minimum total assignment cost.

Definition at line 373 of file Hungarian.H.

References Aleph::Hungarian_Assignment< Cost_Type >::total_cost_.

Referenced by example_basic_assignment(), and example_rectangular().

rows()

template<typename Cost_Type = double>

size_t Aleph::Hungarian_Assignment< Cost_Type >::rows ( ) const

inlinenoexcept

Get the original number of rows.

Returns

The number of rows in the input cost matrix.

Definition at line 434 of file Hungarian.H.

References Aleph::Hungarian_Assignment< Cost_Type >::orig_rows_.

Referenced by Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment().

solve()

template<typename Cost_Type = double>

void Aleph::Hungarian_Assignment< Cost_Type >::solve ( const DynMatrix< Cost_Type > &  cost )

inlineprivate

Core algorithm: shortest augmenting paths with dual variables.

Uses 1-indexed arrays with virtual column 0 trick. cost is an (n+1) x (n+1) matrix with 1-based indexing.

Definition at line 193 of file Hungarian.H.

References Aleph::and, Aleph::Hungarian_Assignment< Cost_Type >::col_to_row_, Aleph::divide_and_conquer_partition_dp(), j0(), j1(), Aleph::Hungarian_Assignment< Cost_Type >::n_, Aleph::Hungarian_Assignment< Cost_Type >::orig_cols_, Aleph::Hungarian_Assignment< Cost_Type >::orig_rows_, Aleph::DynMatrix< T >::read(), Aleph::Hungarian_Assignment< Cost_Type >::row_to_col_, and Aleph::Hungarian_Assignment< Cost_Type >::total_cost_.

Referenced by Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment(), and Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment().

Member Data Documentation

col_to_row_

template<typename Cost_Type = double>

Array<long> Aleph::Hungarian_Assignment< Cost_Type >::col_to_row_

private

Definition at line 186 of file Hungarian.H.

Referenced by Aleph::Hungarian_Assignment< Cost_Type >::get_col_assignments(), and Aleph::Hungarian_Assignment< Cost_Type >::solve().

n_

template<typename Cost_Type = double>

size_t Aleph::Hungarian_Assignment< Cost_Type >::n_ = 0

private

Definition at line 181 of file Hungarian.H.

Referenced by Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment(), Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment(), Aleph::Hungarian_Assignment< Cost_Type >::dimension(), and Aleph::Hungarian_Assignment< Cost_Type >::solve().

orig_cols_

template<typename Cost_Type = double>

size_t Aleph::Hungarian_Assignment< Cost_Type >::orig_cols_ = 0

private

Definition at line 183 of file Hungarian.H.

Referenced by Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment(), Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment(), Aleph::Hungarian_Assignment< Cost_Type >::cols(), Aleph::Hungarian_Assignment< Cost_Type >::get_assignments(), and Aleph::Hungarian_Assignment< Cost_Type >::solve().

orig_rows_

template<typename Cost_Type = double>

size_t Aleph::Hungarian_Assignment< Cost_Type >::orig_rows_ = 0

private

Definition at line 182 of file Hungarian.H.

Referenced by Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment(), Aleph::Hungarian_Assignment< Cost_Type >::Hungarian_Assignment(), Aleph::Hungarian_Assignment< Cost_Type >::get_assignment(), Aleph::Hungarian_Assignment< Cost_Type >::get_assignments(), Aleph::Hungarian_Assignment< Cost_Type >::rows(), and Aleph::Hungarian_Assignment< Cost_Type >::solve().

row_to_col_

template<typename Cost_Type = double>

Array<long> Aleph::Hungarian_Assignment< Cost_Type >::row_to_col_

private

Definition at line 185 of file Hungarian.H.

Referenced by Aleph::Hungarian_Assignment< Cost_Type >::get_assignment(), Aleph::Hungarian_Assignment< Cost_Type >::get_assignments(), Aleph::Hungarian_Assignment< Cost_Type >::get_row_assignments(), and Aleph::Hungarian_Assignment< Cost_Type >::solve().

total_cost_

template<typename Cost_Type = double>

Cost_Type Aleph::Hungarian_Assignment< Cost_Type >::total_cost_ = Cost_Type{0}

private

Definition at line 184 of file Hungarian.H.

Referenced by Aleph::Hungarian_Assignment< Cost_Type >::get_total_cost(), and Aleph::Hungarian_Assignment< Cost_Type >::solve().

---

The documentation for this class was generated from the following file:

• Hungarian.H