octave: libinterp/dldfcn/symrcm.cc annotate

annotate libinterp/dldfcn/symrcm.cc @ 21110:3d0d84305600

Use err_square_matrix_required more widely. * errwarn.h (err_square_matrix_required): Change prototype to take a second argument which is the name of the variable that is not square. * errwarn.cc (err_square_matrix_required): Take second argument NAME and print "NAME must be a square matrix". * balance.cc (Fbalance): Update calling form of err_square_matrix_required. * det.cc (Fdet): Update calling form of err_square_matrix_required. Update pattern in BIST tests to match new output. * eig.cc (Feig): Update calling form of err_square_matrix_required. Update pattern in BIST tests to match new output. * hess.cc (Fhess): Update calling form of err_square_matrix_required. Update pattern in BIST tests to match new output. * inv.cc (Finv): Update calling form of err_square_matrix_required. Update pattern in BIST tests to match new output. * qz.cc (Fqz): Update calling form of err_square_matrix_required. * schur.cc (Fschur): Update calling form of err_square_matrix_required. Update pattern in BIST tests to match new output. * sqrtm.cc (Fsqrtm): Update calling form of err_square_matrix_required. * sylvester.cc (Fsylvester): Update calling form of err_square_matrix_required. Update pattern in BIST tests to match new output. * amd.cc (Famd): Switch from error to err_square_matrix_required. Update pattern in BIST tests to match new output. * ccolamd.cc (Fcsymamd): Switch from error to err_square_matrix_required. * chol.cc (Fcholdelete, Fcholshift): Switch from error to err_square_matrix_required. * colamd.cc (Fsymamd): Switch from error to err_square_matrix_required. * symbfact.cc (Fsymfact): Switch from error to err_square_matrix_required. * symrcm.cc (Fsymrcm): Update calling form of err_square_matrix_required.

author	Rik <rik@octave.org>
date	Tue, 19 Jan 2016 14:09:56 -0800
parents	e39e05d90788
children	f5b17eb2508b

