amd_valid source code

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: DrTimothyAldenDavis@gmail.com                                      */
9 /* ------------------------------------------------------------------------- */
10 
11 /* Check if a column-form matrix is valid or not.  The matrix A is
12  * n_row-by-n_col.  The row indices of entries in column j are in
13  * Ai [Ap [j] ... Ap [j+1]-1].  Required conditions are:
14  *
15  *	n_row >= 0
16  *	n_col >= 0
17  *	nz = Ap [n_col] >= 0	    number of entries in the matrix
18  *	Ap [0] == 0
19  *	Ap [j] <= Ap [j+1] for all j in the range 0 to n_col.
20  *      Ai [0 ... nz-1] must be in the range 0 to n_row-1.
21  *
22  * If any of the above conditions hold, AMD_INVALID is returned.  If the
23  * following condition holds, AMD_OK_BUT_JUMBLED is returned (a warning,
24  * not an error):
25  *
26  *	row indices in Ai [Ap [j] ... Ap [j+1]-1] are not sorted in ascending
27  *	    order, and/or duplicate entries exist.
28  *
29  * Otherwise, AMD_OK is returned.
30  *
31  * In v1.2 and earlier, this function returned TRUE if the matrix was valid
32  * (now returns AMD_OK), or FALSE otherwise (now returns AMD_INVALID or
33  * AMD_OK_BUT_JUMBLED).
34  */
35 
36 module amd_valid;
37 
38 nothrow @nogc extern(C):
39 
40 import amd_internal;
41 import amd;
42 import SuiteSparse_config;
43 
44 
45 /* ------------------------------------------------------------------------- */
46 /* amd_valid */
47 /* ------------------------------------------------------------------------- */
48 
49 /* Returns AMD_OK or AMD_OK_BUT_JUMBLED if the matrix is valid as input to
50  * amd_order; the latter is returned if the matrix has unsorted and/or
51  * duplicate row indices in one or more columns.  Returns AMD_INVALID if the
52  * matrix cannot be passed to amd_order.  For amd_order, the matrix must also
53  * be square.  The first two arguments are the number of rows and the number
54  * of columns of the matrix.  For its use in AMD, these must both equal n.
55  *
56  * NOTE: this routine returned TRUE/FALSE in v1.2 and earlier.
57  */
58 version (DLONG){
59     SuiteSparse_long AMD_valid
60     (
61 		/* inputs, not modified on output: */
62         SuiteSparse_long n_row,			/* A is n_row-by-n_col */
63         SuiteSparse_long n_col,
64         const SuiteSparse_long * Ap,	/* column pointers of A, of size n_col+1 */
65         const SuiteSparse_long * Ai		/* row indices of A, of size nz = Ap [n_col] */
66     )
67 	{
68 		Int nz, j, p1, p2, ilast, i, p, result = AMD_OK ;
69 
70 		if (n_row < 0 || n_col < 0 || Ap == NULL || Ai == NULL)
71 		{
72 		return (AMD_INVALID) ;
73 		}
74 		nz = Ap [n_col] ;
75 		if (Ap [0] != 0 || nz < 0)
76 		{
77 		/* column pointers must start at Ap [0] = 0, and Ap [n] must be >= 0 */
78 		AMD_DEBUG0 ("column 0 pointer bad or nz < 0\n");
79 		return (AMD_INVALID) ;
80 		}
81 		for (j = 0 ; j < n_col ; j++)
82 		{
83 		p1 = Ap [j] ;
84 		p2 = Ap [j+1] ;
85 		AMD_DEBUG2 ("\nColumn: "~ID~" p1: "~ID~" p2: "~ID~"\n", j, p1, p2) ;
86 		if (p1 > p2)
87 		{
88 			/* column pointers must be ascending */
89 			AMD_DEBUG0 ("column "~ID~" pointer bad\n", j) ;
90 			return (AMD_INVALID) ;
91 		}
92 		ilast = EMPTY ;
93 		for (p = p1 ; p < p2 ; p++)
94 		{
95 			i = Ai [p] ;
96 			AMD_DEBUG3 ("row: "~ID~"\n", i) ;
97 			if (i < 0 || i >= n_row)
98 			{
99 			/* row index out of range */
100 			AMD_DEBUG0 ("index out of range, col "~ID~" row "~ID~"\n", j, i);
101 			return (AMD_INVALID) ;
102 			}
103 			if (i <= ilast)
104 			{
105 			/* row index unsorted, or duplicate entry present */
106 			AMD_DEBUG1 ("index unsorted/dupl col "~ID~" row "~ID~"\n", j, i);
107 			result = AMD_OK_BUT_JUMBLED ;
108 			}
109 			ilast = i ;
110 		}
111 		}
112 		return (result) ;
113 	}
114 } // DLONG
115 else {
116     int AMD_valid
117     (
118 		/* inputs, not modified on output: */
119         int n_row,                 /* A is n_row-by-n_col */  /* # of rows */
120         int n_col,                 /* # of columns */
121         const int * Ap,          /* column pointers of A, of size n_col+1 */
122         const int * Ai           /* row indices of A, of size nz = Ap [n_col] */
123     )
124 	{
125 		Int nz, j, p1, p2, ilast, i, p, result = AMD_OK ;
126 
127 		if (n_row < 0 || n_col < 0 || Ap == NULL || Ai == NULL)
128 		{
129 		return (AMD_INVALID) ;
130 		}
131 		nz = Ap [n_col] ;
132 		if (Ap [0] != 0 || nz < 0)
133 		{
134 		/* column pointers must start at Ap [0] = 0, and Ap [n] must be >= 0 */
135 		AMD_DEBUG0 ("column 0 pointer bad or nz < 0\n");
136 		return (AMD_INVALID) ;
137 		}
138 		for (j = 0 ; j < n_col ; j++)
139 		{
140 		p1 = Ap [j] ;
141 		p2 = Ap [j+1] ;
142 		AMD_DEBUG2 ("\nColumn: "~ID~" p1: "~ID~" p2: "~ID~"\n", j, p1, p2) ;
143 		if (p1 > p2)
144 		{
145 			/* column pointers must be ascending */
146 			AMD_DEBUG0 ("column "~ID~" pointer bad\n", j) ;
147 			return (AMD_INVALID) ;
148 		}
149 		ilast = EMPTY ;
150 		for (p = p1 ; p < p2 ; p++)
151 		{
152 			i = Ai [p] ;
153 			AMD_DEBUG3 ("row: "~ID~"\n", i) ;
154 			if (i < 0 || i >= n_row)
155 			{
156 			/* row index out of range */
157 			AMD_DEBUG0 ("index out of range, col "~ID~" row "~ID~"\n", j, i);
158 			return (AMD_INVALID) ;
159 			}
160 			if (i <= ilast)
161 			{
162 			/* row index unsorted, or duplicate entry present */
163 			AMD_DEBUG1 ("index unsorted/dupl col "~ID~" row "~ID~"\n", j, i);
164 			result = AMD_OK_BUT_JUMBLED ;
165 			}
166 			ilast = i ;
167 		}
168 		}
169 		return (result) ;
170 	}
171 } // DLONG
172