libFirm
 All Data Structures Functions Variables Typedefs Enumerations Enumerator Groups Pages
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. More...
 

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_thungarian_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). More...
 
void hungarian_add (hungarian_problem_t *p, unsigned left, unsigned right, unsigned cost)
 Adds an edge from left to right with some costs. More...
 
void hungarian_remove (hungarian_problem_t *p, unsigned left, unsigned right)
 Removes the edge from left to right. More...
 
void hungarian_prepare_cost_matrix (hungarian_problem_t *p, hungarian_mode_t mode)
 Prepares the cost matrix dependent on the given mode. More...
 
void hungarian_free (hungarian_problem_t *p)
 Destroys the hungarian object. More...
 
int hungarian_solve (hungarian_problem_t *p, unsigned *assignment, unsigned *final_cost, unsigned cost_threshold)
 This method computes the optimal assignment. More...
 
void hungarian_print_cost_matrix (hungarian_problem_t const *p, int cost_width)
 Print the cost matrix. More...
 

Detailed Description

Solves bipartite matching problems (minimize/maximize cost function)

Typedef Documentation

Internal representation of a bipartite matching problem.

Definition at line 60 of file hungarian.h.

Enumeration Type Documentation

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.

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

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_free ( hungarian_problem_t p)

Destroys the hungarian object.

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_rowsNumber of rows in the given matrix
num_colsNumber of cols in the given matrix
match_typeThe type of matching
Returns
The problem object.
void hungarian_prepare_cost_matrix ( hungarian_problem_t p,
hungarian_mode_t  mode 
)

Prepares the cost matrix dependent on the given mode.

Parameters
pThe hungarian object
modespecify whether to minimize or maximize the costs
void hungarian_print_cost_matrix ( hungarian_problem_t const *  p,
int  cost_width 
)

Print the cost matrix.

Parameters
pThe hungarian object
cost_widthThe minimum field width of the costs
void hungarian_remove ( hungarian_problem_t p,
unsigned  left,
unsigned  right 
)

Removes the edge from left to right.

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

This method computes the optimal assignment.

Parameters
pThe hungarian object
assignmentThe final assignment
final_costThe final costs
cost_thresholdMatchings with costs >= this limit will be removed (if limit > 0)
Returns
0 on success, negative number otherwise