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