Hungarian Algorithm

Solves bipartite matching problems (minimize/maximize cost function) More...

Typedefs
typedef struct hungarian_problem_t	hungarian_problem_t
	Internal representation of a bipartite matching problem.

Enumerations
enum	match_type_t { HUNGARIAN_MATCH_NORMAL , HUNGARIAN_MATCH_PERFECT }
	type of matching More...
enum	hungarian_mode_t { HUNGARIAN_MODE_MINIMIZE_COST , HUNGARIAN_MODE_MAXIMIZE_UTIL }
	mode of matching (the optimization goal) More...

Functions
hungarian_problem_t *	hungarian_new (unsigned num_rows, unsigned num_cols, match_type_t match_type)
	This method initialize the hungarian_problem structure and init the cost matrix (missing lines or columns are filled with 0).
void	hungarian_add (hungarian_problem_t *p, unsigned left, unsigned right, unsigned cost)
	Adds an edge from left to right with some costs.
void	hungarian_remove (hungarian_problem_t *p, unsigned left, unsigned right)
	Removes the edge from left to right.
void	hungarian_prepare_cost_matrix (hungarian_problem_t *p, hungarian_mode_t mode)
	Prepares the cost matrix dependent on the given mode.
void	hungarian_free (hungarian_problem_t *p)
	Destroys the hungarian object.
int	hungarian_solve (hungarian_problem_t *p, unsigned *assignment, unsigned *final_cost, unsigned cost_threshold)
	This method computes the optimal assignment.
void	hungarian_print_cost_matrix (hungarian_problem_t const *p, int cost_width)
	Print the cost matrix.

Detailed Description

Solves bipartite matching problems (minimize/maximize cost function)

Typedef Documentation

hungarian_problem_t

typedef struct hungarian_problem_t hungarian_problem_t

Internal representation of a bipartite matching problem.

Definition at line 60 of file hungarian.h.

Enumeration Type Documentation

hungarian_mode_t

enum hungarian_mode_t

mode of matching (the optimization goal)

Enumerator
HUNGARIAN_MODE_MINIMIZE_COST	minimize cost
HUNGARIAN_MODE_MAXIMIZE_UTIL	maximize cost

Definition at line 52 of file hungarian.h.

match_type_t

enum match_type_t

type of matching

Enumerator
HUNGARIAN_MATCH_NORMAL	ever nodes matches another node
HUNGARIAN_MATCH_PERFECT	matchings of nodes having no edge getting removed

Definition at line 45 of file hungarian.h.

Function Documentation

hungarian_add()

void hungarian_add	(	hungarian_problem_t *	p,
		unsigned	left,
		unsigned	right,
		unsigned	cost )

Adds an edge from left to right with some costs.

hungarian_free()

void hungarian_free

(

hungarian_problem_t *

p

)

Destroys the hungarian object.

hungarian_new()

hungarian_problem_t * hungarian_new	(	unsigned	num_rows,
		unsigned	num_cols,
		match_type_t	match_type )

This method initialize the hungarian_problem structure and init the cost matrix (missing lines or columns are filled with 0).

Parameters

num_rows	Number of rows in the given matrix
num_cols	Number of cols in the given matrix
match_type	The type of matching

Returns

The problem object.

hungarian_prepare_cost_matrix()

void hungarian_prepare_cost_matrix	(	hungarian_problem_t *	p,
		hungarian_mode_t	mode )

Prepares the cost matrix dependent on the given mode.

Parameters

p	The hungarian object
mode	specify whether to minimize or maximize the costs

hungarian_print_cost_matrix()

void hungarian_print_cost_matrix	(	hungarian_problem_t const *	p,
		int	cost_width )

Print the cost matrix.

Parameters

p	The hungarian object
cost_width	The minimum field width of the costs

hungarian_remove()

void hungarian_remove	(	hungarian_problem_t *	p,
		unsigned	left,
		unsigned	right )

Removes the edge from left to right.

hungarian_solve()

int hungarian_solve	(	hungarian_problem_t *	p,
		unsigned *	assignment,
		unsigned *	final_cost,
		unsigned	cost_threshold )

This method computes the optimal assignment.

Parameters

p	The hungarian object
assignment	The final assignment
final_cost	The final costs
cost_threshold	Matchings with costs >= this limit will be removed (if limit > 0)

Returns

0 on success, negative number otherwise