/*Translated by FOR_C, v3.4.2 (-), on 07/09/115 at 08:30:07 */ /*FOR_C Options SET: ftn=u io=c no=p op=aimnv s=dbov str=l x=f - prototypes */ #include #include "fcrt.h" #include "idsm.h" #include /* File: IDSM.for Graph manipulation subroutines * Copyright (c) 1996 California Institute of Technology, Pasadena, CA. * ALL RIGHTS RESERVED. * Based on Government Sponsored Research NAS7-03001. *>> 1992-04-07 CLL Changing BWA() from LOGICAL to INTEGER. *>> 1991-05-21 CLL @ JPL Changing (1) to (*) in declarations. *>> 1990-03-20 CLL @ JPL *>> 1990-02-21 CLL @ JPL * IDSM Graph manipulation subroutines from * Argonne National Laboratory (MINPACK Project) * used by the separable versions of the David Gay & Linda * Kaufman package for nonlinear least-squares. * Contains IDSM and 7 subrs needed by IDSM: * I7RTDT, IS7ETR, ID7EGR, M7SLO, M7SEQ, I7DO, N7MSRT * IDSM is called by the driver subroutines that need to compute * finite-difference approximations to partial derivatives. * These are [D/S]SFU and [D/S]SFB. * (The names IDSM, I7RTDT, IS7ETR, & ID7EGR were formerly * DSM, S7RTDT, S7ETR, & D7EGR. * These subrs do not use any real or double precision variables. * 1992-04-07 CLL Changing BWA() from LOGICAL to INTEGER because the * subrs that call IDSM pass it an integer array for BWA(). * */ void /*FUNCTION*/ idsm( long m, long n, long npairs, long indrow[], long indcol[], long ngrp[], long *maxgrp, long *mingrp, long *info, long ipntr[], long jpntr[], long iwa[], long liwa, long bwa[]) { long int i, ir, j, jp, jpl, jpu, k, maxclq, nnz, numgrp; /* OFFSET Vectors w/subscript range: 1 to dimension */ long *const Bwa = &bwa[0] - 1; long *const Indcol = &indcol[0] - 1; long *const Indrow = &indrow[0] - 1; long *const Ipntr = &ipntr[0] - 1; long *const Iwa = &iwa[0] - 1; long *const Jpntr = &jpntr[0] - 1; long *const Ngrp = &ngrp[0] - 1; /* end of OFFSET VECTORS */ /* ********** * * SUBROUTINE IDSM * * THE PURPOSE OF IDSM IS TO DETERMINE AN OPTIMAL OR NEAR- * OPTIMAL CONSISTENT PARTITION OF THE COLUMNS OF A SPARSE * M BY N MATRIX A. * * THE SPARSITY PATTERN OF THE MATRIX A IS SPECIFIED BY * THE ARRAYS INDROW AND INDCOL. ON INPUT THE INDICES * FOR THE NON-ZERO ELEMENTS OF A ARE * * INDROW(K),INDCOL(K), K = 1,2,...,NPAIRS. * * THE (INDROW,INDCOL) PAIRS MAY BE SPECIFIED IN ANY ORDER. * DUPLICATE INPUT PAIRS ARE PERMITTED, BUT THE SUBROUTINE * ELIMINATES THEM. * * THE SUBROUTINE PARTITIONS THE COLUMNS OF A INTO GROUPS * SUCH THAT COLUMNS IN THE SAME GROUP DO NOT HAVE A * NON-ZERO IN THE SAME ROW POSITION. A PARTITION OF THE * COLUMNS OF A WITH THIS PROPERTY IS CONSISTENT WITH THE * DIRECT DETERMINATION OF A. * * THE SUBROUTINE STATEMENT IS * * SUBROUTINE IDSM(M,N,NPAIRS,INDROW,INDCOL,NGRP,MAXGRP,MINGRP, * INFO,IPNTR,JPNTR,IWA,LIWA,BWA) * * WHERE * * M IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF ROWS OF A. * * N IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF COLUMNS OF A. * * NPAIRS IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE * NUMBER OF (INDROW,INDCOL) PAIRS USED TO DESCRIBE THE * SPARSITY PATTERN OF A. * * INDROW IS AN INTEGER ARRAY OF LENGTH NPAIRS. ON INPUT INDROW * MUST CONTAIN THE ROW INDICES OF THE NON-ZERO ELEMENTS OF A. * ON OUTPUT INDROW IS PERMUTED SO THAT THE CORRESPONDING * COLUMN INDICES ARE IN NON-DECREASING ORDER. THE COLUMN * INDICES CAN BE RECOVERED FROM THE ARRAY JPNTR. * * INDCOL IS AN INTEGER ARRAY OF LENGTH NPAIRS. ON INPUT INDCOL * MUST CONTAIN THE COLUMN INDICES OF THE NON-ZERO ELEMENTS OF * A. ON OUTPUT INDCOL IS PERMUTED SO THAT THE CORRESPONDING * ROW INDICES ARE IN NON-DECREASING ORDER. THE ROW INDICES * CAN BE RECOVERED FROM THE ARRAY IPNTR. * * NGRP IS AN INTEGER OUTPUT ARRAY OF LENGTH N WHICH SPECIFIES * THE PARTITION OF THE COLUMNS OF A. COLUMN JCOL BELONGS * TO GROUP NGRP(JCOL). * * MAXGRP IS AN INTEGER OUTPUT VARIABLE WHICH SPECIFIES THE * NUMBER OF GROUPS IN THE PARTITION OF THE COLUMNS OF A. * * MINGRP IS AN INTEGER OUTPUT VARIABLE WHICH SPECIFIES A LOWER * BOUND FOR THE NUMBER OF GROUPS IN ANY CONSISTENT PARTITION * OF THE COLUMNS OF A. * * INFO IS AN INTEGER OUTPUT VARIABLE SET AS FOLLOWS. FOR * NORMAL TERMINATION INFO = 1. IF M, N, OR NPAIRS IS NOT * POSITIVE OR LIWA IS LESS THAN MAX(M,6*N), THEN INFO = 0. * IF THE K-TH ELEMENT OF INDROW IS NOT AN INTEGER BETWEEN * 1 AND M OR THE K-TH ELEMENT OF INDCOL IS NOT AN INTEGER * BETWEEN 1 AND N, THEN INFO = -K. * * IPNTR IS AN INTEGER OUTPUT ARRAY OF LENGTH M + 1 WHICH * SPECIFIES THE LOCATIONS OF THE COLUMN INDICES IN INDCOL. * THE COLUMN INDICES FOR ROW I ARE * * INDCOL(K), K = IPNTR(I),...,IPNTR(I+1)-1. * * NOTE THAT IPNTR(M+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * JPNTR IS AN INTEGER OUTPUT ARRAY OF LENGTH N + 1 WHICH * SPECIFIES THE LOCATIONS OF THE ROW INDICES IN INDROW. * THE ROW INDICES FOR COLUMN J ARE * * INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. * * NOTE THAT JPNTR(N+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * IWA IS AN INTEGER WORK ARRAY OF LENGTH LIWA. * * LIWA IS A POSITIVE INTEGER INPUT VARIABLE NOT LESS THAN * MAX(M,6*N). * * BWA() is an INTEGER WORK ARRAY OF LENGTH N. * * SUBPROGRAMS CALLED * * MINPACK-SUPPLIED ...ID7EGR,I7DO,N7MSRT,M7SEQ,IS7ETR,M7SLO,I7RTDT * */ /* FORTRAN-SUPPLIED ... max * * ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. * THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE * * ********** */ /* CHECK THE INPUT DATA. * */ *info = 0; if (((m < 1 || n < 1) || npairs < 1) || liwa < max( m, 6*n )) goto L_130; for (k = 1; k <= npairs; k++) { *info = -k; if (((Indrow[k] < 1 || Indrow[k] > m) || Indcol[k] < 1) || Indcol[k] > n) goto L_130; } *info = 1; /* SORT THE DATA STRUCTURE BY COLUMNS. * */ i7rtdt( n, npairs, indrow, indcol, jpntr, &Iwa[1] ); /* COMPRESS THE DATA AND DETERMINE THE NUMBER OF * NON-ZERO ELEMENTS OF A. * */ for (i = 1; i <= m; i++) { Iwa[i] = 0; } nnz = 0; for (j = 1; j <= n; j++) { jpl = Jpntr[j]; jpu = Jpntr[j + 1] - 1; Jpntr[j] = nnz + 1; if (jpu < jpl) goto L_60; for (jp = jpl; jp <= jpu; jp++) { ir = Indrow[jp]; if (Iwa[ir] != 0) goto L_30; nnz += 1; Indrow[nnz] = ir; Iwa[ir] = 1; L_30: ; } jpl = Jpntr[j]; for (jp = jpl; jp <= nnz; jp++) { ir = Indrow[jp]; Iwa[ir] = 0; } L_60: ; } Jpntr[n + 1] = nnz + 1; /* EXTEND THE DATA STRUCTURE TO ROWS. * */ is7etr( m, n, indrow, jpntr, indcol, ipntr, &Iwa[1] ); /* DETERMINE A LOWER BOUND FOR THE NUMBER OF GROUPS. * */ *mingrp = 0; for (i = 1; i <= m; i++) { *mingrp = max( *mingrp, Ipntr[i + 1] - Ipntr[i] ); } /* DETERMINE THE DEGREE SEQUENCE FOR THE INTERSECTION * GRAPH OF THE COLUMNS OF A. * */ id7egr( n, indrow, jpntr, indcol, ipntr, &Iwa[5*n + 1], &Iwa[n + 1], bwa ); /* COLOR THE INTERSECTION GRAPH OF THE COLUMNS OF A * WITH THE SMALLEST-LAST (SL) ORDERING. * */ m7slo( n, indrow, jpntr, indcol, ipntr, &Iwa[5*n + 1], &Iwa[4*n + 1], &maxclq, &Iwa[1], &Iwa[n + 1], &Iwa[2*n + 1], &Iwa[3*n + 1], bwa ); m7seq( n, indrow, jpntr, indcol, ipntr, &Iwa[4*n + 1], ngrp, maxgrp, &Iwa[n + 1], bwa ); *mingrp = max( *mingrp, maxclq ); if (*maxgrp == *mingrp) goto L_130; /* COLOR THE INTERSECTION GRAPH OF THE COLUMNS OF A * WITH THE INCIDENCE-DEGREE (ID) ORDERING. * */ i7do( m, n, indrow, jpntr, indcol, ipntr, &Iwa[5*n + 1], &Iwa[4*n + 1], &maxclq, &Iwa[1], &Iwa[n + 1], &Iwa[2*n + 1], &Iwa[3*n + 1], bwa ); m7seq( n, indrow, jpntr, indcol, ipntr, &Iwa[4*n + 1], &Iwa[1], &numgrp, &Iwa[n + 1], bwa ); *mingrp = max( *mingrp, maxclq ); if (numgrp >= *maxgrp) goto L_100; *maxgrp = numgrp; for (j = 1; j <= n; j++) { Ngrp[j] = Iwa[j]; } if (*maxgrp == *mingrp) goto L_130; L_100: ; /* COLOR THE INTERSECTION GRAPH OF THE COLUMNS OF A * WITH THE LARGEST-FIRST (LF) ORDERING. * */ n7msrt( n, n - 1, &Iwa[5*n + 1], -1, &Iwa[4*n + 1], &Iwa[2*n + 1], &Iwa[n + 1] ); m7seq( n, indrow, jpntr, indcol, ipntr, &Iwa[4*n + 1], &Iwa[1], &numgrp, &Iwa[n + 1], bwa ); if (numgrp >= *maxgrp) goto L_120; *maxgrp = numgrp; for (j = 1; j <= n; j++) { Ngrp[j] = Iwa[j]; } L_120: ; /* EXIT FROM PROGRAM. * */ L_130: ; return; /* LAST CARD OF SUBROUTINE IDSM. * */ } /* end of function */ void /*FUNCTION*/ i7rtdt( long n, long nnz, long indrow[], long indcol[], long jpntr[], long iwa[]) { long int i, j, k, l; /* OFFSET Vectors w/subscript range: 1 to dimension */ long *const Indcol = &indcol[0] - 1; long *const Indrow = &indrow[0] - 1; long *const Iwa = &iwa[0] - 1; long *const Jpntr = &jpntr[0] - 1; /* end of OFFSET VECTORS */ /* ********** * * SUBROUTINE I7RTDT * * GIVEN THE NON-ZERO ELEMENTS OF AN M BY N MATRIX A IN * ARBITRARY ORDER AS SPECIFIED BY THEIR ROW AND COLUMN * INDICES, THIS SUBROUTINE PERMUTES THESE ELEMENTS SO * THAT THEIR COLUMN INDICES ARE IN NON-DECREASING ORDER. * * ON INPUT IT IS ASSUMED THAT THE ELEMENTS ARE SPECIFIED IN * * INDROW(K),INDCOL(K), K = 1,...,NNZ. * * ON OUTPUT THE ELEMENTS ARE PERMUTED SO THAT INDCOL IS * IN NON-DECREASING ORDER. IN ADDITION, THE ARRAY JPNTR * IS SET SO THAT THE ROW INDICES FOR COLUMN J ARE * * INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. * * NOTE THAT THE VALUE OF M IS NOT NEEDED BY I7RTDT AND IS * THEREFORE NOT PRESENT IN THE SUBROUTINE STATEMENT. * * THE SUBROUTINE STATEMENT IS * * SUBROUTINE I7RTDT(N,NNZ,INDROW,INDCOL,JPNTR,IWA) * * WHERE * * N IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF COLUMNS OF A. * * NNZ IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF NON-ZERO ELEMENTS OF A. * * INDROW IS AN INTEGER ARRAY OF LENGTH NNZ. ON INPUT INDROW * MUST CONTAIN THE ROW INDICES OF THE NON-ZERO ELEMENTS OF A. * ON OUTPUT INDROW IS PERMUTED SO THAT THE CORRESPONDING * COLUMN INDICES OF INDCOL ARE IN NON-DECREASING ORDER. * * INDCOL IS AN INTEGER ARRAY OF LENGTH NNZ. ON INPUT INDCOL * MUST CONTAIN THE COLUMN INDICES OF THE NON-ZERO ELEMENTS * OF A. ON OUTPUT INDCOL IS PERMUTED SO THAT THESE INDICES * ARE IN NON-DECREASING ORDER. * * JPNTR IS AN INTEGER OUTPUT ARRAY OF LENGTH N + 1 WHICH * SPECIFIES THE LOCATIONS OF THE ROW INDICES IN THE OUTPUT * INDROW. THE ROW INDICES FOR COLUMN J ARE * * INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. * * NOTE THAT JPNTR(1) IS SET TO 1 AND THAT JPNTR(N+1)-1 * IS THEN NNZ. * * IWA IS AN INTEGER WORK ARRAY OF LENGTH N. * * SUBPROGRAMS CALLED * * FORTRAN-SUPPLIED ... MAX * * ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. * THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE * * ********** */ /* DETERMINE THE NUMBER OF NON-ZEROES IN THE COLUMNS. * */ for (j = 1; j <= n; j++) { Iwa[j] = 0; } for (k = 1; k <= nnz; k++) { j = Indcol[k]; Iwa[j] += 1; } /* SET POINTERS TO THE START OF THE COLUMNS IN INDROW. * */ Jpntr[1] = 1; for (j = 1; j <= n; j++) { Jpntr[j + 1] = Jpntr[j] + Iwa[j]; Iwa[j] = Jpntr[j]; } k = 1; /* BEGIN IN-PLACE SORT. * */ L_40: ; j = Indcol[k]; if (k < Jpntr[j] || k >= Jpntr[j + 1]) goto L_50; /* CURRENT ELEMENT IS IN POSITION. NOW EXAMINE THE * NEXT ELEMENT OR THE FIRST UN-SORTED ELEMENT IN * THE J-TH GROUP. * */ k = max( k + 1, Iwa[j] ); goto L_60; L_50: ; /* CURRENT ELEMENT IS NOT IN POSITION. PLACE ELEMENT * IN POSITION AND MAKE THE DISPLACED ELEMENT THE * CURRENT ELEMENT. * */ l = Iwa[j]; Iwa[j] += 1; i = Indrow[k]; Indrow[k] = Indrow[l]; Indcol[k] = Indcol[l]; Indrow[l] = i; Indcol[l] = j; L_60: ; if (k <= nnz) goto L_40; return; /* LAST CARD OF SUBROUTINE I7RTDT. * */ } /* end of function */ void /*FUNCTION*/ is7etr( long m, long n, long indrow[], long jpntr[], long indcol[], long ipntr[], long iwa[]) { long int ir, jcol, jp, jpl, jpu, l, nnz; /* OFFSET Vectors w/subscript range: 1 to dimension */ long *const Indcol = &indcol[0] - 1; long *const Indrow = &indrow[0] - 1; long *const Ipntr = &ipntr[0] - 1; long *const Iwa = &iwa[0] - 1; long *const Jpntr = &jpntr[0] - 1; /* end of OFFSET VECTORS */ /* ********** * * SUBROUTINE IS7ETR * * GIVEN A COLUMN-ORIENTED DEFINITION OF THE SPARSITY PATTERN * OF AN M BY N MATRIX A, THIS SUBROUTINE DETERMINES A * ROW-ORIENTED DEFINITION OF THE SPARSITY PATTERN OF A. * * ON INPUT THE COLUMN-ORIENTED DEFINITION IS SPECIFIED BY * THE ARRAYS INDROW AND JPNTR. ON OUTPUT THE ROW-ORIENTED * DEFINITION IS SPECIFIED BY THE ARRAYS INDCOL AND IPNTR. * * THE SUBROUTINE STATEMENT IS * * SUBROUTINE IS7ETR(M,N,INDROW,JPNTR,INDCOL,IPNTR,IWA) * * WHERE * * M IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF ROWS OF A. * * N IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF COLUMNS OF A. * * INDROW IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE ROW * INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * JPNTR IS AN INTEGER INPUT ARRAY OF LENGTH N + 1 WHICH * SPECIFIES THE LOCATIONS OF THE ROW INDICES IN INDROW. * THE ROW INDICES FOR COLUMN J ARE * * INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. * * NOTE THAT JPNTR(N+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * INDCOL IS AN INTEGER OUTPUT ARRAY WHICH CONTAINS THE * COLUMN INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * IPNTR IS AN INTEGER OUTPUT ARRAY OF LENGTH M + 1 WHICH * SPECIFIES THE LOCATIONS OF THE COLUMN INDICES IN INDCOL. * THE COLUMN INDICES FOR ROW I ARE * * INDCOL(K), K = IPNTR(I),...,IPNTR(I+1)-1. * * NOTE THAT IPNTR(1) IS SET TO 1 AND THAT IPNTR(M+1)-1 IS * THEN THE NUMBER OF NON-ZERO ELEMENTS OF THE MATRIX A. * * IWA IS AN INTEGER WORK ARRAY OF LENGTH M. * * ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. * THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE * * ********** */ /* DETERMINE THE NUMBER OF NON-ZEROES IN THE ROWS. * */ for (ir = 1; ir <= m; ir++) { Iwa[ir] = 0; } nnz = Jpntr[n + 1] - 1; for (jp = 1; jp <= nnz; jp++) { ir = Indrow[jp]; Iwa[ir] += 1; } /* SET POINTERS TO THE START OF THE ROWS IN INDCOL. * */ Ipntr[1] = 1; for (ir = 1; ir <= m; ir++) { Ipntr[ir + 1] = Ipntr[ir] + Iwa[ir]; Iwa[ir] = Ipntr[ir]; } /* FILL INDCOL. * */ for (jcol = 1; jcol <= n; jcol++) { jpl = Jpntr[jcol]; jpu = Jpntr[jcol + 1] - 1; if (jpu < jpl) goto L_50; for (jp = jpl; jp <= jpu; jp++) { ir = Indrow[jp]; l = Iwa[ir]; Indcol[l] = jcol; Iwa[ir] += 1; } L_50: ; } return; /* LAST CARD OF SUBROUTINE IS7ETR. * */ } /* end of function */ /* PARAMETER translations */ #define IFALSE 0 #define ITRUE 1 /* end of PARAMETER translations */ void /*FUNCTION*/ id7egr( long n, long indrow[], long jpntr[], long indcol[], long ipntr[], long ndeg[], long iwa[], long bwa[]) { long int deg, ic, ip, ipl, ipu, ir, jcol, jp, jpl, jpu; /* OFFSET Vectors w/subscript range: 1 to dimension */ long *const Bwa = &bwa[0] - 1; long *const Indcol = &indcol[0] - 1; long *const Indrow = &indrow[0] - 1; long *const Ipntr = &ipntr[0] - 1; long *const Iwa = &iwa[0] - 1; long *const Jpntr = &jpntr[0] - 1; long *const Ndeg = &ndeg[0] - 1; /* end of OFFSET VECTORS */ /* ********** * * SUBROUTINE ID7EGR * * GIVEN THE SPARSITY PATTERN OF AN M BY N MATRIX A, * THIS SUBROUTINE DETERMINES THE DEGREE SEQUENCE FOR * THE INTERSECTION GRAPH OF THE COLUMNS OF A. * * IN GRAPH-THEORY TERMINOLOGY, THE INTERSECTION GRAPH OF * THE COLUMNS OF A IS THE LOOPLESS GRAPH G WITH VERTICES * A(J), J = 1,2,...,N WHERE A(J) IS THE J-TH COLUMN OF A * AND WITH EDGE (A(I),A(J)) IF AND ONLY IF COLUMNS I AND J * HAVE A NON-ZERO IN THE SAME ROW POSITION. * * NOTE THAT THE VALUE OF M IS NOT NEEDED BY ID7EGR AND IS * THEREFORE NOT PRESENT IN THE SUBROUTINE STATEMENT. * * THE SUBROUTINE STATEMENT IS * * SUBROUTINE ID7EGR(N,INDROW,JPNTR,INDCOL,IPNTR,NDEG,IWA,BWA) * * WHERE * * N IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF COLUMNS OF A. * * INDROW IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE ROW * INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * JPNTR IS AN INTEGER INPUT ARRAY OF LENGTH N + 1 WHICH * SPECIFIES THE LOCATIONS OF THE ROW INDICES IN INDROW. * THE ROW INDICES FOR COLUMN J ARE * * INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. * * NOTE THAT JPNTR(N+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * INDCOL IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE * COLUMN INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * IPNTR IS AN INTEGER INPUT ARRAY OF LENGTH M + 1 WHICH * SPECIFIES THE LOCATIONS OF THE COLUMN INDICES IN INDCOL. * THE COLUMN INDICES FOR ROW I ARE * * INDCOL(K), K = IPNTR(I),...,IPNTR(I+1)-1. * * NOTE THAT IPNTR(M+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * NDEG IS AN INTEGER OUTPUT ARRAY OF LENGTH N WHICH * SPECIFIES THE DEGREE SEQUENCE. THE DEGREE OF THE * J-TH COLUMN OF A IS NDEG(J). * * IWA IS AN INTEGER WORK ARRAY OF LENGTH N. * * BWA() is an INTEGER WORK ARRAY OF LENGTH N. * * ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. * THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE * * ********** */ /* INITIALIZATION BLOCK. * */ for (jp = 1; jp <= n; jp++) { Ndeg[jp] = 0; Bwa[jp] = IFALSE; } /* COMPUTE THE DEGREE SEQUENCE BY DETERMINING THE CONTRIBUTIONS * TO THE DEGREES FROM THE CURRENT(JCOL) COLUMN AND FURTHER * COLUMNS WHICH HAVE NOT YET BEEN CONSIDERED. * */ if (n < 2) goto L_90; for (jcol = 2; jcol <= n; jcol++) { Bwa[jcol] = ITRUE; deg = 0; /* DETERMINE ALL POSITIONS (IR,JCOL) WHICH CORRESPOND * TO NON-ZEROES IN THE MATRIX. * */ jpl = Jpntr[jcol]; jpu = Jpntr[jcol + 1] - 1; if (jpu < jpl) goto L_50; for (jp = jpl; jp <= jpu; jp++) { ir = Indrow[jp]; /* FOR EACH ROW IR, DETERMINE ALL POSITIONS (IR,IC) * WHICH CORRESPOND TO NON-ZEROES IN THE MATRIX. * */ ipl = Ipntr[ir]; ipu = Ipntr[ir + 1] - 1; for (ip = ipl; ip <= ipu; ip++) { ic = Indcol[ip]; /* Array BWA() MARKS COLUMNS WHICH HAVE CONTRIBUTED TO * THE DEGREE COUNT OF COLUMN JCOL. UPDATE THE DEGREE * COUNTS OF THESE COLUMNS. ARRAY IWA RECORDS THE * MARKED COLUMNS. * */ if (Bwa[ic] == ITRUE) goto L_20; Bwa[ic] = ITRUE; Ndeg[ic] += 1; deg += 1; Iwa[deg] = ic; L_20: ; } } L_50: ; /* UN-MARK THE COLUMNS RECORDED BY IWA AND FINALIZE THE * DEGREE COUNT OF COLUMN JCOL. * */ if (deg < 1) goto L_70; for (jp = 1; jp <= deg; jp++) { ic = Iwa[jp]; Bwa[ic] = IFALSE; } Ndeg[jcol] += deg; L_70: ; } L_90: ; return; /* LAST CARD OF SUBROUTINE ID7EGR. * */ } /* end of function */ void /*FUNCTION*/ m7slo( long n, long indrow[], long jpntr[], long indcol[], long ipntr[], long ndeg[], long list[], long *maxclq, long iwa1[], long iwa2[], long iwa3[], long iwa4[], long bwa[]) { long int deg, head, ic, ip, ipl, ipu, ir, jcol, jp, jpl, jpu, l, mindeg, numdeg, numord; /* OFFSET Vectors w/subscript range: 1 to dimension */ long *const Bwa = &bwa[0] - 1; long *const Indcol = &indcol[0] - 1; long *const Indrow = &indrow[0] - 1; long *const Ipntr = &ipntr[0] - 1; long *const Iwa1 = &iwa1[0] - 1; long *const Iwa2 = &iwa2[0] - 1; long *const Iwa3 = &iwa3[0] - 1; long *const Iwa4 = &iwa4[0] - 1; long *const Jpntr = &jpntr[0] - 1; long *const List = &list[0] - 1; long *const Ndeg = &ndeg[0] - 1; /* end of OFFSET VECTORS */ /* ********** * * SUBROUTINE M7SLO * * GIVEN THE SPARSITY PATTERN OF AN M BY N MATRIX A, THIS * SUBROUTINE DETERMINES THE SMALLEST-LAST ORDERING OF THE * COLUMNS OF A. * * THE SMALLEST-LAST ORDERING IS DEFINED FOR THE LOOPLESS * GRAPH G WITH VERTICES A(J), J = 1,2,...,N WHERE A(J) IS THE * J-TH COLUMN OF A AND WITH EDGE (A(I),A(J)) IF AND ONLY IF * COLUMNS I AND J HAVE A NON-ZERO IN THE SAME ROW POSITION. * * THE SMALLEST-LAST ORDERING IS DETERMINED RECURSIVELY BY * LETTING LIST(K), K = N,...,1 BE A COLUMN WITH LEAST DEGREE * IN THE SUBGRAPH SPANNED BY THE UN-ORDERED COLUMNS. * * NOTE THAT THE VALUE OF M IS NOT NEEDED BY M7SLO AND IS * THEREFORE NOT PRESENT IN THE SUBROUTINE STATEMENT. * * THE SUBROUTINE STATEMENT IS * * SUBROUTINE M7SLO(N,INDROW,JPNTR,INDCOL,IPNTR,NDEG,LIST, * MAXCLQ,IWA1,IWA2,IWA3,IWA4,BWA) * * WHERE * * N IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF COLUMNS OF A. * * INDROW IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE ROW * INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * JPNTR IS AN INTEGER INPUT ARRAY OF LENGTH N + 1 WHICH * SPECIFIES THE LOCATIONS OF THE ROW INDICES IN INDROW. * THE ROW INDICES FOR COLUMN J ARE * * INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. * * NOTE THAT JPNTR(N+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * INDCOL IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE * COLUMN INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * IPNTR IS AN INTEGER INPUT ARRAY OF LENGTH M + 1 WHICH * SPECIFIES THE LOCATIONS OF THE COLUMN INDICES IN INDCOL. * THE COLUMN INDICES FOR ROW I ARE * * INDCOL(K), K = IPNTR(I),...,IPNTR(I+1)-1. * * NOTE THAT IPNTR(M+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * NDEG IS AN INTEGER INPUT ARRAY OF LENGTH N WHICH SPECIFIES * THE DEGREE SEQUENCE. THE DEGREE OF THE J-TH COLUMN * OF A IS NDEG(J). * * LIST IS AN INTEGER OUTPUT ARRAY OF LENGTH N WHICH SPECIFIES * THE SMALLEST-LAST ORDERING OF THE COLUMNS OF A. THE J-TH * COLUMN IN THIS ORDER IS LIST(J). * * MAXCLQ IS AN INTEGER OUTPUT VARIABLE SET TO THE SIZE * OF THE LARGEST CLIQUE FOUND DURING THE ORDERING. * * IWA1,IWA2,IWA3, AND IWA4 ARE INTEGER WORK ARRAYS OF LENGTH N. * * BWA() is an INTEGER WORK ARRAY OF LENGTH N. * * SUBPROGRAMS CALLED * * FORTRAN-SUPPLIED ... min * * ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. * THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE * * ********** */ /* INITIALIZATION BLOCK. * */ mindeg = n; for (jp = 1; jp <= n; jp++) { Iwa1[jp] = 0; Bwa[jp] = IFALSE; List[jp] = Ndeg[jp]; mindeg = min( mindeg, Ndeg[jp] ); } /* CREATE A DOUBLY-LINKED LIST TO ACCESS THE DEGREES OF THE * COLUMNS. THE POINTERS FOR THE LINKED LIST ARE AS FOLLOWS. * * EACH UN-ORDERED COLUMN JCOL IS IN A LIST (THE DEGREE * LIST) OF COLUMNS WITH THE SAME DEGREE. * * IWA1(NUMDEG+1) IS THE FIRST COLUMN IN THE NUMDEG LIST * UNLESS IWA1(NUMDEG+1) = 0. IN THIS CASE THERE ARE * NO COLUMNS IN THE NUMDEG LIST. * * IWA2(JCOL) IS THE COLUMN BEFORE JCOL IN THE DEGREE LIST * UNLESS IWA2(JCOL) = 0. IN THIS CASE JCOL IS THE FIRST * COLUMN IN THIS DEGREE LIST. * * IWA3(JCOL) IS THE COLUMN AFTER JCOL IN THE DEGREE LIST * UNLESS IWA3(JCOL) = 0. IN THIS CASE JCOL IS THE LAST * COLUMN IN THIS DEGREE LIST. * * IF JCOL IS AN UN-ORDERED COLUMN, THEN LIST(JCOL) IS THE * DEGREE OF JCOL IN THE GRAPH INDUCED BY THE UN-ORDERED * COLUMNS. IF JCOL IS AN ORDERED COLUMN, THEN LIST(JCOL) * IS THE SMALLEST-LAST ORDER OF COLUMN JCOL. * */ for (jp = 1; jp <= n; jp++) { numdeg = Ndeg[jp]; head = Iwa1[numdeg + 1]; Iwa1[numdeg + 1] = jp; Iwa2[jp] = 0; Iwa3[jp] = head; if (head > 0) Iwa2[head] = jp; } *maxclq = 0; numord = n; /* BEGINNING OF ITERATION LOOP. * */ L_30: ; /* MARK THE SIZE OF THE LARGEST CLIQUE * FOUND DURING THE ORDERING. * */ if (mindeg + 1 == numord && *maxclq == 0) *maxclq = numord; /* CHOOSE A COLUMN JCOL OF MINIMAL DEGREE MINDEG. * */ L_40: ; jcol = Iwa1[mindeg + 1]; if (jcol > 0) goto L_50; mindeg += 1; goto L_40; L_50: ; List[jcol] = numord; numord -= 1; /* TERMINATION TEST. * */ if (numord == 0) goto L_120; /* DELETE COLUMN JCOL FROM THE MINDEG LIST. * */ l = Iwa3[jcol]; Iwa1[mindeg + 1] = l; if (l > 0) Iwa2[l] = 0; /* FIND ALL COLUMNS ADJACENT TO COLUMN JCOL. * */ Bwa[jcol] = ITRUE; deg = 0; /* DETERMINE ALL POSITIONS (IR,JCOL) WHICH CORRESPOND * TO NON-ZEROES IN THE MATRIX. * */ jpl = Jpntr[jcol]; jpu = Jpntr[jcol + 1] - 1; if (jpu < jpl) goto L_90; for (jp = jpl; jp <= jpu; jp++) { ir = Indrow[jp]; /* FOR EACH ROW IR, DETERMINE ALL POSITIONS (IR,IC) * WHICH CORRESPOND TO NON-ZEROES IN THE MATRIX. * */ ipl = Ipntr[ir]; ipu = Ipntr[ir + 1] - 1; for (ip = ipl; ip <= ipu; ip++) { ic = Indcol[ip]; /* Array BWA() MARKS COLUMNS WHICH ARE ADJACENT TO * COLUMN JCOL. ARRAY IWA4 RECORDS THE MARKED COLUMNS. * */ if (Bwa[ic] == ITRUE) goto L_60; Bwa[ic] = ITRUE; deg += 1; Iwa4[deg] = ic; L_60: ; } } L_90: ; /* UPDATE THE POINTERS TO THE CURRENT DEGREE LISTS. * */ if (deg < 1) goto L_110; for (jp = 1; jp <= deg; jp++) { ic = Iwa4[jp]; numdeg = List[ic]; List[ic] -= 1; mindeg = min( mindeg, List[ic] ); /* DELETE COLUMN IC FROM THE NUMDEG LIST. * */ l = Iwa2[ic]; if (l == 0) Iwa1[numdeg + 1] = Iwa3[ic]; if (l > 0) Iwa3[l] = Iwa3[ic]; l = Iwa3[ic]; if (l > 0) Iwa2[l] = Iwa2[ic]; /* ADD COLUMN IC TO THE NUMDEG-1 LIST. * */ head = Iwa1[numdeg]; Iwa1[numdeg] = ic; Iwa2[ic] = 0; Iwa3[ic] = head; if (head > 0) Iwa2[head] = ic; /* UN-MARK COLUMN IC IN THE ARRAY BWA. * */ Bwa[ic] = IFALSE; } L_110: ; /* END OF ITERATION LOOP. * */ goto L_30; L_120: ; /* INVERT THE ARRAY LIST. * */ for (jcol = 1; jcol <= n; jcol++) { numord = List[jcol]; Iwa1[numord] = jcol; } for (jp = 1; jp <= n; jp++) { List[jp] = Iwa1[jp]; } return; /* LAST CARD OF SUBROUTINE M7SLO. * */ } /* end of function */ void /*FUNCTION*/ m7seq( long n, long indrow[], long jpntr[], long indcol[], long ipntr[], long list[], long ngrp[], long *maxgrp, long iwa[], long bwa[]) { long int deg, ic, ip, ipl, ipu, ir, j, jcol, jp, jpl, jpu, l, numgrp; /* OFFSET Vectors w/subscript range: 1 to dimension */ long *const Bwa = &bwa[0] - 1; long *const Indcol = &indcol[0] - 1; long *const Indrow = &indrow[0] - 1; long *const Ipntr = &ipntr[0] - 1; long *const Iwa = &iwa[0] - 1; long *const Jpntr = &jpntr[0] - 1; long *const List = &list[0] - 1; long *const Ngrp = &ngrp[0] - 1; /* end of OFFSET VECTORS */ /* ********** * * SUBROUTINE M7SEQ * * GIVEN THE SPARSITY PATTERN OF AN M BY N MATRIX A, THIS * SUBROUTINE DETERMINES A CONSISTENT PARTITION OF THE * COLUMNS OF A BY A SEQUENTIAL ALGORITHM. * * A CONSISTENT PARTITION IS DEFINED IN TERMS OF THE LOOPLESS * GRAPH G WITH VERTICES A(J), J = 1,2,...,N WHERE A(J) IS THE * J-TH COLUMN OF A AND WITH EDGE (A(I),A(J)) IF AND ONLY IF * COLUMNS I AND J HAVE A NON-ZERO IN THE SAME ROW POSITION. * * A PARTITION OF THE COLUMNS OF A INTO GROUPS IS CONSISTENT * IF THE COLUMNS IN ANY GROUP ARE NOT ADJACENT IN THE GRAPH G. * IN GRAPH-THEORY TERMINOLOGY, A CONSISTENT PARTITION OF THE * COLUMNS OF A CORRESPONDS TO A COLORING OF THE GRAPH G. * * THE SUBROUTINE EXAMINES THE COLUMNS IN THE ORDER SPECIFIED * BY THE ARRAY LIST, AND ASSIGNS THE CURRENT COLUMN TO THE * GROUP WITH THE SMALLEST POSSIBLE NUMBER. * * NOTE THAT THE VALUE OF M IS NOT NEEDED BY M7SEQ AND IS * THEREFORE NOT PRESENT IN THE SUBROUTINE STATEMENT. * * THE SUBROUTINE STATEMENT IS * * SUBROUTINE M7SEQ(N,INDROW,JPNTR,INDCOL,IPNTR,LIST,NGRP,MAXGRP, * IWA,BWA) * * WHERE * * N IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF COLUMNS OF A. * * INDROW IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE ROW * INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * JPNTR IS AN INTEGER INPUT ARRAY OF LENGTH N + 1 WHICH * SPECIFIES THE LOCATIONS OF THE ROW INDICES IN INDROW. * THE ROW INDICES FOR COLUMN J ARE * * INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. * * NOTE THAT JPNTR(N+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * INDCOL IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE * COLUMN INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * IPNTR IS AN INTEGER INPUT ARRAY OF LENGTH M + 1 WHICH * SPECIFIES THE LOCATIONS OF THE COLUMN INDICES IN INDCOL. * THE COLUMN INDICES FOR ROW I ARE * * INDCOL(K), K = IPNTR(I),...,IPNTR(I+1)-1. * * NOTE THAT IPNTR(M+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * LIST IS AN INTEGER INPUT ARRAY OF LENGTH N WHICH SPECIFIES * THE ORDER TO BE USED BY THE SEQUENTIAL ALGORITHM. * THE J-TH COLUMN IN THIS ORDER IS LIST(J). * * NGRP IS AN INTEGER OUTPUT ARRAY OF LENGTH N WHICH SPECIFIES * THE PARTITION OF THE COLUMNS OF A. COLUMN JCOL BELONGS * TO GROUP NGRP(JCOL). * * MAXGRP IS AN INTEGER OUTPUT VARIABLE WHICH SPECIFIES THE * NUMBER OF GROUPS IN THE PARTITION OF THE COLUMNS OF A. * * IWA IS AN INTEGER WORK ARRAY OF LENGTH N. * * BWA() is an INTEGER WORK ARRAY OF LENGTH N. * * ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. * THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE * * ********** */ /* INITIALIZATION BLOCK. * */ *maxgrp = 0; for (jp = 1; jp <= n; jp++) { Ngrp[jp] = n; Bwa[jp] = IFALSE; } Bwa[n] = ITRUE; /* BEGINNING OF ITERATION LOOP. * */ for (j = 1; j <= n; j++) { jcol = List[j]; /* FIND ALL COLUMNS ADJACENT TO COLUMN JCOL. * */ deg = 0; /* DETERMINE ALL POSITIONS (IR,JCOL) WHICH CORRESPOND * TO NON-ZEROES IN THE MATRIX. * */ jpl = Jpntr[jcol]; jpu = Jpntr[jcol + 1] - 1; if (jpu < jpl) goto L_50; for (jp = jpl; jp <= jpu; jp++) { ir = Indrow[jp]; /* FOR EACH ROW IR, DETERMINE ALL POSITIONS (IR,IC) * WHICH CORRESPOND TO NON-ZEROES IN THE MATRIX. * */ ipl = Ipntr[ir]; ipu = Ipntr[ir + 1] - 1; for (ip = ipl; ip <= ipu; ip++) { ic = Indcol[ip]; l = Ngrp[ic]; /* Array BWA() MARKS THE GROUP NUMBERS OF THE * COLUMNS WHICH ARE ADJACENT TO COLUMN JCOL. * ARRAY IWA RECORDS THE MARKED GROUP NUMBERS. * */ if (Bwa[l] == ITRUE) goto L_20; Bwa[l] = ITRUE; deg += 1; Iwa[deg] = l; L_20: ; } } L_50: ; /* ASSIGN THE SMALLEST UN-MARKED GROUP NUMBER TO JCOL. * */ for (jp = 1; jp <= n; jp++) { numgrp = jp; if (Bwa[jp] == IFALSE) goto L_70; } L_70: ; Ngrp[jcol] = numgrp; *maxgrp = max( *maxgrp, numgrp ); /* UN-MARK THE GROUP NUMBERS. * */ if (deg < 1) goto L_90; for (jp = 1; jp <= deg; jp++) { l = Iwa[jp]; Bwa[l] = IFALSE; } L_90: ; } /* END OF ITERATION LOOP. * */ return; /* LAST CARD OF SUBROUTINE M7SEQ. * */ } /* end of function */ void /*FUNCTION*/ i7do( long m, long n, long indrow[], long jpntr[], long indcol[], long ipntr[], long ndeg[], long list[], long *maxclq, long iwa1[], long iwa2[], long iwa3[], long iwa4[], long bwa[]) { long int deg, head, ic, ip, ipl, ipu, ir, jcol, jp, jpl, jpu, l, maxinc, maxlst, ncomp, numinc, numlst, numord, numwgt; /* OFFSET Vectors w/subscript range: 1 to dimension */ long *const Bwa = &bwa[0] - 1; long *const Indcol = &indcol[0] - 1; long *const Indrow = &indrow[0] - 1; long *const Ipntr = &ipntr[0] - 1; long *const Iwa1 = &iwa1[0] - 1; long *const Iwa2 = &iwa2[0] - 1; long *const Iwa3 = &iwa3[0] - 1; long *const Iwa4 = &iwa4[0] - 1; long *const Jpntr = &jpntr[0] - 1; long *const List = &list[0] - 1; long *const Ndeg = &ndeg[0] - 1; /* end of OFFSET VECTORS */ /* ********** * * SUBROUTINE I7DO * * GIVEN THE SPARSITY PATTERN OF AN M BY N MATRIX A, THIS * SUBROUTINE DETERMINES AN INCIDENCE-DEGREE ORDERING OF THE * COLUMNS OF A. * * THE INCIDENCE-DEGREE ORDERING IS DEFINED FOR THE LOOPLESS * GRAPH G WITH VERTICES A(J), J = 1,2,...,N WHERE A(J) IS THE * J-TH COLUMN OF A AND WITH EDGE (A(I),A(J)) IF AND ONLY IF * COLUMNS I AND J HAVE A NON-ZERO IN THE SAME ROW POSITION. * * AT EACH STAGE OF I7DO, A COLUMN OF MAXIMAL INCIDENCE IS * CHOSEN AND ORDERED. IF JCOL IS AN UN-ORDERED COLUMN, THEN * THE INCIDENCE OF JCOL IS THE NUMBER OF ORDERED COLUMNS * ADJACENT TO JCOL IN THE GRAPH G. AMONG ALL THE COLUMNS OF * MAXIMAL INCIDENCE,I7DO CHOOSES A COLUMN OF MAXIMAL DEGREE. * * THE SUBROUTINE STATEMENT IS * * SUBROUTINE I7DO(M,N,INDROW,JPNTR,INDCOL,IPNTR,NDEG,LIST, * MAXCLQ,IWA1,IWA2,IWA3,IWA4,BWA) * * WHERE * * M IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF ROWS OF A. * * N IS A POSITIVE INTEGER INPUT VARIABLE SET TO THE NUMBER * OF COLUMNS OF A. * * INDROW IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE ROW * INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * JPNTR IS AN INTEGER INPUT ARRAY OF LENGTH N + 1 WHICH * SPECIFIES THE LOCATIONS OF THE ROW INDICES IN INDROW. * THE ROW INDICES FOR COLUMN J ARE * * INDROW(K), K = JPNTR(J),...,JPNTR(J+1)-1. * * NOTE THAT JPNTR(N+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * INDCOL IS AN INTEGER INPUT ARRAY WHICH CONTAINS THE * COLUMN INDICES FOR THE NON-ZEROES IN THE MATRIX A. * * IPNTR IS AN INTEGER INPUT ARRAY OF LENGTH M + 1 WHICH * SPECIFIES THE LOCATIONS OF THE COLUMN INDICES IN INDCOL. * THE COLUMN INDICES FOR ROW I ARE * * INDCOL(K), K = IPNTR(I),...,IPNTR(I+1)-1. * * NOTE THAT IPNTR(M+1)-1 IS THEN THE NUMBER OF NON-ZERO * ELEMENTS OF THE MATRIX A. * * NDEG IS AN INTEGER INPUT ARRAY OF LENGTH N WHICH SPECIFIES * THE DEGREE SEQUENCE. THE DEGREE OF THE J-TH COLUMN * OF A IS NDEG(J). * * LIST IS AN INTEGER OUTPUT ARRAY OF LENGTH N WHICH SPECIFIES * THE INCIDENCE-DEGREE ORDERING OF THE COLUMNS OF A. THE J-TH * COLUMN IN THIS ORDER IS LIST(J). * * MAXCLQ IS AN INTEGER OUTPUT VARIABLE SET TO THE SIZE * OF THE LARGEST CLIQUE FOUND DURING THE ORDERING. * * IWA1,IWA2,IWA3, AND IWA4 ARE INTEGER WORK ARRAYS OF LENGTH N. * * BWA() is an INTEGER WORK ARRAY OF LENGTH N. * * SUBPROGRAMS CALLED * * MINPACK-SUPPLIED ... N7MSRT * * FORTRAN-SUPPLIED ... max * * ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. * THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE * * ********** */ /* SORT THE DEGREE SEQUENCE. * */ n7msrt( n, n - 1, ndeg, -1, iwa4, iwa1, iwa3 ); /* INITIALIZATION BLOCK. * * CREATE A DOUBLY-LINKED LIST TO ACCESS THE INCIDENCES OF THE * COLUMNS. THE POINTERS FOR THE LINKED LIST ARE AS FOLLOWS. * * EACH UN-ORDERED COLUMN JCOL IS IN A LIST (THE INCIDENCE LIST) * OF COLUMNS WITH THE SAME INCIDENCE. * * IWA1(NUMINC+1) IS THE FIRST COLUMN IN THE NUMINC LIST * UNLESS IWA1(NUMINC+1) = 0. IN THIS CASE THERE ARE * NO COLUMNS IN THE NUMINC LIST. * * IWA2(JCOL) IS THE COLUMN BEFORE JCOL IN THE INCIDENCE LIST * UNLESS IWA2(JCOL) = 0. IN THIS CASE JCOL IS THE FIRST * COLUMN IN THIS INCIDENCE LIST. * * IWA3(JCOL) IS THE COLUMN AFTER JCOL IN THE INCIDENCE LIST * UNLESS IWA3(JCOL) = 0. IN THIS CASE JCOL IS THE LAST * COLUMN IN THIS INCIDENCE LIST. * * IF JCOL IS AN UN-ORDERED COLUMN, THEN LIST(JCOL) IS THE * INCIDENCE OF JCOL IN THE GRAPH. IF JCOL IS AN ORDERED COLUMN, * THEN LIST(JCOL) IS THE INCIDENCE-DEGREE ORDER OF COLUMN JCOL. * */ maxinc = 0; for (jp = 1; jp <= n; jp++) { List[jp] = 0; Bwa[jp] = IFALSE; Iwa1[jp] = 0; l = Iwa4[jp]; if (jp != 1) Iwa2[l] = Iwa4[jp - 1]; if (jp != n) Iwa3[l] = Iwa4[jp + 1]; } Iwa1[1] = Iwa4[1]; l = Iwa4[1]; Iwa2[l] = 0; l = Iwa4[n]; Iwa3[l] = 0; /* DETERMINE THE MAXIMAL SEARCH LENGTH FOR THE LIST * OF COLUMNS OF MAXIMAL INCIDENCE. * */ maxlst = 0; for (ir = 1; ir <= m; ir++) { maxlst += ipow(Ipntr[ir + 1] - Ipntr[ir],2); } maxlst /= n; *maxclq = 1; /* BEGINNING OF ITERATION LOOP. * */ for (numord = 1; numord <= n; numord++) { /* CHOOSE A COLUMN JCOL OF MAXIMAL DEGREE AMONG THE * COLUMNS OF MAXIMAL INCIDENCE. * */ jp = Iwa1[maxinc + 1]; numlst = 1; numwgt = -1; L_30: ; if (Ndeg[jp] <= numwgt) goto L_40; numwgt = Ndeg[jp]; jcol = jp; L_40: ; jp = Iwa3[jp]; numlst += 1; if (jp > 0 && numlst <= maxlst) goto L_30; List[jcol] = numord; /* DELETE COLUMN JCOL FROM THE LIST OF COLUMNS OF * MAXIMAL INCIDENCE. * */ l = Iwa2[jcol]; if (l == 0) Iwa1[maxinc + 1] = Iwa3[jcol]; if (l > 0) Iwa3[l] = Iwa3[jcol]; l = Iwa3[jcol]; if (l > 0) Iwa2[l] = Iwa2[jcol]; /* UPDATE THE SIZE OF THE LARGEST CLIQUE * FOUND DURING THE ORDERING. * */ if (maxinc == 0) ncomp = 0; ncomp += 1; if (maxinc + 1 == ncomp) *maxclq = max( *maxclq, ncomp ); /* UPDATE THE MAXIMAL INCIDENCE COUNT. * */ L_50: ; if (Iwa1[maxinc + 1] > 0) goto L_60; maxinc -= 1; if (maxinc >= 0) goto L_50; L_60: ; /* FIND ALL COLUMNS ADJACENT TO COLUMN JCOL. * */ Bwa[jcol] = ITRUE; deg = 0; /* DETERMINE ALL POSITIONS (IR,JCOL) WHICH CORRESPOND * TO NON-ZEROES IN THE MATRIX. * */ jpl = Jpntr[jcol]; jpu = Jpntr[jcol + 1] - 1; if (jpu < jpl) goto L_100; for (jp = jpl; jp <= jpu; jp++) { ir = Indrow[jp]; /* FOR EACH ROW IR, DETERMINE ALL POSITIONS (IR,IC) * WHICH CORRESPOND TO NON-ZEROES IN THE MATRIX. * */ ipl = Ipntr[ir]; ipu = Ipntr[ir + 1] - 1; for (ip = ipl; ip <= ipu; ip++) { ic = Indcol[ip]; /* Array BWA() MARKS COLUMNS WHICH ARE ADJACENT TO * COLUMN JCOL. ARRAY IWA4 RECORDS THE MARKED COLUMNS. * */ if (Bwa[ic] == ITRUE) goto L_70; Bwa[ic] = ITRUE; deg += 1; Iwa4[deg] = ic; L_70: ; } } L_100: ; /* UPDATE THE POINTERS TO THE INCIDENCE LISTS. * */ if (deg < 1) goto L_130; for (jp = 1; jp <= deg; jp++) { ic = Iwa4[jp]; if (List[ic] > 0) goto L_110; numinc = -List[ic] + 1; List[ic] = -numinc; maxinc = max( maxinc, numinc ); /* DELETE COLUMN IC FROM THE NUMINC-1 LIST. * */ l = Iwa2[ic]; if (l == 0) Iwa1[numinc] = Iwa3[ic]; if (l > 0) Iwa3[l] = Iwa3[ic]; l = Iwa3[ic]; if (l > 0) Iwa2[l] = Iwa2[ic]; /* ADD COLUMN IC TO THE NUMINC LIST. * */ head = Iwa1[numinc + 1]; Iwa1[numinc + 1] = ic; Iwa2[ic] = 0; Iwa3[ic] = head; if (head > 0) Iwa2[head] = ic; L_110: ; /* UN-MARK COLUMN IC IN THE ARRAY BWA. * */ Bwa[ic] = IFALSE; } L_130: ; Bwa[jcol] = IFALSE; /* END OF ITERATION LOOP. * */ } /* INVERT THE ARRAY LIST. * */ for (jcol = 1; jcol <= n; jcol++) { numord = List[jcol]; Iwa1[numord] = jcol; } for (jp = 1; jp <= n; jp++) { List[jp] = Iwa1[jp]; } return; /* LAST CARD OF SUBROUTINE I7DO. * */ } /* end of function */ void /*FUNCTION*/ n7msrt( long n, long nmax, long num[], long mode, long index[], long last[], long next[]) { long int i, j, jp, k, l, nmaxp1, nmaxp2; /* OFFSET Vectors w/subscript range: 1 to dimension */ long *const Index = &index[0] - 1; long *const Last = &last[0] - 1; long *const Next = &next[0] - 1; long *const Num = &num[0] - 1; /* end of OFFSET VECTORS */ /* **********. * * SUBROUTINE N7MSRT * * GIVEN A SEQUENCE OF INTEGERS, THIS SUBROUTINE GROUPS * TOGETHER THOSE INDICES WITH THE SAME SEQUENCE VALUE * AND, OPTIONALLY, SORTS THE SEQUENCE INTO EITHER * ASCENDING OR DESCENDING ORDER. * * THE SEQUENCE OF INTEGERS IS DEFINED BY THE ARRAY NUM, * AND IT IS ASSUMED THAT THE INTEGERS ARE EACH FROM THE SET * 0,1,...,NMAX. ON OUTPUT THE INDICES K SUCH THAT NUM(K) = L * FOR ANY L = 0,1,...,NMAX CAN BE OBTAINED FROM THE ARRAYS * LAST AND NEXT AS FOLLOWS. * * K = LAST(L+1) * WHILE (K .NE. 0) K = NEXT(K) * * OPTIONALLY, THE SUBROUTINE PRODUCES AN ARRAY INDEX SO THAT * THE SEQUENCE NUM(INDEX(I)), I = 1,2,...,N IS SORTED. * * THE SUBROUTINE STATEMENT IS * * SUBROUTINE N7MSRT(N,NMAX,NUM,MODE,INDEX,LAST,NEXT) * * WHERE * * N IS A POSITIVE INTEGER INPUT VARIABLE. * * NMAX IS A POSITIVE INTEGER INPUT VARIABLE. * * NUM IS AN INPUT ARRAY OF LENGTH N WHICH CONTAINS THE * SEQUENCE OF INTEGERS TO BE GROUPED AND SORTED. IT * IS ASSUMED THAT THE INTEGERS ARE EACH FROM THE SET * 0,1,...,NMAX. * * MODE IS AN INTEGER INPUT VARIABLE. THE SEQUENCE NUM IS * SORTED IN ASCENDING ORDER IF MODE IS POSITIVE AND IN * DESCENDING ORDER IF MODE IS NEGATIVE. IF MODE IS 0, * NO SORTING IS DONE. * * INDEX IS AN INTEGER OUTPUT ARRAY OF LENGTH N SET SO * THAT THE SEQUENCE * * NUM(INDEX(I)), I = 1,2,...,N * * IS SORTED ACCORDING TO THE SETTING OF MODE. IF MODE * IS 0, INDEX IS NOT REFERENCED. * * LAST IS AN INTEGER OUTPUT ARRAY OF LENGTH NMAX + 1. THE * INDEX OF NUM FOR THE LAST OCCURRENCE OF L IS LAST(L+1) * FOR ANY L = 0,1,...,NMAX UNLESS LAST(L+1) = 0. IN * THIS CASE L DOES NOT APPEAR IN NUM. * * NEXT IS AN INTEGER OUTPUT ARRAY OF LENGTH N. IF * NUM(K) = L, THEN THE INDEX OF NUM FOR THE PREVIOUS * OCCURRENCE OF L IS NEXT(K) FOR ANY L = 0,1,...,NMAX * UNLESS NEXT(K) = 0. IN THIS CASE THERE IS NO PREVIOUS * OCCURRENCE OF L IN NUM. * * ARGONNE NATIONAL LABORATORY. MINPACK PROJECT. JUNE 1982. * THOMAS F. COLEMAN, BURTON S. GARBOW, JORGE J. MORE * * ********** */ /* DETERMINE THE ARRAYS NEXT AND LAST. * */ nmaxp1 = nmax + 1; for (i = 1; i <= nmaxp1; i++) { Last[i] = 0; } for (k = 1; k <= n; k++) { l = Num[k]; Next[k] = Last[l + 1]; Last[l + 1] = k; } if (mode == 0) goto L_60; /* STORE THE POINTERS TO THE SORTED ARRAY IN INDEX. * */ i = 1; nmaxp2 = nmaxp1 + 1; for (j = 1; j <= nmaxp1; j++) { jp = j; if (mode < 0) jp = nmaxp2 - j; k = Last[jp]; L_30: ; if (k == 0) goto L_40; Index[i] = k; i += 1; k = Next[k]; goto L_30; L_40: ; } L_60: ; return; /* LAST CARD OF SUBROUTINE N7MSRT. * */ } /* end of function */