SUBROUTINE D7EGR(N,INDROW,JPNTR,INDCOL,IPNTR,NDEG,IWA,BWA)
INTEGER N
INTEGER INDROW(1),JPNTR(1),INDCOL(1),IPNTR(1),NDEG(N),IWA(N)
LOGICAL BWA(N)
C **********
C
C SUBROUTINE D7EGR
C
C GIVEN THE SPARSITY PATTERN OF AN M BY N MATRIX A,
C THIS SUBROUTINE DETERMINES THE DEGREE SEQUENCE FOR
C THE INTERSECTION GRAPH OF THE COLUMNS OF A.
C
C IN GRAPH-THEORY TERMINOLOGY, THE INTERSECTION GRAPH OF
C THE COLUMNS OF A IS THE LOOPLESS GRAPH G WITH VERTICES
C A(J), J = 1,2,...,N WHERE A(J) IS THE J-TH COLUMN OF A
C AND WITH EDGE (A(I),A(J)) IF AND ONLY IF COLUMNS I AND J
C HAVE A NON-ZERO IN THE SAME ROW POSITION.
C
C NOTE THAT THE VALUE OF M IS NOT NEEDED BY D7EGR AND IS
C THEREFORE NOT PRESENT IN THE SUBROUTINE STATEMENT.
C
C THE SUBROUTINE STATEMENT IS
C
C SUBROUTINE D7EGR(N,INDROW,JPNTR,INDCOL,IPNTR,NDEG,IWA,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 OUTPUT ARRAY OF LENGTH N WHICH
C SPECIFIES THE DEGREE SEQUENCE. THE DEGREE OF THE
C J-TH COLUMN OF A IS NDEG(J).
C
C IWA IS AN INTEGER WORK ARRAY OF LENGTH N.
C
C BWA IS A LOGICAL WORK ARRAY OF LENGTH N.
C
C ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982.
C THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE
C
C **********
INTEGER DEG,IC,IP,IPL,IPU,IR,JCOL,JP,JPL,JPU
C
C INITIALIZATION BLOCK.
C
DO 10 JP = 1, N
NDEG(JP) = 0
BWA(JP) = .FALSE.
10 CONTINUE
C
C COMPUTE THE DEGREE SEQUENCE BY DETERMINING THE CONTRIBUTIONS
C TO THE DEGREES FROM THE CURRENT(JCOL) COLUMN AND FURTHER
C COLUMNS WHICH HAVE NOT YET BEEN CONSIDERED.
C
IF (N .LT. 2) GO TO 90
DO 80 JCOL = 2, N
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 50
DO 40 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 30 IP = IPL, IPU
IC = INDCOL(IP)
C
C ARRAY BWA MARKS COLUMNS WHICH HAVE CONTRIBUTED TO
C THE DEGREE COUNT OF COLUMN JCOL. UPDATE THE DEGREE
C COUNTS OF THESE COLUMNS. ARRAY IWA RECORDS THE
C MARKED COLUMNS.
C
IF (BWA(IC)) GO TO 20
BWA(IC) = .TRUE.
NDEG(IC) = NDEG(IC) + 1
DEG = DEG + 1
IWA(DEG) = IC
20 CONTINUE
30 CONTINUE
40 CONTINUE
50 CONTINUE
C
C UN-MARK THE COLUMNS RECORDED BY IWA AND FINALIZE THE
C DEGREE COUNT OF COLUMN JCOL.
C
IF (DEG .LT. 1) GO TO 70
DO 60 JP = 1, DEG
IC = IWA(JP)
BWA(IC) = .FALSE.
60 CONTINUE
NDEG(JCOL) = NDEG(JCOL) + DEG
70 CONTINUE
80 CONTINUE
90 CONTINUE
RETURN
C
C LAST CARD OF SUBROUTINE D7EGR.
C
END
.