maandree / hungarian-algorithm-n3 Goto Github PK

Unlikely most of Hungarian algorithms, this implementation do not assume that the matrix related to the problem is square or equal number of e.g. workers and tasks.

To terminate progress, the function kuhn_is_done() should be able to return true, in the following cases:
Considered two cases;

• 4 workers with 2 tasks and two workers assigned,
• 2 workers with 4 tasks and two workers assigned.

In both cases, there cannot be more progress possible, but for only one of them, test (count==n) shall return true.

=> the final return statement should be
return (count == MIN(n,m));
or
return (count==n)||(count==m);

I should make this program portable someday…
(It was never intended for anything else than to
be translated into psuedocode.)

The function uses a single allocation for three separate array. One array of c times BitSetLimb, and two arrays of (c+1) times size_t.

When the starting address of this->next is calculated, there are used:
c times BitSetLimb plus only c times size_t.
Now arrays this->prev and this->next are overlapping by one size_t.

I would expect that correct starting address is :
this->next = (size_t *)&this->_buf[c * sizeof(BitSetLimb) + (c+1) * sizeof(size_t)];