diff options
| -rw-r--r-- | .gitignore | 7 | ||||
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | hungarian.c | 80 |
3 files changed, 53 insertions, 39 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..45282db --- /dev/null +++ b/.gitignore @@ -0,0 +1,7 @@ +/hungarian + +*~ +\#*\# +.\#* +*.bak +*.swp @@ -1,11 +1,14 @@ all: gcc -o "hungarian"{,.c} +nodebug: + gcc -o "hungarian"{,.c} + test: ./"hungarian" valgrind: - valgrind --leak-check=full ./"hungarian" + valgrind --tool=memcheck --leak-check=full ./"hungarian" clean: if [ -f "hungarian" ]; then unlink "hungarian"; fi diff --git a/hungarian.c b/hungarian.c index 90f9f64..f0bb446 100644 --- a/hungarian.c +++ b/hungarian.c @@ -93,22 +93,22 @@ typedef struct * The set of all limbs, a limb consist of 64 bits */ cell* limbs; - + /** * Singleton array with the index of the first non-zero limb */ long* first; - + /** - * Array the the index of the previous non-zero limb for echo limb + * Array the the index of the previous non-zero limb for each limb */ long* prev; - + /** - * Array the the index of the next non-zero limb for echo limb + * Array the the index of the next non-zero limb for each limb */ long* next; - + } BitSet; @@ -139,8 +139,8 @@ int main(int argc, char** argv) asm("cpuid"); asm volatile("rdtsc" : "=a" (a), "=d" (d)); srand(((llong)a) | (((llong)d) << 32LL)); - - + + long n = 10, m = 15; long i; @@ -174,8 +174,6 @@ int main(int argc, char** argv) } } - //kuhn_match(table, n, m); - printf("\nInput:\n\n"); print(t, n, m, null); @@ -187,14 +185,14 @@ int main(int argc, char** argv) for (i = 0; i < n; i++) sum += *(*(t + *(*(assignment + i) + 0)) + *(*(assignment + i) + 1)); printf("\n\nSum: %li\n\n", sum); - + return 0; } void print(cell** t, long n, long m, long** assignment) { long i, j; - + long** assigned = new_arrays(n); for (i = 0; i < n; i++) { @@ -205,7 +203,7 @@ void print(cell** t, long n, long m, long** assignment) if (assignment != null) for (i = 0; i < n; i++) (*(*(assigned + **(assignment + i)) + *(*(assignment + i) + 1)))++; - + for (i = 0; i < n; i++) { printf(" "); @@ -224,11 +222,11 @@ void print(cell** t, long n, long m, long** assignment) /** * Calculates an optimal bipartite minimum weight matching using an * O(n³)-time implementation of The Hungarian Algorithm, also known - * as Kuhn's Algorithm. This implemention is restricted to square - * tables. + * as Kuhn's Algorithm. * * @param table The table in which to perform the matching - * @param n The dimension of the table + * @param n The height of the table + * @param h The width of the table * @return The optimal assignment, an array of row–coloumn pairs */ long** kuhn_match(cell** table, long n, long m) @@ -239,7 +237,7 @@ long** kuhn_match(cell** table, long n, long m) kuhn_reduceRows(table, n, m); byte** marks = kuhn_mark(table, n, m); - + boolean* rowCovered = new_booleans(n); boolean* colCovered = new_booleans(m); for (i = 0; i < n; i++) @@ -249,13 +247,13 @@ long** kuhn_match(cell** table, long n, long m) } for (i = n; i < m; i++) *(colCovered + i) = false; - + long* altRow = new_longs(n * m); long* altCol = new_longs(n * m); long* rowPrimes = new_longs(n); long* colMarks = new_longs(m); - + long* prime; for (;;) @@ -307,7 +305,7 @@ void kuhn_reduceRows(cell** t, long n, long m) for (j = 1; j < m; j++) if (min > *(ti + j)) min = *(ti + j); - + for (j = 0; j < m; j++) *(ti + j) -= min; } @@ -335,7 +333,7 @@ byte** kuhn_mark(cell** t, long n, long m) for (j = 0; j < m; j++) *(marksi + j) = UNMARKED; } - + boolean* rowCovered = new_booleans(n); boolean* colCovered = new_booleans(m); for (i = 0; i < n; i++) @@ -384,7 +382,7 @@ boolean kuhn_isDone(byte** marks, boolean* colCovered, long n, long m) for (j = 0; j < m; j++) if (*(colCovered + j)) count++; - + return count == n; } @@ -403,7 +401,7 @@ boolean kuhn_isDone(byte** marks, boolean* colCovered, long n, long m) long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCovered, long n, long m) { long i, j; - BitSet zeroes = new_BitSet(n * n); + BitSet zeroes = new_BitSet(n * m); for (i = 0; i < n; i++) if (!*(rowCovered + i)) @@ -418,8 +416,14 @@ long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCo { p = BitSet_any(zeroes); if (p < 0) + { + free(zeroes.limbs); + free(zeroes.first); + free(zeroes.next); + free(zeroes.prev); return null; - + } + row = p / m; col = p % m; @@ -432,12 +436,12 @@ long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCo markInRow = true; col = j; } - + if (markInRow) { *(rowCovered + row) = true; *(colCovered + col) = false; - + for (i = 0; i < n; i++) if ((*(*(t + i) + col) == 0) && (row != i)) { @@ -446,7 +450,7 @@ long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCo else BitSet_unset(zeroes, i * m + col); } - + for (j = 0; j < m; j++) if ((*(*(t + row) + j) == 0) && (col != j)) { @@ -455,7 +459,7 @@ long* kuhn_findPrime(cell** t, byte** marks, boolean* rowCovered, boolean* colCo else BitSet_unset(zeroes, row * m + j); } - + if ((!*(rowCovered + row)) && (!*(colCovered + col))) BitSet_set(zeroes, row * m + col); else @@ -497,7 +501,7 @@ void kuhn_altMarks(byte** marks, long* altRow, long* altCol, long* colMarks, lon } for (i = n; i < m; i++) *(colMarks + i) = -1; - + for (i = 0; i < n; i++) for (j = 0; j < m; j++) if (*(*(marks + i) + j) == MARKED) @@ -522,7 +526,7 @@ void kuhn_altMarks(byte** marks, long* altRow, long* altCol, long* colMarks, lon *(altRow + index) = *(altRow + index - 1); *(altCol + index) = col; } - + byte* markx; for (i = 0; i <= index; i++) { @@ -587,7 +591,7 @@ void kuhn_addAndSubtract(cell** t, boolean* rowCovered, boolean* colCovered, lon long** kuhn_assign(byte** marks, long n, long m) { long** assignment = new_arrays(n); - + long i, j; for (i = 0; i < n; i++) { @@ -599,7 +603,7 @@ long** kuhn_assign(byte** marks, long n, long m) *(*(assignment + i) + 1) = j; } } - + return assignment; } @@ -644,9 +648,9 @@ void BitSet_set(BitSet this, long i) { long j = i >> 6L; llong old = *(this.limbs + j); - + *(this.limbs + j) |= 1LL << (llong)(i & 63L); - + if ((!*(this.limbs + j)) ^ (!old)) { j++; @@ -669,7 +673,7 @@ void BitSet_unset(BitSet this, long i) llong old = *(this.limbs + j); *(this.limbs + j) &= ~(1LL << (llong)(i & 63L)); - + if ((!*(this.limbs + j)) ^ (!old)) { j++; @@ -678,7 +682,7 @@ void BitSet_unset(BitSet this, long i) *(this.prev + n) = p; *(this.next + p) = n; if (*(this.first) == j) - *(this.first) = *(this.next + j); + *(this.first) = n; } } @@ -692,7 +696,7 @@ long BitSet_any(BitSet this) { if (*(this.first) == 0L) return -1; - + long i = *(this.first) - 1L; return lb(*(this.limbs + i) & -*(this.limbs + i)) + (i << 6L); } @@ -708,7 +712,7 @@ long lb(llong value) { long rc = 0L; llong v = value; - + if (v & 0xFFFFFFFF00000000LL) { rc |= 32L; v >>= 32LL; } if (v & 0x00000000FFFF0000LL) { rc |= 16L; v >>= 16LL; } if (v & 0x000000000000FF00LL) { rc |= 8L; v >>= 8LL; } |