Mercurial > octave
annotate libinterp/corefcn/symrcm.cc @ 31605:e88a07dec498 stable
maint: Use macros to begin/end C++ namespaces.
* oct-conf-post-public.in.h: Define two macros (OCTAVE_BEGIN_NAMESPACE,
OCTAVE_END_NAMESPACE) that can be used to start/end a namespace.
* mk-opts.pl, build-env.h, build-env.in.cc, __betainc__.cc, __contourc__.cc,
__dsearchn__.cc, __eigs__.cc, __expint__.cc, __ftp__.cc, __gammainc__.cc,
__ichol__.cc, __ilu__.cc, __isprimelarge__.cc, __lin_interpn__.cc,
__magick_read__.cc, __pchip_deriv__.cc, __qp__.cc, amd.cc, auto-shlib.cc,
auto-shlib.h, balance.cc, base-text-renderer.cc, base-text-renderer.h,
besselj.cc, bitfcns.cc, bsxfun.cc, c-file-ptr-stream.cc, c-file-ptr-stream.h,
call-stack.cc, call-stack.h, ccolamd.cc, cellfun.cc, chol.cc, colamd.cc,
colloc.cc, conv2.cc, daspk.cc, dasrt.cc, dassl.cc, data.cc, data.h, debug.cc,
defaults.cc, defaults.h, defun-int.h, defun.cc, det.cc, dirfns.cc, display.cc,
display.h, dlmread.cc, dmperm.cc, dot.cc, dynamic-ld.cc, dynamic-ld.h, eig.cc,
ellipj.cc, environment.cc, environment.h, error.cc, error.h, errwarn.h,
event-manager.cc, event-manager.h, event-queue.cc, event-queue.h, fcn-info.cc,
fcn-info.h, fft.cc, fft2.cc, fftn.cc, file-io.cc, filter.cc, find.cc,
ft-text-renderer.cc, ft-text-renderer.h, gcd.cc, getgrent.cc, getpwent.cc,
getrusage.cc, givens.cc, gl-render.cc, gl-render.h, gl2ps-print.cc,
gl2ps-print.h, graphics-toolkit.cc, graphics-toolkit.h, graphics.cc,
graphics.in.h, gsvd.cc, gtk-manager.cc, gtk-manager.h, hash.cc, help.cc,
help.h, hess.cc, hex2num.cc, hook-fcn.cc, hook-fcn.h, input.cc, input.h,
interpreter-private.cc, interpreter-private.h, interpreter.cc, interpreter.h,
inv.cc, jsondecode.cc, jsonencode.cc, kron.cc, latex-text-renderer.cc,
latex-text-renderer.h, load-path.cc, load-path.h, load-save.cc, load-save.h,
lookup.cc, ls-ascii-helper.cc, ls-ascii-helper.h, ls-oct-text.cc, ls-utils.cc,
ls-utils.h, lsode.cc, lu.cc, mappers.cc, matrix_type.cc, max.cc, mex-private.h,
mex.cc, mgorth.cc, nproc.cc, oct-fstrm.cc, oct-fstrm.h, oct-hdf5-types.cc,
oct-hdf5-types.h, oct-hist.cc, oct-hist.h, oct-iostrm.cc, oct-iostrm.h,
oct-opengl.h, oct-prcstrm.cc, oct-prcstrm.h, oct-procbuf.cc, oct-procbuf.h,
oct-process.cc, oct-process.h, oct-stdstrm.h, oct-stream.cc, oct-stream.h,
oct-strstrm.cc, oct-strstrm.h, oct-tex-lexer.in.ll, oct-tex-parser.yy,
ordqz.cc, ordschur.cc, pager.cc, pager.h, pinv.cc, pow2.cc, pr-flt-fmt.cc,
pr-output.cc, procstream.cc, procstream.h, psi.cc, qr.cc, quad.cc, quadcc.cc,
qz.cc, rand.cc, rcond.cc, regexp.cc, schur.cc, settings.cc, settings.h,
sighandlers.cc, sighandlers.h, sparse-xdiv.cc, sparse-xdiv.h, sparse-xpow.cc,
sparse-xpow.h, sparse.cc, spparms.cc, sqrtm.cc, stack-frame.cc, stack-frame.h,
stream-euler.cc, strfind.cc, strfns.cc, sub2ind.cc, svd.cc, sylvester.cc,
symbfact.cc, syminfo.cc, syminfo.h, symrcm.cc, symrec.cc, symrec.h,
symscope.cc, symscope.h, symtab.cc, symtab.h, syscalls.cc, sysdep.cc, sysdep.h,
text-engine.cc, text-engine.h, text-renderer.cc, text-renderer.h, time.cc,
toplev.cc, tril.cc, tsearch.cc, typecast.cc, url-handle-manager.cc,
url-handle-manager.h, urlwrite.cc, utils.cc, utils.h, variables.cc,
variables.h, xdiv.cc, xdiv.h, xnorm.cc, xnorm.h, xpow.cc, xpow.h,
__delaunayn__.cc, __fltk_uigetfile__.cc, __glpk__.cc, __init_fltk__.cc,
__init_gnuplot__.cc, __ode15__.cc, __voronoi__.cc, audiodevinfo.cc,
audioread.cc, convhulln.cc, fftw.cc, gzip.cc, mk-build-env-features.sh,
mk-builtins.pl, cdef-class.cc, cdef-class.h, cdef-fwd.h, cdef-manager.cc,
cdef-manager.h, cdef-method.cc, cdef-method.h, cdef-object.cc, cdef-object.h,
cdef-package.cc, cdef-package.h, cdef-property.cc, cdef-property.h,
cdef-utils.cc, cdef-utils.h, ov-base.cc, ov-base.h, ov-bool-mat.cc,
ov-builtin.h, ov-cell.cc, ov-class.cc, ov-class.h, ov-classdef.cc,
ov-classdef.h, ov-complex.cc, ov-fcn-handle.cc, ov-fcn-handle.h, ov-fcn.h,
ov-java.cc, ov-java.h, ov-mex-fcn.h, ov-null-mat.cc, ov-oncleanup.cc,
ov-struct.cc, ov-typeinfo.cc, ov-typeinfo.h, ov-usr-fcn.cc, ov-usr-fcn.h,
ov.cc, ov.h, octave.cc, octave.h, mk-ops.sh, op-b-b.cc, op-b-bm.cc,
op-b-sbm.cc, op-bm-b.cc, op-bm-bm.cc, op-bm-sbm.cc, op-cdm-cdm.cc, op-cell.cc,
op-chm.cc, op-class.cc, op-cm-cm.cc, op-cm-cs.cc, op-cm-m.cc, op-cm-s.cc,
op-cm-scm.cc, op-cm-sm.cc, op-cs-cm.cc, op-cs-cs.cc, op-cs-m.cc, op-cs-s.cc,
op-cs-scm.cc, op-cs-sm.cc, op-dm-dm.cc, op-dm-scm.cc, op-dm-sm.cc,
op-dm-template.cc, op-dms-template.cc, op-fcdm-fcdm.cc, op-fcm-fcm.cc,
op-fcm-fcs.cc, op-fcm-fm.cc, op-fcm-fs.cc, op-fcn.cc, op-fcs-fcm.cc,
op-fcs-fcs.cc, op-fcs-fm.cc, op-fcs-fs.cc, op-fdm-fdm.cc, op-fm-fcm.cc,
op-fm-fcs.cc, op-fm-fm.cc, op-fm-fs.cc, op-fs-fcm.cc, op-fs-fcs.cc,
op-fs-fm.cc, op-fs-fs.cc, op-i16-i16.cc, op-i32-i32.cc, op-i64-i64.cc,
op-i8-i8.cc, op-int-concat.cc, op-m-cm.cc, op-m-cs.cc, op-m-m.cc, op-m-s.cc,
op-m-scm.cc, op-m-sm.cc, op-mi.cc, op-pm-pm.cc, op-pm-scm.cc, op-pm-sm.cc,
op-pm-template.cc, op-range.cc, op-s-cm.cc, op-s-cs.cc, op-s-m.cc, op-s-s.cc,
op-s-scm.cc, op-s-sm.cc, op-sbm-b.cc, op-sbm-bm.cc, op-sbm-sbm.cc,
op-scm-cm.cc, op-scm-cs.cc, op-scm-m.cc, op-scm-s.cc, op-scm-scm.cc,
op-scm-sm.cc, op-sm-cm.cc, op-sm-cs.cc, op-sm-m.cc, op-sm-s.cc, op-sm-scm.cc,
op-sm-sm.cc, op-str-m.cc, op-str-s.cc, op-str-str.cc, op-struct.cc,
op-ui16-ui16.cc, op-ui32-ui32.cc, op-ui64-ui64.cc, op-ui8-ui8.cc, ops.h,
anon-fcn-validator.cc, anon-fcn-validator.h, bp-table.cc, bp-table.h,
comment-list.cc, comment-list.h, filepos.h, lex.h, lex.ll, oct-lvalue.cc,
oct-lvalue.h, oct-parse.yy, parse.h, profiler.cc, profiler.h,
pt-anon-scopes.cc, pt-anon-scopes.h, pt-arg-list.cc, pt-arg-list.h,
pt-args-block.cc, pt-args-block.h, pt-array-list.cc, pt-array-list.h,
pt-assign.cc, pt-assign.h, pt-binop.cc, pt-binop.h, pt-bp.cc, pt-bp.h,
pt-cbinop.cc, pt-cbinop.h, pt-cell.cc, pt-cell.h, pt-check.cc, pt-check.h,
pt-classdef.cc, pt-classdef.h, pt-cmd.h, pt-colon.cc, pt-colon.h, pt-const.cc,
pt-const.h, pt-decl.cc, pt-decl.h, pt-eval.cc, pt-eval.h, pt-except.cc,
pt-except.h, pt-exp.cc, pt-exp.h, pt-fcn-handle.cc, pt-fcn-handle.h, pt-id.cc,
pt-id.h, pt-idx.cc, pt-idx.h, pt-jump.h, pt-loop.cc, pt-loop.h, pt-mat.cc,
pt-mat.h, pt-misc.cc, pt-misc.h, pt-pr-code.cc, pt-pr-code.h, pt-select.cc,
pt-select.h, pt-spmd.cc, pt-spmd.h, pt-stmt.cc, pt-stmt.h, pt-tm-const.cc,
pt-tm-const.h, pt-unop.cc, pt-unop.h, pt-vm-eval.cc, pt-walk.cc, pt-walk.h,
pt.cc, pt.h, token.cc, token.h, Range.cc, Range.h, idx-vector.cc, idx-vector.h,
range-fwd.h, CollocWt.cc, CollocWt.h, aepbalance.cc, aepbalance.h, chol.cc,
chol.h, gepbalance.cc, gepbalance.h, gsvd.cc, gsvd.h, hess.cc, hess.h,
lo-mappers.cc, lo-mappers.h, lo-specfun.cc, lo-specfun.h, lu.cc, lu.h,
oct-convn.cc, oct-convn.h, oct-fftw.cc, oct-fftw.h, oct-norm.cc, oct-norm.h,
oct-rand.cc, oct-rand.h, oct-spparms.cc, oct-spparms.h, qr.cc, qr.h, qrp.cc,
qrp.h, randgamma.cc, randgamma.h, randmtzig.cc, randmtzig.h, randpoisson.cc,
randpoisson.h, schur.cc, schur.h, sparse-chol.cc, sparse-chol.h, sparse-lu.cc,
sparse-lu.h, sparse-qr.cc, sparse-qr.h, svd.cc, svd.h, child-list.cc,
child-list.h, dir-ops.cc, dir-ops.h, file-ops.cc, file-ops.h, file-stat.cc,
file-stat.h, lo-sysdep.cc, lo-sysdep.h, lo-sysinfo.cc, lo-sysinfo.h,
mach-info.cc, mach-info.h, oct-env.cc, oct-env.h, oct-group.cc, oct-group.h,
oct-password.cc, oct-password.h, oct-syscalls.cc, oct-syscalls.h, oct-time.cc,
oct-time.h, oct-uname.cc, oct-uname.h, action-container.cc, action-container.h,
base-list.h, cmd-edit.cc, cmd-edit.h, cmd-hist.cc, cmd-hist.h, f77-fcn.h,
file-info.cc, file-info.h, lo-array-errwarn.cc, lo-array-errwarn.h, lo-hash.cc,
lo-hash.h, lo-ieee.h, lo-regexp.cc, lo-regexp.h, lo-utils.cc, lo-utils.h,
oct-base64.cc, oct-base64.h, oct-glob.cc, oct-glob.h, oct-inttypes.h,
oct-mutex.cc, oct-mutex.h, oct-refcount.h, oct-shlib.cc, oct-shlib.h,
oct-sparse.cc, oct-sparse.h, oct-string.h, octave-preserve-stream-state.h,
pathsearch.cc, pathsearch.h, quit.cc, quit.h, unwind-prot.cc, unwind-prot.h,
url-transfer.cc, url-transfer.h : Use new macros to begin/end C++ namespaces.
| author | Rik <rik@octave.org> |
|---|---|
| date | Thu, 01 Dec 2022 14:23:45 -0800 |
| parents | 796f54d4ddbf |
| children | aac27ad79be6 |
| rev | line source |
|---|---|
|
27923
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
1 //////////////////////////////////////////////////////////////////////// |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
2 // |
|
30564
796f54d4ddbf
update Octave Project Developers copyright for the new year
John W. Eaton <jwe@octave.org>
parents:
30390
diff
changeset
|
3 // Copyright (C) 2007-2022 The Octave Project Developers |
|
27923
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
4 // |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
5 // See the file COPYRIGHT.md in the top-level directory of this |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
6 // distribution or <https://octave.org/copyright/>. |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
7 // |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
8 // This file is part of Octave. |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
9 // |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
10 // Octave is free software: you can redistribute it and/or modify it |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
11 // under the terms of the GNU General Public License as published by |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
12 // the Free Software Foundation, either version 3 of the License, or |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
13 // (at your option) any later version. |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
14 // |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
15 // Octave is distributed in the hope that it will be useful, but |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
16 // WITHOUT ANY WARRANTY; without even the implied warranty of |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
18 // GNU General Public License for more details. |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
19 // |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
20 // You should have received a copy of the GNU General Public License |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
21 // along with Octave; see the file COPYING. If not, see |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
22 // <https://www.gnu.org/licenses/>. |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
23 // |
|
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
24 //////////////////////////////////////////////////////////////////////// |
| 6608 | 25 |
| 26 /* | |
| 27 An implementation of the Reverse Cuthill-McKee algorithm (symrcm) | |
| 28 | |
| 29 The implementation of this algorithm is based in the descriptions found in | |
| 30 | |
| 31 @INPROCEEDINGS{, | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
32 author = {E. Cuthill and J. McKee}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
33 title = {Reducing the Bandwidth of Sparse Symmetric Matrices}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
34 booktitle = {Proceedings of the 24th ACM National Conference}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
35 publisher = {Brandon Press}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
36 pages = {157 -- 172}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
37 location = {New Jersey}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
38 year = {1969} |
| 6608 | 39 } |
| 40 | |
| 41 @BOOK{, | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
42 author = {Alan George and Joseph W. H. Liu}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
43 title = {Computer Solution of Large Sparse Positive Definite Systems}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
44 publisher = {Prentice Hall Series in Computational Mathematics}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
45 ISBN = {0-13-165274-5}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
46 year = {1981} |
| 6608 | 47 } |
| 48 | |
| 49 The algorithm represents a heuristic approach to the NP-complete minimum | |
| 50 bandwidth problem. | |
| 51 | |
| 6610 | 52 Written by Michael Weitzel <michael.weitzel@@uni-siegen.de> |
| 53 <weitzel@@ldknet.org> | |
| 6608 | 54 */ |
| 55 | |
|
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21301
diff
changeset
|
56 #if defined (HAVE_CONFIG_H) |
|
21301
40de9f8f23a6
Use '#include "config.h"' rather than <config.h>.
Rik <rik@octave.org>
parents:
21200
diff
changeset
|
57 # include "config.h" |
| 6608 | 58 #endif |
| 59 | |
|
23024
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
60 #include <algorithm> |
|
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
61 |
|
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
62 #include "CSparse.h" |
|
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
63 #include "boolNDArray.h" |
|
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
64 #include "dNDArray.h" |
|
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
65 #include "dSparse.h" |
|
8377
25bc2d31e1bf
improve OCTAVE_LOCAL_BUFFER
Jaroslav Hajek <highegg@gmail.com>
parents:
7650
diff
changeset
|
66 #include "oct-locbuf.h" |
|
23024
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
67 #include "oct-sparse.h" |
|
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
68 #include "quit.h" |
| 6608 | 69 |
|
28024
c28b8ba841fb
move sparse functions from dldfcn to corefcn directory (bug #57459)
John W. Eaton <jwe@octave.org>
parents:
27957
diff
changeset
|
70 #include "defun.h" |
|
23024
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
71 #include "errwarn.h" |
|
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
72 #include "ov.h" |
|
a6a7b054e4ba
Rationalize #includes in libinterp/dldfcn directory.
Rik <rik@octave.org>
parents:
22860
diff
changeset
|
73 #include "ovl.h" |
| 6608 | 74 |
|
31605
e88a07dec498
maint: Use macros to begin/end C++ namespaces.
Rik <rik@octave.org>
parents:
30564
diff
changeset
|
75 OCTAVE_BEGIN_NAMESPACE(octave) |
|
29958
32c3a5805893
move DEFUN and DEFMETHOD functions inside octave namespace
John W. Eaton <jwe@octave.org>
parents:
29358
diff
changeset
|
76 |
| 6608 | 77 // A node struct for the Cuthill-McKee algorithm |
| 78 struct CMK_Node | |
| 79 { | |
| 80 // the node's id (matrix row index) | |
| 81 octave_idx_type id; | |
| 82 // the node's degree | |
| 83 octave_idx_type deg; | |
| 84 // minimal distance to the root of the spanning tree | |
| 85 octave_idx_type dist; | |
| 86 }; | |
| 87 | |
| 88 // A simple queue. | |
| 89 // Queues Q have a fixed maximum size N (rows,cols of the matrix) and are | |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
90 // stored in an array. qh and qt point to queue head and tail. |
| 6608 | 91 |
| 92 // Enqueue operation (adds a node "o" at the tail) | |
| 6959 | 93 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
94 inline static void |
| 6959 | 95 Q_enq (CMK_Node *Q, octave_idx_type N, octave_idx_type& qt, const CMK_Node& o) |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
96 { |
| 6959 | 97 Q[qt] = o; |
| 98 qt = (qt + 1) % (N + 1); | |
| 99 } | |
| 6608 | 100 |
| 101 // Dequeue operation (removes a node from the head) | |
| 6959 | 102 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
103 inline static CMK_Node |
|
30390
a61e1a0f6024
maint: style check C++ files in libinterp/ ahead of 7.1 release.
Rik <rik@octave.org>
parents:
29958
diff
changeset
|
104 Q_deq (CMK_Node *Q, octave_idx_type N, octave_idx_type& qh) |
| 6959 | 105 { |
| 106 CMK_Node r = Q[qh]; | |
| 107 qh = (qh + 1) % (N + 1); | |
| 108 return r; | |
| 109 } | |
| 6608 | 110 |
| 111 // Predicate (queue empty) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
112 #define Q_empty(Q, N, qh, qt) ((qh) == (qt)) |
| 6608 | 113 |
| 114 // A simple, array-based binary heap (used as a priority queue for nodes) | |
| 115 | |
| 116 // the left descendant of entry i | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
117 #define LEFT(i) (((i) << 1) + 1) // = (2*(i)+1) |
| 6608 | 118 // the right descendant of entry i |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
119 #define RIGHT(i) (((i) << 1) + 2) // = (2*(i)+2) |
| 6608 | 120 // the parent of entry i |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
121 #define PARENT(i) (((i) - 1) >> 1) // = floor(((i)-1)/2) |
| 6608 | 122 |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
123 // Builds a min-heap (the root contains the smallest element). A is an array |
| 6608 | 124 // with the graph's nodes, i is a starting position, size is the length of A. |
| 6959 | 125 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
126 static void |
| 6959 | 127 H_heapify_min (CMK_Node *A, octave_idx_type i, octave_idx_type size) |
| 128 { | |
| 129 octave_idx_type j = i; | |
| 130 for (;;) | |
| 131 { | |
| 132 octave_idx_type l = LEFT(j); | |
| 133 octave_idx_type r = RIGHT(j); | |
| 134 | |
| 135 octave_idx_type smallest; | |
| 136 if (l < size && A[l].deg < A[j].deg) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
137 smallest = l; |
| 6959 | 138 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
139 smallest = j; |
| 6959 | 140 |
| 141 if (r < size && A[r].deg < A[smallest].deg) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
142 smallest = r; |
| 6959 | 143 |
| 144 if (smallest != j) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
145 { |
|
14862
bbdc822be2b9
smyrcm.cc: use std::swap instead of custom swap code.
Rik <octave@nomad.inbox5.com>
parents:
14854
diff
changeset
|
146 std::swap (A[j], A[smallest]); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
147 j = smallest; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
148 } |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
149 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
150 break; |
| 6959 | 151 } |
| 152 } | |
| 6608 | 153 |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
154 // Heap operation insert. Running time is O(log(n)) |
| 6959 | 155 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
156 static void |
| 6959 | 157 H_insert (CMK_Node *H, octave_idx_type& h, const CMK_Node& o) |
| 158 { | |
| 159 octave_idx_type i = h++; | |
| 160 | |
| 161 H[i] = o; | |
| 162 | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
163 if (i == 0) |
| 6959 | 164 return; |
| 165 do | |
| 166 { | |
| 167 octave_idx_type p = PARENT(i); | |
| 168 if (H[i].deg < H[p].deg) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
169 { |
|
14862
bbdc822be2b9
smyrcm.cc: use std::swap instead of custom swap code.
Rik <octave@nomad.inbox5.com>
parents:
14854
diff
changeset
|
170 std::swap (H[i], H[p]); |
| 6959 | 171 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
172 i = p; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
173 } |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
174 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
175 break; |
| 6959 | 176 } |
| 177 while (i > 0); | |
| 178 } | |
| 6608 | 179 |
|
27956
2310164737b3
fix many spelling errors (bug #57613)
John W. Eaton <jwe@octave.org>
parents:
26376
diff
changeset
|
180 // Heap operation remove-min. Removes the smallest element in O(1) and |
| 6608 | 181 // reorganizes the heap optionally in O(log(n)) |
| 6959 | 182 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
183 inline static CMK_Node |
| 6959 | 184 H_remove_min (CMK_Node *H, octave_idx_type& h, int reorg/*=1*/) |
| 185 { | |
| 186 CMK_Node r = H[0]; | |
| 187 H[0] = H[--h]; | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
188 if (reorg) |
|
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
189 H_heapify_min (H, 0, h); |
| 6959 | 190 return r; |
| 191 } | |
| 6608 | 192 |
| 193 // Predicate (heap empty) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
194 #define H_empty(H, h) ((h) == 0) |
| 6608 | 195 |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
196 // Helper function for the Cuthill-McKee algorithm. Tries to determine a |
| 6608 | 197 // pseudo-peripheral node of the graph as starting node. |
| 6959 | 198 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
199 static octave_idx_type |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
200 find_starting_node (octave_idx_type N, const octave_idx_type *ridx, |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
201 const octave_idx_type *cidx, const octave_idx_type *ridx2, |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
202 const octave_idx_type *cidx2, octave_idx_type *D, |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
203 octave_idx_type start) |
| 6959 | 204 { |
| 205 CMK_Node w; | |
| 206 | |
| 207 OCTAVE_LOCAL_BUFFER (CMK_Node, Q, N+1); | |
| 208 boolNDArray btmp (dim_vector (1, N), false); | |
| 209 bool *visit = btmp.fortran_vec (); | |
| 210 | |
| 211 octave_idx_type qh = 0; | |
| 212 octave_idx_type qt = 0; | |
| 213 CMK_Node x; | |
| 214 x.id = start; | |
| 215 x.deg = D[start]; | |
| 216 x.dist = 0; | |
| 217 Q_enq (Q, N, qt, x); | |
| 218 visit[start] = true; | |
| 219 | |
| 220 // distance level | |
| 221 octave_idx_type level = 0; | |
| 222 // current largest "eccentricity" | |
| 223 octave_idx_type max_dist = 0; | |
| 224 | |
| 225 for (;;) | |
| 226 { | |
| 227 while (! Q_empty (Q, N, qh, qt)) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
228 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
229 CMK_Node v = Q_deq (Q, N, qh); |
| 6959 | 230 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
231 if (v.dist > x.dist || (v.id != x.id && v.deg > x.deg)) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
232 x = v; |
| 6959 | 233 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
234 octave_idx_type i = v.id; |
| 6959 | 235 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
236 // add all unvisited neighbors to the queue |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
237 octave_idx_type j1 = cidx[i]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
238 octave_idx_type j2 = cidx2[i]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
239 while (j1 < cidx[i+1] || j2 < cidx2[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
240 { |
|
22860
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
241 octave_quit (); |
| 6959 | 242 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
243 if (j1 == cidx[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
244 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
245 octave_idx_type r2 = ridx2[j2++]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
246 if (! visit[r2]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
247 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
248 // the distance of node j is dist(i)+1 |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
249 w.id = r2; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
250 w.deg = D[r2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
251 w.dist = v.dist+1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
252 Q_enq (Q, N, qt, w); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
253 visit[r2] = true; |
| 6959 | 254 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
255 if (w.dist > level) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
256 level = w.dist; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
257 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
258 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
259 else if (j2 == cidx2[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
260 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
261 octave_idx_type r1 = ridx[j1++]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
262 if (! visit[r1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
263 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
264 // the distance of node j is dist(i)+1 |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
265 w.id = r1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
266 w.deg = D[r1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
267 w.dist = v.dist+1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
268 Q_enq (Q, N, qt, w); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
269 visit[r1] = true; |
| 6959 | 270 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
271 if (w.dist > level) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
272 level = w.dist; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
273 } |
|
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 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
276 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
277 octave_idx_type r1 = ridx[j1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
278 octave_idx_type r2 = ridx2[j2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
279 if (r1 <= r2) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
280 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
281 if (! visit[r1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
282 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
283 w.id = r1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
284 w.deg = D[r1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
285 w.dist = v.dist+1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
286 Q_enq (Q, N, qt, w); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
287 visit[r1] = true; |
| 6959 | 288 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
289 if (w.dist > level) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
290 level = w.dist; |
|
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 j1++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
293 if (r1 == r2) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
294 j2++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
295 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
296 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
297 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
298 if (! visit[r2]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
299 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
300 w.id = r2; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
301 w.deg = D[r2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
302 w.dist = v.dist+1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
303 Q_enq (Q, N, qt, w); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
304 visit[r2] = true; |
| 6959 | 305 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
306 if (w.dist > level) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
307 level = w.dist; |
|
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 j2++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
310 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
311 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
312 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
313 } // finish of BFS |
| 6959 | 314 |
| 315 if (max_dist < x.dist) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
316 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
317 max_dist = x.dist; |
| 6959 | 318 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
319 for (octave_idx_type i = 0; i < N; i++) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
320 visit[i] = false; |
| 6959 | 321 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
322 visit[x.id] = true; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
323 x.dist = 0; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
324 qt = qh = 0; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
325 Q_enq (Q, N, qt, x); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
326 } |
| 6959 | 327 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
328 break; |
| 6959 | 329 } |
| 330 return x.id; | |
| 331 } | |
| 6608 | 332 |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
333 // Calculates the node's degrees. This means counting the nonzero elements |
|
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
334 // in the symmetric matrix' rows. This works for non-symmetric matrices |
| 6608 | 335 // as well. |
| 6959 | 336 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
337 static octave_idx_type |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
338 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
|
339 const octave_idx_type *cidx, octave_idx_type *D) |
| 6959 | 340 { |
| 341 octave_idx_type max_deg = 0; | |
| 342 | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
343 for (octave_idx_type i = 0; i < N; i++) |
| 6959 | 344 D[i] = 0; |
| 345 | |
| 346 for (octave_idx_type j = 0; j < N; j++) | |
| 347 { | |
| 348 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
|
349 { |
|
22860
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
350 octave_quit (); |
|
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
351 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
352 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
|
353 // there is a nonzero element (k,j) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
354 D[k]++; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
355 if (D[k] > max_deg) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
356 max_deg = D[k]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
357 // 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
|
358 // the symmetric matrix: |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
359 if (k != j) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
360 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
361 bool found = false; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
362 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
|
363 { |
|
22860
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
364 octave_quit (); |
| 6959 | 365 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
366 if (ridx[l] == j) |
|
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 found = true; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
369 break; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
370 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
371 else if (ridx[l] > j) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
372 break; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
373 } |
| 6959 | 374 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
375 if (! found) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
376 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
377 // A(j,k) == 0 |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
378 D[j]++; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
379 if (D[j] > max_deg) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
380 max_deg = D[j]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
381 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
382 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
383 } |
| 6959 | 384 } |
| 385 return max_deg; | |
| 386 } | |
| 6608 | 387 |
| 388 // Transpose of the structure of a square sparse matrix | |
| 6959 | 389 |
| 6608 | 390 static void |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
391 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
|
392 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
|
393 octave_idx_type *cidx2) |
| 6959 | 394 { |
| 395 octave_idx_type nz = cidx[N]; | |
| 396 | |
| 397 OCTAVE_LOCAL_BUFFER (octave_idx_type, w, N + 1); | |
| 398 for (octave_idx_type i = 0; i < N; i++) | |
| 399 w[i] = 0; | |
| 400 for (octave_idx_type i = 0; i < nz; i++) | |
| 401 w[ridx[i]]++; | |
| 402 nz = 0; | |
| 403 for (octave_idx_type i = 0; i < N; i++) | |
| 404 { | |
|
22860
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
405 octave_quit (); |
|
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
406 |
| 6959 | 407 cidx2[i] = nz; |
| 408 nz += w[i]; | |
| 409 w[i] = cidx2[i]; | |
| 410 } | |
| 411 cidx2[N] = nz; | |
| 412 w[N] = nz; | |
| 413 | |
| 414 for (octave_idx_type j = 0; j < N; j++) | |
| 415 for (octave_idx_type k = cidx[j]; k < cidx[j + 1]; k++) | |
| 416 { | |
|
22860
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
417 octave_quit (); |
|
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
418 |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14862
diff
changeset
|
419 octave_idx_type q = w[ridx[k]]++; |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
420 ridx2[q] = j; |
| 6959 | 421 } |
| 422 } | |
| 6608 | 423 |
| 424 // An implementation of the Cuthill-McKee algorithm. | |
|
28024
c28b8ba841fb
move sparse functions from dldfcn to corefcn directory (bug #57459)
John W. Eaton <jwe@octave.org>
parents:
27957
diff
changeset
|
425 DEFUN (symrcm, args, , |
|
c28b8ba841fb
move sparse functions from dldfcn to corefcn directory (bug #57459)
John W. Eaton <jwe@octave.org>
parents:
27957
diff
changeset
|
426 doc: /* -*- texinfo -*- |
|
21966
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
427 @deftypefn {} {@var{p} =} symrcm (@var{S}) |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
428 Return the symmetric reverse @nospell{Cuthill-McKee} permutation of @var{S}. |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
429 |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
430 @var{p} is a permutation vector such that |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
431 @code{@var{S}(@var{p}, @var{p})} tends to have its diagonal elements closer |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
432 to the diagonal than @var{S}. This is a good preordering for LU or |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
433 Cholesky@tie{}factorization of matrices that come from ``long, skinny'' |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
434 problems. It works for both symmetric and asymmetric @var{S}. |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
435 |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
436 The algorithm represents a heuristic approach to the NP-complete bandwidth |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
437 minimization problem. The implementation is based in the descriptions found |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
438 in |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
439 |
|
25032
a1e391e33004
doc: grammarcheck documentation again ahead of 4.4 release.
Rik <rik@octave.org>
parents:
25003
diff
changeset
|
440 @nospell{E. Cuthill, J. McKee}. |
|
a1e391e33004
doc: grammarcheck documentation again ahead of 4.4 release.
Rik <rik@octave.org>
parents:
25003
diff
changeset
|
441 @cite{Reducing the Bandwidth of Sparse Symmetric Matrices}. |
|
a1e391e33004
doc: grammarcheck documentation again ahead of 4.4 release.
Rik <rik@octave.org>
parents:
25003
diff
changeset
|
442 Proceedings of the 24th @nospell{ACM} National Conference, |
|
21966
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
443 157--172 1969, Brandon Press, New Jersey. |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
444 |
|
27800
5a6a19a4e3da
doc: Use Texinfo non-sentence ending periods in citations.
Rik <rik@octave.org>
parents:
26376
diff
changeset
|
445 @nospell{A. George, J.W.H. Liu}. @cite{Computer Solution of Large Sparse |
|
21966
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
446 Positive Definite Systems}, Prentice Hall Series in Computational |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
447 Mathematics, ISBN 0-13-165274-5, 1981. |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
448 |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
449 @seealso{colperm, colamd, symamd} |
|
112b20240c87
move docstrings in C++ files out of C strings and into comments
John W. Eaton <jwe@octave.org>
parents:
21751
diff
changeset
|
450 @end deftypefn */) |
| 6608 | 451 { |
|
20818
cef0448a6ed2
eliminate unnecessary uses of nargin
John W. Eaton <jwe@octave.org>
parents:
20790
diff
changeset
|
452 if (args.length () != 1) |
|
20790
c2d9556d51d0
eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents:
20555
diff
changeset
|
453 print_usage (); |
| 6608 | 454 |
| 6959 | 455 octave_value arg = args(0); |
| 6608 | 456 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
457 // the parameter of the matrix is converted into a sparse matrix |
| 6608 | 458 //(if necessary) |
| 459 octave_idx_type *cidx; | |
| 460 octave_idx_type *ridx; | |
| 461 SparseMatrix Ar; | |
| 462 SparseComplexMatrix Ac; | |
| 463 | |
|
23582
0cc2011d800e
maint: Deprecate is_real_type and replace with isreal.
Rik <rik@octave.org>
parents:
23220
diff
changeset
|
464 if (arg.isreal ()) |
| 6608 | 465 { |
| 6959 | 466 Ar = arg.sparse_matrix_value (); |
| 6608 | 467 // Note cidx/ridx are const, so use xridx and xcidx... |
| 468 cidx = Ar.xcidx (); | |
| 469 ridx = Ar.xridx (); | |
| 470 } | |
| 471 else | |
| 472 { | |
| 6959 | 473 Ac = arg.sparse_complex_matrix_value (); |
| 6608 | 474 cidx = Ac.xcidx (); |
| 475 ridx = Ac.xridx (); | |
| 476 } | |
| 477 | |
| 478 octave_idx_type nr = arg.rows (); | |
| 479 octave_idx_type nc = arg.columns (); | |
| 480 | |
| 481 if (nr != nc) | |
|
21110
3d0d84305600
Use err_square_matrix_required more widely.
Rik <rik@octave.org>
parents:
21100
diff
changeset
|
482 err_square_matrix_required ("symrcm", "S"); |
| 6608 | 483 |
| 484 if (nr == 0 && nc == 0) | |
|
20939
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
485 return ovl (NDArray (dim_vector (1, 0))); |
| 6959 | 486 |
| 6608 | 487 // sizes of the heaps |
| 488 octave_idx_type s = 0; | |
| 6959 | 489 |
| 6608 | 490 // 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
|
491 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
|
492 octave_idx_type qh = 0; |
| 6608 | 493 CMK_Node v, w; |
| 494 // dimension of the matrix | |
| 6959 | 495 octave_idx_type N = nr; |
| 496 | |
| 6608 | 497 OCTAVE_LOCAL_BUFFER (octave_idx_type, cidx2, N + 1); |
| 498 OCTAVE_LOCAL_BUFFER (octave_idx_type, ridx2, cidx[N]); | |
| 499 transpose (N, ridx, cidx, ridx2, cidx2); | |
| 500 | |
| 501 // the permutation vector | |
| 502 NDArray P (dim_vector (1, N)); | |
| 503 | |
| 504 // compute the node degrees | |
| 6959 | 505 OCTAVE_LOCAL_BUFFER (octave_idx_type, D, N); |
| 506 octave_idx_type max_deg = calc_degrees (N, ridx, cidx, D); | |
| 6608 | 507 |
| 508 // if none of the nodes has a degree > 0 (a matrix of zeros) | |
| 509 // the return value corresponds to the identity permutation | |
| 510 if (max_deg == 0) | |
| 511 { | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
512 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
|
513 P(i) = i; |
|
20939
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
514 |
|
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
515 return ovl (P); |
| 6608 | 516 } |
| 517 | |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
518 // a heap for the a node's neighbors. The number of neighbors is |
| 6608 | 519 // limited by the maximum degree max_deg: |
| 6959 | 520 OCTAVE_LOCAL_BUFFER (CMK_Node, S, max_deg); |
| 6608 | 521 |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
522 // a queue for the BFS. The array is always one element larger than |
| 6608 | 523 // the number of entries that are stored. |
| 6959 | 524 OCTAVE_LOCAL_BUFFER (CMK_Node, Q, N+1); |
| 6608 | 525 |
| 526 // a counter (for building the permutation) | |
| 6959 | 527 octave_idx_type c = -1; |
| 6608 | 528 |
| 6959 | 529 // upper bound for the bandwidth (=quality of solution) |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
530 // initialize the bandwidth of the graph with 0. B contains the |
| 6608 | 531 // the maximum of the theoretical lower limits of the subgraphs |
| 532 // bandwidths. | |
| 6959 | 533 octave_idx_type B = 0; |
| 6608 | 534 |
| 535 // mark all nodes as unvisited; with the exception of the nodes | |
| 536 // 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
|
537 |
| 6608 | 538 boolNDArray btmp (dim_vector (1, N), false); |
| 539 bool *visit = btmp.fortran_vec (); | |
| 540 | |
| 541 do | |
| 542 { | |
| 543 // locate an unvisited starting node of the graph | |
| 6959 | 544 octave_idx_type i; |
| 6608 | 545 for (i = 0; i < N; i++) |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
546 if (! visit[i]) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
547 break; |
| 6608 | 548 |
| 549 // locate a probably better starting node | |
| 550 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
|
551 |
| 6608 | 552 // mark the node as visited and enqueue it (a starting node |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
553 // for the BFS). Since the node will be a root of a spanning |
| 6608 | 554 // tree, its dist is 0. |
| 555 v.deg = D[v.id]; | |
| 556 v.dist = 0; | |
| 557 visit[v.id] = true; | |
| 6959 | 558 Q_enq (Q, N, qt, v); |
| 6608 | 559 |
| 6959 | 560 // lower bound for the bandwidth of a subgraph |
| 6608 | 561 // keep a "level" in the spanning tree (= min. distance to the |
| 562 // root) for determining the bandwidth of the computed | |
| 563 // permutation P | |
| 6959 | 564 octave_idx_type Bsub = 0; |
| 6608 | 565 // min. dist. to the root is 0 |
| 6959 | 566 octave_idx_type level = 0; |
| 6608 | 567 // the root is the first/only node on level 0 |
| 6959 | 568 octave_idx_type level_N = 1; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
569 |
| 6677 | 570 while (! Q_empty (Q, N, qh, qt)) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
571 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
572 v = Q_deq (Q, N, qh); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
573 i = v.id; |
| 6608 | 574 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
575 c++; |
| 6608 | 576 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
577 // for computing the inverse permutation P where |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
578 // 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
|
579 // P(i) = c; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
580 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
581 // for computing permutation P where |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
582 // 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
|
583 P(c) = i; |
| 6608 | 584 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
585 // 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
|
586 s = 0; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
587 octave_idx_type j1 = cidx[i]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
588 octave_idx_type j2 = cidx2[i]; |
| 6608 | 589 |
|
22860
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
590 octave_quit (); |
|
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
591 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
592 while (j1 < cidx[i+1] || j2 < cidx2[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
593 { |
|
22860
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
594 octave_quit (); |
|
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
595 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
596 if (j1 == cidx[i+1]) |
|
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 octave_idx_type r2 = ridx2[j2++]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
599 if (! visit[r2]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
600 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
601 // the distance of node j is dist(i)+1 |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
602 w.id = r2; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
603 w.deg = D[r2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
604 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
|
605 H_insert (S, s, w); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
606 visit[r2] = true; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
607 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
608 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
609 else if (j2 == cidx2[i+1]) |
|
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 octave_idx_type r1 = ridx[j1++]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
612 if (! visit[r1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
613 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
614 w.id = r1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
615 w.deg = D[r1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
616 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
|
617 H_insert (S, s, w); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
618 visit[r1] = true; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
619 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
620 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
621 else |
|
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 octave_idx_type r1 = ridx[j1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
624 octave_idx_type r2 = ridx2[j2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
625 if (r1 <= r2) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
626 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
627 if (! visit[r1]) |
|
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 w.id = r1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
630 w.deg = D[r1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
631 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
|
632 H_insert (S, s, w); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
633 visit[r1] = true; |
|
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 j1++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
636 if (r1 == r2) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
637 j2++; |
|
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 else |
|
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 if (! visit[r2]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
642 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
643 w.id = r2; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
644 w.deg = D[r2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
645 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
|
646 H_insert (S, s, w); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
647 visit[r2] = true; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
648 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
649 j2++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
650 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
651 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
652 } |
| 6608 | 653 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
654 // 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
|
655 while (! H_empty (S, s)) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
656 { |
|
22860
0b1e25cc4457
eliminate use of OCTAVE_QUIT macro in C++ sources
John W. Eaton <jwe@octave.org>
parents:
22755
diff
changeset
|
657 octave_quit (); |
| 6608 | 658 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
659 // 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
|
660 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
|
661 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
662 // entered the BFS a new level? |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
663 if (v.dist > level) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
664 { |
|
27956
2310164737b3
fix many spelling errors (bug #57613)
John W. Eaton <jwe@octave.org>
parents:
26376
diff
changeset
|
665 // adjustment of bandwidth: |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
666 // "[...] the minimum bandwidth that |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
667 // can be obtained [...] is the |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
668 // maximum number of nodes per level" |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
669 if (Bsub < level_N) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
670 Bsub = level_N; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
671 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
672 level = v.dist; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
673 // v is the first node on the new level |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
674 level_N = 1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
675 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
676 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
677 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
678 // there is no new level but another node on |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
679 // this level: |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
680 level_N++; |
|
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 // enqueue v in O(1) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
684 Q_enq (Q, N, qt, v); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
685 } |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
686 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
687 // synchronize the bandwidth with level_N once again: |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
688 if (Bsub < level_N) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
689 Bsub = level_N; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
690 } |
|
21751
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
691 // finish of BFS. If there are still unvisited nodes in the graph |
|
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
692 // then it is split into CCs. The computed bandwidth is the maximum |
|
b571fc85953f
maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents:
21724
diff
changeset
|
693 // of all subgraphs. Update: |
| 6608 | 694 if (Bsub > B) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
695 B = Bsub; |
| 6608 | 696 } |
| 697 // are there any nodes left? | |
| 698 while (c+1 < N); | |
| 699 | |
| 700 // compute the reverse-ordering | |
| 701 s = N / 2 - 1; | |
| 6959 | 702 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
|
703 std::swap (P.elem (i), P.elem (j)); |
| 6608 | 704 |
| 705 // increment all indices, since Octave is not C | |
|
20939
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
706 return ovl (P+1); |
| 6608 | 707 } |
|
29958
32c3a5805893
move DEFUN and DEFMETHOD functions inside octave namespace
John W. Eaton <jwe@octave.org>
parents:
29358
diff
changeset
|
708 |
|
31605
e88a07dec498
maint: Use macros to begin/end C++ namespaces.
Rik <rik@octave.org>
parents:
30564
diff
changeset
|
709 OCTAVE_END_NAMESPACE(octave) |