SUBROUTINE M7SLO(N,INDROW,JPNTR,INDCOL,IPNTR,NDEG,LIST, * MAXCLQ,IWA1,IWA2,IWA3,IWA4,BWA) INTEGER N,MAXCLQ INTEGER INDROW(1),JPNTR(1),INDCOL(1),IPNTR(1),NDEG(N), * LIST(N),IWA1(N),IWA2(N),IWA3(N),IWA4(N) LOGICAL BWA(N) C ********** C C SUBROUTINE M7SLO C C GIVEN THE SPARSITY PATTERN OF AN M BY N MATRIX A, THIS C SUBROUTINE DETERMINES THE SMALLEST-LAST ORDERING OF THE C COLUMNS OF A. C C THE SMALLEST-LAST ORDERING IS DEFINED FOR THE LOOPLESS C GRAPH G WITH VERTICES A(J), J = 1,2,...,N WHERE A(J) IS THE C J-TH COLUMN OF A AND WITH EDGE (A(I),A(J)) IF AND ONLY IF C COLUMNS I AND J HAVE A NON-ZERO IN THE SAME ROW POSITION. C C THE SMALLEST-LAST ORDERING IS DETERMINED RECURSIVELY BY C LETTING LIST(K), K = N,...,1 BE A COLUMN WITH LEAST DEGREE C IN THE SUBGRAPH SPANNED BY THE UN-ORDERED COLUMNS. C C NOTE THAT THE VALUE OF M IS NOT NEEDED BY M7SLO AND IS C THEREFORE NOT PRESENT IN THE SUBROUTINE STATEMENT. C C THE SUBROUTINE STATEMENT IS C C SUBROUTINE M7SLO(N,INDROW,JPNTR,INDCOL,IPNTR,NDEG,LIST, C MAXCLQ,IWA1,IWA2,IWA3,IWA4,BWA) C C WHERE C C N IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER C OF COLUMNS OF A. C C INDROW IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE ROW C INDICES FOR THE NON-ZEROES IN THE MATRIX A. C C JPNTR IS AN INTEGER INPUT ARRAY OF LENGTH N + 1 WHICH C SPECIFIES THE LOCATIONS OF THE ROW INDICES IN INDROW. C THE ROW INDICES FOR COLUMN J ARE C C INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. C C NOTE THAT JPNTR(N+1)-1 IS THEN THE NUMBER OF NON-ZERO C ELEMENTS OF THE MATRIX A. C C INDCOL IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE C COLUMN INDICES FOR THE NON-ZEROES IN THE MATRIX A. C C IPNTR IS AN INTEGER INPUT ARRAY OF LENGTH M + 1 WHICH C SPECIFIES THE LOCATIONS OF THE COLUMN INDICES IN INDCOL. C THE COLUMN INDICES FOR ROW I ARE C C INDCOL(K), K = IPNTR(I),...,IPNTR(I+1)-1. C C NOTE THAT IPNTR(M+1)-1 IS THEN THE NUMBER OF NON-ZERO C ELEMENTS OF THE MATRIX A. C C NDEG IS AN INTEGER INPUT ARRAY OF LENGTH N WHICH SPECIFIES C THE DEGREE SEQUENCE. THE DEGREE OF THE J-TH COLUMN C OF A IS NDEG(J). C C LIST IS AN INTEGER OUTPUT ARRAY OF LENGTH N WHICH SPECIFIES C THE SMALLEST-LAST ORDERING OF THE COLUMNS OF A. THE J-TH C COLUMN IN THIS ORDER IS LIST(J). C C MAXCLQ IS AN INTEGER OUTPUT VARIABLE SET TO THE SIZE C OF THE LARGEST CLIQUE FOUND DURING THE ORDERING. C C IWA1,IWA2,IWA3, AND IWA4 ARE INTEGER WORK ARRAYS OF LENGTH N. C C BWA IS A LOGICAL WORK ARRAY OF LENGTH N. C C SUBPROGRAMS CALLED C C FORTRAN-SUPPLIED ... MIN0 C C ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. C THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE C C ********** INTEGER DEG,HEAD,IC,IP,IPL,IPU,IR,JCOL,JP,JPL,JPU, * L,MINDEG,NUMDEG,NUMORD C C INITIALIZATION BLOCK. C MINDEG = N DO 10 JP = 1, N IWA1(JP) = 0 BWA(JP) = .FALSE. LIST(JP) = NDEG(JP) MINDEG = MIN0(MINDEG,NDEG(JP)) 10 CONTINUE C C CREATE A DOUBLY-LINKED LIST TO ACCESS THE DEGREES OF THE C COLUMNS. THE POINTERS FOR THE LINKED LIST ARE AS FOLLOWS. C C EACH UN-ORDERED COLUMN JCOL IS IN A LIST (THE DEGREE C LIST) OF COLUMNS WITH THE SAME DEGREE. C C IWA1(NUMDEG+1) IS THE FIRST COLUMN IN THE NUMDEG LIST C UNLESS IWA1(NUMDEG+1) = 0. IN THIS CASE THERE ARE C NO COLUMNS IN THE NUMDEG LIST. C C IWA2(JCOL) IS THE COLUMN BEFORE JCOL IN THE DEGREE LIST C UNLESS IWA2(JCOL) = 0. IN THIS CASE JCOL IS THE FIRST C COLUMN IN THIS DEGREE LIST. C C IWA3(JCOL) IS THE COLUMN AFTER JCOL IN THE DEGREE LIST C UNLESS IWA3(JCOL) = 0. IN THIS CASE JCOL IS THE LAST C COLUMN IN THIS DEGREE LIST. C C IF JCOL IS AN UN-ORDERED COLUMN, THEN LIST(JCOL) IS THE C DEGREE OF JCOL IN THE GRAPH INDUCED BY THE UN-ORDERED C COLUMNS. IF JCOL IS AN ORDERED COLUMN, THEN LIST(JCOL) C IS THE SMALLEST-LAST ORDER OF COLUMN JCOL. C DO 20 JP = 1, N NUMDEG = NDEG(JP) HEAD = IWA1(NUMDEG+1) IWA1(NUMDEG+1) = JP IWA2(JP) = 0 IWA3(JP) = HEAD IF (HEAD .GT. 0) IWA2(HEAD) = JP 20 CONTINUE MAXCLQ = 0 NUMORD = N C C BEGINNING OF ITERATION LOOP. C 30 CONTINUE C C MARK THE SIZE OF THE LARGEST CLIQUE C FOUND DURING THE ORDERING. C IF (MINDEG + 1 .EQ. NUMORD .AND. MAXCLQ .EQ. 0) * MAXCLQ = NUMORD C C CHOOSE A COLUMN JCOL OF MINIMAL DEGREE MINDEG. C 40 CONTINUE JCOL = IWA1(MINDEG+1) IF (JCOL .GT. 0) GO TO 50 MINDEG = MINDEG + 1 GO TO 40 50 CONTINUE LIST(JCOL) = NUMORD NUMORD = NUMORD - 1 C C TERMINATION TEST. C IF (NUMORD .EQ. 0) GO TO 120 C C DELETE COLUMN JCOL FROM THE MINDEG LIST. C L = IWA3(JCOL) IWA1(MINDEG+1) = L IF (L .GT. 0) IWA2(L) = 0 C C FIND ALL COLUMNS ADJACENT TO COLUMN JCOL. C BWA(JCOL) = .TRUE. DEG = 0 C C DETERMINE ALL POSITIONS (IR,JCOL) WHICH CORRESPOND C TO NON-ZEROES IN THE MATRIX. C JPL = JPNTR(JCOL) JPU = JPNTR(JCOL+1) - 1 IF (JPU .LT. JPL) GO TO 90 DO 80 JP = JPL, JPU IR = INDROW(JP) C C FOR EACH ROW IR, DETERMINE ALL POSITIONS (IR,IC) C WHICH CORRESPOND TO NON-ZEROES IN THE MATRIX. C IPL = IPNTR(IR) IPU = IPNTR(IR+1) - 1 DO 70 IP = IPL, IPU IC = INDCOL(IP) C C ARRAY BWA MARKS COLUMNS WHICH ARE ADJACENT TO C COLUMN JCOL. ARRAY IWA4 RECORDS THE MARKED COLUMNS. C IF (BWA(IC)) GO TO 60 BWA(IC) = .TRUE. DEG = DEG + 1 IWA4(DEG) = IC 60 CONTINUE 70 CONTINUE 80 CONTINUE 90 CONTINUE C C UPDATE THE POINTERS TO THE CURRENT DEGREE LISTS. C IF (DEG .LT. 1) GO TO 110 DO 100 JP = 1, DEG IC = IWA4(JP) NUMDEG = LIST(IC) LIST(IC) = LIST(IC) - 1 MINDEG = MIN0(MINDEG,LIST(IC)) C C DELETE COLUMN IC FROM THE NUMDEG LIST. C L = IWA2(IC) IF (L .EQ. 0) IWA1(NUMDEG+1) = IWA3(IC) IF (L .GT. 0) IWA3(L) = IWA3(IC) L = IWA3(IC) IF (L .GT. 0) IWA2(L) = IWA2(IC) C C ADD COLUMN IC TO THE NUMDEG-1 LIST. C HEAD = IWA1(NUMDEG) IWA1(NUMDEG) = IC IWA2(IC) = 0 IWA3(IC) = HEAD IF (HEAD .GT. 0) IWA2(HEAD) = IC C C UN-MARK COLUMN IC IN THE ARRAY BWA. C BWA(IC) = .FALSE. 100 CONTINUE 110 CONTINUE C C END OF ITERATION LOOP. C GO TO 30 120 CONTINUE C C INVERT THE ARRAY LIST. C DO 130 JCOL = 1, N NUMORD = LIST(JCOL) IWA1(NUMORD) = JCOL 130 CONTINUE DO 140 JP = 1, N LIST(JP) = IWA1(JP) 140 CONTINUE RETURN C C LAST CARD OF SUBROUTINE M7SLO. C END .