octave: libinterp/dldfcn/symrcm.cc annotate

annotate libinterp/dldfcn/symrcm.cc @ 20939:b17fda023ca6

maint: Use new C++ archetype in more files. Place input validation first in files. Move declaration of retval down in function to be closer to point of usage. Eliminate else clause after if () error. Use "return ovl()" where it makes sense. * find.cc, gammainc.cc, gcd.cc, getgrent.cc, getpwent.cc, givens.cc, graphics.cc, help.cc, hess.cc, hex2num.cc, input.cc, kron.cc, load-path.cc, load-save.cc, lookup.cc, mappers.cc, matrix_type.cc, mgorth.cc, nproc.cc, ordschur.cc, pager.cc, pinv.cc, pr-output.cc, profiler.cc, psi.cc, quad.cc, rcond.cc, regexp.cc, schur.cc, sighandlers.cc, sparse.cc, str2double.cc, strfind.cc, strfns.cc, sub2ind.cc, svd.cc, sylvester.cc, symtab.cc, syscalls.cc, sysdep.cc, time.cc, toplev.cc, tril.cc, tsearch.cc, typecast.cc, urlwrite.cc, utils.cc, variables.cc, __delaunayn__.cc, __eigs__.cc, __glpk__.cc, __magick_read__.cc, __osmesa_print__.cc, __voronoi__.cc, amd.cc, audiodevinfo.cc, audioread.cc, chol.cc, colamd.cc, dmperm.cc, fftw.cc, qr.cc, symbfact.cc, symrcm.cc, ov-bool-mat.cc, ov-cell.cc, ov-class.cc, ov-classdef.cc, ov-fcn-handle.cc, ov-fcn-inline.cc, ov-flt-re-mat.cc, ov-java.cc, ov-null-mat.cc, ov-oncleanup.cc, ov-re-mat.cc, ov-struct.cc, ov-typeinfo.cc, ov-usr-fcn.cc, ov.cc, octave.cc: Use new C++ archetype in more files.

