octave-nkf: libinterp/dldfcn/colamd.cc annotate

annotate libinterp/dldfcn/colamd.cc @ 19731:4197fc428c7d

maint: Update copyright notices for 2015.

author	John W. Eaton <jwe@octave.org>
date	Wed, 11 Feb 2015 14:19:08 -0500
parents	0850b5212619
children	075a5e2e1ba5

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\
10840 89f4d7e294cc Grammarcheck .cc files Rik <octave@nomad.inbox5.com> parents: 10527 diff changeset	219 Column approximate minimum degree permutation.\n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	220 @code{@var{p} = colamd (@var{S})} returns the column approximate minimum\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	221 degree permutation vector for the sparse matrix @var{S}. For a\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	222 non-symmetric matrix @var{S}, @code{@var{S}(:,@var{p})} tends to have\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	223 sparser LU@tie{}factors than @var{S}. The Cholesky@tie{}factorization of\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	224 @code{@var{S}(:,@var{p})' * @var{S}(:,@var{p})} also tends to be sparser\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	225 than that of @code{@var{S}' * @var{S}}.\n\
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	226 \n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	227 @var{knobs} is an optional one- to three-element input vector. If @var{S} is\n\
10846 a4f482e66b65 Grammarcheck more of the documentation. Rik <octave@nomad.inbox5.com> parents: 10840 diff changeset	228 m-by-n, then rows with more than @code{max(16,@var{knobs}(1)*sqrt(n))}\n\
a4f482e66b65 Grammarcheck more of the documentation. Rik <octave@nomad.inbox5.com> parents: 10840 diff changeset	229 entries are ignored. Columns with more than\n\
14854 5ae9f0f77635 maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory Rik <octave@nomad.inbox5.com> parents: 14361 diff changeset	230 @code{max (16,@var{knobs}(2)*sqrt(min(m,n)))} entries are removed prior to\n\
10846 a4f482e66b65 Grammarcheck more of the documentation. Rik <octave@nomad.inbox5.com> parents: 10840 diff changeset	231 ordering, and ordered last in the output permutation @var{p}. Only\n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	232 completely dense rows or columns are removed if @code{@var{knobs}(1)} and\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	233 @code{@var{knobs}(2)} are < 0, respectively. If @code{@var{knobs}(3)} is\n\
10846 a4f482e66b65 Grammarcheck more of the documentation. Rik <octave@nomad.inbox5.com> parents: 10840 diff changeset	234 nonzero, @var{stats} and @var{knobs} are printed. The default is\n\
a4f482e66b65 Grammarcheck more of the documentation. Rik <octave@nomad.inbox5.com> parents: 10840 diff changeset	235 @code{@var{knobs} = [10 10 0]}. Note that @var{knobs} differs from earlier\n\
12575 d0b799dafede Grammarcheck files for 3.4.1 release. Rik <octave@nomad.inbox5.com> parents: 11586 diff changeset	236 versions of colamd.\n\
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	237 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	238 @var{stats} is an optional 20-element output vector that provides data\n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	239 about the ordering and the validity of the input matrix @var{S}. Ordering\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	240 statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1)} and\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	241 @code{@var{stats}(2)} are the number of dense or empty rows and columns\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	242 ignored by @sc{colamd} and @code{@var{stats}(3)} is the number of garbage\n\
10840 89f4d7e294cc Grammarcheck .cc files Rik <octave@nomad.inbox5.com> parents: 10527 diff changeset	243 collections performed on the internal data structure used by @sc{colamd}\n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	244 (roughly of size @code{2.2 * nnz(@var{S}) + 4 * @var{m} + 7 * @var{n}}\n\
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	245 integers).\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	246 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	247 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	248 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	249 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	250 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	251 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	252 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	253 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	254 entries and sorting each column of its internal copy of the matrix\n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	255 @var{S} (the input matrix @var{S} is not repaired, however). If a matrix\n\
10846 a4f482e66b65 Grammarcheck more of the documentation. Rik <octave@nomad.inbox5.com> parents: 10840 diff changeset	256 is invalid in other ways then @sc{colamd} cannot continue, an error message\n\
a4f482e66b65 Grammarcheck more of the documentation. Rik <octave@nomad.inbox5.com> parents: 10840 diff changeset	257 is printed, and no output arguments (@var{p} or @var{stats}) are returned.\n\
10840 89f4d7e294cc Grammarcheck .cc files Rik <octave@nomad.inbox5.com> parents: 10527 diff changeset	258 @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	259 valid.\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	260 \n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	261 @code{@var{stats}(4:7)} provide information if COLAMD was able to\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	262 continue. The matrix is OK if @code{@var{stats}(4)} is zero, or 1 if\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	263 invalid. @code{@var{stats}(5)} is the rightmost column index that is\n\
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	264 unsorted or contains duplicate entries, or zero if no such column exists.\n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	265 @code{@var{stats}(6)} is the last seen duplicate or out-of-order row\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	266 index in the column index given by @code{@var{stats}(5)}, or zero if no\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	267 such row index exists. @code{@var{stats}(7)} is the number of duplicate\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	268 or out-of-order row indices. @code{@var{stats}(8:20)} is always zero in\n\
10840 89f4d7e294cc Grammarcheck .cc files Rik <octave@nomad.inbox5.com> parents: 10527 diff changeset	269 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	270 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	271 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	272 \n\
19074 0850b5212619 doc: Add @nospell macro around proper names in documentation. Rik <rik@octave.org> parents: 17787 diff changeset	273 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	274 @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	275 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	276 @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	277 @seealso{colperm, symamd, ccolamd}\n\
5642 2618a0750ae6 [project @ 2006-03-06 21:26:48 by jwe] jwe parents: 5631 diff changeset	278 @end deftypefn")
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	279 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	280 octave_value_list retval;
5451 ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	281
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	282 #ifdef HAVE_COLAMD
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	283
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	284 int nargin = args.length ();
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	285 int spumoni = 0;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	286
10282 c9780d8e228c fix invalid checks in amd functions Jaroslav Hajek <highegg@gmail.com> parents: 10155 diff changeset	287 if (nargout > 2 \|\| nargin < 1 \|\| nargin > 2)
5823 080c08b192d8 [project @ 2006-05-19 05:32:17 by jwe] jwe parents: 5760 diff changeset	288 print_usage ();
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	289 else
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	290 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	291 // Get knobs
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	292 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS);
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	293 COLAMD_NAME (_set_defaults) (knobs);
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	294
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	295 // Check for user-passed knobs
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	296 if (nargin == 2)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	297 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	298 NDArray User_knobs = args(1).array_value ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	299 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	300
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	301 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	302 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	303 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	304 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	305 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	306 spumoni = static_cast<int> (User_knobs(2));
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	307
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	308 // print knob settings if spumoni is set
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	309 if (spumoni)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	310 {
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	311
17787 175b392e91fe Use GNU style coding conventions for code in libinterp/ Rik <rik@octave.org> parents: 17744 diff changeset	312 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	313 << "." << COLAMD_SUB_VERSION
175b392e91fe Use GNU style coding conventions for code in libinterp/ Rik <rik@octave.org> parents: 17744 diff changeset	314 << ", " << COLAMD_DATE << ":\n";
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	315
15020 560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code. Rik <rik@octave.org> parents: 14854 diff changeset	316 if (knobs[COLAMD_DENSE_ROW] >= 0)
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	317 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	318 << ", 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	319 << knobs[COLAMD_DENSE_ROW] << "*sqrt (size(A,2)))"
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	320 << " entries removed\n";
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	321 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	322 octave_stdout << "knobs(1): " << User_knobs (0)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	323 << ", only completely dense rows removed\n";
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	324
15020 560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code. Rik <rik@octave.org> parents: 14854 diff changeset	325 if (knobs[COLAMD_DENSE_COL] >= 0)
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	326 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	327 << ", 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	328 << knobs[COLAMD_DENSE_COL] << "*sqrt (size(A)))"
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	329 << " entries removed\n";
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	330 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	331 octave_stdout << "knobs(2): " << User_knobs (1)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	332 << ", only completely dense columns removed\n";
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	333
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	334 octave_stdout << "knobs(3): " << User_knobs (2)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	335 << ", statistics and knobs printed\n";
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	336
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	337 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	338 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	339
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	340 octave_idx_type n_row, n_col, nnz;
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	341 octave_idx_type ridx, cidx;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	342 SparseComplexMatrix scm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	343 SparseMatrix sm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	344
5631 7171d19706df [project @ 2006-02-22 20:15:06 by dbateman] dbateman parents: 5604 diff changeset	345 if (args(0).is_sparse_type ())
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	346 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	347 if (args(0).is_complex_type ())
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	348 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	349 scm = args(0). sparse_complex_matrix_value ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	350 n_row = scm.rows ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	351 n_col = scm.cols ();
10527 b4d2080b6df7 Replace nzmax by nnz as needed David Bateman <dbateman@free.fr> parents: 10282 diff changeset	352 nnz = scm.nnz ();
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	353 ridx = scm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	354 cidx = scm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	355 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	356 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	357 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	358 sm = args(0).sparse_matrix_value ();
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	359
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	360 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	361 n_col = sm.cols ();
10527 b4d2080b6df7 Replace nzmax by nnz as needed David Bateman <dbateman@free.fr> parents: 10282 diff changeset	362 nnz = sm.nnz ();
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	363 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	364 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	365 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	366 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	367 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	368 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	369 if (args(0).is_complex_type ())
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	370 sm = SparseMatrix (real (args(0).complex_matrix_value ()));
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	371 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	372 sm = SparseMatrix (args(0).matrix_value ());
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	373
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	374 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	375 n_col = sm.cols ();
10527 b4d2080b6df7 Replace nzmax by nnz as needed David Bateman <dbateman@free.fr> parents: 10282 diff changeset	376 nnz = sm.nnz ();
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	377 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	378 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	379 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	380
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	381 // Allocate workspace for colamd
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	382 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	383 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	384 p[i] = cidx[i];
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	385
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	386 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	387 OCTAVE_LOCAL_BUFFER (octave_idx_type, A, Alen);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	388 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	389 A[i] = ridx[i];
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	390
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	391 // Order the columns (destroys A)
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	392 OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, COLAMD_STATS);
b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	393 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	394 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	395 COLAMD_NAME (_report) (stats) ;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	396 error ("colamd: internal error!");
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	397 return retval;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	398 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	399
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	400 // column elimination tree post-ordering (reuse variables)
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	401 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	402 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	403 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	404
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	405 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	406 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	407 colbeg[i] = cidx[p[i]];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	408 colend[i] = cidx[p[i]+1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	409 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	410
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	411 coletree (ridx, colbeg, colend, etree, n_row, n_col);
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	412
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	413 // Calculate the tree post-ordering
7924 4976f66d469b miscellaneous cleanup John W. Eaton <jwe@octave.org> parents: 7520 diff changeset	414 tree_postorder (n_col, etree, colbeg);
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	415
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	416 // return the permutation vector
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	417 NDArray out_perm (dim_vector (1, n_col));
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	418 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	419 out_perm(i) = p[colbeg[i]] + 1;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	420
7924 4976f66d469b miscellaneous cleanup John W. Eaton <jwe@octave.org> parents: 7520 diff changeset	421 retval(0) = out_perm;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	422
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	423 // print stats if spumoni > 0
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	424 if (spumoni > 0)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	425 COLAMD_NAME (_report) (stats) ;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	426
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	427 // Return the stats vector
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	428 if (nargout == 2)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	429 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	430 NDArray out_stats (dim_vector (1, COLAMD_STATS));
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	431 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	432 out_stats(i) = stats[i] ;
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	433 retval(1) = out_stats;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	434
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	435 // 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	436 // jumbled matrix. note that this correction doesn't
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	437 // occur if symamd returns FALSE
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	438 out_stats (COLAMD_INFO1) ++ ;
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	439 out_stats (COLAMD_INFO2) ++ ;
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	440 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	441 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	442
5451 ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	443 #else
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	444
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	445 error ("colamd: not available in this version of Octave");
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	446
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	447 #endif
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	448
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	449 return retval;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	450 }
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 DEFUN_DLD (symamd, args, nargout,
17787 175b392e91fe Use GNU style coding conventions for code in libinterp/ Rik <rik@octave.org> parents: 17744 diff changeset	453 "-- texinfo --\n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	454 @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	455 @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	456 @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	457 @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	458 \n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	459 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	460 vector p such that @code{@var{S}(@var{p}, @var{p})} tends to have a\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	461 sparser Cholesky@tie{}factor than @var{S}. Sometimes @code{symamd} works\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	462 well for symmetric indefinite matrices too. The matrix @var{S} is assumed\n\
12642 f96b9b9f141b doc: Periodic grammarcheck and spellcheck of documentation. Rik <octave@nomad.inbox5.com> parents: 12575 diff changeset	463 to be symmetric; only the strictly lower triangular part is referenced.\n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	464 @var{S} must be square.\n\
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	465 \n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	466 @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	467 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	468 @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	469 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	470 removed if @code{@var{knobs}(1) < 0}. If @code{@var{knobs} (2)} is nonzero,\n\
12642 f96b9b9f141b doc: Periodic grammarcheck and spellcheck of documentation. Rik <octave@nomad.inbox5.com> parents: 12575 diff changeset	471 @code{stats} and @var{knobs} are printed. The default is @code{@var{knobs}\n\
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	472 = [10 0]}. Note that @var{knobs} differs from earlier versions of symamd.\n\
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	473 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	474 @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	475 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	476 statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1) =\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	477 @var{stats}(2)} is the number of dense or empty rows and columns\n\
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	478 ignored by SYMAMD and @code{@var{stats}(3)} is the number of garbage\n\
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	479 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	480 (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	481 integers).\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	482 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	483 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	484 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	485 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	486 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	487 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	488 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	489 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	490 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	491 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	492 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	493 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	494 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	495 \n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	496 @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	497 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	498 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	499 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	500 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	501 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	502 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	503 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	504 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	505 \n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	506 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	507 \n\
19074 0850b5212619 doc: Add @nospell macro around proper names in documentation. Rik <rik@octave.org> parents: 17787 diff changeset	508 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	509 @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	510 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	511 @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	512 @seealso{colperm, colamd}\n\
2618a0750ae6 [project @ 2006-03-06 21:26:48 by jwe] jwe parents: 5631 diff changeset	513 @end deftypefn")
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	514 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	515 octave_value_list retval;
5451 ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	516
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	517 #ifdef HAVE_COLAMD
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	518
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	519 int nargin = args.length ();
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	520 int spumoni = 0;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	521
10282 c9780d8e228c fix invalid checks in amd functions Jaroslav Hajek <highegg@gmail.com> parents: 10155 diff changeset	522 if (nargout > 2 \|\| nargin < 1 \|\| nargin > 2)
5823 080c08b192d8 [project @ 2006-05-19 05:32:17 by jwe] jwe parents: 5760 diff changeset	523 print_usage ();
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	524 else
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	525 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	526 // Get knobs
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	527 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS);
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	528 COLAMD_NAME (_set_defaults) (knobs);
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	529
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	530 // Check for user-passed knobs
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	531 if (nargin == 2)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	532 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	533 NDArray User_knobs = args(1).array_value ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	534 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	535
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	536 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	537 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	538 if (nel_User_knobs > 1)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	539 spumoni = static_cast<int> (User_knobs (1));
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	540 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	541
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	542 // print knob settings if spumoni is set
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	543 if (spumoni > 0)
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	544 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	545 << knobs[COLAMD_DENSE_ROW] << std::endl;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	546
13219 cf5ebc0e47e4 fix warnings for unused but set variables and shadowed variables John W. Eaton <jwe@octave.org> parents: 12642 diff changeset	547 octave_idx_type n_row, n_col;
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	548 octave_idx_type ridx, cidx;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	549 SparseMatrix sm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	550 SparseComplexMatrix scm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	551
5631 7171d19706df [project @ 2006-02-22 20:15:06 by dbateman] dbateman parents: 5604 diff changeset	552 if (args(0).is_sparse_type ())
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	553 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	554 if (args(0).is_complex_type ())
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	555 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	556 scm = args(0).sparse_complex_matrix_value ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	557 n_row = scm.rows ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	558 n_col = scm.cols ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	559 ridx = scm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	560 cidx = scm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	561 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	562 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	563 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	564 sm = args(0).sparse_matrix_value ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	565 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	566 n_col = sm.cols ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	567 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	568 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	569 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	570 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	571 else
10154 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 if (args(0).is_complex_type ())
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	574 sm = SparseMatrix (real (args(0).complex_matrix_value ()));
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	575 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	576 sm = SparseMatrix (args(0).matrix_value ());
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	577
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	578 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	579 n_col = sm.cols ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	580 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	581 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	582 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	583
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	584 if (n_row != n_col)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	585 {
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	586 error ("symamd: matrix S must be square");
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	587 return retval;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	588 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	589
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	590 // Allocate workspace for symamd
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	591 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	592 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	593 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	594 knobs, stats, &calloc, &free))
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	595 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	596 SYMAMD_NAME (_report) (stats) ;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	597 error ("symamd: internal error!") ;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	598 return retval;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	599 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	600
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	601 // column elimination tree post-ordering
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	602 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	603 symetree (ridx, cidx, etree, perm, n_col);
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	604
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	605 // Calculate the tree post-ordering
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	606 OCTAVE_LOCAL_BUFFER (octave_idx_type, post, n_col + 1);
7924 4976f66d469b miscellaneous cleanup John W. Eaton <jwe@octave.org> parents: 7520 diff changeset	607 tree_postorder (n_col, etree, post);
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	608
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	609 // return the permutation vector
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	610 NDArray out_perm (dim_vector (1, n_col));
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	611 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	612 out_perm(i) = perm[post[i]] + 1;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	613
7924 4976f66d469b miscellaneous cleanup John W. Eaton <jwe@octave.org> parents: 7520 diff changeset	614 retval(0) = out_perm;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	615
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	616 // print stats if spumoni > 0
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	617 if (spumoni > 0)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	618 SYMAMD_NAME (_report) (stats) ;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	619
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	620 // Return the stats vector
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	621 if (nargout == 2)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	622 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	623 NDArray out_stats (dim_vector (1, COLAMD_STATS));
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	624 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	625 out_stats(i) = stats[i] ;
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	626 retval(1) = out_stats;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	627
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	628 // 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	629 // jumbled matrix. note that this correction doesn't
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	630 // occur if symamd returns FALSE
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	631 out_stats (COLAMD_INFO1) ++ ;
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	632 out_stats (COLAMD_INFO2) ++ ;
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	633 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	634 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	635
5451 ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	636 #else
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	637
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	638 error ("symamd: not available in this version of Octave");
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	639
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	640 #endif
ed08548b9054 [project @ 2005-09-15 19:52:50 by jwe] jwe parents: 5440 diff changeset	641
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	642 return retval;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	643 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	644
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	645 DEFUN_DLD (etree, args, nargout,
17787 175b392e91fe Use GNU style coding conventions for code in libinterp/ Rik <rik@octave.org> parents: 17744 diff changeset	646 "-- texinfo --\n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	647 @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	648 @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	649 @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	650 \n\
14038 b0cdd60db5e5 doc: Grammarcheck documentation ahead of 3.6.0 release. Rik <octave@nomad.inbox5.com> parents: 13219 diff changeset	651 Return the elimination tree for the matrix @var{S}. By default @var{S}\n\
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	652 is assumed to be symmetric and the symmetric elimination tree is\n\
9064 7c02ec148a3c Check grammar on all .cc files Rik <rdrider0-list@yahoo.com> parents: 8920 diff changeset	653 returned. The argument @var{typ} controls whether a symmetric or\n\
7c02ec148a3c Check grammar on all .cc files Rik <rdrider0-list@yahoo.com> parents: 8920 diff changeset	654 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	655 @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	656 respectively.\n\
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	657 \n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	658 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	659 permutations on the tree.\n\
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	660 @end deftypefn")
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	661 {
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	662 octave_value_list retval;
5297 234abf4c74dd [project @ 2005-04-21 21:29:46 by jwe] jwe parents: 5164 diff changeset	663
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	664 int nargin = args.length ();
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	665
10282 c9780d8e228c fix invalid checks in amd functions Jaroslav Hajek <highegg@gmail.com> parents: 10155 diff changeset	666 if (nargout > 2 \|\| nargin < 1 \|\| nargin > 2)
5823 080c08b192d8 [project @ 2006-05-19 05:32:17 by jwe] jwe parents: 5760 diff changeset	667 print_usage ();
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	668 else
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	669 {
13219 cf5ebc0e47e4 fix warnings for unused but set variables and shadowed variables John W. Eaton <jwe@octave.org> parents: 12642 diff changeset	670 octave_idx_type n_row, n_col;
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	671 octave_idx_type ridx, cidx;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	672 bool is_sym = true;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	673 SparseMatrix sm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	674 SparseComplexMatrix scm;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	675
5631 7171d19706df [project @ 2006-02-22 20:15:06 by dbateman] dbateman parents: 5604 diff changeset	676 if (args(0).is_sparse_type ())
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	677 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	678 if (args(0).is_complex_type ())
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	679 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	680 scm = args(0).sparse_complex_matrix_value ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	681 n_row = scm.rows ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	682 n_col = scm.cols ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	683 ridx = scm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	684 cidx = scm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	685 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	686 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	687 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	688 sm = args(0).sparse_matrix_value ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	689 n_row = sm.rows ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	690 n_col = sm.cols ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	691 ridx = sm.xridx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	692 cidx = sm.xcidx ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	693 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	694
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	695 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	696 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	697 {
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	698 error ("etree: S must be a sparse matrix");
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	699 return retval;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	700 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	701
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	702 if (nargin == 2)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	703 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	704 if (args(1).is_string ())
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	705 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	706 std::string str = args(1).string_value ();
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	707 if (str.find ("C") == 0 \|\| str.find ("c") == 0)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	708 is_sym = false;
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 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	711 {
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	712 error ("etree: TYP must be a string");
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	713 return retval;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	714 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	715 }
7924 4976f66d469b miscellaneous cleanup John W. Eaton <jwe@octave.org> parents: 7520 diff changeset	716
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	717 // column elimination tree post-ordering (reuse variables)
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	718 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	719
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	720 if (is_sym)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	721 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	722 if (n_row != n_col)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	723 {
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	724 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	725 return retval;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	726 }
7924 4976f66d469b miscellaneous cleanup John W. Eaton <jwe@octave.org> parents: 7520 diff changeset	727
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	728 symetree (ridx, cidx, etree, 0, n_col);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	729 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	730 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	731 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	732 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	733 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col);
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	734
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	735 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	736 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	737 colbeg[i] = cidx[i];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	738 colend[i] = cidx[i+1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	739 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	740
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	741 coletree (ridx, colbeg, colend, etree, n_row, n_col);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	742 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	743
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	744 NDArray tree (dim_vector (1, n_col));
5440 b73d469ef0c9 [project @ 2005-09-04 12:31:45 by dbateman] dbateman parents: 5307 diff changeset	745 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	746 // 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	747 // Convert for matlab compatiable output
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	748 if (etree[i] == n_col)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	749 tree(i) = 0;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	750 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	751 tree(i) = etree[i] + 1;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	752
7924 4976f66d469b miscellaneous cleanup John W. Eaton <jwe@octave.org> parents: 7520 diff changeset	753 retval(0) = tree;
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	754
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	755 if (nargout == 2)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	756 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	757 // Calculate the tree post-ordering
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	758 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	759 tree_postorder (n_col, etree, post);
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	760
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	761 NDArray postorder (dim_vector (1, n_col));
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	762 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	763 postorder(i) = post[i] + 1;
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 retval(1) = postorder;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9064 diff changeset	766 }
5164 57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	767 }
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	768
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	769 return retval;
57077d0ddc8e [project @ 2005-02-25 19:55:24 by jwe] jwe parents: diff changeset	770 }

Mercurial > octave-nkf

annotate libinterp/dldfcn/colamd.cc @ 19731:4197fc428c7d