Mercurial > octave

annotate libinterp/dldfcn/symrcm.cc @ 25032:a1e391e33004 stable

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