From ff2050b9e8ec451b613332aa87d357cf08b48108 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Sun, 22 Feb 2026 13:42:13 +0100 Subject: m fixes MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- Makefile | 6 +++--- README | 10 +++++----- hungarian.c | 6 ++---- 3 files changed, 10 insertions(+), 12 deletions(-) diff --git a/Makefile b/Makefile index 0552a4e..7a24eab 100644 --- a/Makefile +++ b/Makefile @@ -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 diff --git a/README b/README index 92df369..2e7db54 100644 --- a/README +++ b/README @@ -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 +#include #include #include #include @@ -19,7 +18,6 @@ #include - /** * 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]) -- cgit v1.2.3-70-g09d2