Mercurial > octave-nkf
annotate libinterp/dldfcn/colamd.cc @ 17787:175b392e91fe
Use GNU style coding conventions for code in libinterp/
* libinterp/corefcn/Cell.h, libinterp/corefcn/__contourc__.cc,
libinterp/corefcn/__dispatch__.cc, libinterp/corefcn/__lin_interpn__.cc,
libinterp/corefcn/__pchip_deriv__.cc, libinterp/corefcn/__qp__.cc,
libinterp/corefcn/balance.cc, libinterp/corefcn/besselj.cc,
libinterp/corefcn/betainc.cc, libinterp/corefcn/bitfcns.cc,
libinterp/corefcn/bsxfun.cc, libinterp/corefcn/c-file-ptr-stream.cc,
libinterp/corefcn/c-file-ptr-stream.h, libinterp/corefcn/cellfun.cc,
libinterp/corefcn/colloc.cc, libinterp/corefcn/comment-list.h,
libinterp/corefcn/conv2.cc, libinterp/corefcn/daspk.cc,
libinterp/corefcn/dasrt.cc, libinterp/corefcn/dassl.cc,
libinterp/corefcn/data.cc, libinterp/corefcn/debug.cc,
libinterp/corefcn/defaults.cc, libinterp/corefcn/defaults.in.h,
libinterp/corefcn/defun-int.h, libinterp/corefcn/defun.cc,
libinterp/corefcn/det.cc, libinterp/corefcn/dirfns.cc,
libinterp/corefcn/display.cc, libinterp/corefcn/dlmread.cc,
libinterp/corefcn/dot.cc, libinterp/corefcn/dynamic-ld.cc,
libinterp/corefcn/dynamic-ld.h, libinterp/corefcn/eig.cc,
libinterp/corefcn/ellipj.cc, libinterp/corefcn/error.cc,
libinterp/corefcn/error.h, libinterp/corefcn/event-queue.h,
libinterp/corefcn/fft.cc, libinterp/corefcn/fft2.cc, libinterp/corefcn/fftn.cc,
libinterp/corefcn/file-io.cc, libinterp/corefcn/filter.cc,
libinterp/corefcn/find.cc, libinterp/corefcn/gammainc.cc,
libinterp/corefcn/gcd.cc, libinterp/corefcn/getgrent.cc,
libinterp/corefcn/getpwent.cc, libinterp/corefcn/getrusage.cc,
libinterp/corefcn/givens.cc, libinterp/corefcn/gl-render.cc,
libinterp/corefcn/gl2ps-renderer.cc, libinterp/corefcn/gl2ps-renderer.h,
libinterp/corefcn/graphics.cc, libinterp/corefcn/graphics.in.h,
libinterp/corefcn/gripes.cc, libinterp/corefcn/gripes.h,
libinterp/corefcn/help.cc, libinterp/corefcn/hess.cc,
libinterp/corefcn/hex2num.cc, libinterp/corefcn/input.cc,
libinterp/corefcn/input.h, libinterp/corefcn/inv.cc,
libinterp/corefcn/jit-ir.h, libinterp/corefcn/jit-typeinfo.cc,
libinterp/corefcn/jit-typeinfo.h, libinterp/corefcn/jit-util.h,
libinterp/corefcn/kron.cc, libinterp/corefcn/load-path.cc,
libinterp/corefcn/load-path.h, libinterp/corefcn/load-save.cc,
libinterp/corefcn/load-save.h, libinterp/corefcn/lookup.cc,
libinterp/corefcn/ls-ascii-helper.cc, libinterp/corefcn/ls-hdf5.cc,
libinterp/corefcn/ls-hdf5.h, libinterp/corefcn/ls-mat-ascii.cc,
libinterp/corefcn/ls-mat-ascii.h, libinterp/corefcn/ls-mat4.cc,
libinterp/corefcn/ls-mat5.cc, libinterp/corefcn/ls-mat5.h,
libinterp/corefcn/ls-oct-ascii.cc, libinterp/corefcn/lsode.cc,
libinterp/corefcn/lu.cc, libinterp/corefcn/luinc.cc,
libinterp/corefcn/mappers.cc, libinterp/corefcn/matrix_type.cc,
libinterp/corefcn/max.cc, libinterp/corefcn/md5sum.cc,
libinterp/corefcn/mex.cc, libinterp/corefcn/mexproto.h,
libinterp/corefcn/mgorth.cc, libinterp/corefcn/mxarray.in.h,
libinterp/corefcn/nproc.cc, libinterp/corefcn/oct-hist.cc,
libinterp/corefcn/oct-lvalue.h, libinterp/corefcn/oct-map.cc,
libinterp/corefcn/oct-map.h, libinterp/corefcn/oct-obj.h,
libinterp/corefcn/oct-prcstrm.h, libinterp/corefcn/oct-stdstrm.h,
libinterp/corefcn/oct-stream.cc, libinterp/corefcn/oct-stream.h,
libinterp/corefcn/octave-link.cc, libinterp/corefcn/octave-link.h,
libinterp/corefcn/pager.cc, libinterp/corefcn/pinv.cc,
libinterp/corefcn/pr-output.cc, libinterp/corefcn/procstream.h,
libinterp/corefcn/profiler.cc, libinterp/corefcn/pt-jit.cc,
libinterp/corefcn/pt-jit.h, libinterp/corefcn/quad.cc,
libinterp/corefcn/quadcc.cc, libinterp/corefcn/qz.cc,
libinterp/corefcn/rand.cc, libinterp/corefcn/rcond.cc,
libinterp/corefcn/regexp.cc, libinterp/corefcn/schur.cc,
libinterp/corefcn/sighandlers.cc, libinterp/corefcn/sighandlers.h,
libinterp/corefcn/sparse-xdiv.cc, libinterp/corefcn/sparse-xdiv.h,
libinterp/corefcn/sparse-xpow.cc, libinterp/corefcn/sparse.cc,
libinterp/corefcn/spparms.cc, libinterp/corefcn/sqrtm.cc,
libinterp/corefcn/str2double.cc, libinterp/corefcn/strfind.cc,
libinterp/corefcn/strfns.cc, libinterp/corefcn/sub2ind.cc,
libinterp/corefcn/svd.cc, libinterp/corefcn/syl.cc,
libinterp/corefcn/symtab.cc, libinterp/corefcn/symtab.h,
libinterp/corefcn/syscalls.cc, libinterp/corefcn/sysdep.cc,
libinterp/corefcn/sysdep.h, libinterp/corefcn/time.cc,
libinterp/corefcn/toplev.cc, libinterp/corefcn/toplev.h,
libinterp/corefcn/tril.cc, libinterp/corefcn/txt-eng-ft.cc,
libinterp/corefcn/txt-eng-ft.h, libinterp/corefcn/txt-eng.h,
libinterp/corefcn/typecast.cc, libinterp/corefcn/urlwrite.cc,
libinterp/corefcn/utils.cc, libinterp/corefcn/variables.cc,
libinterp/corefcn/variables.h, libinterp/corefcn/xdiv.cc,
libinterp/corefcn/xdiv.h, libinterp/corefcn/xnorm.h, libinterp/corefcn/xpow.cc,
libinterp/corefcn/xpow.h, libinterp/corefcn/zfstream.cc,
libinterp/corefcn/zfstream.h, libinterp/dldfcn/__delaunayn__.cc,
libinterp/dldfcn/__dsearchn__.cc, libinterp/dldfcn/__eigs__.cc,
libinterp/dldfcn/__fltk_uigetfile__.cc, libinterp/dldfcn/__glpk__.cc,
libinterp/dldfcn/__init_fltk__.cc, libinterp/dldfcn/__init_gnuplot__.cc,
libinterp/dldfcn/__magick_read__.cc, libinterp/dldfcn/__voronoi__.cc,
libinterp/dldfcn/amd.cc, libinterp/dldfcn/ccolamd.cc, libinterp/dldfcn/chol.cc,
libinterp/dldfcn/colamd.cc, libinterp/dldfcn/convhulln.cc,
libinterp/dldfcn/dmperm.cc, libinterp/dldfcn/fftw.cc, libinterp/dldfcn/qr.cc,
libinterp/dldfcn/symbfact.cc, libinterp/dldfcn/symrcm.cc,
libinterp/dldfcn/tsearch.cc, libinterp/octave-value/ov-base-diag.cc,
libinterp/octave-value/ov-base-diag.h, libinterp/octave-value/ov-base-int.cc,
libinterp/octave-value/ov-base-int.h, libinterp/octave-value/ov-base-mat.h,
libinterp/octave-value/ov-base-scalar.cc,
libinterp/octave-value/ov-base-scalar.h,
libinterp/octave-value/ov-base-sparse.cc,
libinterp/octave-value/ov-base-sparse.h, libinterp/octave-value/ov-base.cc,
libinterp/octave-value/ov-base.h, libinterp/octave-value/ov-bool-mat.cc,
libinterp/octave-value/ov-bool-mat.h, libinterp/octave-value/ov-bool-sparse.cc,
libinterp/octave-value/ov-bool-sparse.h, libinterp/octave-value/ov-bool.cc,
libinterp/octave-value/ov-bool.h, libinterp/octave-value/ov-builtin.cc,
libinterp/octave-value/ov-builtin.h, libinterp/octave-value/ov-cell.cc,
libinterp/octave-value/ov-cell.h, libinterp/octave-value/ov-ch-mat.cc,
libinterp/octave-value/ov-ch-mat.h, libinterp/octave-value/ov-class.cc,
libinterp/octave-value/ov-class.h, libinterp/octave-value/ov-colon.h,
libinterp/octave-value/ov-complex.cc, libinterp/octave-value/ov-complex.h,
libinterp/octave-value/ov-cx-diag.cc, libinterp/octave-value/ov-cx-diag.h,
libinterp/octave-value/ov-cx-mat.cc, libinterp/octave-value/ov-cx-mat.h,
libinterp/octave-value/ov-cx-sparse.cc, libinterp/octave-value/ov-cx-sparse.h,
libinterp/octave-value/ov-dld-fcn.h, libinterp/octave-value/ov-fcn-handle.cc,
libinterp/octave-value/ov-fcn-handle.h,
libinterp/octave-value/ov-fcn-inline.cc,
libinterp/octave-value/ov-fcn-inline.h, libinterp/octave-value/ov-fcn.h,
libinterp/octave-value/ov-float.cc, libinterp/octave-value/ov-float.h,
libinterp/octave-value/ov-flt-complex.cc,
libinterp/octave-value/ov-flt-complex.h,
libinterp/octave-value/ov-flt-cx-diag.cc,
libinterp/octave-value/ov-flt-cx-diag.h,
libinterp/octave-value/ov-flt-cx-mat.cc,
libinterp/octave-value/ov-flt-cx-mat.h,
libinterp/octave-value/ov-flt-re-diag.cc,
libinterp/octave-value/ov-flt-re-diag.h,
libinterp/octave-value/ov-flt-re-mat.cc,
libinterp/octave-value/ov-flt-re-mat.h, libinterp/octave-value/ov-int16.cc,
libinterp/octave-value/ov-int32.cc, libinterp/octave-value/ov-int64.cc,
libinterp/octave-value/ov-int8.cc, libinterp/octave-value/ov-intx.h,
libinterp/octave-value/ov-java.cc, libinterp/octave-value/ov-lazy-idx.h,
libinterp/octave-value/ov-mex-fcn.cc, libinterp/octave-value/ov-mex-fcn.h,
libinterp/octave-value/ov-null-mat.cc, libinterp/octave-value/ov-null-mat.h,
libinterp/octave-value/ov-oncleanup.cc, libinterp/octave-value/ov-perm.cc,
libinterp/octave-value/ov-perm.h, libinterp/octave-value/ov-range.cc,
libinterp/octave-value/ov-range.h, libinterp/octave-value/ov-re-diag.cc,
libinterp/octave-value/ov-re-diag.h, libinterp/octave-value/ov-re-mat.cc,
libinterp/octave-value/ov-re-mat.h, libinterp/octave-value/ov-re-sparse.cc,
libinterp/octave-value/ov-re-sparse.h, libinterp/octave-value/ov-scalar.cc,
libinterp/octave-value/ov-scalar.h, libinterp/octave-value/ov-str-mat.cc,
libinterp/octave-value/ov-str-mat.h, libinterp/octave-value/ov-struct.cc,
libinterp/octave-value/ov-struct.h, libinterp/octave-value/ov-type-conv.h,
libinterp/octave-value/ov-typeinfo.cc, libinterp/octave-value/ov-typeinfo.h,
libinterp/octave-value/ov-uint16.cc, libinterp/octave-value/ov-uint32.cc,
libinterp/octave-value/ov-uint64.cc, libinterp/octave-value/ov-uint8.cc,
libinterp/octave-value/ov-usr-fcn.cc, libinterp/octave-value/ov-usr-fcn.h,
libinterp/octave-value/ov.cc, libinterp/octave-value/ov.h, libinterp/octave.cc,
libinterp/operators/op-b-bm.cc, libinterp/operators/op-b-sbm.cc,
libinterp/operators/op-bm-b.cc, libinterp/operators/op-bm-bm.cc,
libinterp/operators/op-cdm-cdm.cc, libinterp/operators/op-chm.cc,
libinterp/operators/op-class.cc, libinterp/operators/op-cm-cm.cc,
libinterp/operators/op-cm-cs.cc, libinterp/operators/op-cm-s.cc,
libinterp/operators/op-cm-scm.cc, libinterp/operators/op-cm-sm.cc,
libinterp/operators/op-cs-cm.cc, libinterp/operators/op-cs-cs.cc,
libinterp/operators/op-cs-scm.cc, libinterp/operators/op-cs-sm.cc,
libinterp/operators/op-dm-dm.cc, libinterp/operators/op-dm-scm.cc,
libinterp/operators/op-double-conv.cc, libinterp/operators/op-fcdm-fcdm.cc,
libinterp/operators/op-fcm-fcm.cc, libinterp/operators/op-fcm-fcs.cc,
libinterp/operators/op-fcm-fm.cc, libinterp/operators/op-fcm-fs.cc,
libinterp/operators/op-fcs-fcm.cc, libinterp/operators/op-fcs-fcs.cc,
libinterp/operators/op-fcs-fm.cc, libinterp/operators/op-fcs-fs.cc,
libinterp/operators/op-fdm-fdm.cc, libinterp/operators/op-float-conv.cc,
libinterp/operators/op-fm-fcm.cc, libinterp/operators/op-fm-fcs.cc,
libinterp/operators/op-fm-fm.cc, libinterp/operators/op-fm-fs.cc,
libinterp/operators/op-fs-fcm.cc, libinterp/operators/op-fs-fcs.cc,
libinterp/operators/op-fs-fm.cc, libinterp/operators/op-fs-fs.cc,
libinterp/operators/op-m-cm.cc, libinterp/operators/op-m-cs.cc,
libinterp/operators/op-m-m.cc, libinterp/operators/op-m-s.cc,
libinterp/operators/op-m-scm.cc, libinterp/operators/op-m-sm.cc,
libinterp/operators/op-pm-scm.cc, libinterp/operators/op-range.cc,
libinterp/operators/op-s-cm.cc, libinterp/operators/op-s-cs.cc,
libinterp/operators/op-s-scm.cc, libinterp/operators/op-sbm-b.cc,
libinterp/operators/op-sbm-bm.cc, libinterp/operators/op-sbm-sbm.cc,
libinterp/operators/op-scm-cm.cc, libinterp/operators/op-scm-cs.cc,
libinterp/operators/op-scm-m.cc, libinterp/operators/op-scm-s.cc,
libinterp/operators/op-scm-scm.cc, libinterp/operators/op-scm-sm.cc,
libinterp/operators/op-sm-cm.cc, libinterp/operators/op-sm-m.cc,
libinterp/operators/op-sm-s.cc, libinterp/operators/op-sm-scm.cc,
libinterp/operators/op-sm-sm.cc, libinterp/operators/op-str-m.cc,
libinterp/operators/op-str-s.cc, libinterp/operators/op-str-str.cc,
libinterp/operators/ops.h, libinterp/parse-tree/lex.h,
libinterp/parse-tree/parse.h, libinterp/parse-tree/pt-arg-list.cc,
libinterp/parse-tree/pt-arg-list.h, libinterp/parse-tree/pt-assign.cc,
libinterp/parse-tree/pt-assign.h, libinterp/parse-tree/pt-binop.cc,
libinterp/parse-tree/pt-binop.h, libinterp/parse-tree/pt-bp.h,
libinterp/parse-tree/pt-cbinop.cc, libinterp/parse-tree/pt-check.cc,
libinterp/parse-tree/pt-colon.cc, libinterp/parse-tree/pt-colon.h,
libinterp/parse-tree/pt-const.cc, libinterp/parse-tree/pt-decl.cc,
libinterp/parse-tree/pt-decl.h, libinterp/parse-tree/pt-eval.cc,
libinterp/parse-tree/pt-except.h, libinterp/parse-tree/pt-exp.h,
libinterp/parse-tree/pt-fcn-handle.cc, libinterp/parse-tree/pt-id.cc,
libinterp/parse-tree/pt-id.h, libinterp/parse-tree/pt-idx.cc,
libinterp/parse-tree/pt-idx.h, libinterp/parse-tree/pt-loop.h,
libinterp/parse-tree/pt-mat.cc, libinterp/parse-tree/pt-misc.cc,
libinterp/parse-tree/pt-misc.h, libinterp/parse-tree/pt-pr-code.cc,
libinterp/parse-tree/pt-select.h, libinterp/parse-tree/pt-stmt.h,
libinterp/parse-tree/token.h, libinterp/version.cc:
Use GNU style coding conventions for code in libinterp/
| author | Rik <rik@octave.org> |
|---|---|
| date | Mon, 28 Oct 2013 19:51:46 -0700 |
| parents | d63878346099 |
| children | 0850b5212619 |
| rev | line source |
|---|---|
| 5164 | 1 /* |
| 2 | |
|
17744
d63878346099
maint: Update copyright notices for release.
John W. Eaton <jwe@octave.org>
parents:
17281
diff
changeset
|
3 Copyright (C) 2004-2013 David Bateman |
| 11523 | 4 Copyright (C) 1998-2004 Andy Adler |
| 7016 | 5 |
| 6 This file is part of Octave. | |
| 5164 | 7 |
| 8 Octave is free software; you can redistribute it and/or modify it | |
| 9 under the terms of the GNU General Public License as published by the | |
| 7016 | 10 Free Software Foundation; either version 3 of the License, or (at your |
| 11 option) any later version. | |
| 5164 | 12 |
| 13 Octave is distributed in the hope that it will be useful, but WITHOUT | |
| 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 16 for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
| 7016 | 19 along with Octave; see the file COPYING. If not, see |
| 20 <http://www.gnu.org/licenses/>. | |
| 5164 | 21 |
| 22 */ | |
| 23 | |
| 24 // This is the octave interface to colamd, which bore the copyright given | |
| 25 // in the help of the functions. | |
| 26 | |
| 27 #ifdef HAVE_CONFIG_H | |
| 28 #include <config.h> | |
| 29 #endif | |
| 30 | |
| 31 #include <cstdlib> | |
| 32 | |
| 33 #include <string> | |
| 34 #include <vector> | |
| 35 | |
| 36 #include "ov.h" | |
| 37 #include "defun-dld.h" | |
| 38 #include "pager.h" | |
| 39 #include "ov-re-mat.h" | |
| 40 | |
| 41 #include "ov-re-sparse.h" | |
| 42 #include "ov-cx-sparse.h" | |
| 43 | |
| 5451 | 44 #include "oct-sparse.h" |
|
8377
25bc2d31e1bf
improve OCTAVE_LOCAL_BUFFER
Jaroslav Hajek <highegg@gmail.com>
parents:
7924
diff
changeset
|
45 #include "oct-locbuf.h" |
| 5164 | 46 |
|
16313
6aafe87a3144
use int64_t for idx type if --enable-64
John W. Eaton <jwe@octave.org>
parents:
15195
diff
changeset
|
47 #ifdef USE_64_BIT_IDX_T |
| 5440 | 48 #define COLAMD_NAME(name) colamd_l ## name |
| 49 #define SYMAMD_NAME(name) symamd_l ## name | |
| 50 #else | |
| 51 #define COLAMD_NAME(name) colamd ## name | |
| 52 #define SYMAMD_NAME(name) symamd ## name | |
| 53 #endif | |
| 54 | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
55 // The symmetric column elimination tree code take from the Davis LDL code. |
| 5164 | 56 // Copyright given elsewhere in this file. |
| 7924 | 57 static void |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
58 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
|
59 octave_idx_type *Parent, octave_idx_type *P, octave_idx_type n) |
| 5164 | 60 { |
| 5440 | 61 OCTAVE_LOCAL_BUFFER (octave_idx_type, Flag, n); |
| 62 OCTAVE_LOCAL_BUFFER (octave_idx_type, Pinv, (P ? n : 0)); | |
| 5164 | 63 if (P) |
| 64 // If P is present then compute Pinv, the inverse of P | |
| 5440 | 65 for (octave_idx_type k = 0 ; k < n ; k++) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
66 Pinv[P[k]] = k ; |
| 5164 | 67 |
| 5440 | 68 for (octave_idx_type k = 0 ; k < n ; k++) |
| 5164 | 69 { |
| 70 // 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
|
71 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
|
72 Flag[k] = k ; // mark node k as visited |
|
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
73 octave_idx_type kk = (P) ? P[k] // kth original, or permuted, column |
|
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
74 : (k) ; |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
75 octave_idx_type p2 = cidx[kk+1] ; |
|
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
76 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
|
77 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
78 // A (i,k) is nonzero (original or permuted A) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
79 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
|
80 if (i < k) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
81 { |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
82 // 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
|
83 for ( ; Flag[i] != k ; i = Parent[i]) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
84 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
85 // 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
|
86 if (Parent[i] == n) |
|
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
87 Parent[i] = k ; |
|
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
88 Flag[i] = k ; // mark i as visited |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
89 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
90 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
91 } |
| 5164 | 92 } |
| 93 } | |
| 94 | |
| 95 // The elimination tree post-ordering code below is taken from SuperLU | |
| 7924 | 96 static inline octave_idx_type |
| 97 make_set (octave_idx_type i, octave_idx_type *pp) | |
| 5164 | 98 { |
| 99 pp[i] = i; | |
| 100 return i; | |
| 101 } | |
| 102 | |
| 7924 | 103 static inline octave_idx_type |
| 104 link (octave_idx_type s, octave_idx_type t, octave_idx_type *pp) | |
| 5164 | 105 { |
| 106 pp[s] = t; | |
| 107 return t; | |
| 108 } | |
| 109 | |
| 7924 | 110 static inline octave_idx_type |
| 111 find (octave_idx_type i, octave_idx_type *pp) | |
| 5164 | 112 { |
| 5440 | 113 register octave_idx_type p, gp; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
114 |
| 5164 | 115 p = pp[i]; |
| 116 gp = pp[p]; | |
| 7924 | 117 |
| 118 while (gp != p) | |
| 119 { | |
| 120 pp[i] = gp; | |
| 121 i = gp; | |
| 122 p = pp[i]; | |
| 123 gp = pp[p]; | |
| 124 } | |
| 125 | |
| 126 return p; | |
| 5164 | 127 } |
| 128 | |
| 7924 | 129 static octave_idx_type |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
130 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
|
131 octave_idx_type *next_kid, octave_idx_type *post, |
| 7924 | 132 octave_idx_type postnum) |
| 5164 | 133 { |
| 7924 | 134 for (octave_idx_type w = first_kid[v]; w != -1; w = next_kid[w]) |
| 5164 | 135 postnum = etdfs (w, first_kid, next_kid, post, postnum); |
| 7924 | 136 |
| 5164 | 137 post[postnum++] = v; |
| 138 | |
| 139 return postnum; | |
| 140 } | |
| 141 | |
| 7924 | 142 static void |
| 143 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
|
144 octave_idx_type *post) |
| 5164 | 145 { |
| 146 // Allocate storage for working arrays and results | |
| 5440 | 147 OCTAVE_LOCAL_BUFFER (octave_idx_type, first_kid, n+1); |
| 148 OCTAVE_LOCAL_BUFFER (octave_idx_type, next_kid, n+1); | |
| 5164 | 149 |
| 150 // Set up structure describing children | |
| 7924 | 151 for (octave_idx_type v = 0; v <= n; first_kid[v++] = -1) |
| 152 /* do nothing */; | |
| 153 | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
154 for (octave_idx_type v = n-1; v >= 0; v--) |
| 5164 | 155 { |
| 5440 | 156 octave_idx_type dad = parent[v]; |
| 5164 | 157 next_kid[v] = first_kid[dad]; |
| 158 first_kid[dad] = v; | |
| 159 } | |
| 160 | |
| 161 // Depth-first search from dummy root vertex #n | |
| 162 etdfs (n, first_kid, next_kid, post, 0); | |
| 163 } | |
| 164 | |
| 7924 | 165 static void |
| 166 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
|
167 octave_idx_type *colend, octave_idx_type *parent, |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
168 octave_idx_type nr, octave_idx_type nc) |
| 5164 | 169 { |
| 5440 | 170 OCTAVE_LOCAL_BUFFER (octave_idx_type, root, nc); |
| 171 OCTAVE_LOCAL_BUFFER (octave_idx_type, pp, nc); | |
| 172 OCTAVE_LOCAL_BUFFER (octave_idx_type, firstcol, nr); | |
| 5164 | 173 |
| 174 // Compute firstcol[row] = first nonzero column in row | |
| 7924 | 175 for (octave_idx_type row = 0; row < nr; firstcol[row++] = nc) |
| 176 /* do nothing */; | |
| 177 | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
178 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
|
179 for (octave_idx_type p = colbeg[col]; p < colend[col]; p++) |
| 5164 | 180 { |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
181 octave_idx_type row = ridx[p]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
182 if (firstcol[row] > col) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
183 firstcol[row] = col; |
| 5164 | 184 } |
| 185 | |
| 186 // Compute etree by Liu's algorithm for symmetric matrices, | |
| 187 // except use (firstcol[r],c) in place of an edge (r,c) of A. | |
| 188 // Thus each row clique in A'*A is replaced by a star | |
| 189 // 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
|
190 for (octave_idx_type col = 0; col < nc; col++) |
| 5164 | 191 { |
| 5440 | 192 octave_idx_type cset = make_set (col, pp); |
| 5164 | 193 root[cset] = col; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
194 parent[col] = nc; |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
195 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
|
196 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
197 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
|
198 if (row >= col) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
199 continue; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
200 octave_idx_type rset = find (row, pp); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
201 octave_idx_type rroot = root[rset]; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
202 if (rroot != col) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
203 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
204 parent[rroot] = col; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
205 cset = link (cset, rset, pp); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
206 root[cset] = col; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
207 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
208 } |
| 5164 | 209 } |
| 210 } | |
| 211 | |
| 212 DEFUN_DLD (colamd, args, nargout, | |
|
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
213 "-*- texinfo -*-\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
214 @deftypefn {Loadable Function} {@var{p} =} colamd (@var{S})\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
215 @deftypefnx {Loadable Function} {@var{p} =} colamd (@var{S}, @var{knobs})\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
216 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{S})\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
217 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{S}, @var{knobs})\n\ |
| 5164 | 218 \n\ |
| 10840 | 219 Column approximate minimum degree permutation.\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
220 @code{@var{p} = colamd (@var{S})} returns the column approximate minimum\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
221 degree permutation vector for the sparse matrix @var{S}. For a\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
222 non-symmetric matrix @var{S}, @code{@var{S}(:,@var{p})} tends to have\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
223 sparser LU@tie{}factors than @var{S}. The Cholesky@tie{}factorization of\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
224 @code{@var{S}(:,@var{p})' * @var{S}(:,@var{p})} also tends to be sparser\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
225 than that of @code{@var{S}' * @var{S}}.\n\ |
| 5164 | 226 \n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
227 @var{knobs} is an optional one- to three-element input vector. If @var{S} is\n\ |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
228 m-by-n, then rows with more than @code{max(16,@var{knobs}(1)*sqrt(n))}\n\ |
|
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
229 entries are ignored. Columns with more than\n\ |
|
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
230 @code{max (16,@var{knobs}(2)*sqrt(min(m,n)))} entries are removed prior to\n\ |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
231 ordering, and ordered last in the output permutation @var{p}. Only\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
232 completely dense rows or columns are removed if @code{@var{knobs}(1)} and\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
233 @code{@var{knobs}(2)} are < 0, respectively. If @code{@var{knobs}(3)} is\n\ |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
234 nonzero, @var{stats} and @var{knobs} are printed. The default is\n\ |
|
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
235 @code{@var{knobs} = [10 10 0]}. Note that @var{knobs} differs from earlier\n\ |
|
12575
d0b799dafede
Grammarcheck files for 3.4.1 release.
Rik <octave@nomad.inbox5.com>
parents:
11586
diff
changeset
|
236 versions of colamd.\n\ |
| 5164 | 237 \n\ |
| 238 @var{stats} is an optional 20-element output vector that provides data\n\ | |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
239 about the ordering and the validity of the input matrix @var{S}. Ordering\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
240 statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1)} and\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
241 @code{@var{stats}(2)} are the number of dense or empty rows and columns\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
242 ignored by @sc{colamd} and @code{@var{stats}(3)} is the number of garbage\n\ |
| 10840 | 243 collections performed on the internal data structure used by @sc{colamd}\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
244 (roughly of size @code{2.2 * nnz(@var{S}) + 4 * @var{m} + 7 * @var{n}}\n\ |
| 5164 | 245 integers).\n\ |
| 246 \n\ | |
| 247 Octave built-in functions are intended to generate valid sparse matrices,\n\ | |
| 248 with no duplicate entries, with ascending row indices of the nonzeros\n\ | |
| 249 in each column, with a non-negative number of entries in each column (!)\n\ | |
| 10840 | 250 and so on. If a matrix is invalid, then @sc{colamd} may or may not be able\n\ |
| 5164 | 251 to continue. If there are duplicate entries (a row index appears two or\n\ |
| 252 more times in the same column) or if the row indices in a column are out\n\ | |
| 10840 | 253 of order, then @sc{colamd} can correct these errors by ignoring the duplicate\n\ |
| 5164 | 254 entries and sorting each column of its internal copy of the matrix\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
255 @var{S} (the input matrix @var{S} is not repaired, however). If a matrix\n\ |
|
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
256 is invalid in other ways then @sc{colamd} cannot continue, an error message\n\ |
|
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
257 is printed, and no output arguments (@var{p} or @var{stats}) are returned.\n\ |
| 10840 | 258 @sc{colamd} is thus a simple way to check a sparse matrix to see if it's\n\ |
| 5164 | 259 valid.\n\ |
| 260 \n\ | |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
261 @code{@var{stats}(4:7)} provide information if COLAMD was able to\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
262 continue. The matrix is OK if @code{@var{stats}(4)} is zero, or 1 if\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
263 invalid. @code{@var{stats}(5)} is the rightmost column index that is\n\ |
| 5164 | 264 unsorted or contains duplicate entries, or zero if no such column exists.\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
265 @code{@var{stats}(6)} is the last seen duplicate or out-of-order row\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
266 index in the column index given by @code{@var{stats}(5)}, or zero if no\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
267 such row index exists. @code{@var{stats}(7)} is the number of duplicate\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
268 or out-of-order row indices. @code{@var{stats}(8:20)} is always zero in\n\ |
| 10840 | 269 the current version of @sc{colamd} (reserved for future use).\n\ |
| 5164 | 270 \n\ |
| 271 The ordering is followed by a column elimination tree post-ordering.\n\ | |
| 272 \n\ | |
| 273 The authors of the code itself are Stefan I. Larimore and Timothy A.\n\ | |
| 10840 | 274 Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\ |
| 5164 | 275 developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\ |
|
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
276 Ng, Oak Ridge National Laboratory. (see\n\ |
| 5164 | 277 @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
278 @seealso{colperm, symamd, ccolamd}\n\ |
| 5642 | 279 @end deftypefn") |
| 5164 | 280 { |
| 281 octave_value_list retval; | |
| 5451 | 282 |
| 283 #ifdef HAVE_COLAMD | |
| 284 | |
| 5164 | 285 int nargin = args.length (); |
| 286 int spumoni = 0; | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
287 |
|
10282
c9780d8e228c
fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents:
10155
diff
changeset
|
288 if (nargout > 2 || nargin < 1 || nargin > 2) |
| 5823 | 289 print_usage (); |
| 5164 | 290 else |
| 291 { | |
| 292 // Get knobs | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
293 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS); |
| 5440 | 294 COLAMD_NAME (_set_defaults) (knobs); |
| 5164 | 295 |
| 296 // Check for user-passed knobs | |
| 297 if (nargin == 2) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
298 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
299 NDArray User_knobs = args(1).array_value (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
300 int nel_User_knobs = User_knobs.length (); |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
301 |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
302 if (nel_User_knobs > 0) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
303 knobs[COLAMD_DENSE_ROW] = User_knobs(0); |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
304 if (nel_User_knobs > 1) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
305 knobs[COLAMD_DENSE_COL] = User_knobs(1) ; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
306 if (nel_User_knobs > 2) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
307 spumoni = static_cast<int> (User_knobs(2)); |
| 5440 | 308 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
309 // print knob settings if spumoni is set |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
310 if (spumoni) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
311 { |
| 5440 | 312 |
|
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
313 octave_stdout << "\ncolamd version " << COLAMD_MAIN_VERSION |
|
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
314 << "." << COLAMD_SUB_VERSION |
|
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
315 << ", " << COLAMD_DATE << ":\n"; |
| 5164 | 316 |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
317 if (knobs[COLAMD_DENSE_ROW] >= 0) |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
318 octave_stdout << "knobs(1): " << User_knobs (0) |
|
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
319 << ", rows with > max (16," |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
320 << knobs[COLAMD_DENSE_ROW] << "*sqrt (size(A,2)))" |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
321 << " entries removed\n"; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
322 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
323 octave_stdout << "knobs(1): " << User_knobs (0) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
324 << ", only completely dense rows removed\n"; |
| 5440 | 325 |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
326 if (knobs[COLAMD_DENSE_COL] >= 0) |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
327 octave_stdout << "knobs(2): " << User_knobs (1) |
|
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
328 << ", cols with > max (16," |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
329 << knobs[COLAMD_DENSE_COL] << "*sqrt (size(A)))" |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
330 << " entries removed\n"; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
331 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
332 octave_stdout << "knobs(2): " << User_knobs (1) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
333 << ", only completely dense columns removed\n"; |
| 5440 | 334 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
335 octave_stdout << "knobs(3): " << User_knobs (2) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
336 << ", statistics and knobs printed\n"; |
| 5440 | 337 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
338 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
339 } |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
340 |
| 5440 | 341 octave_idx_type n_row, n_col, nnz; |
| 342 octave_idx_type *ridx, *cidx; | |
| 5164 | 343 SparseComplexMatrix scm; |
| 344 SparseMatrix sm; | |
| 345 | |
| 5631 | 346 if (args(0).is_sparse_type ()) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
347 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
348 if (args(0).is_complex_type ()) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
349 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
350 scm = args(0). sparse_complex_matrix_value (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
351 n_row = scm.rows (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
352 n_col = scm.cols (); |
|
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
353 nnz = scm.nnz (); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
354 ridx = scm.xridx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
355 cidx = scm.xcidx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
356 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
357 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
358 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
359 sm = args(0).sparse_matrix_value (); |
| 5164 | 360 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
361 n_row = sm.rows (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
362 n_col = sm.cols (); |
|
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
363 nnz = sm.nnz (); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
364 ridx = sm.xridx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
365 cidx = sm.xcidx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
366 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
367 } |
| 5164 | 368 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
369 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
370 if (args(0).is_complex_type ()) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
371 sm = SparseMatrix (real (args(0).complex_matrix_value ())); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
372 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
373 sm = SparseMatrix (args(0).matrix_value ()); |
| 5164 | 374 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
375 n_row = sm.rows (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
376 n_col = sm.cols (); |
|
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
377 nnz = sm.nnz (); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
378 ridx = sm.xridx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
379 cidx = sm.xcidx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
380 } |
| 5164 | 381 |
| 382 // Allocate workspace for colamd | |
| 5440 | 383 OCTAVE_LOCAL_BUFFER (octave_idx_type, p, n_col+1); |
| 384 for (octave_idx_type i = 0; i < n_col+1; i++) | |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
385 p[i] = cidx[i]; |
| 5164 | 386 |
| 5440 | 387 octave_idx_type Alen = COLAMD_NAME (_recommended) (nnz, n_row, n_col); |
| 388 OCTAVE_LOCAL_BUFFER (octave_idx_type, A, Alen); | |
| 389 for (octave_idx_type i = 0; i < nnz; i++) | |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
390 A[i] = ridx[i]; |
| 5164 | 391 |
| 392 // Order the columns (destroys A) | |
| 5440 | 393 OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, COLAMD_STATS); |
| 394 if (! COLAMD_NAME () (n_row, n_col, Alen, A, p, knobs, stats)) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
395 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
396 COLAMD_NAME (_report) (stats) ; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
397 error ("colamd: internal error!"); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
398 return retval; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
399 } |
| 5164 | 400 |
| 401 // column elimination tree post-ordering (reuse variables) | |
| 5440 | 402 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col + 1); |
| 403 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col + 1); | |
| 404 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1); | |
| 5164 | 405 |
| 5440 | 406 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
|
407 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
408 colbeg[i] = cidx[p[i]]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
409 colend[i] = cidx[p[i]+1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
410 } |
| 5164 | 411 |
| 412 coletree (ridx, colbeg, colend, etree, n_row, n_col); | |
| 413 | |
| 414 // Calculate the tree post-ordering | |
| 7924 | 415 tree_postorder (n_col, etree, colbeg); |
| 5164 | 416 |
| 417 // return the permutation vector | |
| 418 NDArray out_perm (dim_vector (1, n_col)); | |
| 5440 | 419 for (octave_idx_type i = 0; i < n_col; i++) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
420 out_perm(i) = p[colbeg[i]] + 1; |
| 5164 | 421 |
| 7924 | 422 retval(0) = out_perm; |
| 5164 | 423 |
| 424 // print stats if spumoni > 0 | |
| 425 if (spumoni > 0) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
426 COLAMD_NAME (_report) (stats) ; |
| 5164 | 427 |
| 428 // Return the stats vector | |
| 429 if (nargout == 2) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
430 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
431 NDArray out_stats (dim_vector (1, COLAMD_STATS)); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
432 for (octave_idx_type i = 0 ; i < COLAMD_STATS ; i++) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
433 out_stats(i) = stats[i] ; |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
434 retval(1) = out_stats; |
| 5164 | 435 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
436 // fix stats (5) and (6), for 1-based information on |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
437 // jumbled matrix. note that this correction doesn't |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
438 // occur if symamd returns FALSE |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
439 out_stats (COLAMD_INFO1) ++ ; |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
440 out_stats (COLAMD_INFO2) ++ ; |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
441 } |
| 5164 | 442 } |
| 443 | |
| 5451 | 444 #else |
| 445 | |
| 446 error ("colamd: not available in this version of Octave"); | |
| 447 | |
| 448 #endif | |
| 449 | |
| 5164 | 450 return retval; |
| 451 } | |
| 452 | |
| 453 DEFUN_DLD (symamd, args, nargout, | |
|
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
454 "-*- texinfo -*-\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
455 @deftypefn {Loadable Function} {@var{p} =} symamd (@var{S})\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
456 @deftypefnx {Loadable Function} {@var{p} =} symamd (@var{S}, @var{knobs})\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
457 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{S})\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
458 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{S}, @var{knobs})\n\ |
| 5164 | 459 \n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
460 For a symmetric positive definite matrix @var{S}, returns the permutation\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
461 vector p such that @code{@var{S}(@var{p}, @var{p})} tends to have a\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
462 sparser Cholesky@tie{}factor than @var{S}. Sometimes @code{symamd} works\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
463 well for symmetric indefinite matrices too. The matrix @var{S} is assumed\n\ |
|
12642
f96b9b9f141b
doc: Periodic grammarcheck and spellcheck of documentation.
Rik <octave@nomad.inbox5.com>
parents:
12575
diff
changeset
|
464 to be symmetric; only the strictly lower triangular part is referenced.\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
465 @var{S} must be square.\n\ |
| 5164 | 466 \n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
467 @var{knobs} is an optional one- to two-element input vector. If @var{S} is\n\ |
| 5440 | 468 n-by-n, then rows and columns with more than\n\ |
|
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
469 @code{max (16,@var{knobs}(1)*sqrt(n))} entries are removed prior to ordering,\n\ |
|
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
470 and ordered last in the output permutation @var{p}. No rows/columns are\n\ |
| 5440 | 471 removed if @code{@var{knobs}(1) < 0}. If @code{@var{knobs} (2)} is nonzero,\n\ |
|
12642
f96b9b9f141b
doc: Periodic grammarcheck and spellcheck of documentation.
Rik <octave@nomad.inbox5.com>
parents:
12575
diff
changeset
|
472 @code{stats} and @var{knobs} are printed. The default is @code{@var{knobs}\n\ |
| 5440 | 473 = [10 0]}. Note that @var{knobs} differs from earlier versions of symamd.\n\ |
| 5164 | 474 \n\ |
| 475 @var{stats} is an optional 20-element output vector that provides data\n\ | |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
476 about the ordering and the validity of the input matrix @var{S}. Ordering\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
477 statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1) =\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
478 @var{stats}(2)} is the number of dense or empty rows and columns\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
479 ignored by SYMAMD and @code{@var{stats}(3)} is the number of garbage\n\ |
| 5164 | 480 collections performed on the internal data structure used by SYMAMD\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
481 (roughly of size @code{8.4 * nnz (tril (@var{S}, -1)) + 9 * @var{n}}\n\ |
| 5164 | 482 integers).\n\ |
| 483 \n\ | |
| 484 Octave built-in functions are intended to generate valid sparse matrices,\n\ | |
| 485 with no duplicate entries, with ascending row indices of the nonzeros\n\ | |
| 486 in each column, with a non-negative number of entries in each column (!)\n\ | |
| 487 and so on. If a matrix is invalid, then SYMAMD may or may not be able\n\ | |
| 488 to continue. If there are duplicate entries (a row index appears two or\n\ | |
| 489 more times in the same column) or if the row indices in a column are out\n\ | |
| 490 of order, then SYMAMD can correct these errors by ignoring the duplicate\n\ | |
| 491 entries and sorting each column of its internal copy of the matrix S (the\n\ | |
| 492 input matrix S is not repaired, however). If a matrix is invalid in\n\ | |
| 493 other ways then SYMAMD cannot continue, an error message is printed, and\n\ | |
| 494 no output arguments (@var{p} or @var{stats}) are returned. SYMAMD is\n\ | |
| 495 thus a simple way to check a sparse matrix to see if it's valid.\n\ | |
| 496 \n\ | |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
497 @code{@var{stats}(4:7)} provide information if SYMAMD was able to\n\ |
|
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
498 continue. The matrix is OK if @code{@var{stats} (4)} is zero, or 1\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
499 if invalid. @code{@var{stats}(5)} is the rightmost column index that\n\ |
| 5164 | 500 is unsorted or contains duplicate entries, or zero if no such column\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
501 exists. @code{@var{stats}(6)} is the last seen duplicate or out-of-order\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
502 row index in the column index given by @code{@var{stats}(5)}, or zero\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
503 if no such row index exists. @code{@var{stats}(7)} is the number of\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
504 duplicate or out-of-order row indices. @code{@var{stats}(8:20)} is\n\ |
| 5164 | 505 always zero in the current version of SYMAMD (reserved for future use).\n\ |
| 506 \n\ | |
| 507 The ordering is followed by a column elimination tree post-ordering.\n\ | |
| 508 \n\ | |
| 509 The authors of the code itself are Stefan I. Larimore and Timothy A.\n\ | |
| 10840 | 510 Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\ |
| 5164 | 511 developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\ |
|
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
512 Ng, Oak Ridge National Laboratory. (see\n\ |
| 5164 | 513 @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\ |
| 5642 | 514 @seealso{colperm, colamd}\n\ |
| 515 @end deftypefn") | |
| 5164 | 516 { |
| 517 octave_value_list retval; | |
| 5451 | 518 |
| 519 #ifdef HAVE_COLAMD | |
| 520 | |
| 5164 | 521 int nargin = args.length (); |
| 522 int spumoni = 0; | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
523 |
|
10282
c9780d8e228c
fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents:
10155
diff
changeset
|
524 if (nargout > 2 || nargin < 1 || nargin > 2) |
| 5823 | 525 print_usage (); |
| 5164 | 526 else |
| 527 { | |
| 528 // Get knobs | |
| 529 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS); | |
| 5440 | 530 COLAMD_NAME (_set_defaults) (knobs); |
| 5164 | 531 |
| 532 // Check for user-passed knobs | |
| 533 if (nargin == 2) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
534 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
535 NDArray User_knobs = args(1).array_value (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
536 int nel_User_knobs = User_knobs.length (); |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
537 |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
538 if (nel_User_knobs > 0) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
539 knobs[COLAMD_DENSE_ROW] = User_knobs(COLAMD_DENSE_ROW); |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
540 if (nel_User_knobs > 1) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
541 spumoni = static_cast<int> (User_knobs (1)); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
542 } |
| 5164 | 543 |
| 544 // print knob settings if spumoni is set | |
| 545 if (spumoni > 0) | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
546 octave_stdout << "symamd: dense row/col fraction: " |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
547 << knobs[COLAMD_DENSE_ROW] << std::endl; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
548 |
|
13219
cf5ebc0e47e4
fix warnings for unused but set variables and shadowed variables
John W. Eaton <jwe@octave.org>
parents:
12642
diff
changeset
|
549 octave_idx_type n_row, n_col; |
| 5440 | 550 octave_idx_type *ridx, *cidx; |
| 5164 | 551 SparseMatrix sm; |
| 552 SparseComplexMatrix scm; | |
| 553 | |
| 5631 | 554 if (args(0).is_sparse_type ()) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
555 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
556 if (args(0).is_complex_type ()) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
557 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
558 scm = args(0).sparse_complex_matrix_value (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
559 n_row = scm.rows (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
560 n_col = scm.cols (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
561 ridx = scm.xridx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
562 cidx = scm.xcidx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
563 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
564 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
565 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
566 sm = args(0).sparse_matrix_value (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
567 n_row = sm.rows (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
568 n_col = sm.cols (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
569 ridx = sm.xridx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
570 cidx = sm.xcidx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
571 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
572 } |
| 5164 | 573 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
574 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
575 if (args(0).is_complex_type ()) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
576 sm = SparseMatrix (real (args(0).complex_matrix_value ())); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
577 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
578 sm = SparseMatrix (args(0).matrix_value ()); |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
579 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
580 n_row = sm.rows (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
581 n_col = sm.cols (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
582 ridx = sm.xridx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
583 cidx = sm.xcidx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
584 } |
| 5164 | 585 |
| 586 if (n_row != n_col) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
587 { |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
588 error ("symamd: matrix S must be square"); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
589 return retval; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
590 } |
| 5164 | 591 |
| 592 // Allocate workspace for symamd | |
| 5440 | 593 OCTAVE_LOCAL_BUFFER (octave_idx_type, perm, n_col+1); |
| 594 OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, COLAMD_STATS); | |
|
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
595 if (!SYMAMD_NAME () (n_col, ridx, cidx, perm, |
|
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
596 knobs, stats, &calloc, &free)) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
597 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
598 SYMAMD_NAME (_report) (stats) ; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
599 error ("symamd: internal error!") ; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
600 return retval; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
601 } |
| 5164 | 602 |
| 603 // column elimination tree post-ordering | |
| 5440 | 604 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1); |
| 5164 | 605 symetree (ridx, cidx, etree, perm, n_col); |
| 606 | |
| 607 // Calculate the tree post-ordering | |
| 5440 | 608 OCTAVE_LOCAL_BUFFER (octave_idx_type, post, n_col + 1); |
| 7924 | 609 tree_postorder (n_col, etree, post); |
| 5164 | 610 |
| 611 // return the permutation vector | |
| 612 NDArray out_perm (dim_vector (1, n_col)); | |
| 5440 | 613 for (octave_idx_type i = 0; i < n_col; i++) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
614 out_perm(i) = perm[post[i]] + 1; |
| 5164 | 615 |
| 7924 | 616 retval(0) = out_perm; |
| 5164 | 617 |
| 618 // print stats if spumoni > 0 | |
| 619 if (spumoni > 0) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
620 SYMAMD_NAME (_report) (stats) ; |
| 5164 | 621 |
| 622 // Return the stats vector | |
| 623 if (nargout == 2) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
624 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
625 NDArray out_stats (dim_vector (1, COLAMD_STATS)); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
626 for (octave_idx_type i = 0 ; i < COLAMD_STATS ; i++) |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
627 out_stats(i) = stats[i] ; |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
628 retval(1) = out_stats; |
| 5164 | 629 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
630 // fix stats (5) and (6), for 1-based information on |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
631 // jumbled matrix. note that this correction doesn't |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
632 // occur if symamd returns FALSE |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
633 out_stats (COLAMD_INFO1) ++ ; |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
634 out_stats (COLAMD_INFO2) ++ ; |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
635 } |
| 5164 | 636 } |
| 637 | |
| 5451 | 638 #else |
| 639 | |
| 640 error ("symamd: not available in this version of Octave"); | |
| 641 | |
| 642 #endif | |
| 643 | |
| 5164 | 644 return retval; |
| 645 } | |
| 646 | |
| 647 DEFUN_DLD (etree, args, nargout, | |
|
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
648 "-*- texinfo -*-\n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
649 @deftypefn {Loadable Function} {@var{p} =} etree (@var{S})\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
650 @deftypefnx {Loadable Function} {@var{p} =} etree (@var{S}, @var{typ})\n\ |
|
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
651 @deftypefnx {Loadable Function} {[@var{p}, @var{q}] =} etree (@var{S}, @var{typ})\n\ |
| 5164 | 652 \n\ |
|
14038
b0cdd60db5e5
doc: Grammarcheck documentation ahead of 3.6.0 release.
Rik <octave@nomad.inbox5.com>
parents:
13219
diff
changeset
|
653 Return the elimination tree for the matrix @var{S}. By default @var{S}\n\ |
| 5164 | 654 is assumed to be symmetric and the symmetric elimination tree is\n\ |
|
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
655 returned. The argument @var{typ} controls whether a symmetric or\n\ |
|
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
656 column elimination tree is returned. Valid values of @var{typ} are\n\ |
|
17281
bc924baa2c4e
doc: Add new @qcode macro for code samples which are quoted.
Rik <rik@octave.org>
parents:
16313
diff
changeset
|
657 @qcode{\"sym\"} or @qcode{\"col\"}, for symmetric or column elimination tree\n\ |
|
bc924baa2c4e
doc: Add new @qcode macro for code samples which are quoted.
Rik <rik@octave.org>
parents:
16313
diff
changeset
|
658 respectively.\n\ |
| 5164 | 659 \n\ |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
660 Called with a second argument, @code{etree} also returns the postorder\n\ |
| 5164 | 661 permutations on the tree.\n\ |
| 662 @end deftypefn") | |
| 663 { | |
| 664 octave_value_list retval; | |
| 5297 | 665 |
| 5164 | 666 int nargin = args.length (); |
| 667 | |
|
10282
c9780d8e228c
fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents:
10155
diff
changeset
|
668 if (nargout > 2 || nargin < 1 || nargin > 2) |
| 5823 | 669 print_usage (); |
| 5164 | 670 else |
| 671 { | |
|
13219
cf5ebc0e47e4
fix warnings for unused but set variables and shadowed variables
John W. Eaton <jwe@octave.org>
parents:
12642
diff
changeset
|
672 octave_idx_type n_row, n_col; |
| 5440 | 673 octave_idx_type *ridx, *cidx; |
| 5164 | 674 bool is_sym = true; |
| 675 SparseMatrix sm; | |
| 676 SparseComplexMatrix scm; | |
| 677 | |
| 5631 | 678 if (args(0).is_sparse_type ()) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
679 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
680 if (args(0).is_complex_type ()) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
681 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
682 scm = args(0).sparse_complex_matrix_value (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
683 n_row = scm.rows (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
684 n_col = scm.cols (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
685 ridx = scm.xridx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
686 cidx = scm.xcidx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
687 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
688 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
689 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
690 sm = args(0).sparse_matrix_value (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
691 n_row = sm.rows (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
692 n_col = sm.cols (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
693 ridx = sm.xridx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
694 cidx = sm.xcidx (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
695 } |
| 5164 | 696 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
697 } |
| 5164 | 698 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
699 { |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
700 error ("etree: S must be a sparse matrix"); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
701 return retval; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
702 } |
| 5164 | 703 |
| 704 if (nargin == 2) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
705 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
706 if (args(1).is_string ()) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
707 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
708 std::string str = args(1).string_value (); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
709 if (str.find ("C") == 0 || str.find ("c") == 0) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
710 is_sym = false; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
711 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
712 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
713 { |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
714 error ("etree: TYP must be a string"); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
715 return retval; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
716 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
717 } |
| 7924 | 718 |
| 5164 | 719 // column elimination tree post-ordering (reuse variables) |
| 5440 | 720 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1); |
| 5164 | 721 |
| 722 if (is_sym) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
723 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
724 if (n_row != n_col) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
725 { |
|
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
726 error ("etree: S is marked as symmetric, but is not square"); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
727 return retval; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
728 } |
| 7924 | 729 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
730 symetree (ridx, cidx, etree, 0, n_col); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
731 } |
| 5164 | 732 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
733 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
734 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
735 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col); |
| 5164 | 736 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
737 for (octave_idx_type i = 0; i < n_col; i++) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
738 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
739 colbeg[i] = cidx[i]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
740 colend[i] = cidx[i+1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
741 } |
| 5164 | 742 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
743 coletree (ridx, colbeg, colend, etree, n_row, n_col); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
744 } |
| 5164 | 745 |
| 746 NDArray tree (dim_vector (1, n_col)); | |
| 5440 | 747 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
|
748 // We flag a root with n_col while Matlab does it with zero |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
749 // Convert for matlab compatiable output |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
750 if (etree[i] == n_col) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
751 tree(i) = 0; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
752 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
753 tree(i) = etree[i] + 1; |
| 5164 | 754 |
| 7924 | 755 retval(0) = tree; |
| 5164 | 756 |
| 757 if (nargout == 2) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
758 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
759 // Calculate the tree post-ordering |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
760 OCTAVE_LOCAL_BUFFER (octave_idx_type, post, n_col + 1); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
761 tree_postorder (n_col, etree, post); |
| 5164 | 762 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
763 NDArray postorder (dim_vector (1, n_col)); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
764 for (octave_idx_type i = 0; i < n_col; i++) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
765 postorder(i) = post[i] + 1; |
| 5164 | 766 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
767 retval(1) = postorder; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
768 } |
| 5164 | 769 } |
| 770 | |
| 771 return retval; | |
| 772 } |