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