Télécharger perm24.eso

Retour à la liste

Numérotation des lignes :

  1. C PERM24 SOURCE BP208322 16/06/27 21:16:23 8990
  2.  
  3. SUBROUTINE PERM24(N,A,II,F,INF,JJ,U,V,FB,RC)
  4. C
  5. C DETERMINATION OF AN AUGMENTING PATH STARTING FROM
  6. C UNASSIGNED ROW II AND TERMINATING AT UNASSIGNED COLUMN
  7. C JJ , WITH UPDATING OF DUAL VARIABLES U(I) AND V(J) .
  8. C
  9. C MEANING OF THE MAIN INTERNAL VARIABLES:
  10. C LR(L) = L-TH LABELLED ROW ( L=1,NLR ).
  11. C PI(J) = MIN ( A(I,J) - U(I) - V(J) , SUCH THAT ROW I IS
  12. C LABELLED AND NOT EQUAL TO FB(J) ).
  13. C RC(J) = ROW PRECEDING COLUMN J IN THE CURRENT
  14. C ALTERNATING PATH.
  15. C UC(L) = L-TH UNLABELLED COLUMN ( L=1,NUC ).
  16. C
  17. IMPLICIT INTEGER(I-N)
  18. IMPLICIT REAL*8(A-H,O-Z)
  19.  
  20. INTEGER A(N,N),F(N)
  21. INTEGER PI(N),LR(N),UC(N)
  22. INTEGER U(N),V(N),FB(N),RC(N),R
  23. C INITIALIZATION.
  24. LR(1) = II
  25. DO 10 K=1,N
  26. PI(K) = A(II,K) - U(II) - V(K)
  27. RC(K) = II
  28. UC(K) = K
  29. 10 CONTINUE
  30. NUC = N
  31. NLR = 1
  32. GO TO 40
  33. C SCANNING OF THE LABELLED ROWS.
  34. 20 R = LR(NLR)
  35. DO 30 L=1,NUC
  36. J = UC(L)
  37. IA = A(R,J) - U(R) - V(J)
  38. IF ( IA .GE. PI(J) ) GO TO 30
  39. PI(J) = IA
  40. RC(J) = R
  41. 30 CONTINUE
  42. C SEARCH FOR A ZERO ELEMENT IN AN UNLABELLED COLUMN.
  43. 40 DO 50 L=1,NUC
  44. J = UC(L)
  45. IF ( PI(J) .EQ. 0 ) GO TO 100
  46. 50 CONTINUE
  47. C UPDATING OF THE DUAL VARIABLES U(I) AND V(J) .
  48. MIN = INF
  49. DO 60 L=1,NUC
  50. J = UC(L)
  51. IF ( MIN .GT. PI(J) ) MIN = PI(J)
  52. 60 CONTINUE
  53. DO 70 L=1,NLR
  54. R = LR(L)
  55. U(R) = U(R) + MIN
  56. 70 CONTINUE
  57. DO 90 J=1,N
  58. IF ( PI(J) .EQ. 0 ) GO TO 80
  59. PI(J) = PI(J) - MIN
  60. GO TO 90
  61. 80 V(J) = V(J) - MIN
  62. 90 CONTINUE
  63. GO TO 40
  64. 100 IF ( FB(J) .EQ. 0 ) GO TO 110
  65. C LABELLING OF ROW FB(J) AND REMOVAL OF THE LABEL OF
  66. C COLUMN J .
  67. NLR = NLR + 1
  68. LR(NLR) = FB(J)
  69. UC(L) = UC(NUC)
  70. NUC = NUC - 1
  71. GO TO 20
  72. C DETERMINATION OF THE UNASSIGNED COLUMN J .
  73. 110 JJ = J
  74. RETURN
  75. END
  76.  
  77.  

© Cast3M 2003 - Tous droits réservés.
Mentions légales