author	Rik <rik@octave.org>
date	Fri, 18 Dec 2015 15:37:22 -0800
parents	1142cf6abc0d
children	6176560b03d9

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"
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	60 #include "gripes.h"
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)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	472 {
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	473 gripe_square_matrix_required ("symrcm");
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	474 return retval;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	475 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	476
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	477 if (nr == 0 && nc == 0)
20939 b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	478 return ovl (NDArray (dim_vector (1, 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 // sizes of the heaps
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	481 octave_idx_type s = 0;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	482
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	483 // 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	484 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	485 octave_idx_type qh = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	486 CMK_Node v, w;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	487 // dimension of the matrix
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	488 octave_idx_type N = nr;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	489
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	490 OCTAVE_LOCAL_BUFFER (octave_idx_type, cidx2, N + 1);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	491 OCTAVE_LOCAL_BUFFER (octave_idx_type, ridx2, cidx[N]);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	492 transpose (N, ridx, cidx, ridx2, cidx2);
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 // the permutation vector
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	495 NDArray P (dim_vector (1, N));
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	496
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	497 // compute the node degrees
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	498 OCTAVE_LOCAL_BUFFER (octave_idx_type, D, N);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	499 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	500
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	501 // 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	502 // the return value corresponds to the identity permutation
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	503 if (max_deg == 0)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	504 {
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	505 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	506 P(i) = i;
20939 b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	507
b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	508 return ovl (P);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	509 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	510
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	511 // 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	512 // limited by the maximum degree max_deg:
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	513 OCTAVE_LOCAL_BUFFER (CMK_Node, S, max_deg);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	514
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	515 // 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	516 // the number of entries that are stored.
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	517 OCTAVE_LOCAL_BUFFER (CMK_Node, Q, N+1);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	518
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	519 // a counter (for building the permutation)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	520 octave_idx_type c = -1;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	521
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	522 // upper bound for the bandwidth (=quality of solution)
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	523 // 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	524 // the maximum of the theoretical lower limits of the subgraphs
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	525 // bandwidths.
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	526 octave_idx_type B = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	527
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	528 // 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	529 // 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	530
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	531 boolNDArray btmp (dim_vector (1, N), false);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	532 bool *visit = btmp.fortran_vec ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	533
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	534 do
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	535 {
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	536 // locate an unvisited starting node of the graph
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	537 octave_idx_type i;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	538 for (i = 0; i < N; i++)
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	539 if (! visit[i])
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	540 break;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	541
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	542 // locate a probably better starting node
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	543 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	544
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	545 // 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	546 // 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	547 // tree, its dist is 0.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	548 v.deg = D[v.id];
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	549 v.dist = 0;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	550 visit[v.id] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	551 Q_enq (Q, N, qt, v);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	552
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	553 // lower bound for the bandwidth of a subgraph
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	554 // 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	555 // root) for determining the bandwidth of the computed
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	556 // permutation P
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	557 octave_idx_type Bsub = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	558 // min. dist. to the root is 0
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	559 octave_idx_type level = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	560 // 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	561 octave_idx_type level_N = 1;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	562
6677 9a8861bc2b34 [project @ 2007-05-31 19:39:12 by jwe] jwe parents: 6610 diff changeset	563 while (! Q_empty (Q, N, qh, qt))
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	564 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	565 v = Q_deq (Q, N, qh);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	566 i = v.id;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	567
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	568 c++;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	569
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	570 // for computing the inverse permutation P where
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	571 // 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	572 // P(i) = c;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	573
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	574 // for computing permutation P where
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	575 // A(P(i),P(j)) or PAP' is banded
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	576 P(c) = i;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	577
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	578 // 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	579 s = 0;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	580 octave_idx_type j1 = cidx[i];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	581 octave_idx_type j2 = cidx2[i];
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	582
10154 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 while (j1 < cidx[i+1] \|\| j2 < cidx2[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_QUIT;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	587 if (j1 == cidx[i+1])
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 octave_idx_type r2 = ridx2[j2++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	590 if (! visit[r2])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	591 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	592 // the distance of node j is dist(i)+1
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	593 w.id = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	594 w.deg = D[r2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	595 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	596 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	597 visit[r2] = true;
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 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	600 else if (j2 == cidx2[i+1])
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 octave_idx_type r1 = ridx[j1++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	603 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	604 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	605 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	606 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	607 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	608 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	609 visit[r1] = true;
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 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	612 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	613 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	614 octave_idx_type r1 = ridx[j1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	615 octave_idx_type r2 = ridx2[j2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	616 if (r1 <= r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	617 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	618 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	619 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	620 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	621 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	622 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	623 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	624 visit[r1] = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	625 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	626 j1++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	627 if (r1 == r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	628 j2++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	629 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	630 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	631 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	632 if (! visit[r2])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	633 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	634 w.id = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	635 w.deg = D[r2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	636 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	637 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	638 visit[r2] = true;
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 j2++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	641 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	642 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	643 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	644
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	645 // 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	646 while (! H_empty (S, s))
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	647 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	648 OCTAVE_QUIT;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	649
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	650 // 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	651 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	652
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	653 // entered the BFS a new level?
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	654 if (v.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	655 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	656 // adjustment of bandwith:
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	657 // "[...] the minimum bandwidth that
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	658 // can be obtained [...] is the
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	659 // maximum number of nodes per level"
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	660 if (Bsub < level_N)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	661 Bsub = level_N;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	662
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	663 level = v.dist;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	664 // v is the first node on the new level
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	665 level_N = 1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	666 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	667 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	668 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	669 // there is no new level but another node on
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	670 // this level:
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	671 level_N++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	672 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	673
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	674 // enqueue v in O(1)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	675 Q_enq (Q, N, qt, v);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	676 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	677
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	678 // synchronize the bandwidth with level_N once again:
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	679 if (Bsub < level_N)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	680 Bsub = level_N;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	681 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	682 // 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	683 // 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	684 // of all subgraphs. Update:
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	685 if (Bsub > B)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	686 B = Bsub;
6608 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 // are there any nodes left?
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	689 while (c+1 < N);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	690
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	691 // compute the reverse-ordering
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	692 s = N / 2 - 1;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	693 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	694 std::swap (P.elem (i), P.elem (j));
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	695
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	696 // 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	697 return ovl (P+1);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	698 }

Mercurial > octave

annotate libinterp/dldfcn/symrcm.cc @ 20939:b17fda023ca6