Code:
#include "hungarian.h"
hungarian::hungarian()
{
int i, j;
int xArray[size1][size2] = {
{ 62,77,39,77,23,1,70,65,41,18 },
{ 72,36,37,63,26,83,46,2,12,6 },
{ 71,18,86,7,75,21,90,18,88,35 },
{ 6,52,10,68,74,77,98,11,9,88 },
{ 19,55,99,17,87,4,46,43,39,66 },
{ 48,18,90,44,63,35,65,92,37,18 },
{ 81,12,29,61,39,76,5,86,27,31 },
{ 85,18,86,51,49,96,38,83,52,7 },
{ 48,11,60,83,74,88,43,95,30,96 },
{ 12,47,37,3,2,91,19,90,41,83 } };
for (i = 0;i < size1;++i)
for (j = 0;j < size2;++j) {
Array[i][j] = xArray[i][j];
}
m = size1;
n = size2;
}
hungarian::~hungarian()
{
}
void hungarian::ShowArray(void)
{
int i, j;
for (i = 0;i < size1;++i){
for (j = 0;j < size2;++j) {
printf("%02d\t", Array[i][j]);
}
printf("\n");
}
}
void hungarian::done(void)
{
for (i = 0;i < m;i++) cost += row_dec[i];
for (i = 0;i < n;i++) cost -= col_inc[i];
printf("Cost is %d\n", cost);
}
void initLoop(int (*array)[10], int limit, int initvalue)
{
int l;
for (l = 0;l < limit;l++)
(*array)[l] = initvalue;
}
int hungarian::hungi(void)
{
int rewer = 0, sleib = 1;
//int falsch, wahr;
//falsch = 0;
//wahr = 1;
//printf("Using heuristic\n");
SetArrays();
if (t == 0)
{
done();
return rewer;
}
unmatched = t;
while (1)
{
if (verbose)
printf("Matched %d rows.\n", m - t);
q = 0;
sleib = 1;
do
{
do
{
if((Schleife_b()) == 0) {sleib = 0; break;}
q++;
} while (q < t);
if(sleib == 0) break;
SetArraysb();
if((Schleife_a()) == 0) break;
}while (sleib != 0);
if((durchbruch()) == 0)
return rewer;
}
done();
return rewer;
}
int hungarian::durchbruch(void)
{
int rewer = -1;
if (verbose)
printf("Breakthrough at node %d of %d!\n", q, t);
while (1)
{
j = col_mate[k];
col_mate[k] = l;
row_mate[l] = k;
if (verbose)
printf("rematching col %d==row %d\n", l, k);
if (j < 0)
break;
k = parent_row[j];
l = j;
}
--unmatched;
if (unmatched == 0)
{
done();
rewer = 0;
return rewer;
}
t = 0;
initLoop(&parent_row, n, -1);
initLoop(&slack, n, INT_MAX);
for (k = 0; k < m; k++)
if (col_mate[k] < 0)
{
if (verbose)
unchosen_row[t++] = k;
}
return rewer;
}
void hungarian::SetArrays(void)
{
for (l = 0; l < n; l++)
{
s = Array[0][l];
for (k = 1;k < n;k++)
if (Array[k][l] < s)
s = Array[k][l];
cost += s;
if (s != 0)
for (k = 0;k < n;k++)
Array[k][l] -= s;
}
t = 0;
for (l = 0;l < n;l++)
{
row_mate[l] = -1;
parent_row[l] = -1;
col_inc[l] = 0;
slack[l] = INT_MAX;
}
for (k = 0;k < m;k++)
{
SetArraysc();
if((SetArraysd()) != 0)
{
col_mate[k] = -1;
if (verbose) printf("node %d: unmatched row %d\n", t, k);
unchosen_row[t++] = k;
}
}
}
void hungarian::SetArraysb(void)
{
s = INT_MAX;
for (l = 0;l < n;l++)
if (slack[l] && slack[l] < s)
s = slack[l];
for (q = 0;q < t;q++)
row_dec[unchosen_row[q]] += s;
}
int hungarian::Schleife_a(void)
{
int rewer = -1;
for (l = 0;l < n;l++)
if (slack[l])
{
slack[l] -= s;
if (slack[l] == 0)
{
k = slack_row[l];
if (verbose)
printf(
"Decreasing uncovered elements by %d produces zero at [%d,%d]\n",
s, k, l);
if (row_mate[l] < 0)
{
for (j = l + 1;j < n;j++)
if (slack[j] == 0)
col_inc[j] += s;
return 0;
}
else
{
parent_row[l] = k;
if (verbose)
printf("node %d: row %d==col %d--row %d\n", t, row_mate[l], l, k);
unchosen_row[t++] = row_mate[l];
}
// End look at a new zero 22
}
}
else
col_inc[l] += s;
return rewer;
}
int hungarian::Schleife_b(void)
{
int rewer = -1;
k = unchosen_row[q];
s = row_dec[k];
for (l = 0;l < n;l++)
if (slack[l])
{
del = Array[k][l] - s + col_inc[l];
if (del < slack[l])
{
if (del == 0)
{
if (row_mate[l] < 0)
{
return 0;
}
slack[l] = 0;
parent_row[l] = k;
if (verbose)
printf("node %d: row %d==col %d--row %d\n",
t, row_mate[l], l, k);
unchosen_row[t++] = row_mate[l];
}
else
{
slack[l] = del;
slack_row[l] = k;
}
}
}
return rewer;
}
void hungarian::SetArraysc(void)
{
s = Array[k][0];
for (l = 1;l < n;l++)
if (Array[k][l] < s)
s = Array[k][l];
row_dec[k] = s;
}
int hungarian::SetArraysd(void)
{
int rewer = -1;
for (l = 0;l < n;l++)
if (s == Array[k][l] && row_mate[l] < 0)
{
col_mate[k] = l;
row_mate[l] = k;
rewer = 0;
return rewer;
}
return rewer;
}
at last main.cpp:
