Google Git
Sign in
eclipse / gerrit / platform / eclipse.platform.team / 3016ad1cff90ae391ecd96d9bf5821c8140569bb / . / examples / org.eclipse.compare.examples.xml / src / org / eclipse / compare / examples / xml / HungarianMethod.java
blob: dbd2cc623ba6dd889ff613ac13940e24f3b32dfe [file] [log] [blame]
/*******************************************************************************
* Copyright (c) 2000, 2003 IBM Corporation and others.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Common Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/cpl-v10.html
*
* Contributors:
* IBM Corporation - initial API and implementation
*******************************************************************************/
package org.eclipse.compare.examples.xml;
/** This algorithm solves the assignment problem.
* It was translated from Fortran to Java.
* The original algorithm was taken from http://www.netlib.no/netlib/toms/548
*/
public class HungarianMethod {
public int solve(int[][] A, int[] C) {
final int N = A.length-1;
final int NP1 = A[0].length-1;
int[] CH = new int[A.length];
int[] LC = new int[A.length];
int[] LR = new int[A.length];
int[] LZ = new int[A.length];
int[] NZ = new int[A.length];
int[] RH = new int[A[0].length];
int[] SLC = new int[A.length];
int[] SLR = new int[A.length];
int[] U = new int[A[0].length];
int H, Q, R, S, T;
boolean while100goto120 = false;
// SUBROUTINE ASSCT ( N, A, C, T ) 10
// INTEGER A(130,131), C(130), CH(130), LC(130), LR(130),
// * LZ(130), NZ(130), RH(131), SLC(130), SLR(130),
// * U(131)
// INTEGER H, Q, R, S, T
// EQUIVALENCE (LZ,RH), (NZ,CH)
// C
// C THIS SUBROUTINE SOLVES THE SQUARE ASSIGNMENT PROBLEM
// C THE MEANING OF THE INPUT PARAMETERS IS
// C N = NUMBER OF ROWS AND COLUMNS OF THE COST MATRIX, WITH
// C THE CURRENT DIMENSIONS THE MAXIMUM VALUE OF N IS 130
// C A(I,J) = ELEMENT IN ROW I AND COLUMN J OF THE COST MATRIX
// C ( AT THE END OF COMPUTATION THE ELEMENTS OF A ARE CHANGED)
// C THE MEANING OF THE OUTPUT PARAMETERS IS
// C C(J) = ROW ASSIGNED TO COLUMN J (J=1,N)
// C T = COST OF THE OPTIMAL ASSIGNMENT
// C ALL PARAMETERS ARE INTEGER
// C THE MEANING OF THE LOCAL VARIABLES IS
// C A(I,J) = ELEMENT OF THE COST MATRIX IF A(I,J) IS POSITIVE,
// C COLUMN OF THE UNASSIGNED ZERO FOLLOWING IN ROW I
// C (I=1,N) THE UNASSIGNED ZERO OF COLUMN J (J=1,N)
// C IF A(I,J) IS NOT POSITIVE
// C A(I,N+1) = COLUMN OF THE FIRST UNASSIGNED ZERO OF ROW I
// C (I=1,N)
// C CH(I) = COLUMN OF THE NEXT UNEXPLORED AND UNASSIGNED ZERO
// C OF ROW I (I=1,N)
// C LC(J) = LABEL OF COLUMN J (J=1,N)
// C LR(I) = LABEL OF ROW I (I=1,N)
// C LZ(I) = COLUMN OF THE LAST UNASSIGNED ZERO OF ROW I(I=1,N)
// C NZ(I) = COLUMN OF THE NEXT UNASSIGNED ZERO OF ROW I(I=1,N)
// C RH(I) = UNEXPLORED ROW FOLLOWING THE UNEXPLORED ROW I
// C (I=1,N)
// C RH(N+1) = FIRST UNEXPLORED ROW
// C SLC(K) = K-TH ELEMENT CONTAINED IN THE SET OF THE LABELLED
// C COLUMNS
// C SLR(K) = K-TH ELEMENT CONTAINED IN THE SET OF THE LABELLED
// C ROWS
// C U(I) = UNASSIGNED ROW FOLLOWING THE UNASSIGNED ROW I
// C (I=1,N)
// C U(N+1) = FIRST UNASSIGNED ROW
// C
// C THE VECTORS C,CH,LC,LR,LZ,NZ,SLC,SLR MUST BE DIMENSIONED
// C AT LEAST AT (N), THE VECTORS RH,U AT LEAST AT (N+1),
// C THE MATRIX A AT LEAST AT (N,N+1)
// C
// C INITIALIZATION
int KSLC = -1;
int L = -1;
int I = -1;
int M = -1;
int J = -1;
int K = -1;
int LJ = -1;
int LM = -1;
int KSLR = -1;
int NL = -1;
int NM = -1;
//N = N-1;
//NP1 = NP1-1;
// NP1 = N+1
for (J=1; J<=N; J++) {
// DO 10 J=1,N
C[J] = 0;
LZ[J] = 0;
NZ[J] = 0;
U[J] = 0;
}//for (int J=0; J<N; J++)
//10 CONTINUE
U[NP1] = 0;
T = 0;
//C REDUCTION OF THE INITIAL COST MATRIX
for (J=1; J<=N; J++) {
// DO 40 J=1,N
S = A[1][J];
for (L=2; L<=N; L++) {
//DO 20 L=2,N
if (A[L][J] < S) S = A[L][J];
//IF ( A(L,J) .LT. S ) S = A(L,J)
}//for (int L=1; L<N; L++)
//20 CONTINUE
T = T+S;
for (I=1; I<=N; I++) {
//DO 30 I=1,N
A[I][J] = A[I][J]-S;
}//for (int I=0; I<N; I++)
//30 CONTINUE
}//for (int J=0; J<N; J++)
// 40 CONTINUE
for (I=1; I<=N; I++) {
//DO 70 I=1,N
Q = A[I][1];
for (L=2; L<=N; L++) {
//DO 50 L=2,N
//System.out.println("I="+I+" L="+L);
if (A[I][L] < Q) Q = A[I][L];
//IF ( A(I,L) .LT. Q ) Q = A(I,L)
}//for (int L=1; L<N; L++)
//50 CONTINUE
T = T+Q;
L = NP1;
for (J=1; J<=N; J++) {
//DO 60 J=1,N
A[I][J] = A[I][J]-Q;
if (A[I][J] != 0) continue;
//IF ( A[I,J] .NE. 0 ) GO TO 60
A[I][L] = -J;
L = J;
}//for (int J=0; J<N; J++)
//60 CONTINUE
}//for (int I=0; I<N; N++)
//70 CONTINUE
//C CHOICE OF THE INITIAL SOLUTION
K = NP1;
for140:
for (I=1; I<=N; I++) {
// DO 140 I=1,N
LJ = NP1;
J = -A[I][NP1];
do {
if (C[J] == 0) {
// 80 IF ( C(J) .EQ. 0 ) { GO TO 130
C[J] = I;
A[I][LJ] = A[I][J];
NZ[I] = -A[I][J];
LZ[I] = LJ;
A[I][J] = 0;
continue for140; //break??
}
LJ = J;
J = -A[I][J];
} while (J != 0);
// IF ( J .NE. 0 ) GO TO 80
LJ = NP1;
J = -A[I][NP1];
do90:
do {
R = C[J];
LM = LZ[R];
M = NZ[R];
while100goto120 = false;
while100:
while (true) {
if (M == 0) break while100;
// 100 IF ( M .EQ. 0 ) GO TO 110
if (C[M] == 0){
while100goto120 = true;
break do90;
}
// IF ( C(M) .EQ. 0 ) GO TO 120// M != 0 && C[m] == 0
LM = M;
M = -A[R][M];
}
// GO TO 100
//110
LJ = J;
J = -A[I][J];
} while (J != 0);
// IF ( J .NE. 0 ) GO TO 90
if ( !while100goto120 ) {
U[K] = I;
K = I;
continue for140;
// GO TO 140
}
// 120
while100goto120 = false;
NZ[R] = -A[R][M];
LZ[R] = J;
A[R][LM] = -J;
A[R][J] = A[R][M];
A[R][M] = 0;
C[M] = R;
//130
C[J] = I;
A[I][LJ] = A[I][J];
NZ[I] = -A[I][J];
LZ[I] = LJ;
A[I][J] = 0;
// 140 CONTINUE
}
//C RESEARCH OF A NEW ASSIGNMENT
while392:
while (true) {
if (U[NP1] == 0) return T;
// 150 IF ( U(NP1) .EQ. 0 ) RETURN
for (I=1; I<=N; I++) {
// DO 160 I=1,N
CH[I] = 0;
LC[I] = 0;
LR[I] = 0;
RH[I] = 0;
}
// 160 CONTINUE
RH[NP1] = -1;
KSLC = 0;
KSLR = 1;
R = U[NP1];
//System.out.println("R: "+R);
LR[R] = -1;
SLR[1] = R;
boolean goto190 = false;
while360:
while(true) {
do350:
do {
//System.out.println("R: "+R+" NP1: "+NP1);
if (goto190 || A[R][NP1] != 0) {
// IF ( A(R,NP1) .EQ. 0 ) GO TO 220
do200:
do {
if (!goto190) {
// 170
L = -A[R][NP1];
if (A[R][L] != 0) {
// IF ( A(R,L) .EQ. 0 ) GO TO 180
if (RH[R] == 0) {
// IF ( RH(R) .NE. 0 ) GO TO 180
RH[R] = RH[NP1];
CH[R] = -A[R][L];
RH[NP1] = R;
}
}
}// if (!goto190)
//boolean goto210 = false;
while190:
while (true) {
if (!goto190) {
if (LC[L] ==0) break while190;
//180 IF ( LC(L) .EQ. 0 ) GO TO 200
if (RH[R] == 0) {
break do200;
// goto210 = true;
//break;
}
// IF ( RH(R) .EQ. 0 ) GO TO 210
}// if (!goto190)
goto190 = false;
// 190
L = CH[R];
CH[R] = -A[R][L];
if (A[R][L] != 0) continue while190;
//IF ( A(R,L) .NE. 0 ) GO TO 180
RH[NP1] = RH[R];
RH[R] = 0;
//GO TO 180
}//end while190
//if (!goto210) {
//200
LC[L] = R;
if (C[L] == 0) break while360;
//IF ( C(L) .EQ. 0 ) GO TO 360
KSLC = KSLC+1;
SLC[KSLC] = L;
R = C[L];
LR[R] = L;
KSLR = KSLR+1;
SLR[KSLR] = R;
//}
} while (A[R][NP1] != 0); //do200
// IF ( A(R,NP1) .NE. 0 ) GO TO 170
//}// if (!goto210)
// goto210 = false;
// 210 CONTINUE
if (RH[NP1] > 0) break do350;
//IF ( RH(NP1) .GT. 0 ) GO TO 350
}// if (A[R,L] != 0)
//C REDUCTION OF THE CURRENT COST MATRIX
// 220
H = Integer.MAX_VALUE;
for240:
for (J=1; J<=N; J++) {
// DO 240 J=1,N
if (LC[J] != 0) continue for240;
// IF ( LC(J) .NE. 0 ) GO TO 240
for (K=1; K<=KSLR; K++) {
// DO 230 K=1,KSLR
I = SLR[K];
if (A[I][J] < H) H = A[I][J];
// IF ( A(I,J) .LT. H ) H = A(I,J)
}// for (int K=0; K<KSLR; K++)
// 230 CONTINUE
}// for (int J; J<N; J++)
// 240 CONTINUE
T = T+H;
for290:
for (J=1; J<=N; J++) {
// DO 290 J=1,N
if (LC[J] != 0 ) continue for290;
// IF ( LC(J) .NE. 0 ) GO TO 290
for280:
for (K=1; K<=KSLR; K++) {
// DO 280 K=1,KSLR
I = SLR[K];
A[I][J] = A[I][J]-H;
if (A[I][J] != 0) continue for280;
// IF ( A(I,J) .NE. 0 ) GO TO 280
if (RH[I] == 0) {
// IF ( RH(I) .NE. 0 ) GO TO 250
RH[I] = RH[NP1];
CH[I] = J;
RH[NP1] = I;
}// if (RH[I] == 0)
//250
L = NP1;
//260
while (true) {
NL = -A[I][L];
if (NL == 0) break;
// IF ( NL .EQ. 0 ) GO TO 270
L = NL;
}// while (true)
// GO TO 260
//270
A[I][L] = -J;
}// for (int K=0; K<KSLR; K++)
// 280 CONTINUE
}// for (int J=0; J<N; J++)
// 290 CONTINUE
if (KSLC != 0) {
//IF ( KSLC .EQ. 0 ) GO TO 350
for340:
for (I=1; I<=N; I++) {
// DO 340 I=1,N
if (LR[I] != 0) continue for340;
//IF ( LR(I) .NE. 0 ) GO TO 340
for330:
for (K=1; K<=KSLC; K++) {
//DO 330 K=1,KSLC
J = SLC[K];
boolean enter_if = false;
if (A[I][J] <= 0) {
//IF ( A(I,J) .GT. 0 ) GO TO 320
L = NP1;
//300
while (true) {
NL = - A[I][L];
if (NL == J) break;
//IF ( NL .EQ. J ) GO TO 310
L = NL;
}//while (true)
//GO TO 300
//310
A[I][L] = A[I][J];
A[I][J] = H;
//GO TO 330
enter_if = true;
}//if (A[I,J] <=0)
if (!enter_if) {
//320
A[I][J] = A[I][J]+H;
}
}//for (int K=0; K<KSLC; K++)
// 330 CONTINUE
}//for (int I=0; I<N; I++)
// 340 CONTINUE
}// if (KSLC != 0)
} while (false);//do350
//350
R = RH[NP1];
//System.out.println("R: "+R+" at 350");
goto190 = true;
}//while360
// GO TO 190
//C ASSIGNMENT OF A NEW ROW
while389:
while (true) {
//360
C[L] = R;
M = NP1;
//370
while (true) {
NM = -A[R][M];
if (NM == L) break;
// IF ( NM .EQ. L ) GO TO 380
M = NM;
}//while (true)
// GO TO 370
//380
A[R][M] = A[R][L];
A[R][L] = 0;
if (LR[R] < 0) break while389;
// IF ( LR(R) .LT. 0 ) GO TO 390
L = LR[R];
A[R][L] = A[R][NP1];
A[R][NP1] = -L;
R = LC[L];
}//while389
// GO TO 360
//390
U[NP1] = U[R];
U[R] = 0;
}
// GO TO 150
//END
}
}