Mercurial > octave-nkf

annotate libinterp/dldfcn/colamd.cc @ 20216:aa36fb998a4d stable

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
maint: Remove unnecessary whitespace at end of lines. * libgui/Makefile.am, libgui/graphics/Canvas.cc, libgui/graphics/EditControl.cc, libgui/graphics/Figure.cc, libgui/graphics/MouseModeActionGroup.cc, libgui/graphics/annotation-dialog.cc, libgui/graphics/annotation-dialog.h, libgui/graphics/gl-select.cc, libgui/graphics/module.mk, libgui/kb-layouts/default.keytab, libgui/kb-layouts/linux.keytab, libgui/kb-layouts/vt420pc.keytab, libgui/src/m-editor/find-dialog.cc, libgui/src/main-window.cc, libgui/src/octave-qt-link.cc, libgui/src/octave-qt-link.h, libgui/src/shortcut-manager.h, libinterp/corefcn/error.cc, libinterp/corefcn/find.cc, libinterp/corefcn/gl2ps-renderer.cc, libinterp/corefcn/graphics.cc, libinterp/corefcn/graphics.in.h, libinterp/corefcn/octave-link.cc, libinterp/corefcn/quadcc.cc, libinterp/corefcn/strfns.cc, libinterp/corefcn/syscalls.cc, libinterp/corefcn/sysdep.cc, libinterp/corefcn/urlwrite.cc, libinterp/corefcn/utils.cc, libinterp/corefcn/variables.cc, libinterp/dldfcn/__init_fltk__.cc, libinterp/dldfcn/ccolamd.cc, libinterp/dldfcn/colamd.cc, libinterp/octave-value/ov-bool-sparse.cc, libinterp/octave-value/ov-classdef.cc, libinterp/octave-value/ov-re-sparse.cc, libinterp/octave-value/ov-struct.cc, libinterp/parse-tree/pt-arg-list.cc, scripts/audio/@audiorecorder/play.m, scripts/audio/wavwrite.m, scripts/general/cart2sph.m, scripts/geometry/inpolygon.m, scripts/gui/listdlg.m, scripts/gui/msgbox.m, scripts/gui/private/message_dialog.m, scripts/help/get_first_help_sentence.m, scripts/help/lookfor.m, scripts/image/imshow.m, scripts/io/strread.m, scripts/java/javamem.m, scripts/miscellaneous/dir.m, scripts/miscellaneous/edit.m, scripts/miscellaneous/genvarname.m, scripts/miscellaneous/gzip.m, scripts/miscellaneous/private/__w2mpth__.m, scripts/plot/appearance/annotation.m, scripts/plot/draw/colorbar.m, scripts/plot/draw/quiver3.m, scripts/plot/util/hold.m, scripts/plot/util/print.m, scripts/polynomial/mkpp.m, scripts/polynomial/polyder.m, scripts/polynomial/spline.m, scripts/polynomial/unmkpp.m, scripts/signal/arma_rnd.m, scripts/sparse/gplot.m, scripts/statistics/tests/t_test.m, scripts/statistics/tests/t_test_regression.m, scripts/strings/mat2str.m, scripts/strings/strsplit.m, scripts/strings/strtrunc.m, scripts/strings/untabify.m, scripts/testfun/assert.m: maint: Remove unnecessary whitespace at end of lines.
author Rik <rik@octave.org>
date Tue, 12 May 2015 09:22:01 -0700
parents 075a5e2e1ba5
children a9574e3c6e9e
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
19731
4197fc428c7d maint: Update copyright notices for 2015.
John W. Eaton <jwe@octave.org>
parents: 19074
diff changeset
3 Copyright (C) 2004-2015 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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
9 under the terms of the GNU General Public License as published by the
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6484
diff changeset
10 Free Software Foundation; either version 3 of the License, or (at your
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6484
diff changeset
11 option) any later version.
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
12
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
13 Octave is distributed in the hope that it will be useful, but WITHOUT
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
16 for more details.
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
27 #ifdef HAVE_CONFIG_H
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
28 #include <config.h>
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 #include <vector>
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
35
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
36 #include "ov.h"
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
37 #include "defun-dld.h"
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
38 #include "pager.h"
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
39 #include "ov-re-mat.h"
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
40
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
41 #include "ov-re-sparse.h"
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
42 #include "ov-cx-sparse.h"
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
43
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
48 #define COLAMD_NAME(name) colamd_l ## name
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
49 #define SYMAMD_NAME(name) symamd_l ## name
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
50 #else
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
51 #define COLAMD_NAME(name) colamd ## name
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
52 #define SYMAMD_NAME(name) symamd ## name
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
53 #endif
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
56 // Copyright given elsewhere in this file.
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
60 {
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
61 OCTAVE_LOCAL_BUFFER (octave_idx_type, Flag, n);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
62 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
63 if (P)
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
64 // 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
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
67
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
68 for (octave_idx_type k = 0 ; k < n ; k++)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
69 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
92 }
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
95 // 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
96 static inline octave_idx_type
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
97 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
98 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
99 pp[i] = i;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
100 return i;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
101 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
102
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
103 static inline octave_idx_type
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
104 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
105 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
106 pp[s] = t;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
107 return t;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
108 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
109
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
110 static inline octave_idx_type
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
111 find (octave_idx_type i, octave_idx_type *pp)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
112 {
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
115 p = pp[i];
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
116 gp = pp[p];
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
117
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
118 while (gp != p)
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
119 {
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
120 pp[i] = gp;
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
121 i = gp;
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
122 p = pp[i];
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
123 gp = pp[p];
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
124 }
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
125
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
126 return p;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
127 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
128
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
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
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
132 octave_idx_type postnum)
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
133 {
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
134 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
135 postnum = etdfs (w, first_kid, next_kid, post, postnum);
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
136
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
137 post[postnum++] = v;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
138
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
139 return postnum;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
140 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
141
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
142 static void
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
145 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
146 // Allocate storage for working arrays and results
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
147 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
148 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
149
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
150 // Set up structure describing children
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
151 for (octave_idx_type v = 0; v <= n; first_kid[v++] = -1)
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
152 /* do nothing */;
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
155 {
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
156 octave_idx_type dad = parent[v];
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
157 next_kid[v] = first_kid[dad];
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
158 first_kid[dad] = v;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
159 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
160
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
161 // Depth-first search from dummy root vertex #n
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
162 etdfs (n, first_kid, next_kid, post, 0);
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
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
165 static void
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
169 {
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
170 OCTAVE_LOCAL_BUFFER (octave_idx_type, root, nc);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
171 OCTAVE_LOCAL_BUFFER (octave_idx_type, pp, nc);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
172 OCTAVE_LOCAL_BUFFER (octave_idx_type, firstcol, nr);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
173
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
174 // Compute firstcol[row] = first nonzero column in row
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
175 for (octave_idx_type row = 0; row < nr; firstcol[row++] = nc)
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
176 /* do nothing */;
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
184 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
185
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
186 // Compute etree by Liu's algorithm for symmetric matrices,
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
187 // 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
188 // 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
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
191 {
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
192 octave_idx_type cset = make_set (col, pp);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
209 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
210 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
211
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
218 \n\
20198
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
219 Compute the column approximate minimum degree permutation.\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
220 \n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
221 @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
222 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
223 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
224 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
225 @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
226 than that of @code{@var{S}' * @var{S}}.\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
227 \n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
228 @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
229 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
230 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
231 @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
232 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
233 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
234 @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
235 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
236 @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
237 versions of colamd.\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
238 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
239 @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
240 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
241 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
242 @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
243 ignored by @sc{colamd} and @code{@var{stats}(3)} is the number of garbage\n\
10840
89f4d7e294cc Grammarcheck .cc files
Rik <octave@nomad.inbox5.com>
parents: 10527
diff changeset
244 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
245 (roughly of size @code{2.2 * nnz(@var{S}) + 4 * @var{m} + 7 * @var{n}}\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
246 integers).\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
247 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
248 Octave built-in functions are intended to generate valid sparse matrices,\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
249 with no duplicate entries, with ascending row indices of the nonzeros\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
250 in each column, with a non-negative number of entries in each column (!)\n\
10840
89f4d7e294cc Grammarcheck .cc files
Rik <octave@nomad.inbox5.com>
parents: 10527
diff changeset
251 and so on. If a matrix is invalid, then @sc{colamd} may or may not be able\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
252 to continue. If there are duplicate entries (a row index appears two or\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
253 more times in the same column) or if the row indices in a column are out\n\
10840
89f4d7e294cc Grammarcheck .cc files
Rik <octave@nomad.inbox5.com>
parents: 10527
diff changeset
254 of order, then @sc{colamd} can correct these errors by ignoring the duplicate\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
255 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
256 @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
257 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
258 is printed, and no output arguments (@var{p} or @var{stats}) are returned.\n\
10840
89f4d7e294cc Grammarcheck .cc files
Rik <octave@nomad.inbox5.com>
parents: 10527
diff changeset
259 @sc{colamd} is thus a simple way to check a sparse matrix to see if it's\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
260 valid.\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
261 \n\
20198
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
262 @code{@var{stats}(4:7)} provide information if @sc{colamd} was able to\n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
263 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
264 invalid. @code{@var{stats}(5)} is the rightmost column index that is\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
265 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
266 @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
267 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
268 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
269 or out-of-order row indices. @code{@var{stats}(8:20)} is always zero in\n\
10840
89f4d7e294cc Grammarcheck .cc files
Rik <octave@nomad.inbox5.com>
parents: 10527
diff changeset
270 the current version of @sc{colamd} (reserved for future use).\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
271 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
272 The ordering is followed by a column elimination tree post-ordering.\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
273 \n\
19074
0850b5212619 doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents: 17787
diff changeset
274 The authors of the code itself are @nospell{Stefan I. Larimore} and\n\
0850b5212619 doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents: 17787
diff changeset
275 @nospell{Timothy A. Davis @email{davis@@cise.ufl.edu}}, University of Florida. The algorithm was developed in collaboration with @nospell{John Gilbert},\n\
0850b5212619 doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents: 17787
diff changeset
276 Xerox PARC, and @nospell{Esmond Ng}, Oak Ridge National Laboratory. (see\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
2618a0750ae6 [project @ 2006-03-06 21:26:48 by jwe]
jwe
parents: 5631
diff changeset
279 @end deftypefn")
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
280 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
281 octave_value_list retval;
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
282
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
283 #ifdef HAVE_COLAMD
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
284
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
285 int nargin = args.length ();
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
080c08b192d8 [project @ 2006-05-19 05:32:17 by jwe]
jwe
parents: 5760
diff changeset
289 print_usage ();
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
290 else
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
291 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
294 COLAMD_NAME (_set_defaults) (knobs);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
295
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
296 // Check for user-passed knobs
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
341 octave_idx_type n_row, n_col, nnz;
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
342 octave_idx_type *ridx, *cidx;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
343 SparseComplexMatrix scm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
344 SparseMatrix sm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
345
5631
7171d19706df [project @ 2006-02-22 20:15:06 by dbateman]
dbateman
parents: 5604
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
381
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
382 // Allocate workspace for colamd
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
383 OCTAVE_LOCAL_BUFFER (octave_idx_type, p, n_col+1);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
386
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
387 octave_idx_type Alen = COLAMD_NAME (_recommended) (nnz, n_row, n_col);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
388 OCTAVE_LOCAL_BUFFER (octave_idx_type, A, Alen);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
391
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
392 // Order the columns (destroys A)
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
393 OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, COLAMD_STATS);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
400
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
401 // column elimination tree post-ordering (reuse variables)
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
402 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col + 1);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
403 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col + 1);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
404 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
405
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
411
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
412 coletree (ridx, colbeg, colend, etree, n_row, n_col);
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
413
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
414 // Calculate the tree post-ordering
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
415 tree_postorder (n_col, etree, colbeg);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
416
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
417 // return the permutation vector
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
418 NDArray out_perm (dim_vector (1, n_col));
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
421
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
422 retval(0) = out_perm;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
423
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
424 // print stats if spumoni > 0
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
427
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
428 // Return the stats vector
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
442 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
443
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
444 #else
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
445
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
446 error ("colamd: not available in this version of Octave");
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
447
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
448 #endif
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
449
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
450 return retval;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
451 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
452
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
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\
20198
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
462 sparser Cholesky@tie{}factor than @var{S}.\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
463 \n\
20216
aa36fb998a4d maint: Remove unnecessary whitespace at end of lines.
Rik <rik@octave.org>
parents: 20198
diff changeset
464 Sometimes @code{symamd} works well for symmetric indefinite matrices too. \n\
20198
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
465 The matrix @var{S} is assumed to be symmetric; only the strictly lower\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
466 triangular part is referenced. @var{S} must be square.\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
467 \n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
468 @var{knobs} is an optional one- to two-element input vector. If @var{S} is\n\
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
469 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
470 @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
471 and ordered last in the output permutation @var{p}. No rows/columns are\n\
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
472 removed if @code{@var{knobs}(1) < 0}. If @code{@var{knobs} (2)} is nonzero,\n\
20198
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
473 @code{stats} and @var{knobs} are printed. The default is\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
474 @code{@var{knobs} = [10 0]}. Note that @var{knobs} differs from earlier\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
475 versions of @code{symamd}.\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
476 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
477 @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
478 about the ordering and the validity of the input matrix @var{S}. Ordering\n\
20198
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
479 statistics are in @code{@var{stats}(1:3)}.\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
480 @code{@var{stats}(1) = @var{stats}(2)} is the number of dense or empty rows\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
481 and columns ignored by SYMAMD and @code{@var{stats}(3)} is the number of\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
482 garbage 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
483 (roughly of size @code{8.4 * nnz (tril (@var{S}, -1)) + 9 * @var{n}}\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
484 integers).\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
485 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
486 Octave built-in functions are intended to generate valid sparse matrices,\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
487 with no duplicate entries, with ascending row indices of the nonzeros\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
488 in each column, with a non-negative number of entries in each column (!)\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
489 and so on. If a matrix is invalid, then SYMAMD may or may not be able\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
490 to continue. If there are duplicate entries (a row index appears two or\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
491 more times in the same column) or if the row indices in a column are out\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
492 of order, then SYMAMD can correct these errors by ignoring the duplicate\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
493 entries and sorting each column of its internal copy of the matrix S (the\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
494 input matrix S is not repaired, however). If a matrix is invalid in\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
495 other ways then SYMAMD cannot continue, an error message is printed, and\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
496 no output arguments (@var{p} or @var{stats}) are returned. SYMAMD is\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
497 thus a simple way to check a sparse matrix to see if it's valid.\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
498 \n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
499 @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
500 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
501 if invalid. @code{@var{stats}(5)} is the rightmost column index that\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
502 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
503 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
504 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
505 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
506 duplicate or out-of-order row indices. @code{@var{stats}(8:20)} is\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
507 always zero in the current version of SYMAMD (reserved for future use).\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
508 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
509 The ordering is followed by a column elimination tree post-ordering.\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
510 \n\
19074
0850b5212619 doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents: 17787
diff changeset
511 The authors of the code itself are @nospell{Stefan I. Larimore} and\n\
0850b5212619 doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents: 17787
diff changeset
512 @nospell{Timothy A. Davis @email{davis@@cise.ufl.edu}}, University of Florida. The algorithm was developed in collaboration with @nospell{John Gilbert},\n\
0850b5212619 doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents: 17787
diff changeset
513 Xerox PARC, and @nospell{Esmond Ng}, Oak Ridge National Laboratory. (see\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
514 @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\
5642
2618a0750ae6 [project @ 2006-03-06 21:26:48 by jwe]
jwe
parents: 5631
diff changeset
515 @seealso{colperm, colamd}\n\
2618a0750ae6 [project @ 2006-03-06 21:26:48 by jwe]
jwe
parents: 5631
diff changeset
516 @end deftypefn")
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
517 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
518 octave_value_list retval;
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
519
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
520 #ifdef HAVE_COLAMD
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
521
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
522 int nargin = args.length ();
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
523 int spumoni = 0;
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
524
10282
c9780d8e228c fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents: 10155
diff changeset
525 if (nargout > 2 || nargin < 1 || nargin > 2)
5823
080c08b192d8 [project @ 2006-05-19 05:32:17 by jwe]
jwe
parents: 5760
diff changeset
526 print_usage ();
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
527 else
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
528 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
529 // Get knobs
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
530 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS);
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
531 COLAMD_NAME (_set_defaults) (knobs);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
532
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
533 // Check for user-passed knobs
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
534 if (nargin == 2)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
535 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
536 NDArray User_knobs = args(1).array_value ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
537 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
538
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
539 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
540 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
541 if (nel_User_knobs > 1)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
542 spumoni = static_cast<int> (User_knobs (1));
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
543 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
544
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
545 // print knob settings if spumoni is set
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
546 if (spumoni > 0)
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
547 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
548 << knobs[COLAMD_DENSE_ROW] << std::endl;
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
549
13219
cf5ebc0e47e4 fix warnings for unused but set variables and shadowed variables
John W. Eaton <jwe@octave.org>
parents: 12642
diff changeset
550 octave_idx_type n_row, n_col;
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
551 octave_idx_type *ridx, *cidx;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
552 SparseMatrix sm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
553 SparseComplexMatrix scm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
554
5631
7171d19706df [project @ 2006-02-22 20:15:06 by dbateman]
dbateman
parents: 5604
diff changeset
555 if (args(0).is_sparse_type ())
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
556 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
557 if (args(0).is_complex_type ())
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
558 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
559 scm = args(0).sparse_complex_matrix_value ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
560 n_row = scm.rows ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
561 n_col = scm.cols ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
562 ridx = scm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
563 cidx = scm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
564 }
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
565 else
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
566 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
567 sm = args(0).sparse_matrix_value ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
568 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
569 n_col = sm.cols ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
570 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
571 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
572 }
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
573 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
574 else
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
575 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
576 if (args(0).is_complex_type ())
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
577 sm = SparseMatrix (real (args(0).complex_matrix_value ()));
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
578 else
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
579 sm = SparseMatrix (args(0).matrix_value ());
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
580
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
581 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
582 n_col = sm.cols ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
583 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
584 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
585 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
586
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
587 if (n_row != n_col)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
588 {
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
589 error ("symamd: matrix S must be square");
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
590 return retval;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
591 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
592
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
593 // Allocate workspace for symamd
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
594 OCTAVE_LOCAL_BUFFER (octave_idx_type, perm, n_col+1);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
595 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
596 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
597 knobs, stats, &calloc, &free))
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
598 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
599 SYMAMD_NAME (_report) (stats) ;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
600 error ("symamd: internal error!") ;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
601 return retval;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
602 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
603
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
604 // column elimination tree post-ordering
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
605 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
606 symetree (ridx, cidx, etree, perm, n_col);
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
607
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
608 // Calculate the tree post-ordering
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
609 OCTAVE_LOCAL_BUFFER (octave_idx_type, post, n_col + 1);
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
610 tree_postorder (n_col, etree, post);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
611
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
612 // return the permutation vector
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
613 NDArray out_perm (dim_vector (1, n_col));
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
614 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
615 out_perm(i) = perm[post[i]] + 1;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
616
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
617 retval(0) = out_perm;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
618
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
619 // print stats if spumoni > 0
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
620 if (spumoni > 0)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
621 SYMAMD_NAME (_report) (stats) ;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
622
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
623 // Return the stats vector
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
624 if (nargout == 2)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
625 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
626 NDArray out_stats (dim_vector (1, COLAMD_STATS));
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
627 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
628 out_stats(i) = stats[i] ;
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
629 retval(1) = out_stats;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
630
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
631 // 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
632 // jumbled matrix. note that this correction doesn't
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
633 // occur if symamd returns FALSE
11586
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
634 out_stats (COLAMD_INFO1) ++ ;
12df7854fa7c strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents: 11553
diff changeset
635 out_stats (COLAMD_INFO2) ++ ;
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
636 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
637 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
638
5451
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
639 #else
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
640
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
641 error ("symamd: not available in this version of Octave");
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
642
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
643 #endif
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe]
jwe
parents: 5440
diff changeset
644
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
645 return retval;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
646 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
647
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
648 DEFUN_DLD (etree, args, nargout,
17787
175b392e91fe Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents: 17744
diff changeset
649 "-*- texinfo -*-\n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
650 @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
651 @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
652 @deftypefnx {Loadable Function} {[@var{p}, @var{q}] =} etree (@var{S}, @var{typ})\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
653 \n\
20198
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
654 Return the elimination tree for the matrix @var{S}.\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
655 \n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
656 By default @var{S} is assumed to be symmetric and the symmetric elimination\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19731
diff changeset
657 tree is returned. The argument @var{typ} controls whether a symmetric or\n\
9064
7c02ec148a3c Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents: 8920
diff changeset
658 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
659 @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
660 respectively.\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
661 \n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
662 Called with a second argument, @code{etree} also returns the postorder\n\
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
663 permutations on the tree.\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
664 @end deftypefn")
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
665 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
666 octave_value_list retval;
5297
234abf4c74dd [project @ 2005-04-21 21:29:46 by jwe]
jwe
parents: 5164
diff changeset
667
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
668 int nargin = args.length ();
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
669
10282
c9780d8e228c fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents: 10155
diff changeset
670 if (nargout > 2 || nargin < 1 || nargin > 2)
5823
080c08b192d8 [project @ 2006-05-19 05:32:17 by jwe]
jwe
parents: 5760
diff changeset
671 print_usage ();
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
672 else
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
673 {
13219
cf5ebc0e47e4 fix warnings for unused but set variables and shadowed variables
John W. Eaton <jwe@octave.org>
parents: 12642
diff changeset
674 octave_idx_type n_row, n_col;
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
675 octave_idx_type *ridx, *cidx;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
676 bool is_sym = true;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
677 SparseMatrix sm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
678 SparseComplexMatrix scm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
679
5631
7171d19706df [project @ 2006-02-22 20:15:06 by dbateman]
dbateman
parents: 5604
diff changeset
680 if (args(0).is_sparse_type ())
10154
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 if (args(0).is_complex_type ())
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
683 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
684 scm = args(0).sparse_complex_matrix_value ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
685 n_row = scm.rows ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
686 n_col = scm.cols ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
687 ridx = scm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
688 cidx = scm.xcidx ();
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 else
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
691 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
692 sm = args(0).sparse_matrix_value ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
693 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
694 n_col = sm.cols ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
695 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
696 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
697 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
698
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
699 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
700 else
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
701 {
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
702 error ("etree: S must be a sparse matrix");
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
703 return retval;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
704 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
705
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
706 if (nargin == 2)
10154
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 if (args(1).is_string ())
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
709 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
710 std::string str = args(1).string_value ();
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
711 if (str.find ("C") == 0 || str.find ("c") == 0)
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
712 is_sym = false;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
713 }
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
714 else
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
715 {
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
716 error ("etree: TYP must be a string");
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
717 return retval;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
718 }
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
719 }
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
720
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
721 // column elimination tree post-ordering (reuse variables)
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
722 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
723
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
724 if (is_sym)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
725 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
726 if (n_row != n_col)
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
727 {
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
728 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
729 return retval;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
730 }
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
731
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
732 symetree (ridx, cidx, etree, 0, n_col);
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
733 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
734 else
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
735 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
736 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col);
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
737 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
738
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
739 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
740 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
741 colbeg[i] = cidx[i];
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
742 colend[i] = cidx[i+1];
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
743 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
744
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
745 coletree (ridx, colbeg, colend, etree, n_row, n_col);
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
746 }
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 NDArray tree (dim_vector (1, n_col));
5440
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman]
dbateman
parents: 5307
diff changeset
749 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
750 // 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
751 // Convert for matlab compatiable output
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
752 if (etree[i] == n_col)
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
753 tree(i) = 0;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
754 else
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
755 tree(i) = etree[i] + 1;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
756
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7520
diff changeset
757 retval(0) = tree;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
758
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
759 if (nargout == 2)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
760 {
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
761 // Calculate the tree post-ordering
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
762 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
763 tree_postorder (n_col, etree, post);
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
764
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
765 NDArray postorder (dim_vector (1, n_col));
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
766 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
767 postorder(i) = post[i] + 1;
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
768
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
769 retval(1) = postorder;
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9064
diff changeset
770 }
5164
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
771 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
772
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
773 return retval;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe]
jwe
parents:
diff changeset
774 }