lemon-project-template-glpk

annotate deps/glpk/src/amd/amd_valid.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* ========================================================================= */
alpar@9 2 /* === AMD_valid =========================================================== */
alpar@9 3 /* ========================================================================= */
alpar@9 4
alpar@9 5 /* ------------------------------------------------------------------------- */
alpar@9 6 /* AMD, Copyright (c) Timothy A. Davis, */
alpar@9 7 /* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */
alpar@9 8 /* email: davis at cise.ufl.edu CISE Department, Univ. of Florida. */
alpar@9 9 /* web: http://www.cise.ufl.edu/research/sparse/amd */
alpar@9 10 /* ------------------------------------------------------------------------- */
alpar@9 11
alpar@9 12 /* Check if a column-form matrix is valid or not. The matrix A is
alpar@9 13 * n_row-by-n_col. The row indices of entries in column j are in
alpar@9 14 * Ai [Ap [j] ... Ap [j+1]-1]. Required conditions are:
alpar@9 15 *
alpar@9 16 * n_row >= 0
alpar@9 17 * n_col >= 0
alpar@9 18 * nz = Ap [n_col] >= 0 number of entries in the matrix
alpar@9 19 * Ap [0] == 0
alpar@9 20 * Ap [j] <= Ap [j+1] for all j in the range 0 to n_col.
alpar@9 21 * Ai [0 ... nz-1] must be in the range 0 to n_row-1.
alpar@9 22 *
alpar@9 23 * If any of the above conditions hold, AMD_INVALID is returned. If the
alpar@9 24 * following condition holds, AMD_OK_BUT_JUMBLED is returned (a warning,
alpar@9 25 * not an error):
alpar@9 26 *
alpar@9 27 * row indices in Ai [Ap [j] ... Ap [j+1]-1] are not sorted in ascending
alpar@9 28 * order, and/or duplicate entries exist.
alpar@9 29 *
alpar@9 30 * Otherwise, AMD_OK is returned.
alpar@9 31 *
alpar@9 32 * In v1.2 and earlier, this function returned TRUE if the matrix was valid
alpar@9 33 * (now returns AMD_OK), or FALSE otherwise (now returns AMD_INVALID or
alpar@9 34 * AMD_OK_BUT_JUMBLED).
alpar@9 35 */
alpar@9 36
alpar@9 37 #include "amd_internal.h"
alpar@9 38
alpar@9 39 GLOBAL Int AMD_valid
alpar@9 40 (
alpar@9 41 /* inputs, not modified on output: */
alpar@9 42 Int n_row, /* A is n_row-by-n_col */
alpar@9 43 Int n_col,
alpar@9 44 const Int Ap [ ], /* column pointers of A, of size n_col+1 */
alpar@9 45 const Int Ai [ ] /* row indices of A, of size nz = Ap [n_col] */
alpar@9 46 )
alpar@9 47 {
alpar@9 48 Int nz, j, p1, p2, ilast, i, p, result = AMD_OK ;
alpar@9 49
alpar@9 50 if (n_row < 0 || n_col < 0 || Ap == NULL || Ai == NULL)
alpar@9 51 {
alpar@9 52 return (AMD_INVALID) ;
alpar@9 53 }
alpar@9 54 nz = Ap [n_col] ;
alpar@9 55 if (Ap [0] != 0 || nz < 0)
alpar@9 56 {
alpar@9 57 /* column pointers must start at Ap [0] = 0, and Ap [n] must be >= 0 */
alpar@9 58 AMD_DEBUG0 (("column 0 pointer bad or nz < 0\n")) ;
alpar@9 59 return (AMD_INVALID) ;
alpar@9 60 }
alpar@9 61 for (j = 0 ; j < n_col ; j++)
alpar@9 62 {
alpar@9 63 p1 = Ap [j] ;
alpar@9 64 p2 = Ap [j+1] ;
alpar@9 65 AMD_DEBUG2 (("\nColumn: "ID" p1: "ID" p2: "ID"\n", j, p1, p2)) ;
alpar@9 66 if (p1 > p2)
alpar@9 67 {
alpar@9 68 /* column pointers must be ascending */
alpar@9 69 AMD_DEBUG0 (("column "ID" pointer bad\n", j)) ;
alpar@9 70 return (AMD_INVALID) ;
alpar@9 71 }
alpar@9 72 ilast = EMPTY ;
alpar@9 73 for (p = p1 ; p < p2 ; p++)
alpar@9 74 {
alpar@9 75 i = Ai [p] ;
alpar@9 76 AMD_DEBUG3 (("row: "ID"\n", i)) ;
alpar@9 77 if (i < 0 || i >= n_row)
alpar@9 78 {
alpar@9 79 /* row index out of range */
alpar@9 80 AMD_DEBUG0 (("index out of range, col "ID" row "ID"\n", j, i));
alpar@9 81 return (AMD_INVALID) ;
alpar@9 82 }
alpar@9 83 if (i <= ilast)
alpar@9 84 {
alpar@9 85 /* row index unsorted, or duplicate entry present */
alpar@9 86 AMD_DEBUG1 (("index unsorted/dupl col "ID" row "ID"\n", j, i));
alpar@9 87 result = AMD_OK_BUT_JUMBLED ;
alpar@9 88 }
alpar@9 89 ilast = i ;
alpar@9 90 }
alpar@9 91 }
alpar@9 92 return (result) ;
alpar@9 93 }