C ALGORITHM 481 COLLECTED ALGORITHMS FROM ACM. C ALGORITHM APPEARED IN COMM. ACM, VOL. 17, NO. 08, C P. 467. C THIS IS THE TEST PROGRAM FOR THE TRANSFORMATION ALGORITHM. A 10 C IT READS THE ARROW NETWORK DESCRIPTION AND ESTABLISHES A 20 C THE INPUT ARRAYS FOR THE ROUTINE (TRNFRM). A 30 C IT IS LIMITED TO 700 ACTIVITIES IN ARROW NOTATION. A 40 C THE ROUTINE (HASH) IS UTILIZED TO CREATE A SEQUENTIAL A 50 C NUMBERING. A 60 C THE ROUTINE (TRNFRM) CREATES THE ACTUAL TRANSFORMATION. A 70 C TAPE(2) -A BINARY SCRATCH TAPE (FILE) WITH ALL DATA TO A 80 C BE INCLUDED WITH THE TRANSFORMED ACTIVITIES.NOTE- CHANGE A 90 C STMT 140 TO CORRESPOND WITH ACTUAL DATA STORED. A 100 C TAPE(4) -A BINARY SCRATCH TAPE FOR TRANSFERING THE TRANS- A 110 C FORMED DATA BACK TO THE MAIN PROGRAM FOR PRINT OUT, OR ANY A 120 C OTHER USE. THE DATA IS IN THE FORM (I,M,FOL) WHERE I IS A 130 C THE NEW ACTIVITY LABEL AND M IS THE NUMBER OF FOLLOWERS A 140 C AND FOL IS AN ARRAY CONTAINING THE LABELS OF THE M A 150 C FOLLOWERS... A 160 INTEGER II(700), JJ(700), NLOC(700), ACT(2), DUMMY, A 170 * HASH, FOL(50) A 180 DATA DUMMY/5HDUMMY/, IBLNK/1H / A 190 C READ IN ARROW ACTIVITIES ACCORDING TO CURRENT FORMAT. A 200 99999 FORMAT(1H1, 13H INPUT ORDER, 6X, 5HLABEL, 5X, 4HDESC, A 210 * 7HRIPTION, 12X, 3HDUR) A 220 99998 FORMAT(2A4, 2A10, I3, 3X, I6) A 230 99997 FORMAT(I14, 4X, A4, 1H-, A4, 3X, 2A10, I6) A 240 99996 FORMAT(1H1, 19HTRANSFORMED NETWORK//14H LABEL DESCR, A 250 * 6HIPTION, 10X, 3HDUR, 3X, 9HFOLLOWERS) A 260 99995 FORMAT(1H , I7, 2X, 2A10, I4) A 270 99994 FORMAT(1H+, 36X, 15I5/(37X, 15I5)) A 280 WRITE (6,99999) A 290 NACT = 0 A 300 NTAPE2 = 0 A 310 10 READ (5,99998) I, J, ACT, IDUR A 320 C FORMAT (99998) WILL VARY FOR INDIVIDUAL NEEDS. A 330 C THE TEST FOR END OF DATA IS A BLANK CARD. A 340 IF (I.EQ.IBLNK) GO TO 30 A 350 NACT = NACT + 1 A 360 C LIST THE ARROW DATA FOR REFERENCE. A 370 WRITE (6,99997) NACT, I, J, ACT, IDUR A 380 C CONVERT THE ALPHANUMERIC I-J LABELS INTO SEQUENTIAL A 390 C NUMERIC. (ROUTINE HASH PERFORMS THIS TASK.) A 400 C STORE THE CONVERTED LABELS IN THE ARRAYS (II AND JJ). A 410 C NOTE. THE VALUE STORED IN ARRAY (JJ) IS ALSO SAVED AS A 420 C VARIABLE J TO ALLOW IT TO BE USED AT STMT 20 WITHOUT AN A 430 C ARRAY REFERENCE. A 440 II(NACT) = HASH(I) A 450 J = HASH(J) A 460 JJ(NACT) = J A 470 C STORE THE INCOMING INPUT SEQUENCE VALUE IN ARRAY (NLOC) A 480 NLOC(NACT) = NACT A 490 C EXAMPLE OF USER CREATED LABELING, SEE ALSO COMMENTS AFTER A 500 C STMT 140 IN ROUTINE TRNFRM. A 510 C LABLS(NACT)=CONCATENATION OF INPUT (I-J) A 520 C THE CONCATENATION IS PERFORMED IN ACCORDANCE WITH VALID A 530 C FORTRAN FOR THE COMPILER IN USE. A 540 C TEST FOR A DUMMY ACTIVITY AS IT WILL NOT BE TRANSFORMED. A 550 IF (ACT(1).EQ.DUMMY) GO TO 20 A 560 C SAVE ON TAPE (2) ALL INFORMATION RELATING TO THE ACTIVITY A 570 C JUST READ THAT IS TO BE ASSOCIATED WITH THE TRANSFORMED A 580 C ACTIVITY.(FOR THE EXAMPLES ONLY THE DESCRIPTION AND DUR A 590 C ARE SAVED,ACTUAL USERS WILL HAVE INDIVIDUAL REQUIREMENTS) A 600 NTAPE2 = NTAPE2 + 1 A 610 WRITE (2) ACT, IDUR A 620 GO TO 10 A 630 C IF AN ACTIVITY WAS A DUMMY, SO NOTE BY SETTING THE A 640 C LOCATION AND JJ LABEL VECTORS NEGATIVE. A 650 20 NLOC(NACT) = -NACT A 660 JJ(NACT) = -J A 670 C RETURN FOR NEXT INPUT ACTIVITY. TRANSFER WILL BE MADE TO A 680 C STMT 30 WHEN LAST INPUT IS RECOGNIZED. A 690 GO TO 10 A 700 30 REWIND 2 A 710 C CALL THE TRANSFORMATION ROUTINE.,DESCRIPTION OF INPUT A 720 C ARRAYS IS FOUND IN THE (TRNFRM) ROUTINE. A 730 CALL TRNFRM(NACT, II, JJ, NLOC) A 740 C PRINT OUT THE TRANSFORMED NETWORK... A 750 WRITE (6,99996) A 760 DO 40 N=1,NTAPE2 A 770 C RECOVER THE REQUIRED DATA RELATING TO THE TRANSFORMED A 780 C ACTIVITY FROM TAPE(2) AND TAPE (4). A 790 READ (2) ACT, IDUR A 800 READ (4) I, M, FOL A 810 WRITE (6,99995) I, ACT, IDUR A 820 IF (M.LE.0) GO TO 40 A 830 WRITE (6,99994) (FOL(MM),MM=1,M) A 840 40 CONTINUE A 850 STOP A 860 END A 870 INTEGER FUNCTION HASH(N) B 10 C THIS ROUTINE CONVERTS THE ALPHANUMERIC ARROW LABELS INTO A C SEQUENTIAL NUMERIC EQUIVALENT. THE MAXIMUM NUMBER OF C SEPARATE ACTIVITY LABELS IS 500 FOR THIS TEST PACKAGE. C THE ACTUAL INCOMING LABEL IS STORED IN ARRAY (HOLD) AND C THE SEQUENTIAL NUMERIC EQUIVALENT IS STORED IN ARRAY C (SAVE) C VARIABLE (NUM) PROVIDES THE SEQUENTIAL NUMBERS. INTEGER HOLD(500), SAVE(500) DATA NUM/0/, HOLD/500*0/ C USE A MODIFIED HASHING ROUTINE TO FIND AND STORE THE C EQUIVALENT VALUES. C NN IS A HASHED VALUE FOR THE INPUT VARIABLE N. 99999 FORMAT(34H EXCEEDED THE EVENT TABLE CAPACITY) NN = MOD(IABS(N/68719476736),375) 10 DO 20 I=NN,500 C THE ARRAY (HOLD) IS EXAMINED STARTING WITH THE HASHED C VALUE, IF THE ARRAY ELEMENT CONTAINS THE INPUT VARIABLE N, C TRANSFER IS MADE TO STMT 40 AND THE EQUIVALENT SEQUENTIAL C NUMBER IS RECALLED FROM ARRAY (SAVE). IF THE ARRAY ELEMENT C CONTAINS A ZERO,TRANSFER IS MADE TO STMT 30 AND A C NUMERICAL C EQUIVALENT IS ASSIGNED. THE SEARCH OF (HOLD) CONTINUES C UNTIL AN OPEN ELEMENT IS FOUND... IF (HOLD(I).EQ.N) GO TO 40 IF (HOLD(I).EQ.0) GO TO 30 20 CONTINUE C IF NO OPEN ELEMENT WAS FOUND AND NN=1 THERE ARE NO OPEN C ELEMENTS IN THE ENTIRE ARRAY. IF NN IS NOT EQUAL TO 1, SET C IT TO 1 AND SEARCH LOWER PART OF (HOLD)... IF (NN.EQ.1) GO TO 60 NN = 1 GO TO 10 C FOUND A NEW LABEL-GIVE IT AN EQUIVALENT SEQUENTIAL NUMBER 30 HOLD(I) = N NUM = NUM + 1 IVAL = NUM SAVE(I) = IVAL C TRANSFER TO STMT 50 AND SAVE A REDUNDANT RECALL FROM C (SAVE) GO TO 50 40 IVAL = SAVE(I) 50 HASH = IVAL RETURN C AN ERROR MESSAGE IS GENERATED IF THE NUMBER OF EVENTS C EXCEEDS THE DIMENSION ALLOWED. 60 WRITE (6,99999) STOP END SUBROUTINE TRNFRM(NACT, II, JJ, NLOC) C 10 C ALL DATA WAS STORED IN THE ARRAYS (II-JJ-NLOC) BY THE C CALLING ROUTINE AND COMFORMS TO THE FOLLOWING DESCRIPTION C (NACT) -THE NUMBER OF ARROW ACTIVITIES INCLUDING DUMMIES. C (II) -AN ARRAY OF CONVERTED -I- LABELS STORED IN THE ARROW C NETWORK INPUT ORDER.REFER TO THE COMMENTS AFTER STMT 140 C IF USER GERERATED LABELS ARE DESIRED.SEE ALSO COMMENTS IN C MAIN ROUTINE. C (JJ) -AN ARRAY LIKE (II) FOR -J- LABELS EXCEPT THAT THE C VALUE IS NEGATIVE FOR ALL DUMMY ACTIVITIES. C (NLOC) -AN ARRAY INDICATING INPUT ORDER.(A SEQUENTIAL LIST C SUCH THAT THE ABSOLUTE VALUES WOULD RANGE FROM ONE TO NACT C ) NOTE- THE VALUE STORED IN (NLOC) IS NEGATIVE WHEN THE C CORRESPONDING ARROW ACTIVITY WAS A -DUMMY- . C TAPE(4) -A BINARY SCRATCH TAPE FOR TRANSFERING THE TRANS- C FORMED DATA BACK TO THE MAIN PROGRAM FOR PRINT OUT, OR ANY C OTHER USE. THE DATA IS IN THE FORM (I,M,FOL) WHERE I IS C THE NEW ACTIVITY LABEL AND M IS THE NUMBER OF FOLLOWERS C AND FOL IS AN ARRAY CONTAINING THE LABELS OF THE M C FOLLOWERS... C STORAGE FOR THE ARRAYS IS ALSO SPECIFIED IN THE CALLING C PROGRAM. INTEGER II(1), JJ(1), NLOC(1) INTEGER STACK(50), FOL(50) C THE DIMENSION STAMENTS FOR (II-JJ-NLOC) MUST BE MODIFIED C FOR USE WITH SOME FORTRAN COMPILERS. C DIMENSIONS ON STACK AND FOL LIMIT THE NUMBER OF FOLLOWING C ACTIVITIES TO 50. C STATEMENT FUNCTION TO PROVIDE OVERLAYING ARRAY (II) WITH C ARRAY (ILOC).REFER TO THE WARNING AFTER STMT 30,IF A C SEPERATE ARRAY (ILOC) IS UTILIZED THE STATEMENT FUNCTION C WOULD BE DELETED. 99999 FORMAT(41H THE FOLLOWING ACTIVITY APPEARS TO HAVE M, * 22HORE THAN 50 FOLLOWERS ) 99998 FORMAT(41H SUSPECT THE FOLLOWING ACTIVITY IS INVOLV, * 41HED IN A NETWORK LOOP - CHECK INPUT DATA. /I5) ILOC(I) = II(I) C REWIND TAPE 4 FOR TRANSFER OF TRANSFORMED DATA. REWIND 4 C PLACE THE ARRAYS (II-NLOC) IN ASENDING ORDER USING (II) C AS THE SORT VARIABLE. (THIS IS A BUBBLE UP SORT.) LIMIT = NACT - 1 DO 20 M=1,LIMIT LL = M + 1 DO 10 N=LL,NACT IF (II(M).LE.II(N)) GO TO 10 IHOLD = II(N) II(N) = II(M) II(M) = IHOLD IHOLD = NLOC(N) NLOC(N) = NLOC(M) NLOC(M) = IHOLD 10 CONTINUE 20 CONTINUE C REPLACE THE ARRAY (II) WITH AN INTEGER POINTER SUCH THAT C THE (K TH) ELEMENT OF THE POINTER POINTS TO THE FIRST C LOCATION IN THE SORTED ARRAY (II) WHICH CONTAINS THE VALUE C (K).THE POINTER ARRAY WILL BE CALLED (ILOC) SINCE IT C INDICATES THE BEGINNING OF SORTED ARROW NODES (ARRAY II) C AND THESE NODES ARE NORMALLY REFERRED TO AS (I) NODES. C THE VARIABLE (N) IS SET TO THE MINIMUM VALUE IN ARRAY (II) C N IS ALSO A VARIABLE THAT INDICATES THE CURRENT VALUE C UNDER INVESTIGATION IN ARRAY (II). C L IS A POINTER TO THE ARRAY (ILOC),INDICATING THE LOCATION C OF THE NEXT ELEMENT.IN ADDITION L ALSO INDICATES THE NEXT C SEQUENTIAL NUMBER,AND IS USED TO FIND THE END NODES.(NODES C WHERE THERE EXISTS NO -I- IN THE (I-J) PAIRS,AND THERE- C FORE NO ENTRY IN THE SORTED (II) ARRAY..) N = 1 L = 2 DO 50 I=2,NACT IF (II(I).EQ.N) GO TO 50 N = II(I) 30 IF (N.EQ.L) GO TO 40 C THIS TEST FINDS THE REFERENCES TO THE END NODE WHICH WILL C NOT BE IN THE SORTED ARRAY OF (I) NODES. C WARNING -- ALTHOUGH INPUT ORDER IS NOT NORMALLY IMPORTANT C REFERENCE TO END NODES,THAT IS (I-J) PAIRS WITH -J- EQUAL C TO AN END NODE,SHOULD BE POSITIONED IN THE LATER PORTION C OF THE INPUT DATA.THIS RESTRICTION CAN BE ELIMINATED BY C USING A SEPARATE ARRAY FOR (ILOC). C II(L) IS SET TO ZERO TO INDICATE THAT NODE -L- IS AN END C NODE IN THE ARROW INPUT NETWORK. II(L) = 0 L = L + 1 GO TO 30 C STORE THE SUBSCRIPT VALUE OF THE ARRAY (II) IN TO THE C OVERLAYED ARRAY (ILOC). 40 II(L) = I L = L + 1 50 CONTINUE C SET THE NEXT LOCATION OF THE POINTER TO ONE PAST THE LAST C ACTIVITY NUMBER. MAXLST = L - 1 II(L) = NACT + 1 C FOR ALL NON DUMMY ACTIVITIES,TRANSFORM THE ARROW LOGIC C CONSTRAINTS INTO THE PRECEDENCE NOTATION BY GIVING THE C ACTIVITY A LABEL EQUAL TO ITS INPUT ORDER,THEN LIST ALL C TRANSFORMED FOLLOWERS. DO 160 I=1,NACT L = 0 M = 0 C L INDICATES THE LENGTH OF THE STACK AND M IS THE NUMBER OF C FOLLOWERS.THE STACK IS USED TO RECURSIVELY TRACE ALL C DUMMIES TO FIND LOGICAL FOLLOWERS. N = JJ(I) C IF N IS NEGATIVE THE ARROW ACTIVITY WAS A DUMMY. IF (N.LE.0) GO TO 160 60 LOC = N IF (LOC.GT.MAXLST) GO TO 110 C LOC HAS A VALUE EQUAL TO THE -J- LABEL OF ACTIVITY UNDER C TRANSFORMATION. ILOCR POINTS TO THE BEGINNING OF THAT SAME C VALUE IN THE SORTED ARRAY (II).WHEN (LOC) EXCEEDS THE C VALUE OF (MAXLST) THE -J- LABEL ON THE ARROW NETWORK WAS C THE END NODE,THEREFORE THERE ARE NO FOLLOWERS. ILOCR = ILOC(LOC) IF (ILOCR.LE.0) GO TO 110 C IF ILOCR IS NEG OR ZERO THE ACTIVITY HAS NO FOLLOWERS. 70 LOC = LOC + 1 NN = ILOC(LOC) - ILOCR C NN INDICATES THE NUMBER OF ELEMENTS IN ARRAY (II) WITH THE C VALUE. IF (NN.LE.0) GO TO 70 DO 100 LOOP=1,NN LOCS = NLOC(ILOCR) IF (LOCS.EQ.0) GO TO 90 IF (LOCS.GT.0) GO TO 80 C LOCS NEGATIVE INDICATES A DUMMY AND THESE ARE HELD IN THE C STACK FOR LATER CONTINUED SEARCH OF FOLLOWERS. L = L + 1 IF (L.GT.50) GO TO 130 STACK(L) = -LOCS GO TO 90 80 M = M + 1 C A FOLLOWER HAS BEEN FOUND.STORE IT IN THE ARRAY (FOL). IF (M.GT.50) GO TO 120 FOL(M) = LOCS C INCREASE THE POINTER TO NEXT POTENTIAL FOLLOWER. 90 ILOCR = ILOCR + 1 100 CONTINUE 110 IF (L.LE.0) GO TO 140 C IF (L) IS NON-ZERO,THERE ARE DUMMY LINKAGES TO BE CONSIDER C ED. (N) WILL INDICATE FIRST OF THESE AND THE SEARCH FOR C FOLLOWERS WILL CONTINUE. K = STACK(L) N = IABS(JJ(K)) L = L - 1 GO TO 60 C ERROR MESSAGES IF DIMENSIONS EXCEEDED- LOOP ASSUMED. 120 WRITE (6,99999) 130 WRITE (6,99998) I 140 WRITE (4) I, M, FOL C IF USER LABELS ARE USED THEY WOULD BE RETRIEVED THUSLY -- C I = LABLS(I) C DO 150 LOOP=1,M C ISUB = FOL(LOOP) C FOL(LOOP) = LABLS(ISUB) C 150 CONTINUE C WHERE LABLS WOULD BE AN ARRAY PASSED IN THE ARGUMENT LIST 160 CONTINUE REWIND 4 RETURN END