rev	line source
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	1 /*
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	2
19697 4197fc428c7d maint: Update copyright notices for 2015. John W. Eaton <jwe@octave.org> parents: 19405 diff changeset	3 Copyright (C) 2007-2015 Michael Weitzel
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	4
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	5 This file is part of Octave.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	6
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	7 Octave is free software; you can redistribute it and/or modify it
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	8 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: 6959 diff changeset	9 Free Software Foundation; either version 3 of the License, or (at your
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe] jwe parents: 6959 diff changeset	10 option) any later version.
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	11
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	12 Octave is distributed in the hope that it will be useful, but WITHOUT
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	15 for more details.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	16
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	17 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: 6959 diff changeset	18 along with Octave; see the file COPYING. If not, see
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe] jwe parents: 6959 diff changeset	19 <http://www.gnu.org/licenses/>.
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	20
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	21 */
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	22
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	23 /*
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	24 An implementation of the Reverse Cuthill-McKee algorithm (symrcm)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	25
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	26 The implementation of this algorithm is based in the descriptions found in
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	27
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	28 @INPROCEEDINGS{,
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	29 author = {E. Cuthill and J. McKee},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	30 title = {Reducing the Bandwidth of Sparse Symmetric Matrices},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	31 booktitle = {Proceedings of the 24th ACM National Conference},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	32 publisher = {Brandon Press},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	33 pages = {157 -- 172},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	34 location = {New Jersey},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	35 year = {1969}
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	36 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	37
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	38 @BOOK{,
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	39 author = {Alan George and Joseph W. H. Liu},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	40 title = {Computer Solution of Large Sparse Positive Definite Systems},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	41 publisher = {Prentice Hall Series in Computational Mathematics},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	42 ISBN = {0-13-165274-5},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	43 year = {1981}
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	44 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	45
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	46 The algorithm represents a heuristic approach to the NP-complete minimum
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	47 bandwidth problem.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	48
6610 fb8bddaa07c4 [project @ 2007-05-09 02:28:40 by jwe] jwe parents: 6608 diff changeset	49 Written by Michael Weitzel <michael.weitzel@@uni-siegen.de>
fb8bddaa07c4 [project @ 2007-05-09 02:28:40 by jwe] jwe parents: 6608 diff changeset	50 <weitzel@@ldknet.org>
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	51 */
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	52
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	53 #ifdef HAVE_CONFIG_H
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	54 #include <config.h>
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	55 #endif
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	56
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	57 #include "ov.h"
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	58 #include "defun-dld.h"
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	59 #include "error.h"
21100 e39e05d90788 Switch gripe_XXX to either err_XXX or warn_XXX naming scheme. Rik <rik@octave.org> parents: 21024 diff changeset	60 #include "errwarn.h"
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	61 #include "utils.h"
8377 25bc2d31e1bf improve OCTAVE_LOCAL_BUFFER Jaroslav Hajek <highegg@gmail.com> parents: 7650 diff changeset	62 #include "oct-locbuf.h"
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	63
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	64 #include "ov-re-mat.h"
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	65 #include "ov-re-sparse.h"
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	66 #include "ov-cx-sparse.h"
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	67 #include "oct-sparse.h"
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	68
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	69 // A node struct for the Cuthill-McKee algorithm
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	70 struct CMK_Node
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	71 {
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	72 // the node's id (matrix row index)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	73 octave_idx_type id;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	74 // the node's degree
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	75 octave_idx_type deg;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	76 // minimal distance to the root of the spanning tree
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	77 octave_idx_type dist;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	78 };
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	79
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	80 // A simple queue.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	81 // Queues Q have a fixed maximum size N (rows,cols of the matrix) and are
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	82 // stored in an array. qh and qt point to queue head and tail.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	83
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	84 // Enqueue operation (adds a node "o" at the tail)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	85
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	86 inline static void
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	87 Q_enq (CMK_Node *Q, octave_idx_type N, octave_idx_type& qt, const CMK_Node& o)
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	88 {
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	89 Q[qt] = o;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	90 qt = (qt + 1) % (N + 1);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	91 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	92
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	93 // Dequeue operation (removes a node from the head)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	94
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	95 inline static CMK_Node
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	96 Q_deq (CMK_Node * Q, octave_idx_type N, octave_idx_type& qh)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	97 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	98 CMK_Node r = Q[qh];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	99 qh = (qh + 1) % (N + 1);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	100 return r;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	101 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	102
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	103 // Predicate (queue empty)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	104 #define Q_empty(Q, N, qh, qt) ((qh) == (qt))
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	105
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	106 // A simple, array-based binary heap (used as a priority queue for nodes)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	107
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	108 // the left descendant of entry i
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	109 #define LEFT(i) (((i) << 1) + 1) // = (2*(i)+1)
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	110 // the right descendant of entry i
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	111 #define RIGHT(i) (((i) << 1) + 2) // = (2*(i)+2)
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	112 // the parent of entry i
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	113 #define PARENT(i) (((i) - 1) >> 1) // = floor(((i)-1)/2)
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	114
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	115 // Builds a min-heap (the root contains the smallest element). A is an array
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	116 // with the graph's nodes, i is a starting position, size is the length of A.
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	117
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	118 static void
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	119 H_heapify_min (CMK_Node *A, octave_idx_type i, octave_idx_type size)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	120 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	121 octave_idx_type j = i;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	122 for (;;)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	123 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	124 octave_idx_type l = LEFT(j);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	125 octave_idx_type r = RIGHT(j);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	126
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	127 octave_idx_type smallest;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	128 if (l < size && A[l].deg < A[j].deg)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	129 smallest = l;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	130 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	131 smallest = j;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	132
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	133 if (r < size && A[r].deg < A[smallest].deg)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	134 smallest = r;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	135
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	136 if (smallest != j)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	137 {
14862 bbdc822be2b9 smyrcm.cc: use std::swap instead of custom swap code. Rik <octave@nomad.inbox5.com> parents: 14854 diff changeset	138 std::swap (A[j], A[smallest]);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	139 j = smallest;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	140 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	141 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	142 break;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	143 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	144 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	145
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	146 // Heap operation insert. Running time is O(log(n))
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	147
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	148 static void
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	149 H_insert (CMK_Node *H, octave_idx_type& h, const CMK_Node& o)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	150 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	151 octave_idx_type i = h++;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	152
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	153 H[i] = o;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	154
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	155 if (i == 0)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	156 return;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	157 do
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	158 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	159 octave_idx_type p = PARENT(i);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	160 if (H[i].deg < H[p].deg)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	161 {
14862 bbdc822be2b9 smyrcm.cc: use std::swap instead of custom swap code. Rik <octave@nomad.inbox5.com> parents: 14854 diff changeset	162 std::swap (H[i], H[p]);
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	163
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	164 i = p;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	165 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	166 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	167 break;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	168 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	169 while (i > 0);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	170 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	171
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	172 // Heap operation remove-min. Removes the smalles element in O(1) and
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	173 // reorganizes the heap optionally in O(log(n))
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	174
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	175 inline static CMK_Node
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	176 H_remove_min (CMK_Node H, octave_idx_type& h, int reorg/=1*/)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	177 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	178 CMK_Node r = H[0];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	179 H[0] = H[--h];
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	180 if (reorg)
14854 5ae9f0f77635 maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory Rik <octave@nomad.inbox5.com> parents: 14361 diff changeset	181 H_heapify_min (H, 0, h);
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	182 return r;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	183 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	184
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	185 // Predicate (heap empty)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	186 #define H_empty(H, h) ((h) == 0)
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	187
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	188 // Helper function for the Cuthill-McKee algorithm. Tries to determine a
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	189 // pseudo-peripheral node of the graph as starting node.
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	190
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	191 static octave_idx_type
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	192 find_starting_node (octave_idx_type N, const octave_idx_type *ridx,
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	193 const octave_idx_type cidx, const octave_idx_type ridx2,
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	194 const octave_idx_type cidx2, octave_idx_type D,
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	195 octave_idx_type start)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	196 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	197 CMK_Node w;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	198
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	199 OCTAVE_LOCAL_BUFFER (CMK_Node, Q, N+1);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	200 boolNDArray btmp (dim_vector (1, N), false);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	201 bool *visit = btmp.fortran_vec ();
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	202
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	203 octave_idx_type qh = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	204 octave_idx_type qt = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	205 CMK_Node x;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	206 x.id = start;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	207 x.deg = D[start];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	208 x.dist = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	209 Q_enq (Q, N, qt, x);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	210 visit[start] = true;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	211
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	212 // distance level
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	213 octave_idx_type level = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	214 // current largest "eccentricity"
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	215 octave_idx_type max_dist = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	216
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	217 for (;;)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	218 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	219 while (! Q_empty (Q, N, qh, qt))
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	220 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	221 CMK_Node v = Q_deq (Q, N, qh);
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	222
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	223 if (v.dist > x.dist \|\| (v.id != x.id && v.deg > x.deg))
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	224 x = v;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	225
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	226 octave_idx_type i = v.id;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	227
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	228 // add all unvisited neighbors to the queue
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	229 octave_idx_type j1 = cidx[i];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	230 octave_idx_type j2 = cidx2[i];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	231 while (j1 < cidx[i+1] \|\| j2 < cidx2[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	232 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	233 OCTAVE_QUIT;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	234
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	235 if (j1 == cidx[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	236 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	237 octave_idx_type r2 = ridx2[j2++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	238 if (! visit[r2])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	239 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	240 // the distance of node j is dist(i)+1
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	241 w.id = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	242 w.deg = D[r2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	243 w.dist = v.dist+1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	244 Q_enq (Q, N, qt, w);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	245 visit[r2] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	246
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	247 if (w.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	248 level = w.dist;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	249 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	250 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	251 else if (j2 == cidx2[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	252 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	253 octave_idx_type r1 = ridx[j1++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	254 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	255 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	256 // the distance of node j is dist(i)+1
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	257 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	258 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	259 w.dist = v.dist+1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	260 Q_enq (Q, N, qt, w);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	261 visit[r1] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	262
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	263 if (w.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	264 level = w.dist;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	265 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	266 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	267 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	268 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	269 octave_idx_type r1 = ridx[j1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	270 octave_idx_type r2 = ridx2[j2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	271 if (r1 <= r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	272 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	273 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	274 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	275 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	276 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	277 w.dist = v.dist+1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	278 Q_enq (Q, N, qt, w);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	279 visit[r1] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	280
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	281 if (w.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	282 level = w.dist;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	283 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	284 j1++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	285 if (r1 == r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	286 j2++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	287 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	288 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	289 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	290 if (! visit[r2])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	291 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	292 w.id = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	293 w.deg = D[r2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	294 w.dist = v.dist+1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	295 Q_enq (Q, N, qt, w);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	296 visit[r2] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	297
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	298 if (w.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	299 level = w.dist;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	300 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	301 j2++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	302 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	303 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	304 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	305 } // finish of BFS
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	306
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	307 if (max_dist < x.dist)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	308 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	309 max_dist = x.dist;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	310
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	311 for (octave_idx_type i = 0; i < N; i++)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	312 visit[i] = false;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	313
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	314 visit[x.id] = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	315 x.dist = 0;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	316 qt = qh = 0;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	317 Q_enq (Q, N, qt, x);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	318 }
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	319 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	320 break;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	321 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	322 return x.id;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	323 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	324
18812 9ac2357f19bc doc: Replace "non-zero" with "nonzero" to match existing usage. Rik <rik@octave.org> parents: 18100 diff changeset	325 // Calculates the node's degrees. This means counting the nonzero elements
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	326 // in the symmetric matrix' rows. This works for non-symmetric matrices
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	327 // as well.
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	328
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	329 static octave_idx_type
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	330 calc_degrees (octave_idx_type N, const octave_idx_type *ridx,
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	331 const octave_idx_type cidx, octave_idx_type D)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	332 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	333 octave_idx_type max_deg = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	334
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	335 for (octave_idx_type i = 0; i < N; i++)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	336 D[i] = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	337
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	338 for (octave_idx_type j = 0; j < N; j++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	339 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	340 for (octave_idx_type i = cidx[j]; i < cidx[j+1]; i++)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	341 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	342 OCTAVE_QUIT;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	343 octave_idx_type k = ridx[i];
18812 9ac2357f19bc doc: Replace "non-zero" with "nonzero" to match existing usage. Rik <rik@octave.org> parents: 18100 diff changeset	344 // there is a nonzero element (k,j)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	345 D[k]++;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	346 if (D[k] > max_deg)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	347 max_deg = D[k];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	348 // if there is no element (j,k) there is one in
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	349 // the symmetric matrix:
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	350 if (k != j)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	351 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	352 bool found = false;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	353 for (octave_idx_type l = cidx[k]; l < cidx[k + 1]; l++)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	354 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	355 OCTAVE_QUIT;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	356
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	357 if (ridx[l] == j)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	358 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	359 found = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	360 break;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	361 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	362 else if (ridx[l] > j)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	363 break;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	364 }
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	365
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	366 if (! found)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	367 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	368 // A(j,k) == 0
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	369 D[j]++;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	370 if (D[j] > max_deg)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	371 max_deg = D[j];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	372 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	373 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	374 }
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	375 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	376 return max_deg;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	377 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	378
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	379 // Transpose of the structure of a square sparse matrix
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	380
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	381 static void
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	382 transpose (octave_idx_type N, const octave_idx_type *ridx,
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	383 const octave_idx_type cidx, octave_idx_type ridx2,
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	384 octave_idx_type *cidx2)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	385 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	386 octave_idx_type nz = cidx[N];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	387
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	388 OCTAVE_LOCAL_BUFFER (octave_idx_type, w, N + 1);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	389 for (octave_idx_type i = 0; i < N; i++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	390 w[i] = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	391 for (octave_idx_type i = 0; i < nz; i++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	392 w[ridx[i]]++;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	393 nz = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	394 for (octave_idx_type i = 0; i < N; i++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	395 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	396 OCTAVE_QUIT;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	397 cidx2[i] = nz;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	398 nz += w[i];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	399 w[i] = cidx2[i];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	400 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	401 cidx2[N] = nz;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	402 w[N] = nz;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	403
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	404 for (octave_idx_type j = 0; j < N; j++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	405 for (octave_idx_type k = cidx[j]; k < cidx[j + 1]; k++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	406 {
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	407 OCTAVE_QUIT;
15020 560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code. Rik <rik@octave.org> parents: 14862 diff changeset	408 octave_idx_type q = w[ridx[k]]++;
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	409 ridx2[q] = j;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	410 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	411 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	412
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	413 // An implementation of the Cuthill-McKee algorithm.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	414 DEFUN_DLD (symrcm, args, ,
17787 175b392e91fe Use GNU style coding conventions for code in libinterp/ Rik <rik@octave.org> parents: 17744 diff changeset	415 "-- texinfo --\n\
20853 1142cf6abc0d 2015 Code Sprint: remove class of function from docstring for all C++ files. Rik <rik@octave.org> parents: 20818 diff changeset	416 @deftypefn {} {@var{p} =} symrcm (@var{S})\n\
19040 0850b5212619 doc: Add @nospell macro around proper names in documentation. Rik <rik@octave.org> parents: 18812 diff changeset	417 Return the symmetric reverse @nospell{Cuthill-McKee} permutation of @var{S}.\n\
20163 075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19697 diff changeset	418 \n\
11553 01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory. Rik <octave@nomad.inbox5.com> parents: 11523 diff changeset	419 @var{p} is a permutation vector such that\n\
20163 075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19697 diff changeset	420 @code{@var{S}(@var{p}, @var{p})} tends to have its diagonal elements closer\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19697 diff changeset	421 to the diagonal than @var{S}. This is a good preordering for LU or\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19697 diff changeset	422 Cholesky@tie{}factorization of matrices that come from ``long, skinny''\n\
6610 fb8bddaa07c4 [project @ 2007-05-09 02:28:40 by jwe] jwe parents: 6608 diff changeset	423 problems. It works for both symmetric and asymmetric @var{S}.\n\
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	424 \n\
20163 075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19697 diff changeset	425 The algorithm represents a heuristic approach to the NP-complete bandwidth\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19697 diff changeset	426 minimization problem. The implementation is based in the descriptions found\n\
075a5e2e1ba5 doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19697 diff changeset	427 in\n\
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	428 \n\
19040 0850b5212619 doc: Add @nospell macro around proper names in documentation. Rik <rik@octave.org> parents: 18812 diff changeset	429 @nospell{E. Cuthill, J. McKee}. @cite{Reducing the Bandwidth of Sparse\n\
19405 cbce5d1bcaf9 doc: Periodic grammarcheck of documentation. Rik <rik@octave.org> parents: 19040 diff changeset	430 Symmetric Matrices}. Proceedings of the 24th ACM National Conference,\n\
cbce5d1bcaf9 doc: Periodic grammarcheck of documentation. Rik <rik@octave.org> parents: 19040 diff changeset	431 157--172 1969, Brandon Press, New Jersey.\n\
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	432 \n\
19040 0850b5212619 doc: Add @nospell macro around proper names in documentation. Rik <rik@octave.org> parents: 18812 diff changeset	433 @nospell{A. George, J.W.H. Liu}. @cite{Computer Solution of Large Sparse\n\
10791 3140cb7a05a1 Add spellchecker scripts for Octave and run spellcheck of documentation Rik <octave@nomad.inbox5.com> parents: 10154 diff changeset	434 Positive Definite Systems}, Prentice Hall Series in Computational\n\
6610 fb8bddaa07c4 [project @ 2007-05-09 02:28:40 by jwe] jwe parents: 6608 diff changeset	435 Mathematics, ISBN 0-13-165274-5, 1981.\n\
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	436 \n\
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	437 @seealso{colperm, colamd, symamd}\n\
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	438 @end deftypefn")
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	439 {
20818 cef0448a6ed2 eliminate unnecessary uses of nargin John W. Eaton <jwe@octave.org> parents: 20790 diff changeset	440 if (args.length () != 1)
20790 c2d9556d51d0 eliminate return statements after calls to print_usage John W. Eaton <jwe@octave.org> parents: 20555 diff changeset	441 print_usage ();
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	442
20939 b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	443 octave_value retval;
b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	444
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	445 octave_value arg = args(0);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	446
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	447 // the parameter of the matrix is converted into a sparse matrix
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	448 //(if necessary)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	449 octave_idx_type *cidx;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	450 octave_idx_type *ridx;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	451 SparseMatrix Ar;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	452 SparseComplexMatrix Ac;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	453
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	454 if (arg.is_real_type ())
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	455 {
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	456 Ar = arg.sparse_matrix_value ();
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	457 // Note cidx/ridx are const, so use xridx and xcidx...
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	458 cidx = Ar.xcidx ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	459 ridx = Ar.xridx ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	460 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	461 else
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	462 {
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	463 Ac = arg.sparse_complex_matrix_value ();
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	464 cidx = Ac.xcidx ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	465 ridx = Ac.xridx ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	466 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	467
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	468 octave_idx_type nr = arg.rows ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	469 octave_idx_type nc = arg.columns ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	470
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	471 if (nr != nc)
21110 3d0d84305600 Use err_square_matrix_required more widely. Rik <rik@octave.org> parents: 21100 diff changeset	472 err_square_matrix_required ("symrcm", "S");
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	473
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	474 if (nr == 0 && nc == 0)
20939 b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	475 return ovl (NDArray (dim_vector (1, 0)));
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	476
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	477 // sizes of the heaps
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	478 octave_idx_type s = 0;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	479
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	480 // head- and tail-indices for the queue
18100 6a71e5030df5 Follow coding convention of defining and initializing only 1 variable per line in liboctinterp. Rik <rik@octave.org> parents: 17787 diff changeset	481 octave_idx_type qt = 0;
6a71e5030df5 Follow coding convention of defining and initializing only 1 variable per line in liboctinterp. Rik <rik@octave.org> parents: 17787 diff changeset	482 octave_idx_type qh = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	483 CMK_Node v, w;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	484 // dimension of the matrix
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	485 octave_idx_type N = nr;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	486
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	487 OCTAVE_LOCAL_BUFFER (octave_idx_type, cidx2, N + 1);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	488 OCTAVE_LOCAL_BUFFER (octave_idx_type, ridx2, cidx[N]);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	489 transpose (N, ridx, cidx, ridx2, cidx2);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	490
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	491 // the permutation vector
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	492 NDArray P (dim_vector (1, N));
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	493
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	494 // compute the node degrees
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	495 OCTAVE_LOCAL_BUFFER (octave_idx_type, D, N);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	496 octave_idx_type max_deg = calc_degrees (N, ridx, cidx, D);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	497
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	498 // if none of the nodes has a degree > 0 (a matrix of zeros)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	499 // the return value corresponds to the identity permutation
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	500 if (max_deg == 0)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	501 {
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	502 for (octave_idx_type i = 0; i < N; i++)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	503 P(i) = i;
20939 b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	504
b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	505 return ovl (P);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	506 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	507
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	508 // a heap for the a node's neighbors. The number of neighbors is
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	509 // limited by the maximum degree max_deg:
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	510 OCTAVE_LOCAL_BUFFER (CMK_Node, S, max_deg);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	511
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	512 // a queue for the BFS. The array is always one element larger than
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	513 // the number of entries that are stored.
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	514 OCTAVE_LOCAL_BUFFER (CMK_Node, Q, N+1);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	515
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	516 // a counter (for building the permutation)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	517 octave_idx_type c = -1;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	518
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	519 // upper bound for the bandwidth (=quality of solution)
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	520 // initialize the bandwidth of the graph with 0. B contains the
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	521 // the maximum of the theoretical lower limits of the subgraphs
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	522 // bandwidths.
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	523 octave_idx_type B = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	524
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	525 // mark all nodes as unvisited; with the exception of the nodes
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	526 // that have degree==0 and build a CC of the graph.
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	527
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	528 boolNDArray btmp (dim_vector (1, N), false);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	529 bool *visit = btmp.fortran_vec ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	530
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	531 do
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	532 {
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	533 // locate an unvisited starting node of the graph
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	534 octave_idx_type i;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	535 for (i = 0; i < N; i++)
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	536 if (! visit[i])
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	537 break;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	538
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	539 // locate a probably better starting node
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	540 v.id = find_starting_node (N, ridx, cidx, ridx2, cidx2, D, i);
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	541
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	542 // mark the node as visited and enqueue it (a starting node
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	543 // for the BFS). Since the node will be a root of a spanning
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	544 // tree, its dist is 0.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	545 v.deg = D[v.id];
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	546 v.dist = 0;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	547 visit[v.id] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	548 Q_enq (Q, N, qt, v);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	549
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	550 // lower bound for the bandwidth of a subgraph
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	551 // keep a "level" in the spanning tree (= min. distance to the
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	552 // root) for determining the bandwidth of the computed
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	553 // permutation P
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	554 octave_idx_type Bsub = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	555 // min. dist. to the root is 0
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	556 octave_idx_type level = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	557 // the root is the first/only node on level 0
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	558 octave_idx_type level_N = 1;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	559
6677 9a8861bc2b34 [project @ 2007-05-31 19:39:12 by jwe] jwe parents: 6610 diff changeset	560 while (! Q_empty (Q, N, qh, qt))
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	561 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	562 v = Q_deq (Q, N, qh);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	563 i = v.id;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	564
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	565 c++;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	566
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	567 // for computing the inverse permutation P where
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	568 // A(inv(P),inv(P)) or P'AP is banded
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	569 // P(i) = c;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	570
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	571 // for computing permutation P where
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	572 // A(P(i),P(j)) or PAP' is banded
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	573 P(c) = i;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	574
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	575 // put all unvisited neighbors j of node i on the heap
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	576 s = 0;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	577 octave_idx_type j1 = cidx[i];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	578 octave_idx_type j2 = cidx2[i];
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	579
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	580 OCTAVE_QUIT;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	581 while (j1 < cidx[i+1] \|\| j2 < cidx2[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	582 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	583 OCTAVE_QUIT;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	584 if (j1 == cidx[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	585 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	586 octave_idx_type r2 = ridx2[j2++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	587 if (! visit[r2])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	588 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	589 // the distance of node j is dist(i)+1
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	590 w.id = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	591 w.deg = D[r2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	592 w.dist = v.dist+1;
14854 5ae9f0f77635 maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory Rik <octave@nomad.inbox5.com> parents: 14361 diff changeset	593 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	594 visit[r2] = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	595 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	596 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	597 else if (j2 == cidx2[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	598 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	599 octave_idx_type r1 = ridx[j1++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	600 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	601 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	602 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	603 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	604 w.dist = v.dist+1;
14854 5ae9f0f77635 maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory Rik <octave@nomad.inbox5.com> parents: 14361 diff changeset	605 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	606 visit[r1] = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	607 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	608 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	609 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	610 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	611 octave_idx_type r1 = ridx[j1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	612 octave_idx_type r2 = ridx2[j2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	613 if (r1 <= r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	614 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	615 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	616 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	617 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	618 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	619 w.dist = v.dist+1;
14854 5ae9f0f77635 maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory Rik <octave@nomad.inbox5.com> parents: 14361 diff changeset	620 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	621 visit[r1] = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	622 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	623 j1++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	624 if (r1 == r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	625 j2++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	626 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	627 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	628 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	629 if (! visit[r2])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	630 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	631 w.id = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	632 w.deg = D[r2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	633 w.dist = v.dist+1;
14854 5ae9f0f77635 maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory Rik <octave@nomad.inbox5.com> parents: 14361 diff changeset	634 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	635 visit[r2] = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	636 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	637 j2++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	638 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	639 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	640 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	641
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	642 // add the neighbors to the queue (sorted by node degree)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	643 while (! H_empty (S, s))
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	644 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	645 OCTAVE_QUIT;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	646
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	647 // locate a neighbor of i with minimal degree in O(log(N))
14854 5ae9f0f77635 maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory Rik <octave@nomad.inbox5.com> parents: 14361 diff changeset	648 v = H_remove_min (S, s, 1);
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	649
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	650 // entered the BFS a new level?
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	651 if (v.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	652 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	653 // adjustment of bandwith:
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	654 // "[...] the minimum bandwidth that
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	655 // can be obtained [...] is the
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	656 // maximum number of nodes per level"
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	657 if (Bsub < level_N)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	658 Bsub = level_N;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	659
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	660 level = v.dist;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	661 // v is the first node on the new level
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	662 level_N = 1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	663 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	664 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	665 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	666 // there is no new level but another node on
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	667 // this level:
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	668 level_N++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	669 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	670
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	671 // enqueue v in O(1)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	672 Q_enq (Q, N, qt, v);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	673 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	674
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	675 // synchronize the bandwidth with level_N once again:
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	676 if (Bsub < level_N)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	677 Bsub = level_N;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	678 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	679 // finish of BFS. If there are still unvisited nodes in the graph
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	680 // then it is split into CCs. The computed bandwidth is the maximum
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	681 // of all subgraphs. Update:
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	682 if (Bsub > B)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	683 B = Bsub;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	684 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	685 // are there any nodes left?
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	686 while (c+1 < N);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	687
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	688 // compute the reverse-ordering
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	689 s = N / 2 - 1;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	690 for (octave_idx_type i = 0, j = N - 1; i <= s; i++, j--)
14862 bbdc822be2b9 smyrcm.cc: use std::swap instead of custom swap code. Rik <octave@nomad.inbox5.com> parents: 14854 diff changeset	691 std::swap (P.elem (i), P.elem (j));
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	692
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	693 // increment all indices, since Octave is not C
20939 b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	694 return ovl (P+1);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	695 }

Mercurial > octave

annotate libinterp/dldfcn/symrcm.cc @ 21110:3d0d84305600