This repository has been archived by the owner on Nov 9, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 32
/
hungarian.hpp
66 lines (56 loc) · 1.81 KB
/
hungarian.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/********************************************************************
********************************************************************
**
** libhungarian by Cyrill Stachniss, 2004
** http://www2.informatik.uni-freiburg.de/~stachnis/misc.html
**
** Modified and adapted from C to C++ by Justin Buchanan
**
** 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.
**
********************************************************************
********************************************************************/
#pragma once
#include <vector>
namespace Hungarian {
typedef enum {
MODE_MINIMIZE_COST,
MODE_MAXIMIZE_UTIL,
} MODE;
typedef enum {
NOT_ASSIGNED,
ASSIGNED,
} ASSIGN;
using Matrix = std::vector<std::vector<int>>;
struct Result {
// True if the algorithm completed and found a solution.
bool success = false;
// The solution
Matrix assignment;
// A normalized form of the input cost matrix.
Matrix cost;
// The costs incurred by the assignment
int totalCost = 0;
};
/**
* Runs the hungarian algorithm on the input cost matrix and returns a result
* containing the normalized (square) cost matrix and a solution if one was
* found.
*/
Result Solve(const Matrix &input, MODE mode);
void PrintMatrix(const Matrix &m);
}; // namespace Hungarian