|
5164
|
1 /* ========================================================================= */ |
|
|
2 /* === amd_internal.h ====================================================== */ |
|
|
3 /* ========================================================================= */ |
|
|
4 |
|
|
5 /* ------------------------------------------------------------------------- */ |
|
|
6 /* AMD Version 1.1 (Jan. 21, 2004), Copyright (c) 2004 by Timothy A. Davis, */ |
|
|
7 /* Patrick R. Amestoy, and Iain S. Duff. See ../README for License. */ |
|
|
8 /* email: davis@cise.ufl.edu CISE Department, Univ. of Florida. */ |
|
|
9 /* web: http://www.cise.ufl.edu/research/sparse/amd */ |
|
|
10 /* ------------------------------------------------------------------------- */ |
|
|
11 |
|
|
12 /* This file is for internal use in AMD itself, and does not normally need to |
|
|
13 * be included in user code. Use amd.h instead. |
|
|
14 * |
|
|
15 * The following compile-time definitions affect how AMD is compiled. |
|
|
16 * |
|
|
17 * -DMATLAB_MEX_FILE |
|
|
18 * |
|
|
19 * This flag is turned on when compiling the amd mexFunction for |
|
|
20 * use in MATLAB. |
|
|
21 * |
|
|
22 * -DMATHWORKS |
|
|
23 * |
|
|
24 * This flag is turned on when compiling amd as a built-in routine |
|
|
25 * in MATLAB. Internal routines utMalloc, utFree, utRealloc, and |
|
|
26 * utPrintf are used, and the MathWorks "util.h" file is included. |
|
|
27 * This option is intended for use by The MathWorks, Inc., only. |
|
|
28 * |
|
|
29 * -DNDEBUG |
|
|
30 * |
|
|
31 * Debugging mode (if NDEBUG is not defined). The default, of course, |
|
|
32 * is no debugging. Turning on debugging takes some work (see below). |
|
|
33 * If you do not edit this file, then debugging is turned off anyway, |
|
|
34 * regardless of whether or not -DNDEBUG is specified in your compiler |
|
|
35 * options. |
|
|
36 * |
|
|
37 * -DALLOCATE=allocation_routine |
|
|
38 * -DFREE=free_routine |
|
|
39 * |
|
|
40 * If you do not wish to use malloc or free, you can define the |
|
|
41 * routines to be used here. You must specify both of them, or |
|
|
42 * neither. |
|
|
43 * |
|
|
44 * -DPRINTF=printf_routine |
|
|
45 * |
|
|
46 * If you wish to use a routine other than printf, you can define it |
|
|
47 * with -DPRINTF= followed by the name of the printf replacement. |
|
|
48 */ |
|
|
49 |
|
|
50 /* ========================================================================= */ |
|
|
51 /* === NDEBUG ============================================================== */ |
|
|
52 /* ========================================================================= */ |
|
|
53 |
|
|
54 /* |
|
|
55 AMD will be exceedingly slow when running in debug mode. The next three |
|
|
56 lines ensure that debugging is turned off. |
|
|
57 */ |
|
|
58 #ifndef NDEBUG |
|
|
59 #define NDEBUG |
|
|
60 #endif |
|
|
61 |
|
|
62 /* |
|
|
63 To enable debugging, uncomment the following line: |
|
|
64 #undef NDEBUG |
|
|
65 */ |
|
|
66 |
|
|
67 /* ------------------------------------------------------------------------- */ |
|
|
68 /* ANSI include files */ |
|
|
69 /* ------------------------------------------------------------------------- */ |
|
|
70 |
|
|
71 /* from stdlib.h: malloc, free, realloc (when not compiling for MATLAB) */ |
|
|
72 #include <stdlib.h> |
|
|
73 |
|
|
74 /* from stdio.h: printf. When in debug mode: fopen, fscanf */ |
|
|
75 #include <stdio.h> |
|
|
76 |
|
|
77 /* from limits.h: INT_MAX and LONG_MAX */ |
|
|
78 #include <limits.h> |
|
|
79 |
|
|
80 /* from math.h: sqrt */ |
|
|
81 #include <math.h> |
|
|
82 |
|
|
83 /* ------------------------------------------------------------------------- */ |
|
|
84 /* MATLAB include files (only if being used in or via MATLAB) */ |
|
|
85 /* ------------------------------------------------------------------------- */ |
|
|
86 |
|
|
87 #ifdef MATHWORKS |
|
|
88 #include "util.h" |
|
|
89 #endif |
|
|
90 |
|
|
91 #ifdef MATLAB_MEX_FILE |
|
|
92 #include "matrix.h" |
|
|
93 #include "mex.h" |
|
|
94 #endif |
|
|
95 |
|
|
96 /* ------------------------------------------------------------------------- */ |
|
|
97 /* basic definitions */ |
|
|
98 /* ------------------------------------------------------------------------- */ |
|
|
99 |
|
|
100 #ifdef FLIP |
|
|
101 #undef FLIP |
|
|
102 #endif |
|
|
103 |
|
|
104 #ifdef MAX |
|
|
105 #undef MAX |
|
|
106 #endif |
|
|
107 |
|
|
108 #ifdef MIN |
|
|
109 #undef MIN |
|
|
110 #endif |
|
|
111 |
|
|
112 #ifdef EMPTY |
|
|
113 #undef EMPTY |
|
|
114 #endif |
|
|
115 |
|
|
116 #ifdef GLOBAL |
|
|
117 #undef GLOBAL |
|
|
118 #endif |
|
|
119 |
|
|
120 #ifdef PRIVATE |
|
|
121 #undef PRIVATE |
|
|
122 #endif |
|
|
123 |
|
|
124 /* FLIP is a "negation about -1", and is used to mark an integer i that is |
|
|
125 * normally non-negative. FLIP (EMPTY) is EMPTY. FLIP of a number > EMPTY |
|
|
126 * is negative, and FLIP of a number < EMTPY is positive. FLIP (FLIP (i)) = i |
|
|
127 * for all integers i. UNFLIP (i) is >= EMPTY. */ |
|
|
128 #define EMPTY (-1) |
|
|
129 #define FLIP(i) (-(i)-2) |
|
|
130 #define UNFLIP(i) ((i < EMPTY) ? FLIP (i) : (i)) |
|
|
131 |
|
|
132 /* for integer MAX/MIN, or for doubles when we don't care how NaN's behave: */ |
|
|
133 #define MAX(a,b) (((a) > (b)) ? (a) : (b)) |
|
|
134 #define MIN(a,b) (((a) < (b)) ? (a) : (b)) |
|
|
135 |
|
|
136 /* logical expression of p implies q: */ |
|
|
137 #define IMPLIES(p,q) (!(p) || (q)) |
|
|
138 |
|
|
139 /* Note that the IBM RS 6000 xlc predefines TRUE and FALSE in <types.h>. */ |
|
|
140 /* The Compaq Alpha also predefines TRUE and FALSE. */ |
|
|
141 #ifdef TRUE |
|
|
142 #undef TRUE |
|
|
143 #endif |
|
|
144 #ifdef FALSE |
|
|
145 #undef FALSE |
|
|
146 #endif |
|
|
147 |
|
|
148 #define TRUE (1) |
|
|
149 #define FALSE (0) |
|
|
150 #define PRIVATE static |
|
|
151 #define GLOBAL |
|
|
152 #define EMPTY (-1) |
|
|
153 |
|
|
154 /* Note that Linux's gcc 2.96 defines NULL as ((void *) 0), but other */ |
|
|
155 /* compilers (even gcc 2.95.2 on Solaris) define NULL as 0 or (0). We */ |
|
|
156 /* need to use the ANSI standard value of 0. */ |
|
|
157 #ifdef NULL |
|
|
158 #undef NULL |
|
|
159 #endif |
|
|
160 |
|
|
161 #define NULL 0 |
|
|
162 |
|
|
163 /* ------------------------------------------------------------------------- */ |
|
|
164 /* integer type for AMD: int or long */ |
|
|
165 /* ------------------------------------------------------------------------- */ |
|
|
166 |
|
|
167 #if defined (DLONG) || defined (ZLONG) |
|
|
168 |
|
|
169 #define Int long |
|
|
170 #define ID "%ld" |
|
|
171 #define Int_MAX LONG_MAX |
|
|
172 #define Int_MIN LONG_MIN |
|
|
173 |
|
|
174 #define AMD_order amd_l_order |
|
|
175 #define AMD_defaults amd_l_defaults |
|
|
176 #define AMD_control amd_l_control |
|
|
177 #define AMD_info amd_l_info |
|
|
178 #define AMD_1 amd_l1 |
|
|
179 #define AMD_2 amd_l2 |
|
|
180 #define AMD_valid amd_l_valid |
|
|
181 #define AMD_aat amd_l_aat |
|
|
182 #define AMD_postorder amd_l_postorder |
|
|
183 #define AMD_post_tree amd_l_post_tree |
|
|
184 #define AMD_dump amd_l_dump |
|
|
185 #define AMD_debug amd_l_debug |
|
|
186 #define AMD_debug_init amd_l_debug_init |
|
|
187 #define AMD_wpreprocess amd_l_wpreprocess |
|
|
188 #define AMD_preprocess amd_l_preprocess |
|
|
189 #define AMD_preprocess_valid amd_l_preprocess_valid |
|
|
190 |
|
|
191 #else |
|
|
192 |
|
|
193 #define Int int |
|
|
194 #define ID "%d" |
|
|
195 #define Int_MAX INT_MAX |
|
|
196 #define Int_MIN INT_MIN |
|
|
197 |
|
|
198 #define AMD_order amd_order |
|
|
199 #define AMD_defaults amd_defaults |
|
|
200 #define AMD_control amd_control |
|
|
201 #define AMD_info amd_info |
|
|
202 #define AMD_1 amd_1 |
|
|
203 #define AMD_2 amd_2 |
|
|
204 #define AMD_valid amd_valid |
|
|
205 #define AMD_aat amd_aat |
|
|
206 #define AMD_postorder amd_postorder |
|
|
207 #define AMD_post_tree amd_post_tree |
|
|
208 #define AMD_dump amd_dump |
|
|
209 #define AMD_debug amd_debug |
|
|
210 #define AMD_debug_init amd_debug_init |
|
|
211 #define AMD_wpreprocess amd_wpreprocess |
|
|
212 #define AMD_preprocess amd_preprocess |
|
|
213 #define AMD_preprocess_valid amd_preprocess_valid |
|
|
214 |
|
|
215 #endif |
|
|
216 |
|
|
217 /* ========================================================================= */ |
|
|
218 /* === Memory allocator ==================================================== */ |
|
|
219 /* ========================================================================= */ |
|
|
220 |
|
|
221 /* The MATLAB mexFunction uses MATLAB's memory manager, while the C-callable */ |
|
|
222 /* AMD routine uses the ANSI C malloc, free, and realloc routines. */ |
|
|
223 |
|
|
224 #ifndef ALLOCATE |
|
|
225 #ifdef MATLAB_MEX_FILE |
|
|
226 #define ALLOCATE mxMalloc |
|
|
227 #define FREE mxFree |
|
|
228 #else |
|
|
229 #ifdef MATHWORKS |
|
|
230 /* Compiling as a built-in routine. Since out-of-memory conditions are checked |
|
|
231 * after every allocation, we can use ut* routines here. */ |
|
|
232 #define ALLOCATE utMalloc |
|
|
233 #define FREE utFree |
|
|
234 #else |
|
|
235 /* use the ANSI C memory allocation routines */ |
|
|
236 #define ALLOCATE malloc |
|
|
237 #define FREE free |
|
|
238 #endif |
|
|
239 #endif |
|
|
240 #endif |
|
|
241 |
|
|
242 |
|
|
243 /* ========================================================================= */ |
|
|
244 /* === PRINTF macro ======================================================== */ |
|
|
245 /* ========================================================================= */ |
|
|
246 |
|
|
247 /* All output goes through the PRINTF macro. */ |
|
|
248 |
|
|
249 #ifndef PRINTF |
|
|
250 #ifdef MATLAB_MEX_FILE |
|
|
251 #define PRINTF(params) { (void) mexPrintf params ; } |
|
|
252 #else |
|
|
253 #ifdef MATHWORKS |
|
|
254 #define PRINTF(params) { (void) utPrintf params ; } |
|
|
255 #else |
|
|
256 #define PRINTF(params) { (void) printf params ; } |
|
|
257 #endif |
|
|
258 #endif |
|
|
259 #endif |
|
|
260 |
|
|
261 /* ------------------------------------------------------------------------- */ |
|
|
262 /* AMD routine definitions (user-callable) */ |
|
|
263 /* ------------------------------------------------------------------------- */ |
|
|
264 |
|
|
265 #include "amd.h" |
|
|
266 |
|
|
267 /* ------------------------------------------------------------------------- */ |
|
|
268 /* AMD routine definitions (not user-callable) */ |
|
|
269 /* ------------------------------------------------------------------------- */ |
|
|
270 |
|
|
271 GLOBAL Int AMD_valid |
|
|
272 ( |
|
|
273 Int n_row, |
|
|
274 Int n_col, |
|
|
275 const Int Ap [ ], |
|
|
276 const Int Ai [ ] |
|
|
277 ) ; |
|
|
278 |
|
|
279 GLOBAL Int AMD_aat |
|
|
280 ( |
|
|
281 Int n, |
|
|
282 const Int Ap [ ], |
|
|
283 const Int Ai [ ], |
|
|
284 Int Len [ ], |
|
|
285 Int Tp [ ], |
|
|
286 double Info [ ] |
|
|
287 ) ; |
|
|
288 |
|
|
289 GLOBAL void AMD_1 |
|
|
290 ( |
|
|
291 Int n, |
|
|
292 const Int Ap [ ], |
|
|
293 const Int Ai [ ], |
|
|
294 Int P [ ], |
|
|
295 Int Pinv [ ], |
|
|
296 Int Len [ ], |
|
|
297 Int slen, |
|
|
298 Int S [ ], |
|
|
299 double Control [ ], |
|
|
300 double Info [ ] |
|
|
301 ) ; |
|
|
302 |
|
|
303 GLOBAL void AMD_2 ( |
|
|
304 Int n, |
|
|
305 Int Pe [ ], |
|
|
306 Int Iw [ ], |
|
|
307 Int Len [ ], |
|
|
308 Int iwlen, |
|
|
309 Int pfree, |
|
|
310 Int Nv [ ], |
|
|
311 Int Next [ ], |
|
|
312 Int Last [ ], |
|
|
313 Int Head [ ], |
|
|
314 Int Elen [ ], |
|
|
315 Int Degree [ ], |
|
|
316 Int W [ ], |
|
|
317 double Control [ ], |
|
|
318 double Info [ ] |
|
|
319 ) ; |
|
|
320 |
|
|
321 GLOBAL void AMD_postorder |
|
|
322 ( |
|
|
323 Int nn, |
|
|
324 Int Parent [ ], |
|
|
325 Int Npiv [ ], |
|
|
326 Int Fsize [ ], |
|
|
327 Int Order [ ], |
|
|
328 Int Child [ ], |
|
|
329 Int Sibling [ ], |
|
|
330 Int Stack [ ] |
|
|
331 ) ; |
|
|
332 |
|
|
333 GLOBAL Int AMD_post_tree |
|
|
334 ( |
|
|
335 Int root, |
|
|
336 Int k, |
|
|
337 Int Child [ ], |
|
|
338 const Int Sibling [ ], |
|
|
339 Int Order [ ], |
|
|
340 Int Stack [ ] |
|
|
341 #ifndef NDEBUG |
|
|
342 , Int nn |
|
|
343 #endif |
|
|
344 ) ; |
|
|
345 |
|
|
346 GLOBAL void AMD_wpreprocess |
|
|
347 ( |
|
|
348 Int n, |
|
|
349 const Int Ap [ ], |
|
|
350 const Int Ai [ ], |
|
|
351 Int Rp [ ], |
|
|
352 Int Ri [ ], |
|
|
353 Int W [ ], |
|
|
354 Int Flag [ ] |
|
|
355 ) ; |
|
|
356 |
|
|
357 GLOBAL Int AMD_preprocess_valid |
|
|
358 ( |
|
|
359 Int n, |
|
|
360 const Int Ap [ ], |
|
|
361 const Int Ai [ ] |
|
|
362 ) ; |
|
|
363 |
|
|
364 /* ------------------------------------------------------------------------- */ |
|
|
365 /* debugging definitions */ |
|
|
366 /* ------------------------------------------------------------------------- */ |
|
|
367 |
|
|
368 /* from assert.h: assert macro */ |
|
|
369 #if !defined (MATHWORKS) && !defined (MATLAB_MEX_FILE) |
|
|
370 #include <assert.h> |
|
|
371 #endif |
|
|
372 |
|
|
373 #ifndef NDEBUG |
|
|
374 |
|
|
375 GLOBAL Int AMD_debug ; |
|
|
376 |
|
|
377 GLOBAL void AMD_debug_init ( char *s ) ; |
|
|
378 |
|
|
379 GLOBAL void AMD_dump ( |
|
|
380 Int n, |
|
|
381 Int Pe [ ], |
|
|
382 Int Iw [ ], |
|
|
383 Int Len [ ], |
|
|
384 Int iwlen, |
|
|
385 Int pfree, |
|
|
386 Int Nv [ ], |
|
|
387 Int Next [ ], |
|
|
388 Int Last [ ], |
|
|
389 Int Head [ ], |
|
|
390 Int Elen [ ], |
|
|
391 Int Degree [ ], |
|
|
392 Int W [ ], |
|
|
393 Int nel |
|
|
394 ) ; |
|
|
395 |
|
|
396 #ifdef ASSERT |
|
|
397 #undef ASSERT |
|
|
398 #endif |
|
|
399 |
|
|
400 #ifdef MATLAB_MEX_FILE |
|
|
401 #define ASSERT(expression) (mxAssert ((expression), "")) |
|
|
402 #else |
|
|
403 #ifdef MATHWORKS |
|
|
404 #define ASSERT(expression) (utAssert (expression)) |
|
|
405 #else |
|
|
406 #define ASSERT(expression) (assert (expression)) |
|
|
407 #endif |
|
|
408 #endif /* MATLAB_MEX_FILE */ |
|
|
409 |
|
|
410 #define AMD_DEBUG0(params) { PRINTF (params) ; } |
|
|
411 #define AMD_DEBUG1(params) { if (AMD_debug >= 1) PRINTF (params) ; } |
|
|
412 #define AMD_DEBUG2(params) { if (AMD_debug >= 2) PRINTF (params) ; } |
|
|
413 #define AMD_DEBUG3(params) { if (AMD_debug >= 3) PRINTF (params) ; } |
|
|
414 #define AMD_DEBUG4(params) { if (AMD_debug >= 4) PRINTF (params) ; } |
|
|
415 |
|
|
416 #else |
|
|
417 |
|
|
418 #define AMD_DEBUG0(params) |
|
|
419 #define AMD_DEBUG1(params) |
|
|
420 #define AMD_DEBUG2(params) |
|
|
421 #define AMD_DEBUG3(params) |
|
|
422 #define AMD_DEBUG4(params) |
|
|
423 |
|
|
424 #define ASSERT(expression) |
|
|
425 |
|
|
426 #endif |
