alpar@1: /* ========================================================================= */
alpar@1: /* === AMD_preprocess ====================================================== */
alpar@1: /* ========================================================================= */
alpar@1: 
alpar@1: /* ------------------------------------------------------------------------- */
alpar@1: /* AMD, Copyright (c) Timothy A. Davis,                                      */
alpar@1: /* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */
alpar@1: /* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */
alpar@1: /* web: http://www.cise.ufl.edu/research/sparse/amd                          */
alpar@1: /* ------------------------------------------------------------------------- */
alpar@1: 
alpar@1: /* Sorts, removes duplicate entries, and transposes from the nonzero pattern of
alpar@1:  * a column-form matrix A, to obtain the matrix R.  The input matrix can have
alpar@1:  * duplicate entries and/or unsorted columns (AMD_valid (n,Ap,Ai) must not be
alpar@1:  * AMD_INVALID).
alpar@1:  *
alpar@1:  * This input condition is NOT checked.  This routine is not user-callable.
alpar@1:  */
alpar@1: 
alpar@1: #include "amd_internal.h"
alpar@1: 
alpar@1: /* ========================================================================= */
alpar@1: /* === AMD_preprocess ====================================================== */
alpar@1: /* ========================================================================= */
alpar@1: 
alpar@1: /* AMD_preprocess does not check its input for errors or allocate workspace.
alpar@1:  * On input, the condition (AMD_valid (n,n,Ap,Ai) != AMD_INVALID) must hold.
alpar@1:  */
alpar@1: 
alpar@1: GLOBAL void AMD_preprocess
alpar@1: (
alpar@1:     Int n,              /* input matrix: A is n-by-n */
alpar@1:     const Int Ap [ ],   /* size n+1 */
alpar@1:     const Int Ai [ ],   /* size nz = Ap [n] */
alpar@1: 
alpar@1:     /* output matrix R: */
alpar@1:     Int Rp [ ],         /* size n+1 */
alpar@1:     Int Ri [ ],         /* size nz (or less, if duplicates present) */
alpar@1: 
alpar@1:     Int W [ ],          /* workspace of size n */
alpar@1:     Int Flag [ ]        /* workspace of size n */
alpar@1: )
alpar@1: {
alpar@1: 
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1:     /* local variables */
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1: 
alpar@1:     Int i, j, p, p2 ;
alpar@1: 
alpar@1:     ASSERT (AMD_valid (n, n, Ap, Ai) != AMD_INVALID) ;
alpar@1: 
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1:     /* count the entries in each row of A (excluding duplicates) */
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1: 
alpar@1:     for (i = 0 ; i < n ; i++)
alpar@1:     {
alpar@1:         W [i] = 0 ;             /* # of nonzeros in row i (excl duplicates) */
alpar@1:         Flag [i] = EMPTY ;      /* Flag [i] = j if i appears in column j */
alpar@1:     }
alpar@1:     for (j = 0 ; j < n ; j++)
alpar@1:     {
alpar@1:         p2 = Ap [j+1] ;
alpar@1:         for (p = Ap [j] ; p < p2 ; p++)
alpar@1:         {
alpar@1:             i = Ai [p] ;
alpar@1:             if (Flag [i] != j)
alpar@1:             {
alpar@1:                 /* row index i has not yet appeared in column j */
alpar@1:                 W [i]++ ;           /* one more entry in row i */
alpar@1:                 Flag [i] = j ;      /* flag row index i as appearing in col j*/
alpar@1:             }
alpar@1:         }
alpar@1:     }
alpar@1: 
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1:     /* compute the row pointers for R */
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1: 
alpar@1:     Rp [0] = 0 ;
alpar@1:     for (i = 0 ; i < n ; i++)
alpar@1:     {
alpar@1:         Rp [i+1] = Rp [i] + W [i] ;
alpar@1:     }
alpar@1:     for (i = 0 ; i < n ; i++)
alpar@1:     {
alpar@1:         W [i] = Rp [i] ;
alpar@1:         Flag [i] = EMPTY ;
alpar@1:     }
alpar@1: 
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1:     /* construct the row form matrix R */
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1: 
alpar@1:     /* R = row form of pattern of A */
alpar@1:     for (j = 0 ; j < n ; j++)
alpar@1:     {
alpar@1:         p2 = Ap [j+1] ;
alpar@1:         for (p = Ap [j] ; p < p2 ; p++)
alpar@1:         {
alpar@1:             i = Ai [p] ;
alpar@1:             if (Flag [i] != j)
alpar@1:             {
alpar@1:                 /* row index i has not yet appeared in column j */
alpar@1:                 Ri [W [i]++] = j ;  /* put col j in row i */
alpar@1:                 Flag [i] = j ;      /* flag row index i as appearing in col j*/
alpar@1:             }
alpar@1:         }
alpar@1:     }
alpar@1: 
alpar@1: #ifndef NDEBUG
alpar@1:     ASSERT (AMD_valid (n, n, Rp, Ri) == AMD_OK) ;
alpar@1:     for (j = 0 ; j < n ; j++)
alpar@1:     {
alpar@1:         ASSERT (W [j] == Rp [j+1]) ;
alpar@1:     }
alpar@1: #endif
alpar@1: }