Mercurial > octave

annotate libinterp/dldfcn/symrcm.cc @ 20818:cef0448a6ed2

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