SUBROUTINE I7DO(M,N,INDROW,JPNTR,INDCOL,IPNTR,NDEG,LIST, * MAXCLQ,IWA1,IWA2,IWA3,IWA4,BWA) INTEGER M,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 I7DO C C GIVEN THE SPARSITY PATTERN OF AN M BY N MATRIX A, THIS C SUBROUTINE DETERMINES AN INCIDENCE-DEGREE ORDERING OF THE C COLUMNS OF A. C C THE INCIDENCE-DEGREE 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 AT EACH STAGE OF I7DO, A COLUMN OF MAXIMAL INCIDENCE IS C CHOSEN AND ORDERED. IF JCOL IS AN UN-ORDERED COLUMN, THEN C THE INCIDENCE OF JCOL IS THE NUMBER OF ORDERED COLUMNS C ADJACENT TO JCOL IN THE GRAPH G. AMONG ALL THE COLUMNS OF C MAXIMAL INCIDENCE,I7DO CHOOSES A COLUMN OF MAXIMAL DEGREE. C C THE SUBROUTINE STATEMENT IS C C SUBROUTINE I7DO(M,N,INDROW,JPNTR,INDCOL,IPNTR,NDEG,LIST, C MAXCLQ,IWA1,IWA2,IWA3,IWA4,BWA) C C WHERE C C M IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER C OF ROWS OF A. 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 INCIDENCE-DEGREE 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 MINPACK-SUPPLIED ... N7MSRT C C FORTRAN-SUPPLIED ... MAX0 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,MAXINC, * MAXLST,NCOMP,NUMINC,NUMLST,NUMORD,NUMWGT C C SORT THE DEGREE SEQUENCE. C CALL N7MSRT(N,N-1,NDEG,-1,IWA4,IWA1,IWA3) C C INITIALIZATION BLOCK. C C CREATE A DOUBLY-LINKED LIST TO ACCESS THE INCIDENCES 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 INCIDENCE LIST) C OF COLUMNS WITH THE SAME INCIDENCE. C C IWA1(NUMINC+1) IS THE FIRST COLUMN IN THE NUMINC LIST C UNLESS IWA1(NUMINC+1) = 0. IN THIS CASE THERE ARE C NO COLUMNS IN THE NUMINC LIST. C C IWA2(JCOL) IS THE COLUMN BEFORE JCOL IN THE INCIDENCE LIST C UNLESS IWA2(JCOL) = 0. IN THIS CASE JCOL IS THE FIRST C COLUMN IN THIS INCIDENCE LIST. C C IWA3(JCOL) IS THE COLUMN AFTER JCOL IN THE INCIDENCE LIST C UNLESS IWA3(JCOL) = 0. IN THIS CASE JCOL IS THE LAST C COLUMN IN THIS INCIDENCE LIST. C C IF JCOL IS AN UN-ORDERED COLUMN, THEN LIST(JCOL) IS THE C INCIDENCE OF JCOL IN THE GRAPH. IF JCOL IS AN ORDERED COLUMN, C THEN LIST(JCOL) IS THE INCIDENCE-DEGREE ORDER OF COLUMN JCOL. C MAXINC = 0 DO 10 JP = 1, N LIST(JP) = 0 BWA(JP) = .FALSE. IWA1(JP) = 0 L = IWA4(JP) IF (JP .NE. 1) IWA2(L) = IWA4(JP-1) IF (JP .NE. N) IWA3(L) = IWA4(JP+1) 10 CONTINUE IWA1(1) = IWA4(1) L = IWA4(1) IWA2(L) = 0 L = IWA4(N) IWA3(L) = 0 C C DETERMINE THE MAXIMAL SEARCH LENGTH FOR THE LIST C OF COLUMNS OF MAXIMAL INCIDENCE. C MAXLST = 0 DO 20 IR = 1, M MAXLST = MAXLST + (IPNTR(IR+1) - IPNTR(IR))**2 20 CONTINUE MAXLST = MAXLST/N MAXCLQ = 1 C C BEGINNING OF ITERATION LOOP. C DO 140 NUMORD = 1, N C C CHOOSE A COLUMN JCOL OF MAXIMAL DEGREE AMONG THE C COLUMNS OF MAXIMAL INCIDENCE. C JP = IWA1(MAXINC+1) NUMLST = 1 NUMWGT = -1 30 CONTINUE IF (NDEG(JP) .LE. NUMWGT) GO TO 40 NUMWGT = NDEG(JP) JCOL = JP 40 CONTINUE JP = IWA3(JP) NUMLST = NUMLST + 1 IF (JP .GT. 0 .AND. NUMLST .LE. MAXLST) GO TO 30 LIST(JCOL) = NUMORD C C DELETE COLUMN JCOL FROM THE LIST OF COLUMNS OF C MAXIMAL INCIDENCE. C L = IWA2(JCOL) IF (L .EQ. 0) IWA1(MAXINC+1) = IWA3(JCOL) IF (L .GT. 0) IWA3(L) = IWA3(JCOL) L = IWA3(JCOL) IF (L .GT. 0) IWA2(L) = IWA2(JCOL) C C UPDATE THE SIZE OF THE LARGEST CLIQUE C FOUND DURING THE ORDERING. C IF (MAXINC .EQ. 0) NCOMP = 0 NCOMP = NCOMP + 1 IF (MAXINC + 1 .EQ. NCOMP) MAXCLQ = MAX0(MAXCLQ,NCOMP) C C UPDATE THE MAXIMAL INCIDENCE COUNT. C 50 CONTINUE IF (IWA1(MAXINC+1) .GT. 0) GO TO 60 MAXINC = MAXINC - 1 IF (MAXINC .GE. 0) GO TO 50 60 CONTINUE 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 100 DO 90 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 80 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 70 BWA(IC) = .TRUE. DEG = DEG + 1 IWA4(DEG) = IC 70 CONTINUE 80 CONTINUE 90 CONTINUE 100 CONTINUE C C UPDATE THE POINTERS TO THE INCIDENCE LISTS. C IF (DEG .LT. 1) GO TO 130 DO 120 JP = 1, DEG IC = IWA4(JP) IF (LIST(IC) .GT. 0) GO TO 110 NUMINC = -LIST(IC) + 1 LIST(IC) = -NUMINC MAXINC = MAX0(MAXINC,NUMINC) C C DELETE COLUMN IC FROM THE NUMINC-1 LIST. C L = IWA2(IC) IF (L .EQ. 0) IWA1(NUMINC) = 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 NUMINC LIST. C HEAD = IWA1(NUMINC+1) IWA1(NUMINC+1) = IC IWA2(IC) = 0 IWA3(IC) = HEAD IF (HEAD .GT. 0) IWA2(HEAD) = IC 110 CONTINUE C C UN-MARK COLUMN IC IN THE ARRAY BWA. C BWA(IC) = .FALSE. 120 CONTINUE 130 CONTINUE BWA(JCOL) = .FALSE. C C END OF ITERATION LOOP. C 140 CONTINUE C C INVERT THE ARRAY LIST. C DO 150 JCOL = 1, N NUMORD = LIST(JCOL) IWA1(NUMORD) = JCOL 150 CONTINUE DO 160 JP = 1, N LIST(JP) = IWA1(JP) 160 CONTINUE RETURN C C LAST CARD OF SUBROUTINE I7DO. C END