libfirm/adt/hungarian.h File Reference

Solving the Minimum Assignment Problem using the Hungarian Method. More...

#include "../begin.h"
#include "../end.h"

Go to the source code of this file.

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 *p, int cost_width)
	Print the cost matrix.

---

Detailed Description

Solving the Minimum Assignment Problem using the Hungarian Method.

Definition in file hungarian.h.