libFirm
 All Data Structures Functions Variables Typedefs Enumerations Enumerator Groups Pages
hungarian.h
1 /********************************************************************
2  ********************************************************************
3  **
4  ** libhungarian by Cyrill Stachniss, 2004
5  **
6  ** Added to libFirm by Christian Wuerdig, 2006
7  ** Added several options for not-perfect matchings.
8  **
9  ** Solving the Minimum Assignment Problem using the
10  ** Hungarian Method.
11  **
12  ** ** This file may be freely copied and distributed! **
13  **
14  ** Parts of the used code was originally provided by the
15  ** "Stanford GraphGase", but I made changes to this code.
16  ** As asked by the copyright node of the "Stanford GraphGase",
17  ** I hereby proclaim that this file are *NOT* part of the
18  ** "Stanford GraphGase" distribution!
19  **
20  ** This file is distributed in the hope that it will be useful,
21  ** but WITHOUT ANY WARRANTY; without even the implied
22  ** warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
23  ** PURPOSE.
24  **
25  ********************************************************************
26  ********************************************************************/
27 
32 #ifndef FIRM_ADT_HUNGARIAN_H
33 #define FIRM_ADT_HUNGARIAN_H
34 
35 #include "../begin.h"
36 
45 typedef enum match_type_t {
49 } match_type_t;
50 
52 typedef enum hungarian_mode_t {
56 
61 
71 FIRM_API hungarian_problem_t *hungarian_new(unsigned num_rows,
72  unsigned num_cols,
73  match_type_t match_type);
74 
78 FIRM_API void hungarian_add(hungarian_problem_t *p, unsigned left,
79  unsigned right, unsigned cost);
80 
84 FIRM_API void hungarian_remove(hungarian_problem_t *p, unsigned left,
85  unsigned right);
86 
94  hungarian_mode_t mode);
95 
99 FIRM_API void hungarian_free(hungarian_problem_t *p);
100 
109 FIRM_API int hungarian_solve(hungarian_problem_t *p, unsigned *assignment,
110  unsigned *final_cost, unsigned cost_threshold);
111 
117 FIRM_API void hungarian_print_cost_matrix(hungarian_problem_t const *p,
118  int cost_width);
119 
122 #include "../end.h"
123 
124 #endif
match_type_t
type of matching
Definition: hungarian.h:45
void hungarian_free(hungarian_problem_t *p)
Destroys the hungarian object.
void hungarian_print_cost_matrix(hungarian_problem_t const *p, int cost_width)
Print the cost matrix.
hungarian_mode_t
mode of matching (the optimization goal)
Definition: hungarian.h:52
struct hungarian_problem_t hungarian_problem_t
Internal representation of a bipartite matching problem.
Definition: hungarian.h:60
matchings of nodes having no edge getting removed
Definition: hungarian.h:47
void hungarian_prepare_cost_matrix(hungarian_problem_t *p, hungarian_mode_t mode)
Prepares the cost matrix dependent on the given mode.
void hungarian_remove(hungarian_problem_t *p, unsigned left, unsigned right)
Removes the edge from left to right.
void hungarian_add(hungarian_problem_t *p, unsigned left, unsigned right, unsigned cost)
Adds an edge from left to right with some costs.
int hungarian_solve(hungarian_problem_t *p, unsigned *assignment, unsigned *final_cost, unsigned cost_threshold)
This method computes the optimal assignment.
ever nodes matches another node
Definition: hungarian.h:46
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 col...