PROGRAM DYNAMIC
      IMPLICIT INTEGER(A-Z)
      DOUBLE PRECISION TIMEA,TIMEB,TIMTOT,A(50,50),EPS
      REAL S1
      INTEGER X(50),Q(50),D(50,50),S(50)
C
C #################################################################
C  5/2005: Finds a maximum cardinality subset of objects with
C          perfect dominance structure.
C #################################################################
C
      OPEN(1,FILE='AMAT.DAT')          ! Dissimilarity matrix
      OPEN(2,FILE='SEQ.OUT')           ! Output file
      EPS = 1.0d-07
      READ(1,*) N                      ! Read number of objects
      READ(1,*) ((A(I,J),J=1,N),I=1,N)
      CALL GETTIM (IHR, IMIN, ISEC, I100)
      CALL GETDAT (IYR, IMON, IDAY)
      TIMEA=DFLOAT(86400*IDAY+3600*IHR+60*IMIN+ISEC)+DFLOAT(I100)/100.
      DO I = 1,N
        A(I,I) = 0.0D0
      END DO
C
      DO 848 I = 1,N-1
        DO 849 J = 1+I,N
          IF(A(I,J).GT.A(J,I)) THEN
            D(I,J) = 1
            D(J,I) = 0
          ELSEIF(A(I,J).LT.A(J,I)) THEN
            D(I,J) = 0
            D(J,I) = 1
          ELSE
            D(I,J) = 1      ! IN SOME SITUATIONS, IT MIGHT BE 
            D(J,I) = 1      ! BEST TO MAKE THESE ZEROS
          END IF
 849    CONTINUE
 848  CONTINUE
C
      Z = 0
      DO I = 1,N
        Q(I) = 0
      END DO
C
      M=1
      Q(M)=1
      S(1)=1
      DO K = 2,N
        Q(K)=0
      END DO
C
  1   M = M + 1
C
  2   Q(M)=Q(M)+1
C
      IF(S(Q(M)).EQ.1) GO TO 2               ! REDUNDANCY
      IF(M.EQ.1.AND.Q(M).GT.N) GO TO 9       ! TERMINATE
      IF(M.GT.1.AND.Q(M).GT.N) GO TO 7       ! GO TO RETRACTION
      S(Q(M))=1
      R3 = Q(M)
      DO I = 1,M-1
        R1 = Q(I)
        IF(D(R1,R3).EQ.0) THEN
          S(Q(M))=0
          GO TO 2
        END IF
      END DO
      IF(M.GT.Z) THEN
        Z = M
        DO I = 1,N
          X(I)=Q(I)
        END DO
      END IF
      GO TO 1
C
   7  S(Q(M))=0
      Q(M)=0
      M=M-1
      S(Q(M))=0
      GO TO 2
   9  CALL GETTIM (IHR, IMIN, ISEC, I100)
      CALL GETDAT (IYR, IMON, IDAY)
      TIMEB=DFLOAT(86400*IDAY+3600*IHR+60*IMIN+ISEC)+DFLOAT(I100)/100.
      TIMTOT=TIMEB-TIMEA
      WRITE(*,69) Z
      WRITE(2,69) Z
      WRITE(*,79) TIMTOT
      WRITE(2,79) TIMTOT
      WRITE(2,70) (X(I),I=1,N)
 69   FORMAT(' MAXIMUM SUBSET SIZE WITH PERFECT DOMINANCE ',I7)
 79   FORMAT(' CPU TIME ',F8.2)
 70   FORMAT(30I3)
C
      END