octave: libinterp/corefcn/symrcm.cc annotate

annotate libinterp/corefcn/symrcm.cc @ 33612:23bb1d9fcec8 bytecode-interpreter tip

maint: Merge default to bytecode-interpreter.

author	Nicholas R. Jankowski <jankowski.nicholas@gmail.com>
date	Sun, 19 May 2024 23:02:07 -0400
parents	f53ac65ffba6
children

rev	line source
27923 bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	1 ////////////////////////////////////////////////////////////////////////
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	2 //
32632 2e484f9f1f18 maint: update Octave Project Developers copyright for the new year John W. Eaton <jwe@octave.org> parents: 32589 diff changeset	3 // Copyright (C) 2007-2024 The Octave Project Developers
27923 bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	4 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	5 // See the file COPYRIGHT.md in the top-level directory of this
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	6 // distribution or <https://octave.org/copyright/>.
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	7 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	8 // This file is part of Octave.
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	9 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	10 // Octave is free software: you can redistribute it and/or modify it
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	11 // under the terms of the GNU General Public License as published by
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	12 // the Free Software Foundation, either version 3 of the License, or
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	13 // (at your option) any later version.
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	14 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	15 // Octave is distributed in the hope that it will be useful, but
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	16 // WITHOUT ANY WARRANTY; without even the implied warranty of
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	18 // GNU General Public License for more details.
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	19 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	20 // You should have received a copy of the GNU General Public License
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	21 // along with Octave; see the file COPYING. If not, see
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	22 // <https://www.gnu.org/licenses/>.
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	23 //
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	24 ////////////////////////////////////////////////////////////////////////
6608 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 /*
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	27 An implementation of the Reverse Cuthill-McKee algorithm (symrcm)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	28
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	29 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	30
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	31 @INPROCEEDINGS{,
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	32 author = {E. Cuthill and J. McKee},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	33 title = {Reducing the Bandwidth of Sparse Symmetric Matrices},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	34 booktitle = {Proceedings of the 24th ACM National Conference},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	35 publisher = {Brandon Press},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	36 pages = {157 -- 172},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	37 location = {New Jersey},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	38 year = {1969}
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	39 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	40
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	41 @BOOK{,
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	42 author = {Alan George and Joseph W. H. Liu},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	43 title = {Computer Solution of Large Sparse Positive Definite Systems},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	44 publisher = {Prentice Hall Series in Computational Mathematics},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	45 ISBN = {0-13-165274-5},
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	46 year = {1981}
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	47 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	48
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	49 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	50 bandwidth problem.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	51
6610 fb8bddaa07c4 [project @ 2007-05-09 02:28:40 by jwe] jwe parents: 6608 diff changeset	52 Written by Michael Weitzel <michael.weitzel@@uni-siegen.de>
fb8bddaa07c4 [project @ 2007-05-09 02:28:40 by jwe] jwe parents: 6608 diff changeset	53 <weitzel@@ldknet.org>
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	54 */
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	55
21724 aba2e6293dd8 use "#if ..." consistently instead of "#ifdef" and "#ifndef" John W. Eaton <jwe@octave.org> parents: 21301 diff changeset	56 #if defined (HAVE_CONFIG_H)
21301 40de9f8f23a6 Use '#include "config.h"' rather than <config.h>. Rik <rik@octave.org> parents: 21200 diff changeset	57 # include "config.h"
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	58 #endif
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	59
23024 a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	60 #include <algorithm>
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	61
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	62 #include "CSparse.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	63 #include "boolNDArray.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	64 #include "dNDArray.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	65 #include "dSparse.h"
8377 25bc2d31e1bf improve OCTAVE_LOCAL_BUFFER Jaroslav Hajek <highegg@gmail.com> parents: 7650 diff changeset	66 #include "oct-locbuf.h"
23024 a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	67 #include "oct-sparse.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	68 #include "quit.h"
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	69
28024 c28b8ba841fb move sparse functions from dldfcn to corefcn directory (bug #57459) John W. Eaton <jwe@octave.org> parents: 27957 diff changeset	70 #include "defun.h"
23024 a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	71 #include "errwarn.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	72 #include "ov.h"
a6a7b054e4ba Rationalize #includes in libinterp/dldfcn directory. Rik <rik@octave.org> parents: 22860 diff changeset	73 #include "ovl.h"
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	74
31605 e88a07dec498 maint: Use macros to begin/end C++ namespaces. Rik <rik@octave.org> parents: 30564 diff changeset	75 OCTAVE_BEGIN_NAMESPACE(octave)
29958 32c3a5805893 move DEFUN and DEFMETHOD functions inside octave namespace John W. Eaton <jwe@octave.org> parents: 29358 diff changeset	76
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	77 // A node struct for the Cuthill-McKee algorithm
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	78 struct CMK_Node
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 // the node's id (matrix row index)
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	81 octave_idx_type id;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	82 // the node's degree
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	83 octave_idx_type deg;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	84 // minimal distance to the root of the spanning tree
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	85 octave_idx_type dist;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	86 };
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	87
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	88 // A simple queue.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	89 // Queues Q have a fixed maximum size N (rows,cols of the matrix) and are
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	90 // stored in an array. qh and qt point to queue head and tail.
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	91
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	92 // 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	93
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	94 inline static void
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	95 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	96 {
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	97 Q[qt] = o;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	98 qt = (qt + 1) % (N + 1);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	99 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	100
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	101 // Dequeue operation (removes a node from the head)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	102
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	103 inline static CMK_Node
30390 a61e1a0f6024 maint: style check C++ files in libinterp/ ahead of 7.1 release. Rik <rik@octave.org> parents: 29958 diff changeset	104 Q_deq (CMK_Node *Q, octave_idx_type N, octave_idx_type& qh)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	105 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	106 CMK_Node r = Q[qh];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	107 qh = (qh + 1) % (N + 1);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	108 return r;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	109 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	110
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	111 // Predicate (queue empty)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	112 #define Q_empty(Q, N, qh, qt) ((qh) == (qt))
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	113
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	114 // 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	115
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	116 // the left descendant of entry i
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	117 #define LEFT(i) (((i) << 1) + 1) // = (2*(i)+1)
31607 aac27ad79be6 maint: Re-indent code after switch to using namespace macros. Rik <rik@octave.org> parents: 31605 diff changeset	118 // the right descendant of entry i
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	119 #define RIGHT(i) (((i) << 1) + 2) // = (2*(i)+2)
31607 aac27ad79be6 maint: Re-indent code after switch to using namespace macros. Rik <rik@octave.org> parents: 31605 diff changeset	120 // the parent of entry i
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	121 #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	122
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	123 // Builds a min-heap (the root contains the smallest element). A is an array
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	124 // 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	125
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	126 static void
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	127 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	128 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	129 octave_idx_type j = i;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	130 for (;;)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	131 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	132 octave_idx_type l = LEFT(j);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	133 octave_idx_type r = RIGHT(j);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	134
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	135 octave_idx_type smallest;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	136 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	137 smallest = l;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	138 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	139 smallest = j;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	140
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	141 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	142 smallest = r;
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 if (smallest != j)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	145 {
14862 bbdc822be2b9 smyrcm.cc: use std::swap instead of custom swap code. Rik <octave@nomad.inbox5.com> parents: 14854 diff changeset	146 std::swap (A[j], A[smallest]);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	147 j = smallest;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	148 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	149 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	150 break;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	151 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	152 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	153
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	154 // 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	155
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	156 static void
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	157 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	158 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	159 octave_idx_type i = h++;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	160
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	161 H[i] = o;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	162
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	163 if (i == 0)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	164 return;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	165 do
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	166 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	167 octave_idx_type p = PARENT(i);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	168 if (H[i].deg < H[p].deg)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	169 {
14862 bbdc822be2b9 smyrcm.cc: use std::swap instead of custom swap code. Rik <octave@nomad.inbox5.com> parents: 14854 diff changeset	170 std::swap (H[i], H[p]);
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	171
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	172 i = p;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	173 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	174 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	175 break;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	176 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	177 while (i > 0);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	178 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	179
27956 2310164737b3 fix many spelling errors (bug #57613) John W. Eaton <jwe@octave.org> parents: 26376 diff changeset	180 // Heap operation remove-min. Removes the smallest element in O(1) and
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	181 // reorganizes the heap optionally in O(log(n))
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	182
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	183 inline static CMK_Node
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	184 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	185 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	186 CMK_Node r = H[0];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	187 H[0] = H[--h];
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	188 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	189 H_heapify_min (H, 0, h);
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	190 return r;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	191 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	192
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	193 // Predicate (heap empty)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	194 #define H_empty(H, h) ((h) == 0)
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	195
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	196 // Helper function for the Cuthill-McKee algorithm. Tries to determine a
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	197 // 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	198
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	199 static octave_idx_type
12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	200 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	201 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	202 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	203 octave_idx_type start)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	204 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	205 CMK_Node w;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	206
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	207 OCTAVE_LOCAL_BUFFER (CMK_Node, Q, N+1);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	208 boolNDArray btmp (dim_vector (1, N), false);
32660 f53ac65ffba6 maint: New method rwdata() as clearer alternative to fortran_vec(). Rik <rik@octave.org> parents: 32632 diff changeset	209 bool *visit = btmp.rwdata ();
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	210
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	211 octave_idx_type qh = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	212 octave_idx_type qt = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	213 CMK_Node x;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	214 x.id = start;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	215 x.deg = D[start];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	216 x.dist = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	217 Q_enq (Q, N, qt, x);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	218 visit[start] = true;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	219
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	220 // distance level
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	221 octave_idx_type level = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	222 // current largest "eccentricity"
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	223 octave_idx_type max_dist = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	224
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	225 for (;;)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	226 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	227 while (! Q_empty (Q, N, qh, qt))
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	228 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	229 CMK_Node v = Q_deq (Q, N, qh);
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	230
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	231 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	232 x = v;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	233
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	234 octave_idx_type i = v.id;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	235
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	236 // add all unvisited neighbors to the queue
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	237 octave_idx_type j1 = cidx[i];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	238 octave_idx_type j2 = cidx2[i];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	239 while (j1 < cidx[i+1] \|\| j2 < cidx2[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	240 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	241 if (j1 == cidx[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	242 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	243 octave_idx_type r2 = ridx2[j2++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	244 if (! visit[r2])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	245 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	246 // the distance of node j is dist(i)+1
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	247 w.id = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	248 w.deg = D[r2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	249 w.dist = v.dist+1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	250 Q_enq (Q, N, qt, w);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	251 visit[r2] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	252
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	253 if (w.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	254 level = w.dist;
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 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	257 else if (j2 == cidx2[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	258 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	259 octave_idx_type r1 = ridx[j1++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	260 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	261 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	262 // the distance of node j is dist(i)+1
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	263 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	264 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	265 w.dist = v.dist+1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	266 Q_enq (Q, N, qt, w);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	267 visit[r1] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	268
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	269 if (w.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	270 level = w.dist;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	271 }
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 else
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 octave_idx_type r1 = ridx[j1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	276 octave_idx_type r2 = ridx2[j2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	277 if (r1 <= r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	278 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	279 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	280 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	281 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	282 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	283 w.dist = v.dist+1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	284 Q_enq (Q, N, qt, w);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	285 visit[r1] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	286
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	287 if (w.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	288 level = w.dist;
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 j1++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	291 if (r1 == r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	292 j2++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	293 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	294 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	295 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	296 if (! visit[r2])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	297 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	298 w.id = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	299 w.deg = D[r2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	300 w.dist = v.dist+1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	301 Q_enq (Q, N, qt, w);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	302 visit[r2] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	303
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	304 if (w.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	305 level = w.dist;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	306 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	307 j2++;
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 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	310 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	311 } // finish of BFS
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	312
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	313 if (max_dist < x.dist)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	314 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	315 max_dist = x.dist;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	316
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	317 for (octave_idx_type i = 0; i < N; i++)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	318 visit[i] = false;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	319
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	320 visit[x.id] = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	321 x.dist = 0;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	322 qt = qh = 0;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	323 Q_enq (Q, N, qt, x);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	324 }
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	325 else
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	326 break;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	327 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	328 return x.id;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	329 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	330
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	331 // Calculates the node's degrees. This means counting the nonzero elements
b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	332 // 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	333 // as well.
6959 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 static octave_idx_type
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	336 calc_degrees (octave_idx_type N, octave_idx_type cidx, octave_idx_type ridx,
32589 05b4479c29d8 maint: C++ style check for libinterp/ before 9.1 release. Rik <rik@octave.org> parents: 32340 diff changeset	337 octave_idx_type cidx2, octave_idx_type ridx2, octave_idx_type *D)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	338 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	339 octave_idx_type max_deg = 0;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	340 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	341 D[i] = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	342
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	343 for (octave_idx_type j = 0; j < N; j++)
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	344 for (octave_idx_type i = cidx[j]; i < cidx[j+1]; i++)
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	345 D[ridx[i]]++;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	346
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	347 for (octave_idx_type j = 0; j < N; j++)
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	348 for (octave_idx_type i = cidx2[j]; i < cidx2[j+1]; i++)
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	349 D[ridx2[i]]++;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	350
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	351 for (octave_idx_type i = 0; i < N; i++)
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	352 if (D[i] > max_deg)
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	353 max_deg = D[i];
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	354
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	355 return max_deg;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	356 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	357
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	358 // 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	359
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	360 static void
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	361 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	362 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	363 octave_idx_type *cidx2)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	364 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	365 octave_idx_type nz = cidx[N];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	366
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	367 OCTAVE_LOCAL_BUFFER (octave_idx_type, w, N + 1);
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	368 for (octave_idx_type i = 0; i < N; i++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	369 w[i] = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	370 for (octave_idx_type i = 0; i < nz; i++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	371 w[ridx[i]]++;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	372 nz = 0;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	373 for (octave_idx_type i = 0; i < N; i++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	374 {
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	375 cidx2[i] = nz;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	376 nz += w[i];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	377 w[i] = cidx2[i];
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	378 }
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	379 cidx2[N] = nz;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	380 w[N] = nz;
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	381
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	382 for (octave_idx_type j = 0; j < N; j++)
47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	383 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	384 {
15020 560317fd5977 maint: Cuddle open bracket used for indexing C++ arrays in source code. Rik <rik@octave.org> parents: 14862 diff changeset	385 octave_idx_type q = w[ridx[k]]++;
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	386 ridx2[q] = j;
6959 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 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	389
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	390 // An implementation of the Cuthill-McKee algorithm.
28024 c28b8ba841fb move sparse functions from dldfcn to corefcn directory (bug #57459) John W. Eaton <jwe@octave.org> parents: 27957 diff changeset	391 DEFUN (symrcm, args, ,
c28b8ba841fb move sparse functions from dldfcn to corefcn directory (bug #57459) John W. Eaton <jwe@octave.org> parents: 27957 diff changeset	392 doc: /* -- texinfo --
21966 112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	393 @deftypefn {} {@var{p} =} symrcm (@var{S})
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	394 Return the symmetric reverse @nospell{Cuthill-McKee} permutation of @var{S}.
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	395
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	396 @var{p} is a permutation vector such that
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	397 @code{@var{S}(@var{p}, @var{p})} tends to have its diagonal elements closer
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	398 to the diagonal than @var{S}. This is a good preordering for LU or
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	399 Cholesky@tie{}factorization of matrices that come from ``long, skinny''
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	400 problems. It works for both symmetric and asymmetric @var{S}.
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	401
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	402 The algorithm represents a heuristic approach to the NP-complete bandwidth
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	403 minimization problem. The implementation is based in the descriptions found
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	404 in
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	405
25032 a1e391e33004 doc: grammarcheck documentation again ahead of 4.4 release. Rik <rik@octave.org> parents: 25003 diff changeset	406 @nospell{E. Cuthill, J. McKee}.
a1e391e33004 doc: grammarcheck documentation again ahead of 4.4 release. Rik <rik@octave.org> parents: 25003 diff changeset	407 @cite{Reducing the Bandwidth of Sparse Symmetric Matrices}.
a1e391e33004 doc: grammarcheck documentation again ahead of 4.4 release. Rik <rik@octave.org> parents: 25003 diff changeset	408 Proceedings of the 24th @nospell{ACM} National Conference,
21966 112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	409 157--172 1969, Brandon Press, New Jersey.
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	410
27800 5a6a19a4e3da doc: Use Texinfo non-sentence ending periods in citations. Rik <rik@octave.org> parents: 26376 diff changeset	411 @nospell{A. George, J.W.H. Liu}. @cite{Computer Solution of Large Sparse
21966 112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	412 Positive Definite Systems}, Prentice Hall Series in Computational
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	413 Mathematics, ISBN 0-13-165274-5, 1981.
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	414
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	415 @seealso{colperm, colamd, symamd}
112b20240c87 move docstrings in C++ files out of C strings and into comments John W. Eaton <jwe@octave.org> parents: 21751 diff changeset	416 @end deftypefn */)
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	417 {
20818 cef0448a6ed2 eliminate unnecessary uses of nargin John W. Eaton <jwe@octave.org> parents: 20790 diff changeset	418 if (args.length () != 1)
20790 c2d9556d51d0 eliminate return statements after calls to print_usage John W. Eaton <jwe@octave.org> parents: 20555 diff changeset	419 print_usage ();
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	420
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	421 octave_value arg = args(0);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	422
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	423 octave_idx_type nr = arg.rows ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	424 octave_idx_type nc = arg.columns ();
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	425
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	426 if (nr != nc)
21110 3d0d84305600 Use err_square_matrix_required more widely. Rik <rik@octave.org> parents: 21100 diff changeset	427 err_square_matrix_required ("symrcm", "S");
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	428
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	429 if (nr == 0 && nc == 0)
20939 b17fda023ca6 maint: Use new C++ archetype in more files. Rik <rik@octave.org> parents: 20853 diff changeset	430 return ovl (NDArray (dim_vector (1, 0)));
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	431
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	432 // dimension of the matrix
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	433 octave_idx_type N = nr;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	434
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	435 // the parameter of the matrix is converted into a sparse matrix
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	436 //(if necessary)
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	437 SparseMatrix Ar;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	438
32340 19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	439 octave_quit ();
19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	440
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	441 if (arg.isreal ())
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	442 {
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	443 Ar = arg.sparse_matrix_value ();
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	444 }
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	445 else
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	446 {
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	447 SparseComplexMatrix Ac = arg.sparse_complex_matrix_value ();
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	448 Ar = max (max (real (Ac), -real (Ac)), max (imag (Ac), -imag (Ac)));
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	449 }
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	450
32340 19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	451 octave_quit ();
19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	452
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	453 // Note cidx/ridx are const, so use xridx and xcidx...
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	454 octave_idx_type *cidx = Ar.xcidx ();
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	455 octave_idx_type *ridx = Ar.xridx ();
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	456
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	457 // transpose
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	458 OCTAVE_LOCAL_BUFFER (octave_idx_type, cidx2, N + 1);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	459 OCTAVE_LOCAL_BUFFER (octave_idx_type, ridx2, cidx[N]);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	460 transpose (N, ridx, cidx, ridx2, cidx2);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	461
32340 19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	462 octave_quit ();
19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	463
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	464 // vertex degrees
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	465 OCTAVE_LOCAL_BUFFER (octave_idx_type, D, N);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	466 octave_idx_type max_deg = calc_degrees (N, cidx, ridx, cidx2, ridx2, D);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	467
32340 19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	468 octave_quit ();
19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	469
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	470 // the permutation vector
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	471 NDArray P (dim_vector (1, N));
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	472
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	473 // if none of the nodes has a degree > 0 (a matrix of zeros)
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	474 // the return value corresponds to the identity permutation
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	475 if (max_deg == 0)
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	476 {
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	477 for (octave_idx_type i = 0; i < N; i++)
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	478 P(i) = i+1; // +1 to convert from base-0 to base-1
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	479
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	480 return ovl (P);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	481 }
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	482
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	483 // At this point, all early returns have completed.
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	484 // Proceed to BFS.
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	485
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	486 // sizes of the heaps
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	487 octave_idx_type s = 0;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	488
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	489 // 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	490 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	491 octave_idx_type qh = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	492 CMK_Node v, w;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	493
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	494 // a heap for the a node's neighbors. The number of neighbors is
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	495 // limited by the maximum degree max_deg:
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	496 OCTAVE_LOCAL_BUFFER (CMK_Node, S, max_deg);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	497
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	498 // a queue for the BFS. The array is always one element larger than
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	499 // the number of entries that are stored.
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	500 OCTAVE_LOCAL_BUFFER (CMK_Node, Q, N+1);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	501
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	502 // a counter (for building the permutation)
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	503 octave_idx_type c = -1;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	504
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	505 // upper bound for the bandwidth (=quality of solution)
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	506 // initialize the bandwidth of the graph with 0. B contains the
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	507 // the maximum of the theoretical lower limits of the subgraphs
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	508 // bandwidths.
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	509 octave_idx_type B = 0;
6608 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 // 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	512 // 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	513
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	514 boolNDArray btmp (dim_vector (1, N), false);
32660 f53ac65ffba6 maint: New method rwdata() as clearer alternative to fortran_vec(). Rik <rik@octave.org> parents: 32632 diff changeset	515 bool *visit = btmp.rwdata ();
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	516
32340 19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	517 octave_quit ();
19a98292d7bf symrcm.cc: Redistribute octave_quit calls from functions to DEFUN Arun Giridhar <arungiridhar@gmail.com> parents: 32339 diff changeset	518
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	519 do
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	520 {
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	521 // locate an unvisited starting node of the graph
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	522 octave_idx_type i;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	523 for (i = 0; i < N; i++)
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	524 if (! visit[i])
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	525 break;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	526
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	527 // locate a probably better starting node
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	528 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	529
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	530 // mark the node as visited and enqueue it (a starting node
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	531 // for the BFS). Since the node will be a root of a spanning
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	532 // tree, its dist is 0.
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	533 v.deg = D[v.id];
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	534 v.dist = 0;
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	535 visit[v.id] = true;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	536 Q_enq (Q, N, qt, v);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	537
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	538 // lower bound for the bandwidth of a subgraph
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	539 // 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	540 // root) for determining the bandwidth of the computed
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	541 // permutation P
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	542 octave_idx_type Bsub = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	543 // min. dist. to the root is 0
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	544 octave_idx_type level = 0;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	545 // 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	546 octave_idx_type level_N = 1;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	547
6677 9a8861bc2b34 [project @ 2007-05-31 19:39:12 by jwe] jwe parents: 6610 diff changeset	548 while (! Q_empty (Q, N, qh, qt))
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	549 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	550 v = Q_deq (Q, N, qh);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	551 i = v.id;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	552
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	553 c++;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	554
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	555 // for computing the inverse permutation P where
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	556 // 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	557 // P(i) = c;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	558
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	559 // for computing permutation P where
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	560 // A(P(i),P(j)) or PAP' is banded
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	561 P(c) = i;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	562
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	563 // 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	564 s = 0;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	565 octave_idx_type j1 = cidx[i];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	566 octave_idx_type j2 = cidx2[i];
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 while (j1 < cidx[i+1] \|\| j2 < cidx2[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	569 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	570 if (j1 == cidx[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	571 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	572 octave_idx_type r2 = ridx2[j2++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	573 if (! visit[r2])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	574 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	575 // the distance of node j is dist(i)+1
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	576 w.id = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	577 w.deg = D[r2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	578 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	579 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	580 visit[r2] = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	581 }
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 else if (j2 == cidx2[i+1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	584 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	585 octave_idx_type r1 = ridx[j1++];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	586 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	587 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	588 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	589 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	590 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	591 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	592 visit[r1] = true;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	593 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	594 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	595 else
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 octave_idx_type r1 = ridx[j1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	598 octave_idx_type r2 = ridx2[j2];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	599 if (r1 <= r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	600 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	601 if (! visit[r1])
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	602 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	603 w.id = r1;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	604 w.deg = D[r1];
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	605 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	606 H_insert (S, s, w);
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	607 visit[r1] = true;
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 j1++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	610 if (r1 == r2)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	611 j2++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	612 }
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	613 else
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[r2])
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 = r2;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	618 w.deg = D[r2];
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[r2] = 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 j2++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	624 }
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 }
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	627
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	628 // 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	629 while (! H_empty (S, s))
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 // 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	632 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	633
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	634 // entered the BFS a new level?
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	635 if (v.dist > level)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	636 {
27956 2310164737b3 fix many spelling errors (bug #57613) John W. Eaton <jwe@octave.org> parents: 26376 diff changeset	637 // adjustment of bandwidth:
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	638 // "[...] the minimum bandwidth that
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	639 // can be obtained [...] is the
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	640 // maximum number of nodes per level"
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	641 if (Bsub < level_N)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	642 Bsub = level_N;
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	643
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	644 level = v.dist;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	645 // v is the first node on the new level
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	646 level_N = 1;
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 else
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	649 {
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	650 // there is no new level but another node on
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	651 // this level:
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	652 level_N++;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	653 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	654
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	655 // enqueue v in O(1)
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	656 Q_enq (Q, N, qt, v);
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	657 }
11586 12df7854fa7c strip trailing whitespace from source files John W. Eaton <jwe@octave.org> parents: 11553 diff changeset	658
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	659 // synchronize the bandwidth with level_N once again:
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;
40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	662 }
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	663 // finish of BFS. If there are still unvisited nodes in the graph
b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	664 // then it is split into CCs. The computed bandwidth is the maximum
b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21724 diff changeset	665 // of all subgraphs. Update:
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	666 if (Bsub > B)
10154 40dfc0c99116 DLD-FUNCTIONS/.cc: untabify John W. Eaton <jwe@octave.org>* parents: 9066 diff changeset	667 B = Bsub;
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	668 }
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	669 // are there any nodes left?
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	670 while (c+1 < N);
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	671
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	672 // compute the reverse-ordering
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	673 s = N / 2 - 1;
6959 47f4f4e88166 [project @ 2007-10-04 20:43:32 by jwe] jwe parents: 6690 diff changeset	674 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	675 std::swap (P.elem (i), P.elem (j));
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	676
2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	677 // 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	678 return ovl (P+1);
6608 2581a3c23f18 [project @ 2007-05-08 01:17:56 by dbateman] dbateman parents: diff changeset	679 }
29958 32c3a5805893 move DEFUN and DEFMETHOD functions inside octave namespace John W. Eaton <jwe@octave.org> parents: 29358 diff changeset	680
32339 4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	681 /*
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	682
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	683 basic functionality test, with icosahedron:
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	684 %!test <*64718>
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	685 %! adj = [ 0 1 1 1 1 1 0 0 0 0 0 0;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	686 %! 1 0 1 0 0 1 1 0 0 0 1 0;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	687 %! 1 1 0 1 0 0 1 1 0 0 0 0;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	688 %! 1 0 1 0 1 0 0 1 1 0 0 0;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	689 %! 1 0 0 1 0 1 0 0 1 1 0 0;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	690 %! 1 1 0 0 1 0 0 0 0 1 1 0;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	691 %! 0 1 1 0 0 0 0 1 0 0 1 1;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	692 %! 0 0 1 1 0 0 1 0 1 0 0 1;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	693 %! 0 0 0 1 1 0 0 1 0 1 0 1;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	694 %! 0 0 0 0 1 1 0 0 1 0 1 1;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	695 %! 0 1 0 0 0 1 1 0 0 1 0 1;
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	696 %! 0 0 0 0 0 0 1 1 1 1 1 0 ];
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	697 %! p = symrcm (adj);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	698 %! assert (p, [12 8 9 10 11 7 3 4 5 6 2 1]);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	699 %! assert (bandwidth (adj), 9);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	700 %! assert (bandwidth (adj(p, p)), 6);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	701
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	702 handle zero-matrix properly:
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	703 %!test <*64718>
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	704 %! adj = false (5);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	705 %! p = symrcm (adj);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	706 %! assert (p, 1:5);
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	707
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	708 */
4de460f3ffe0 symrcm.cc: Speed up degree calculation (Bug #64718) Arun Giridhar <arungiridhar@gmail.com> parents: 31706 diff changeset	709
31605 e88a07dec498 maint: Use macros to begin/end C++ namespaces. Rik <rik@octave.org> parents: 30564 diff changeset	710 OCTAVE_END_NAMESPACE(octave)

Mercurial > octave

annotate libinterp/corefcn/symrcm.cc @ 33612:23bb1d9fcec8 bytecode-interpreter tip