Implementation of the Hungarian (Munkres) algorithm. 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.

Array< long >	extract_row_assignments () &&noexcept
	Move out the row-to-column assignment array.

Array< long >	extract_col_assignments () &&noexcept
	Move out 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.

Detailed Description

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

Implementation of the Hungarian (Munkres) algorithm.

Computes the minimum-cost perfect matching in a bipartite graph represented as a cost matrix.

The constructor performs the entire computation. Results can then be queried using provided methods.

Template Parameters

Cost_Type Numeric type for costs. Must be a signed type or floating-point to support internal reductions.

Complexity:: Time \(O(n^3)\), Space \(O(n^2)\), where \(n = \max(rows, cols)\).

Definition at line 141 of file Hungarian.H.

Constructor & Destructor Documentation

template<typename Cost_Type = double>

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

inlineexplicit

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 272 of file Hungarian.H.

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}

});

Aleph::Hungarian_Assignment
Implementation of the Hungarian (Munkres) algorithm.
Definition Hungarian.H:143

Aleph::blossom_maximum_cardinality_matching
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466