alpar@9: /* ========================================================================= */
alpar@9: /* === AMD_valid =========================================================== */
alpar@9: /* ========================================================================= */
alpar@9: 
alpar@9: /* ------------------------------------------------------------------------- */
alpar@9: /* AMD, Copyright (c) Timothy A. Davis,                                      */
alpar@9: /* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */
alpar@9: /* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */
alpar@9: /* web: http://www.cise.ufl.edu/research/sparse/amd                          */
alpar@9: /* ------------------------------------------------------------------------- */
alpar@9: 
alpar@9: /* Check if a column-form matrix is valid or not.  The matrix A is
alpar@9:  * n_row-by-n_col.  The row indices of entries in column j are in
alpar@9:  * Ai [Ap [j] ... Ap [j+1]-1].  Required conditions are:
alpar@9:  *
alpar@9:  *      n_row >= 0
alpar@9:  *      n_col >= 0
alpar@9:  *      nz = Ap [n_col] >= 0        number of entries in the matrix
alpar@9:  *      Ap [0] == 0
alpar@9:  *      Ap [j] <= Ap [j+1] for all j in the range 0 to n_col.
alpar@9:  *      Ai [0 ... nz-1] must be in the range 0 to n_row-1.
alpar@9:  *
alpar@9:  * If any of the above conditions hold, AMD_INVALID is returned.  If the
alpar@9:  * following condition holds, AMD_OK_BUT_JUMBLED is returned (a warning,
alpar@9:  * not an error):
alpar@9:  *
alpar@9:  *      row indices in Ai [Ap [j] ... Ap [j+1]-1] are not sorted in ascending
alpar@9:  *          order, and/or duplicate entries exist.
alpar@9:  *
alpar@9:  * Otherwise, AMD_OK is returned.
alpar@9:  *
alpar@9:  * In v1.2 and earlier, this function returned TRUE if the matrix was valid
alpar@9:  * (now returns AMD_OK), or FALSE otherwise (now returns AMD_INVALID or
alpar@9:  * AMD_OK_BUT_JUMBLED).
alpar@9:  */
alpar@9: 
alpar@9: #include "amd_internal.h"
alpar@9: 
alpar@9: GLOBAL Int AMD_valid
alpar@9: (
alpar@9:     /* inputs, not modified on output: */
alpar@9:     Int n_row,          /* A is n_row-by-n_col */
alpar@9:     Int n_col,
alpar@9:     const Int Ap [ ],   /* column pointers of A, of size n_col+1 */
alpar@9:     const Int Ai [ ]    /* row indices of A, of size nz = Ap [n_col] */
alpar@9: )
alpar@9: {
alpar@9:     Int nz, j, p1, p2, ilast, i, p, result = AMD_OK ;
alpar@9: 
alpar@9:     if (n_row < 0 || n_col < 0 || Ap == NULL || Ai == NULL)
alpar@9:     {
alpar@9:         return (AMD_INVALID) ;
alpar@9:     }
alpar@9:     nz = Ap [n_col] ;
alpar@9:     if (Ap [0] != 0 || nz < 0)
alpar@9:     {
alpar@9:         /* column pointers must start at Ap [0] = 0, and Ap [n] must be >= 0 */
alpar@9:         AMD_DEBUG0 (("column 0 pointer bad or nz < 0\n")) ;
alpar@9:         return (AMD_INVALID) ;
alpar@9:     }
alpar@9:     for (j = 0 ; j < n_col ; j++)
alpar@9:     {
alpar@9:         p1 = Ap [j] ;
alpar@9:         p2 = Ap [j+1] ;
alpar@9:         AMD_DEBUG2 (("\nColumn: "ID" p1: "ID" p2: "ID"\n", j, p1, p2)) ;
alpar@9:         if (p1 > p2)
alpar@9:         {
alpar@9:             /* column pointers must be ascending */
alpar@9:             AMD_DEBUG0 (("column "ID" pointer bad\n", j)) ;
alpar@9:             return (AMD_INVALID) ;
alpar@9:         }
alpar@9:         ilast = EMPTY ;
alpar@9:         for (p = p1 ; p < p2 ; p++)
alpar@9:         {
alpar@9:             i = Ai [p] ;
alpar@9:             AMD_DEBUG3 (("row: "ID"\n", i)) ;
alpar@9:             if (i < 0 || i >= n_row)
alpar@9:             {
alpar@9:                 /* row index out of range */
alpar@9:                 AMD_DEBUG0 (("index out of range, col "ID" row "ID"\n", j, i));
alpar@9:                 return (AMD_INVALID) ;
alpar@9:             }
alpar@9:             if (i <= ilast)
alpar@9:             {
alpar@9:                 /* row index unsorted, or duplicate entry present */
alpar@9:                 AMD_DEBUG1 (("index unsorted/dupl col "ID" row "ID"\n", j, i));
alpar@9:                 result = AMD_OK_BUT_JUMBLED ;
alpar@9:             }
alpar@9:             ilast = i ;
alpar@9:         }
alpar@9:     }
alpar@9:     return (result) ;
alpar@9: }