diff options
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | README | 10 | ||||
| -rw-r--r-- | hungarian.c | 6 |
3 files changed, 10 insertions, 12 deletions
@@ -1,10 +1,11 @@ .POSIX: +CC = c99 + CPPFLAGS = -D_DEFAULT_SOURCE -D_BSD_SOURCE -D_XOPEN_SOURCE=700 -CFLAGS = -std=c99 -g +CFLAGS = -g LDFLAGS = - all: hungarian hungarian: hungarian.c @@ -13,5 +14,4 @@ hungarian: hungarian.c clean: -rm -f -- hungarian - .PHONY: all clean @@ -2,16 +2,16 @@ also known as the Hungarian method, Kuhn–Munkres algorithm or Munkres assignment. -The Hungarian algorithm solves the minmum bipartite +The Hungarian algorithm solves the minimum bipartite matching problem in 𝓞(n⁴). By implementing the priority queue with a van Emde Boas tree the time can be reduced to 𝓞(n³ log log n). The van Emde Boas tree -is possible to use because the elements values are +is possible to use because the element values are bounded within the priority queue's capacity. -However this implemention achives 𝓞(n³) by not using +However, this implementation achieves 𝓞(n³) by not using a priority queue. -Edmonds and Karp, and independently Tomizawa, has +Edmonds and Karp, and independently Tomizawa, have also reduced the time complexity to 𝓞(n³), but I -do not known how. +do not know how. diff --git a/hungarian.c b/hungarian.c index faf7243..793790e 100644 --- a/hungarian.c +++ b/hungarian.c @@ -9,9 +9,8 @@ * To Public License, Version 2, as published by Sam Hocevar. See * http://sam.zoy.org/wtfpl/COPYING for more details. */ - - #include <sys/types.h> +#include <limits.h> #include <stddef.h> #include <stdio.h> #include <stdlib.h> @@ -19,7 +18,6 @@ #include <string.h> - /** * Cell markings **/ @@ -457,7 +455,7 @@ static void kuhn_add_and_subtract(size_t n, size_t m, Cell **t, Boolean row_covered[n], Boolean col_covered[m]) { size_t i, j; - Cell min = 0x7FFFFFFFL; + Cell min = LONG_MAX; for (i = 0; i < n; i++) if (!row_covered[i]) |