hungarian.h 3.14 KB
Newer Older
1
2
3
4
5
/********************************************************************
 ********************************************************************
 **
 ** libhungarian by Cyrill Stachniss, 2004
 **
Christian Würdig's avatar
Christian Würdig committed
6
7
 ** Added to libFirm by Christian Wuerdig, 2006
 ** Added several options for not-perfect matchings.
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 **
 ** Solving the Minimum Assignment Problem using the
 ** Hungarian Method.
 **
 ** ** This file may be freely copied and distributed! **
 **
 ** Parts of the used code was originally provided by the
 ** "Stanford GraphGase", but I made changes to this code.
 ** As asked by  the copyright node of the "Stanford GraphGase",
 ** I hereby proclaim that this file are *NOT* part of the
 ** "Stanford GraphGase" distrubition!
 **
 ** This file is distributed in the hope that it will be useful,
 ** but WITHOUT ANY WARRANTY; without even the implied
 ** warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 ** PURPOSE.
 **
 ********************************************************************
 ********************************************************************/

28
29
30
31
32
33
34
/**
 * @file
 * @brief   Solving the Minimum Assignment Problem using the Hungarian Method.
 * @version $Id$
 */
#ifndef FIRM_ADT_HUNGARIAN_H
#define FIRM_ADT_HUNGARIAN_H
35
36
37
38

#define HUNGARIAN_MODE_MINIMIZE_COST 0
#define HUNGARIAN_MODE_MAXIMIZE_UTIL 1

39
40
41
#define HUNGARIAN_MATCH_NORMAL  0
#define HUNGARIAN_MATCH_PERFECT 1

42
43
44
45
46
47
typedef struct _hungarian_problem_t hungarian_problem_t;

/**
 * This method initialize the hungarian_problem structure and init
 * the cost matrix (missing lines or columns are filled with 0).
 *
48
49
 * @param rows       Number of rows in the given matrix
 * @param cols       Number of cols in the given matrix
Christian Würdig's avatar
Christian Würdig committed
50
51
52
 * @param match_type The type of matching:
 *                   HUNGARIAN_MATCH_PERFECT - every nodes matches another node
 *                   HUNGARIAN_MATCH_NORMAL  - matchings of nodes having no edge getting removed
53
54
 * @return The problem object.
 */
Matthias Braun's avatar
Matthias Braun committed
55
hungarian_problem_t *hungarian_new(int rows, int cols, int match_type);
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

/**
 * Adds an edge from left to right with some costs.
 */
void hungarian_add(hungarian_problem_t *p, int left, int right, int cost);

/**
* Removes the edge from left to right.
*/
void hungarian_remv(hungarian_problem_t *p, int left, int right);

/**
 * Prepares the cost matrix, dependend on the given mode.
 *
 * @param p     The hungarian object
 * @param mode  HUNGARIAN_MODE_MAXIMIZE_UTIL or HUNGARIAN_MODE_MINIMIZE_COST (default)
 */
void hungarian_prepare_cost_matrix(hungarian_problem_t *p, int mode);

/**
 * Destroys the hungarian object.
 */
void hungarian_free(hungarian_problem_t *p);

/**
 * This method computes the optimal assignment.
Christian Würdig's avatar
Christian Würdig committed
82
83
84
85
 * @param p              The hungarian object
 * @param assignment     The final assignment
 * @param final_cost     The final costs
 * @param cost_threshold Matchings with costs >= this limit will be removed (if limit > 0)
86
 * @return 0 on success, negative number otherwise
87
 */
Christian Würdig's avatar
Christian Würdig committed
88
int hungarian_solve(hungarian_problem_t *p, int *assignment, int *final_cost, int cost_threshold);
89
90
91
92
93

/**
 * Print the cost matrix.
 * @param p The hungarian object
 */
Matthias Braun's avatar
Matthias Braun committed
94
void hungarian_print_costmatrix(hungarian_problem_t *p, int cost_width);
95
96

#endif /* _HUNGARIAN_H_ */