Mercurial > octave

annotate libinterp/dldfcn/colamd.cc @ 23450:855122b993da

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
maint: Wrap tertiary operator in parentheses "(COND ? x : y)". * Canvas.cc, color-picker.cc, dialog.cc, marker.cc, main-window.cc, Cell.cc, __magick_read__.cc, __pchip_deriv__.cc, __qp__.cc, bsxfun.cc, call-stack.cc, cellfun.cc, data.cc, defaults.cc, det.cc, eig.cc, error.cc, file-io.cc, filter.cc, find.cc, gammainc.cc, gcd.cc, gl-render.cc, graphics.cc, graphics.in.h, help.cc, hex2num.cc, inv.cc, load-save.cc, lookup.cc, ls-mat4.cc, ls-mat5.cc, ls-oct-binary.cc, ls-oct-text.cc, lu.cc, max.cc, mex.cc, oct-hist.cc, oct-map.cc, oct-procbuf.cc, oct-stream.cc, pr-output.cc, rand.cc, regexp.cc, schur.cc, str2double.cc, strfns.cc, symtab.cc, sysdep.cc, tril.cc, variables.cc, xdiv.cc, audiodevinfo.cc, audioread.cc, colamd.cc, gzip.cc, ov-base-diag.cc, ov-base-mat.h, ov-base-scalar.h, ov-class.cc, ov-classdef.cc, ov-fcn-handle.cc, ov-range.cc, ov-range.h, ov-struct.cc, ov-usr-fcn.cc, ov.cc, octave.cc, op-class.cc, pt-eval.cc, pt-funcall.cc, pt-idx.cc, pt-jit.cc, pt-stmt.cc, version.cc, Array-util.cc, Array.cc, CDiagMatrix.cc, CMatrix.cc, CNDArray.cc, CSparse.cc, Range.cc, Sparse.cc, chNDArray.cc, dDiagMatrix.cc, dMatrix.cc, dNDArray.cc, dSparse.cc, dim-vector.cc, fCDiagMatrix.cc, fCMatrix.cc, fCNDArray.cc, fDiagMatrix.cc, fMatrix.cc, fNDArray.cc, idx-vector.cc, idx-vector.h, Faddeeva.cc, DASPK.cc, DASRT.cc, DASSL.cc, EIG.cc, fEIG.cc, gsvd.cc, lo-specfun.cc, oct-rand.cc, qr.cc, qrp.cc, randgamma.cc, schur.cc, svd.cc, Sparse-diag-op-defs.h, mx-inlines.cc, oct-env.cc, cmd-edit.cc, kpse.cc, oct-inttypes.h, oct-sort.cc: Wrap tertiary operator in parentheses "(COND ? x : y)".
author Rik <rik@octave.org>
date Thu, 27 Apr 2017 17:33:10 -0700
parents 209e749363a2
children 21baad6b35c4
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
1 /*
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
2
23219
3ac9f9ecfae5 maint: Update copyright dates.
John W. Eaton <jwe@octave.org>
parents: 23083
diff changeset
3 Copyright (C) 2004-2017 David Bateman
11523
fd0a3ac60b0e update copyright notices
John W. Eaton <jwe@octave.org>
parents: 10846
diff changeset
4 Copyright (C) 1998-2004 Andy Adler
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6484
diff changeset
5
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6484
diff changeset
6 This file is part of Octave.
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
7
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
8 Octave is free software; you can redistribute it and/or modify it
22755
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22407
diff changeset
9 under the terms of the GNU General Public License as published by
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22407
diff changeset
10 the Free Software Foundation; either version 3 of the License, or
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22407
diff changeset
11 (at your option) any later version.
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
12
22755
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22407
diff changeset
13 Octave is distributed in the hope that it will be useful, but
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22407
diff changeset
14 WITHOUT ANY WARRANTY; without even the implied warranty of
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22407
diff changeset
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22407
diff changeset
16 GNU General Public License for more details.
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
17
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
18 You should have received a copy of the GNU General Public License
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6484
diff changeset
19 along with Octave; see the file COPYING. If not, see
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6484
diff changeset
20 <http://www.gnu.org/licenses/>.
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
21
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
22 */
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
23
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
24 // This is the octave interface to colamd, which bore the copyright given
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
25 // in the help of the functions.
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
26
21724
aba2e6293dd8 use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents: 21691
diff changeset
27 #if defined (HAVE_CONFIG_H)
21301
40de9f8f23a6 Use '#include "config.h"' rather than <config.h>.
Rik <rik@octave.org>
parents: 21229
diff changeset
28 # include "config.h"
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
29 #endif
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
30
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
31 #include <cstdlib>
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
32
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
33 #include <string>
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
34
23024
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents: 22755
diff changeset
35 #include "CSparse.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents: 22755
diff changeset
36 #include "dNDArray.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents: 22755
diff changeset
37 #include "dSparse.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents: 22755
diff changeset
38 #include "oct-locbuf.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents: 22755
diff changeset
39 #include "oct-sparse.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents: 22755
diff changeset
40
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
41 #include "defun-dld.h"
23024
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents: 22755
diff changeset
42 #include "error.h"
21110
3d0d84305600 Use err_square_matrix_required more widely.
Rik <rik@octave.org>
parents: 21109
diff changeset
43 #include "errwarn.h"
23024
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents: 22755
diff changeset
44 #include "ovl.h"
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
45 #include "pager.h"
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
46
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
47 // The symmetric column elimination tree code take from the Davis LDL code.
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
48 // Copyright given elsewhere in this file.
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
49 static void
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
50 symetree (const octave_idx_type *ridx, const octave_idx_type *cidx,
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
51 octave_idx_type *Parent, octave_idx_type *P, octave_idx_type n)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
52 {
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
53 OCTAVE_LOCAL_BUFFER (octave_idx_type, Flag, n);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
54 OCTAVE_LOCAL_BUFFER (octave_idx_type, Pinv, (P ? n : 0));
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
55 if (P)
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
56 // If P is present then compute Pinv, the inverse of P
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
57 for (octave_idx_type k = 0 ; k < n ; k++)
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
58 Pinv[P[k]] = k;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
59
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
60 for (octave_idx_type k = 0 ; k < n ; k++)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
61 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
62 // L(k,:) pattern: all nodes reachable in etree from nz in A(0:k-1,k)
15020
560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents: 14854
diff changeset
63 Parent[k] = n ; // parent of k is not yet known
560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents: 14854
diff changeset
64 Flag[k] = k ; // mark node k as visited
23450
855122b993da maint: Wrap tertiary operator in parentheses "(COND ? x : y)".
Rik <rik@octave.org>
parents: 23391
diff changeset
65 octave_idx_type kk = (P ? P[k] // kth original, or permuted, column
855122b993da maint: Wrap tertiary operator in parentheses "(COND ? x : y)".
Rik <rik@octave.org>
parents: 23391
diff changeset
66 : (k));
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
67 octave_idx_type p2 = cidx[kk+1];
15020
560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents: 14854
diff changeset
68 for (octave_idx_type p = cidx[kk] ; p < p2 ; p++)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
69 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
70 // A (i,k) is nonzero (original or permuted A)
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
71 octave_idx_type i = (Pinv) ? (Pinv[ridx[p]]) : (ridx[p]);
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
72 if (i < k)
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
73 {
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
74 // follow path from i to root of etree, stop at flagged node
15020
560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents: 14854
diff changeset
75 for ( ; Flag[i] != k ; i = Parent[i])
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
76 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
77 // find parent of i if not yet determined
15020
560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents: 14854
diff changeset
78 if (Parent[i] == n)
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
79 Parent[i] = k;
15020
560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents: 14854
diff changeset
80 Flag[i] = k ; // mark i as visited
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
81 }
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
82 }
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
83 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
84 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
85 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
86
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
87 // The elimination tree post-ordering code below is taken from SuperLU
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
88 static inline octave_idx_type
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
89 make_set (octave_idx_type i, octave_idx_type *pp)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
90 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
91 pp[i] = i;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
92 return i;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
93 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
94
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
95 static inline octave_idx_type
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
96 link (octave_idx_type s, octave_idx_type t, octave_idx_type *pp)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
97 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
98 pp[s] = t;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
99 return t;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
100 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
101
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
102 static inline octave_idx_type
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
103 find (octave_idx_type i, octave_idx_type *pp)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
104 {
21332
db574711df78 eliminate deprecated register storage class specifier
John W. Eaton <jwe@octave.org>
parents: 21301
diff changeset
105 octave_idx_type p = pp[i];
db574711df78 eliminate deprecated register storage class specifier
John W. Eaton <jwe@octave.org>
parents: 21301
diff changeset
106 octave_idx_type gp = pp[p];
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
107
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
108 while (gp != p)
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
109 {
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
110 pp[i] = gp;
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
111 i = gp;
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
112 p = pp[i];
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
113 gp = pp[p];
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
114 }
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
115
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
116 return p;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
117 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
118
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
119 static octave_idx_type
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
120 etdfs (octave_idx_type v, octave_idx_type *first_kid,
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
121 octave_idx_type *next_kid, octave_idx_type *post,
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
122 octave_idx_type postnum)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
123 {
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
124 for (octave_idx_type w = first_kid[v]; w != -1; w = next_kid[w])
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
125 postnum = etdfs (w, first_kid, next_kid, post, postnum);
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
126
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
127 post[postnum++] = v;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
128
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
129 return postnum;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
130 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
131
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
132 static void
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
133 tree_postorder (octave_idx_type n, octave_idx_type *parent,
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
134 octave_idx_type *post)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
135 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
136 // Allocate storage for working arrays and results
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
137 OCTAVE_LOCAL_BUFFER (octave_idx_type, first_kid, n+1);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
138 OCTAVE_LOCAL_BUFFER (octave_idx_type, next_kid, n+1);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
139
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
140 // Set up structure describing children
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
141 for (octave_idx_type v = 0; v <= n; first_kid[v++] = -1)
20946
6eff66fb8a02 style fixes for comments
John W. Eaton <jwe@octave.org>
parents: 20939
diff changeset
142 ; // do nothing
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
143
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
144 for (octave_idx_type v = n-1; v >= 0; v--)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
145 {
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
146 octave_idx_type dad = parent[v];
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
147 next_kid[v] = first_kid[dad];
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
148 first_kid[dad] = v;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
149 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
150
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
151 // Depth-first search from dummy root vertex #n
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
152 etdfs (n, first_kid, next_kid, post, 0);
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
153 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
154
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
155 static void
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
156 coletree (const octave_idx_type *ridx, const octave_idx_type *colbeg,
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
157 octave_idx_type *colend, octave_idx_type *parent,
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
158 octave_idx_type nr, octave_idx_type nc)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
159 {
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
160 OCTAVE_LOCAL_BUFFER (octave_idx_type, root, nc);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
161 OCTAVE_LOCAL_BUFFER (octave_idx_type, pp, nc);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
162 OCTAVE_LOCAL_BUFFER (octave_idx_type, firstcol, nr);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
163
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
164 // Compute firstcol[row] = first nonzero column in row
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
165 for (octave_idx_type row = 0; row < nr; firstcol[row++] = nc)
20946
6eff66fb8a02 style fixes for comments
John W. Eaton <jwe@octave.org>
parents: 20939
diff changeset
166 ; // do nothing
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
167
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
168 for (octave_idx_type col = 0; col < nc; col++)
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
169 for (octave_idx_type p = colbeg[col]; p < colend[col]; p++)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
170 {
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
171 octave_idx_type row = ridx[p];
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
172 if (firstcol[row] > col)
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
173 firstcol[row] = col;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
174 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
175
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
176 // Compute etree by Liu's algorithm for symmetric matrices,
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
177 // except use (firstcol[r],c) in place of an edge (r,c) of A.
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
178 // Thus each row clique in A'*A is replaced by a star
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
179 // centered at its first vertex, which has the same fill.
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
180 for (octave_idx_type col = 0; col < nc; col++)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
181 {
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
182 octave_idx_type cset = make_set (col, pp);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
183 root[cset] = col;
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
184 parent[col] = nc;
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
185 for (octave_idx_type p = colbeg[col]; p < colend[col]; p++)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
186 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
187 octave_idx_type row = firstcol[ridx[p]];
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
188 if (row >= col)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
189 continue;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
190 octave_idx_type rset = find (row, pp);
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
191 octave_idx_type rroot = root[rset];
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
192 if (rroot != col)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
193 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
194 parent[rroot] = col;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
195 cset = link (cset, rset, pp);
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
196 root[cset] = col;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
197 }
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
198 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
199 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
200 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
201
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
202 DEFUN_DLD (colamd, args, nargout,
21966
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
203 doc: /* -*- texinfo -*-
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
204 @deftypefn {} {@var{p} =} colamd (@var{S})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
205 @deftypefnx {} {@var{p} =} colamd (@var{S}, @var{knobs})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
206 @deftypefnx {} {[@var{p}, @var{stats}] =} colamd (@var{S})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
207 @deftypefnx {} {[@var{p}, @var{stats}] =} colamd (@var{S}, @var{knobs})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
208
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
209 Compute the column approximate minimum degree permutation.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
210
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
211 @code{@var{p} = colamd (@var{S})} returns the column approximate minimum
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
212 degree permutation vector for the sparse matrix @var{S}. For a
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
213 non-symmetric matrix @var{S}, @code{@var{S}(:,@var{p})} tends to have
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
214 sparser LU@tie{}factors than @var{S}. The Cholesky@tie{}factorization of
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
215 @code{@var{S}(:,@var{p})' * @var{S}(:,@var{p})} also tends to be sparser
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
216 than that of @code{@var{S}' * @var{S}}.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
217
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
218 @var{knobs} is an optional one- to three-element input vector. If @var{S}
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
219 is m-by-n, then rows with more than @code{max(16,@var{knobs}(1)*sqrt(n))}
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
220 entries are ignored. Columns with more than
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
221 @code{max (16,@var{knobs}(2)*sqrt(min(m,n)))} entries are removed prior to
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
222 ordering, and ordered last in the output permutation @var{p}. Only
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
223 completely dense rows or columns are removed if @code{@var{knobs}(1)} and
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
224 @code{@var{knobs}(2)} are < 0, respectively. If @code{@var{knobs}(3)} is
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
225 nonzero, @var{stats} and @var{knobs} are printed. The default is
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
226 @code{@var{knobs} = [10 10 0]}. Note that @var{knobs} differs from earlier
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
227 versions of colamd.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
228
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
229 @var{stats} is an optional 20-element output vector that provides data
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
230 about the ordering and the validity of the input matrix @var{S}. Ordering
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
231 statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1)} and
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
232 @code{@var{stats}(2)} are the number of dense or empty rows and columns
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
233 ignored by @sc{colamd} and @code{@var{stats}(3)} is the number of garbage
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
234 collections performed on the internal data structure used by @sc{colamd}
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
235 (roughly of size @code{2.2 * nnz(@var{S}) + 4 * @var{m} + 7 * @var{n}}
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
236 integers).
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
237
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
238 Octave built-in functions are intended to generate valid sparse matrices,
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
239 with no duplicate entries, with ascending row indices of the nonzeros
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
240 in each column, with a non-negative number of entries in each column (!)
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
241 and so on. If a matrix is invalid, then @sc{colamd} may or may not be able
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
242 to continue. If there are duplicate entries (a row index appears two or
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
243 more times in the same column) or if the row indices in a column are out
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
244 of order, then @sc{colamd} can correct these errors by ignoring the
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
245 duplicate entries and sorting each column of its internal copy of the
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
246 matrix @var{S} (the input matrix @var{S} is not repaired, however). If a
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
247 matrix is invalid in other ways then @sc{colamd} cannot continue, an error
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
248 message is printed, and no output arguments (@var{p} or @var{stats}) are
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
249 returned.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
250 @sc{colamd} is thus a simple way to check a sparse matrix to see if it's
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
251 valid.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
252
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
253 @code{@var{stats}(4:7)} provide information if @sc{colamd} was able to
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
254 continue. The matrix is OK if @code{@var{stats}(4)} is zero, or 1 if
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
255 invalid. @code{@var{stats}(5)} is the rightmost column index that is
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
256 unsorted or contains duplicate entries, or zero if no such column exists.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
257 @code{@var{stats}(6)} is the last seen duplicate or out-of-order row
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
258 index in the column index given by @code{@var{stats}(5)}, or zero if no
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
259 such row index exists. @code{@var{stats}(7)} is the number of duplicate
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
260 or out-of-order row indices. @code{@var{stats}(8:20)} is always zero in
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
261 the current version of @sc{colamd} (reserved for future use).
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
262
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
263 The ordering is followed by a column elimination tree post-ordering.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
264
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
265 The authors of the code itself are @nospell{Stefan I. Larimore} and
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
266 @nospell{Timothy A. Davis @email{davis@@cise.ufl.edu}}, University of Florida. The algorithm was developed in collaboration with @nospell{John Gilbert},
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
267 Xerox PARC, and @nospell{Esmond Ng}, Oak Ridge National Laboratory. (see
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
268 @url{http://www.cise.ufl.edu/research/sparse/colamd})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
269 @seealso{colperm, symamd, ccolamd}
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
270 @end deftypefn */)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
271 {
21724
aba2e6293dd8 use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents: 21691
diff changeset
272 #if defined (HAVE_COLAMD)
21691
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
273
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
274 int nargin = args.length ();
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
275
20909
03e4ddd49396 omit unnecessary nargout checks
John W. Eaton <jwe@octave.org>
parents: 20898
diff changeset
276 if (nargin < 1 || nargin > 2)
5823
080c08b192d8 [project @ 2006-05-19 05:32:17 by jwe]
jwe
parents: 5760
diff changeset
277 print_usage ();
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
278
20898
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
279 octave_value_list retval (nargout == 2 ? 2 : 1);
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
280 int spumoni = 0;
20862
ac1f8c640d8f 2015 Code Sprint: colamd.cc: use ovl().
Rik <rik@octave.org>
parents: 20853
diff changeset
281
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
282 // Get knobs
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
283 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
284 COLAMD_NAME (_set_defaults) (knobs);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
285
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
286 // Check for user-passed knobs
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
287 if (nargin == 2)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
288 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
289 NDArray User_knobs = args(1).array_value ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
290 int nel_User_knobs = User_knobs.numel ();
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
291
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
292 if (nel_User_knobs > 0)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
293 knobs[COLAMD_DENSE_ROW] = User_knobs(0);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
294 if (nel_User_knobs > 1)
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
295 knobs[COLAMD_DENSE_COL] = User_knobs(1);
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
296 if (nel_User_knobs > 2)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
297 spumoni = static_cast<int> (User_knobs(2));
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
298
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
299 // print knob settings if spumoni is set
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
300 if (spumoni)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
301 {
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
302
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
303 octave_stdout << "\ncolamd version " << COLAMD_MAIN_VERSION
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
304 << "." << COLAMD_SUB_VERSION
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
305 << ", " << COLAMD_DATE << ":\n";
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
306
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
307 if (knobs[COLAMD_DENSE_ROW] >= 0)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
308 octave_stdout << "knobs(1): " << User_knobs (0)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
309 << ", rows with > max (16,"
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
310 << knobs[COLAMD_DENSE_ROW] << "*sqrt (size(A,2)))"
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
311 << " entries removed\n";
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
312 else
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
313 octave_stdout << "knobs(1): " << User_knobs (0)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
314 << ", only completely dense rows removed\n";
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
315
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
316 if (knobs[COLAMD_DENSE_COL] >= 0)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
317 octave_stdout << "knobs(2): " << User_knobs (1)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
318 << ", cols with > max (16,"
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
319 << knobs[COLAMD_DENSE_COL] << "*sqrt (size(A)))"
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
320 << " entries removed\n";
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
321 else
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
322 octave_stdout << "knobs(2): " << User_knobs (1)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
323 << ", only completely dense columns removed\n";
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
324
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
325 octave_stdout << "knobs(3): " << User_knobs (2)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
326 << ", statistics and knobs printed\n";
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
327
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
328 }
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
329 }
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
330
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
331 octave_idx_type n_row, n_col, nnz;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
332 octave_idx_type *ridx, *cidx;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
333 SparseComplexMatrix scm;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
334 SparseMatrix sm;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
335
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
336 if (args(0).is_sparse_type ())
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
337 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
338 if (args(0).is_complex_type ())
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
339 {
21751
b571fc85953f maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents: 21724
diff changeset
340 scm = args(0).sparse_complex_matrix_value ();
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
341 n_row = scm.rows ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
342 n_col = scm.cols ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
343 nnz = scm.nnz ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
344 ridx = scm.xridx ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
345 cidx = scm.xcidx ();
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
346 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
347 else
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
348 {
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
349 sm = args(0).sparse_matrix_value ();
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
350
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
351 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
352 n_col = sm.cols ();
10527
b4d2080b6df7 Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents: 10282
diff changeset
353 nnz = sm.nnz ();
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
354 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
355 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
356 }
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
357 }
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
358 else
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
359 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
360 if (args(0).is_complex_type ())
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
361 sm = SparseMatrix (real (args(0).complex_matrix_value ()));
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
362 else
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
363 sm = SparseMatrix (args(0).matrix_value ());
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
364
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
365 n_row = sm.rows ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
366 n_col = sm.cols ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
367 nnz = sm.nnz ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
368 ridx = sm.xridx ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
369 cidx = sm.xcidx ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
370 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
371
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
372 // Allocate workspace for colamd
23391
209e749363a2 safe cast between SuiteSparse_long and octave_idx_type pointers (bug #50510)
John W. Eaton <jwe@octave.org>
parents: 23390
diff changeset
373 OCTAVE_LOCAL_BUFFER (octave::suitesparse_integer, p, n_col+1);
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
374 for (octave_idx_type i = 0; i < n_col+1; i++)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
375 p[i] = cidx[i];
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
376
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
377 octave_idx_type Alen = COLAMD_NAME (_recommended) (nnz, n_row, n_col);
23391
209e749363a2 safe cast between SuiteSparse_long and octave_idx_type pointers (bug #50510)
John W. Eaton <jwe@octave.org>
parents: 23390
diff changeset
378 OCTAVE_LOCAL_BUFFER (octave::suitesparse_integer, A, Alen);
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
379 for (octave_idx_type i = 0; i < nnz; i++)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
380 A[i] = ridx[i];
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
381
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
382 // Order the columns (destroys A)
23391
209e749363a2 safe cast between SuiteSparse_long and octave_idx_type pointers (bug #50510)
John W. Eaton <jwe@octave.org>
parents: 23390
diff changeset
383 OCTAVE_LOCAL_BUFFER (octave::suitesparse_integer, stats, COLAMD_STATS);
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
384 if (! COLAMD_NAME () (n_row, n_col, Alen, A, p, knobs, stats))
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
385 {
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
386 COLAMD_NAME (_report)(stats);
20825
66cd994d1b79 eliminate return statements after calls to error
John W. Eaton <jwe@octave.org>
parents: 20790
diff changeset
387
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
388 error ("colamd: internal error!");
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
389 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
390
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
391 // column elimination tree post-ordering (reuse variables)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
392 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col + 1);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
393 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col + 1);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
394 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
395
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
396 for (octave_idx_type i = 0; i < n_col; i++)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
397 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
398 colbeg[i] = cidx[p[i]];
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
399 colend[i] = cidx[p[i]+1];
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
400 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
401
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
402 coletree (ridx, colbeg, colend, etree, n_row, n_col);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
403
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
404 // Calculate the tree post-ordering
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
405 tree_postorder (n_col, etree, colbeg);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
406
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
407 // return the permutation vector
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
408 NDArray out_perm (dim_vector (1, n_col));
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
409 for (octave_idx_type i = 0; i < n_col; i++)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
410 out_perm(i) = p[colbeg[i]] + 1;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
411
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
412 retval(0) = out_perm;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
413
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
414 // print stats if spumoni > 0
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
415 if (spumoni > 0)
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
416 COLAMD_NAME (_report)(stats);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
417
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
418 // Return the stats vector
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
419 if (nargout == 2)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
420 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
421 NDArray out_stats (dim_vector (1, COLAMD_STATS));
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
422 for (octave_idx_type i = 0 ; i < COLAMD_STATS ; i++)
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
423 out_stats(i) = stats[i];
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
424 retval(1) = out_stats;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
425
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
426 // fix stats (5) and (6), for 1-based information on
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
427 // jumbled matrix. note that this correction doesn't
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
428 // occur if symamd returns FALSE
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
429 out_stats(COLAMD_INFO1)++;
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
430 out_stats(COLAMD_INFO2)++;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
431 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
432
20898
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
433 return retval;
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
434
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
435 #else
21691
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
436
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
437 octave_unused_parameter (args);
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
438 octave_unused_parameter (nargout);
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
439
21109
bd1752782e56 Use err_disabled_feature, warn_disabled_feature throughout code base.
Rik <rik@octave.org>
parents: 20955
diff changeset
440 err_disabled_feature ("colamd", "COLAMD");
21691
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
441
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
442 #endif
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
443 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
444
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
445 DEFUN_DLD (symamd, args, nargout,
21966
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
446 doc: /* -*- texinfo -*-
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
447 @deftypefn {} {@var{p} =} symamd (@var{S})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
448 @deftypefnx {} {@var{p} =} symamd (@var{S}, @var{knobs})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
449 @deftypefnx {} {[@var{p}, @var{stats}] =} symamd (@var{S})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
450 @deftypefnx {} {[@var{p}, @var{stats}] =} symamd (@var{S}, @var{knobs})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
451
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
452 For a symmetric positive definite matrix @var{S}, returns the permutation
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
453 vector p such that @code{@var{S}(@var{p}, @var{p})} tends to have a
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
454 sparser Cholesky@tie{}factor than @var{S}.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
455
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
456 Sometimes @code{symamd} works well for symmetric indefinite matrices too.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
457 The matrix @var{S} is assumed to be symmetric; only the strictly lower
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
458 triangular part is referenced. @var{S} must be square.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
459
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
460 @var{knobs} is an optional one- to two-element input vector. If @var{S} is
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
461 n-by-n, then rows and columns with more than
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
462 @code{max (16,@var{knobs}(1)*sqrt(n))} entries are removed prior to
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
463 ordering, and ordered last in the output permutation @var{p}. No
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
464 rows/columns are removed if @code{@var{knobs}(1) < 0}. If
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
465 @code{@var{knobs} (2)} is nonzero, @code{stats} and @var{knobs} are
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
466 printed. The default is @code{@var{knobs} = [10 0]}. Note that
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
467 @var{knobs} differs from earlier versions of @code{symamd}.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
468
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
469 @var{stats} is an optional 20-element output vector that provides data
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
470 about the ordering and the validity of the input matrix @var{S}. Ordering
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
471 statistics are in @code{@var{stats}(1:3)}.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
472 @code{@var{stats}(1) = @var{stats}(2)} is the number of dense or empty rows
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
473 and columns ignored by SYMAMD and @code{@var{stats}(3)} is the number of
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
474 garbage collections performed on the internal data structure used by SYMAMD
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
475 (roughly of size @code{8.4 * nnz (tril (@var{S}, -1)) + 9 * @var{n}}
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
476 integers).
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
477
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
478 Octave built-in functions are intended to generate valid sparse matrices,
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
479 with no duplicate entries, with ascending row indices of the nonzeros
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
480 in each column, with a non-negative number of entries in each column (!)
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
481 and so on. If a matrix is invalid, then SYMAMD may or may not be able
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
482 to continue. If there are duplicate entries (a row index appears two or
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
483 more times in the same column) or if the row indices in a column are out
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
484 of order, then SYMAMD can correct these errors by ignoring the duplicate
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
485 entries and sorting each column of its internal copy of the matrix S (the
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
486 input matrix S is not repaired, however). If a matrix is invalid in
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
487 other ways then SYMAMD cannot continue, an error message is printed, and
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
488 no output arguments (@var{p} or @var{stats}) are returned. SYMAMD is
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
489 thus a simple way to check a sparse matrix to see if it's valid.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
490
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
491 @code{@var{stats}(4:7)} provide information if SYMAMD was able to
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
492 continue. The matrix is OK if @code{@var{stats} (4)} is zero, or 1
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
493 if invalid. @code{@var{stats}(5)} is the rightmost column index that
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
494 is unsorted or contains duplicate entries, or zero if no such column
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
495 exists. @code{@var{stats}(6)} is the last seen duplicate or out-of-order
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
496 row index in the column index given by @code{@var{stats}(5)}, or zero
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
497 if no such row index exists. @code{@var{stats}(7)} is the number of
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
498 duplicate or out-of-order row indices. @code{@var{stats}(8:20)} is
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
499 always zero in the current version of SYMAMD (reserved for future use).
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
500
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
501 The ordering is followed by a column elimination tree post-ordering.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
502
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
503 The authors of the code itself are @nospell{Stefan I. Larimore} and
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
504 @nospell{Timothy A. Davis @email{davis@@cise.ufl.edu}}, University of Florida. The algorithm was developed in collaboration with @nospell{John Gilbert},
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
505 Xerox PARC, and @nospell{Esmond Ng}, Oak Ridge National Laboratory. (see
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
506 @url{http://www.cise.ufl.edu/research/sparse/colamd})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
507 @seealso{colperm, colamd}
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
508 @end deftypefn */)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
509 {
21724
aba2e6293dd8 use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents: 21691
diff changeset
510 #if defined (HAVE_COLAMD)
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
511
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
512 int nargin = args.length ();
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
513
20909
03e4ddd49396 omit unnecessary nargout checks
John W. Eaton <jwe@octave.org>
parents: 20898
diff changeset
514 if (nargin < 1 || nargin > 2)
5823
080c08b192d8 [project @ 2006-05-19 05:32:17 by jwe]
jwe
parents: 5760
diff changeset
515 print_usage ();
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
516
20898
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
517 octave_value_list retval (nargin == 2 ? 2 : 1);
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
518 int spumoni = 0;
20862
ac1f8c640d8f 2015 Code Sprint: colamd.cc: use ovl().
Rik <rik@octave.org>
parents: 20853
diff changeset
519
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
520 // Get knobs
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
521 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
522 COLAMD_NAME (_set_defaults) (knobs);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
523
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
524 // Check for user-passed knobs
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
525 if (nargin == 2)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
526 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
527 NDArray User_knobs = args(1).array_value ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
528 int nel_User_knobs = User_knobs.numel ();
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
529
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
530 if (nel_User_knobs > 0)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
531 knobs[COLAMD_DENSE_ROW] = User_knobs(COLAMD_DENSE_ROW);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
532 if (nel_User_knobs > 1)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
533 spumoni = static_cast<int> (User_knobs (1));
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
534 }
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
535
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
536 // print knob settings if spumoni is set
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
537 if (spumoni > 0)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
538 octave_stdout << "symamd: dense row/col fraction: "
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
539 << knobs[COLAMD_DENSE_ROW] << std::endl;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
540
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
541 octave_idx_type n_row, n_col;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
542 octave_idx_type *ridx, *cidx;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
543 SparseMatrix sm;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
544 SparseComplexMatrix scm;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
545
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
546 if (args(0).is_sparse_type ())
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
547 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
548 if (args(0).is_complex_type ())
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
549 {
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
550 scm = args(0).sparse_complex_matrix_value ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
551 n_row = scm.rows ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
552 n_col = scm.cols ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
553 ridx = scm.xridx ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
554 cidx = scm.xcidx ();
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
555 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
556 else
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
557 {
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
558 sm = args(0).sparse_matrix_value ();
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
559 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
560 n_col = sm.cols ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
561 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
562 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
563 }
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
564 }
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
565 else
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
566 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
567 if (args(0).is_complex_type ())
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
568 sm = SparseMatrix (real (args(0).complex_matrix_value ()));
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
569 else
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
570 sm = SparseMatrix (args(0).matrix_value ());
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
571
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
572 n_row = sm.rows ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
573 n_col = sm.cols ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
574 ridx = sm.xridx ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
575 cidx = sm.xcidx ();
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
576 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
577
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
578 if (n_row != n_col)
21110
3d0d84305600 Use err_square_matrix_required more widely.
Rik <rik@octave.org>
parents: 21109
diff changeset
579 err_square_matrix_required ("symamd", "S");
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
580
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
581 // Allocate workspace for symamd
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
582 OCTAVE_LOCAL_BUFFER (octave_idx_type, perm, n_col+1);
23391
209e749363a2 safe cast between SuiteSparse_long and octave_idx_type pointers (bug #50510)
John W. Eaton <jwe@octave.org>
parents: 23390
diff changeset
583 OCTAVE_LOCAL_BUFFER (octave::suitesparse_integer, stats, COLAMD_STATS);
209e749363a2 safe cast between SuiteSparse_long and octave_idx_type pointers (bug #50510)
John W. Eaton <jwe@octave.org>
parents: 23390
diff changeset
584 if (! SYMAMD_NAME () (n_col, octave::to_suitesparse_intptr (ridx),
209e749363a2 safe cast between SuiteSparse_long and octave_idx_type pointers (bug #50510)
John W. Eaton <jwe@octave.org>
parents: 23390
diff changeset
585 octave::to_suitesparse_intptr (cidx),
209e749363a2 safe cast between SuiteSparse_long and octave_idx_type pointers (bug #50510)
John W. Eaton <jwe@octave.org>
parents: 23390
diff changeset
586 octave::to_suitesparse_intptr (perm),
22407
34ce5be04942 maint: Style check C++ code in libinterp/.
Rik <rik@octave.org>
parents: 22323
diff changeset
587 knobs, stats, &calloc, &free))
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
588 {
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
589 SYMAMD_NAME (_report)(stats);
20825
66cd994d1b79 eliminate return statements after calls to error
John W. Eaton <jwe@octave.org>
parents: 20790
diff changeset
590
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
591 error ("symamd: internal error!");
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
592 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
593
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
594 // column elimination tree post-ordering
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
595 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
596 symetree (ridx, cidx, etree, perm, n_col);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
597
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
598 // Calculate the tree post-ordering
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
599 OCTAVE_LOCAL_BUFFER (octave_idx_type, post, n_col + 1);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
600 tree_postorder (n_col, etree, post);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
601
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
602 // return the permutation vector
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
603 NDArray out_perm (dim_vector (1, n_col));
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
604 for (octave_idx_type i = 0; i < n_col; i++)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
605 out_perm(i) = perm[post[i]] + 1;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
606
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
607 retval(0) = out_perm;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
608
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
609 // print stats if spumoni > 0
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
610 if (spumoni > 0)
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
611 SYMAMD_NAME (_report)(stats);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
612
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
613 // Return the stats vector
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
614 if (nargout == 2)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
615 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
616 NDArray out_stats (dim_vector (1, COLAMD_STATS));
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
617 for (octave_idx_type i = 0 ; i < COLAMD_STATS ; i++)
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
618 out_stats(i) = stats[i];
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
619 retval(1) = out_stats;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
620
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
621 // fix stats (5) and (6), for 1-based information on
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
622 // jumbled matrix. note that this correction doesn't
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
623 // occur if symamd returns FALSE
21602
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
624 out_stats(COLAMD_INFO1)++;
47c76e56a1de maint: Remove extra space between end of statement and semicolon.
Rik <rik@octave.org>
parents: 21547
diff changeset
625 out_stats(COLAMD_INFO2)++;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
626 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
627
20898
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
628 return retval;
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
629
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
630 #else
21691
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
631
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
632 octave_unused_parameter (args);
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
633 octave_unused_parameter (nargout);
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
634
21109
bd1752782e56 Use err_disabled_feature, warn_disabled_feature throughout code base.
Rik <rik@octave.org>
parents: 20955
diff changeset
635 err_disabled_feature ("symamd", "COLAMD");
21691
263d18409fdf Eliminate unused variable warnings for conditionally compiled code.
John W. Eaton <jwe@octave.org>
parents: 21602
diff changeset
636
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
637 #endif
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
638 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
639
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
640 DEFUN_DLD (etree, args, nargout,
21966
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
641 doc: /* -*- texinfo -*-
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
642 @deftypefn {} {@var{p} =} etree (@var{S})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
643 @deftypefnx {} {@var{p} =} etree (@var{S}, @var{typ})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
644 @deftypefnx {} {[@var{p}, @var{q}] =} etree (@var{S}, @var{typ})
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
645
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
646 Return the elimination tree for the matrix @var{S}.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
647
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
648 By default @var{S} is assumed to be symmetric and the symmetric elimination
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
649 tree is returned. The argument @var{typ} controls whether a symmetric or
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
650 column elimination tree is returned. Valid values of @var{typ} are
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
651 @qcode{"sym"} or @qcode{"col"}, for symmetric or column elimination tree
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
652 respectively.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
653
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
654 Called with a second argument, @code{etree} also returns the postorder
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
655 permutations on the tree.
112b20240c87 move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents: 21751
diff changeset
656 @end deftypefn */)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
657 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
658 int nargin = args.length ();
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
659
20909
03e4ddd49396 omit unnecessary nargout checks
John W. Eaton <jwe@octave.org>
parents: 20898
diff changeset
660 if (nargin < 1 || nargin > 2)
5823
080c08b192d8 [project @ 2006-05-19 05:32:17 by jwe]
jwe
parents: 5760
diff changeset
661 print_usage ();
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
662
20898
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
663 octave_value_list retval (nargout == 2 ? 2 : 1);
20862
ac1f8c640d8f 2015 Code Sprint: colamd.cc: use ovl().
Rik <rik@octave.org>
parents: 20853
diff changeset
664
20898
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
665 octave_idx_type n_row = 0;
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
666 octave_idx_type n_col = 0;
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
667 octave_idx_type *ridx = 0;
8da80da1ac37 maint: Use ovl() more places in the code.
Rik <rik@octave.org>
parents: 20862
diff changeset
668 octave_idx_type *cidx = 0;
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
669
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
670 if (args(0).is_sparse_type ())
20939
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
671 error ("etree: S must be a sparse matrix");
20825
66cd994d1b79 eliminate return statements after calls to error
John W. Eaton <jwe@octave.org>
parents: 20790
diff changeset
672
20939
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
673 if (args(0).is_complex_type ())
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
674 {
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
675 SparseComplexMatrix scm = args(0).sparse_complex_matrix_value ();
20825
66cd994d1b79 eliminate return statements after calls to error
John W. Eaton <jwe@octave.org>
parents: 20790
diff changeset
676
20939
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
677 n_row = scm.rows ();
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
678 n_col = scm.cols ();
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
679 ridx = scm.xridx ();
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
680 cidx = scm.xcidx ();
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
681 }
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
682 else
20939
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
683 {
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
684 SparseMatrix sm = args(0).sparse_matrix_value ();
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
685
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
686 n_row = sm.rows ();
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
687 n_col = sm.cols ();
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
688 ridx = sm.xridx ();
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
689 cidx = sm.xcidx ();
b17fda023ca6 maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents: 20909
diff changeset
690 }
20825
66cd994d1b79 eliminate return statements after calls to error
John W. Eaton <jwe@octave.org>
parents: 20790
diff changeset
691
66cd994d1b79 eliminate return statements after calls to error
John W. Eaton <jwe@octave.org>
parents: 20790
diff changeset
692 bool is_sym = true;
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
693
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
694 if (nargin == 2)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
695 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
696 std::string str = args(1).xstring_value ("etree: TYP must be a string");
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
697 if (str.find ("C") == 0 || str.find ("c") == 0)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
698 is_sym = false;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
699 }
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
700
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
701 // column elimination tree post-ordering (reuse variables)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
702 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
703
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
704 if (is_sym)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
705 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
706 if (n_row != n_col)
20825
66cd994d1b79 eliminate return statements after calls to error
John W. Eaton <jwe@octave.org>
parents: 20790
diff changeset
707 error ("etree: S is marked as symmetric, but is not square");
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
708
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
709 symetree (ridx, cidx, etree, 0, n_col);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
710 }
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
711 else
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
712 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
713 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
714 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
715
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
716 for (octave_idx_type i = 0; i < n_col; i++)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
717 {
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
718 colbeg[i] = cidx[i];
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
719 colend[i] = cidx[i+1];
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
720 }
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
721
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
722 coletree (ridx, colbeg, colend, etree, n_row, n_col);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
723 }
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
724
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
725 NDArray tree (dim_vector (1, n_col));
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
726 for (octave_idx_type i = 0; i < n_col; i++)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
727 // We flag a root with n_col while Matlab does it with zero
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
728 // Convert for matlab compatiable output
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
729 if (etree[i] == n_col)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
730 tree(i) = 0;
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
731 else
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
732 tree(i) = etree[i] + 1;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
733
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
734 retval(0) = tree;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
735
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
736 if (nargout == 2)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
737 {
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
738 // Calculate the tree post-ordering
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
739 OCTAVE_LOCAL_BUFFER (octave_idx_type, post, n_col + 1);
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
740 tree_postorder (n_col, etree, post);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
741
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
742 NDArray postorder (dim_vector (1, n_col));
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
743 for (octave_idx_type i = 0; i < n_col; i++)
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
744 postorder(i) = post[i] + 1;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
745
20790
c2d9556d51d0 eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents: 20700
diff changeset
746 retval(1) = postorder;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
747 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
748
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
749 return retval;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
750 }