Mercurial > octave
annotate libinterp/dldfcn/symrcm.cc @ 21301:40de9f8f23a6
Use '#include "config.h"' rather than <config.h>.
* mk-octave-config-h.sh, mk-opts.pl, Backend.cc, BaseControl.cc,
ButtonControl.cc, Canvas.cc, CheckBoxControl.cc, Container.cc, ContextMenu.cc,
EditControl.cc, Figure.cc, FigureWindow.cc, GLCanvas.cc, KeyMap.cc,
ListBoxControl.cc, Logger.cc, Menu.cc, MouseModeActionGroup.cc, Object.cc,
ObjectFactory.cc, ObjectProxy.cc, Panel.cc, PopupMenuControl.cc,
PushButtonControl.cc, PushTool.cc, QtHandlesUtils.cc, RadioButtonControl.cc,
SliderControl.cc, TextControl.cc, TextEdit.cc, ToggleButtonControl.cc,
ToggleTool.cc, ToolBar.cc, ToolBarButton.cc, __init_qt__.cc,
annotation-dialog.cc, gl-select.cc, module.mk, kpty.cpp, color-picker.cc,
dialog.cc, documentation-dock-widget.cc, files-dock-widget.cc,
find-files-dialog.cc, find-files-model.cc, history-dock-widget.cc,
file-editor-tab.cc, file-editor-tab.h, file-editor.cc, find-dialog.cc,
marker.cc, octave-qscintilla.cc, octave-txt-lexer.cc, main-window.cc,
octave-cmd.cc, octave-dock-widget.cc, octave-gui.cc, octave-interpreter.cc,
octave-qt-link.cc, parser.cc, webinfo.cc, resource-manager.cc,
settings-dialog.cc, shortcut-manager.cc, terminal-dock-widget.cc,
thread-manager.cc, welcome-wizard.cc, workspace-model.cc, workspace-view.cc,
build-env-features.sh, build-env.in.cc, Cell.cc, __contourc__.cc,
__dispatch__.cc, __dsearchn__.cc, __ichol__.cc, __ilu__.cc, __lin_interpn__.cc,
__pchip_deriv__.cc, __qp__.cc, balance.cc, besselj.cc, betainc.cc, bitfcns.cc,
bsxfun.cc, c-file-ptr-stream.cc, cdisplay.c, cellfun.cc, coct-hdf5-types.c,
colloc.cc, comment-list.cc, conv2.cc, daspk.cc, dasrt.cc, dassl.cc, data.cc,
debug.cc, defaults.cc, defun.cc, det.cc, dirfns.cc, display.cc, dlmread.cc,
dot.cc, dynamic-ld.cc, eig.cc, ellipj.cc, error.cc, errwarn.cc, event-queue.cc,
fft.cc, fft2.cc, fftn.cc, file-io.cc, filter.cc, find.cc, ft-text-renderer.cc,
gammainc.cc, gcd.cc, getgrent.cc, getpwent.cc, getrusage.cc, givens.cc,
gl-render.cc, gl2ps-print.cc, graphics.cc, gripes.cc, hash.cc, help.cc,
hess.cc, hex2num.cc, hook-fcn.cc, input.cc, inv.cc, jit-ir.cc, jit-typeinfo.cc,
jit-util.cc, kron.cc, load-path.cc, load-save.cc, lookup.cc,
ls-ascii-helper.cc, ls-hdf5.cc, ls-mat-ascii.cc, ls-mat4.cc, ls-mat5.cc,
ls-oct-binary.cc, ls-oct-text.cc, ls-utils.cc, lsode.cc, lu.cc, luinc.cc,
mappers.cc, matrix_type.cc, max.cc, mex.cc, mgorth.cc, nproc.cc,
oct-errno.in.cc, oct-fstrm.cc, oct-hdf5-types.cc, oct-hist.cc, oct-iostrm.cc,
oct-lvalue.cc, oct-map.cc, oct-prcstrm.cc, oct-procbuf.cc, oct-stream.cc,
oct-strstrm.cc, oct-tex-lexer.in.ll, oct-tex-parser.in.yy, octave-link.cc,
ordschur.cc, pager.cc, pinv.cc, pr-output.cc, procstream.cc, profiler.cc,
psi.cc, pt-jit.cc, quad.cc, quadcc.cc, qz.cc, rand.cc, rcond.cc, regexp.cc,
schur.cc, sighandlers.cc, siglist.c, sparse-xdiv.cc, sparse-xpow.cc, sparse.cc,
spparms.cc, sqrtm.cc, str2double.cc, strfind.cc, strfns.cc, sub2ind.cc, svd.cc,
sylvester.cc, symtab.cc, syscalls.cc, sysdep.cc, text-renderer.cc, time.cc,
toplev.cc, tril.cc, tsearch.cc, txt-eng.cc, typecast.cc, urlwrite.cc, utils.cc,
variables.cc, xdiv.cc, xgl2ps.c, xnorm.cc, xpow.cc, zfstream.cc,
__delaunayn__.cc, __eigs__.cc, __fltk_uigetfile__.cc, __glpk__.cc,
__init_fltk__.cc, __init_gnuplot__.cc, __magick_read__.cc, __osmesa_print__.cc,
__voronoi__.cc, amd.cc, audiodevinfo.cc, audioread.cc, ccolamd.cc, chol.cc,
colamd.cc, convhulln.cc, dmperm.cc, fftw.cc, qr.cc, symbfact.cc, symrcm.cc,
mkbuiltins, mkops, ov-base-diag.cc, ov-base-int.cc, ov-base-mat.cc,
ov-base-scalar.cc, ov-base-sparse.cc, ov-base.cc, ov-bool-mat.cc,
ov-bool-sparse.cc, ov-bool.cc, ov-builtin.cc, ov-cell.cc, ov-ch-mat.cc,
ov-class.cc, ov-classdef.cc, ov-colon.cc, ov-complex.cc, ov-cs-list.cc,
ov-cx-diag.cc, ov-cx-mat.cc, ov-cx-sparse.cc, ov-dld-fcn.cc, ov-fcn-handle.cc,
ov-fcn-inline.cc, ov-fcn.cc, ov-float.cc, ov-flt-complex.cc, ov-flt-cx-diag.cc,
ov-flt-cx-mat.cc, ov-flt-re-diag.cc, ov-flt-re-mat.cc, ov-int16.cc,
ov-int32.cc, ov-int64.cc, ov-int8.cc, ov-java.cc, ov-lazy-idx.cc,
ov-mex-fcn.cc, ov-null-mat.cc, ov-oncleanup.cc, ov-perm.cc, ov-range.cc,
ov-re-diag.cc, ov-re-mat.cc, ov-re-sparse.cc, ov-scalar.cc, ov-str-mat.cc,
ov-struct.cc, ov-typeinfo.cc, ov-uint16.cc, ov-uint32.cc, ov-uint64.cc,
ov-uint8.cc, ov-usr-fcn.cc, ov.cc, ovl.cc, octave.cc, 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-double-conv.cc, op-fcdm-fcdm.cc,
op-fcdm-fdm.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-float-conv.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-int-conv.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-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, lex.ll, oct-parse.in.yy,
pt-arg-list.cc, pt-array-list.cc, pt-assign.cc, pt-binop.cc, pt-bp.cc,
pt-cbinop.cc, pt-cell.cc, pt-check.cc, pt-classdef.cc, pt-cmd.cc, pt-colon.cc,
pt-const.cc, pt-decl.cc, pt-eval.cc, pt-except.cc, pt-exp.cc, pt-fcn-handle.cc,
pt-funcall.cc, pt-id.cc, pt-idx.cc, pt-jump.cc, pt-loop.cc, pt-mat.cc,
pt-misc.cc, pt-pr-code.cc, pt-select.cc, pt-stmt.cc, pt-unop.cc, pt.cc,
token.cc, Array-jit.cc, Array-os.cc, Array-sym.cc, Array-tc.cc, version.cc,
Array-C.cc, Array-b.cc, Array-ch.cc, Array-d.cc, Array-f.cc, Array-fC.cc,
Array-i.cc, Array-idx-vec.cc, Array-s.cc, Array-str.cc, Array-util.cc,
Array-voidp.cc, Array.cc, CColVector.cc, CDiagMatrix.cc, CMatrix.cc,
CNDArray.cc, CRowVector.cc, CSparse.cc, DiagArray2.cc, MArray-C.cc,
MArray-d.cc, MArray-f.cc, MArray-fC.cc, MArray-i.cc, MArray-s.cc, MArray.cc,
MDiagArray2.cc, MSparse-C.cc, MSparse-d.cc, MatrixType.cc, PermMatrix.cc,
Range.cc, Sparse-C.cc, Sparse-b.cc, Sparse-d.cc, Sparse.cc, boolMatrix.cc,
boolNDArray.cc, boolSparse.cc, chMatrix.cc, chNDArray.cc, dColVector.cc,
dDiagMatrix.cc, dMatrix.cc, dNDArray.cc, dRowVector.cc, dSparse.cc,
dim-vector.cc, fCColVector.cc, fCDiagMatrix.cc, fCMatrix.cc, fCNDArray.cc,
fCRowVector.cc, fColVector.cc, fDiagMatrix.cc, fMatrix.cc, fNDArray.cc,
fRowVector.cc, idx-vector.cc, int16NDArray.cc, int32NDArray.cc,
int64NDArray.cc, int8NDArray.cc, intNDArray.cc, uint16NDArray.cc,
uint32NDArray.cc, uint64NDArray.cc, uint8NDArray.cc, blaswrap.c, cquit.c,
f77-extern.cc, f77-fcn.c, lo-error.c, quit.cc, CollocWt.cc, DASPK.cc, DASRT.cc,
DASSL.cc, EIG.cc, LSODE.cc, ODES.cc, Quad.cc, aepbalance.cc, chol.cc,
eigs-base.cc, fEIG.cc, gepbalance.cc, hess.cc, lo-mappers.cc, lo-specfun.cc,
lu.cc, oct-convn.cc, oct-fftw.cc, oct-norm.cc, oct-rand.cc, oct-spparms.cc,
qr.cc, qrp.cc, randgamma.c, randmtzig.c, randpoisson.c, schur.cc,
sparse-chol.cc, sparse-dmsolve.cc, sparse-lu.cc, sparse-qr.cc, svd.cc,
mk-ops.awk, dir-ops.cc, file-ops.cc, file-stat.cc, lo-sysdep.cc, mach-info.cc,
oct-env.cc, oct-group.cc, oct-passwd.cc, oct-syscalls.cc, oct-time.cc,
oct-uname.cc, cmd-edit.cc, cmd-hist.cc, data-conv.cc, f2c-main.c,
glob-match.cc, kpse.cc, lo-array-errwarn.cc, lo-array-gripes.cc, lo-cutils.c,
lo-ieee.cc, lo-regexp.cc, lo-utils.cc, oct-base64.cc, oct-glob.cc,
oct-inttypes.cc, oct-locbuf.cc, oct-mutex.cc, oct-rl-edit.c, oct-rl-hist.c,
oct-shlib.cc, oct-sort.cc, pathsearch.cc, singleton-cleanup.cc, sparse-sort.cc,
sparse-util.cc, str-vec.cc, unwind-prot.cc, url-transfer.cc,
display-available.c, main-cli.cc, main-gui.cc, main.in.cc, mkoctfile.in.cc,
octave-config.in.cc:
Use '#include "config.h"' rather than <config.h>.
| author | Rik <rik@octave.org> |
|---|---|
| date | Thu, 18 Feb 2016 13:34:50 -0800 |
| parents | fcac5dbbf9ed |
| children | aba2e6293dd8 |
| rev | line source |
|---|---|
| 6608 | 1 /* |
| 2 | |
|
19697
4197fc428c7d
maint: Update copyright notices for 2015.
John W. Eaton <jwe@octave.org>
parents:
19405
diff
changeset
|
3 Copyright (C) 2007-2015 Michael Weitzel |
| 6608 | 4 |
| 5 This file is part of Octave. | |
| 6 | |
| 7 Octave is free software; you can redistribute it and/or modify it | |
| 8 under the terms of the GNU General Public License as published by the | |
| 7016 | 9 Free Software Foundation; either version 3 of the License, or (at your |
| 10 option) any later version. | |
| 6608 | 11 |
| 12 Octave is distributed in the hope that it will be useful, but WITHOUT | |
| 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 15 for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 7016 | 18 along with Octave; see the file COPYING. If not, see |
| 19 <http://www.gnu.org/licenses/>. | |
| 6608 | 20 |
| 21 */ | |
| 22 | |
| 23 /* | |
| 24 An implementation of the Reverse Cuthill-McKee algorithm (symrcm) | |
| 25 | |
| 26 The implementation of this algorithm is based in the descriptions found in | |
| 27 | |
| 28 @INPROCEEDINGS{, | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
29 author = {E. Cuthill and J. McKee}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
30 title = {Reducing the Bandwidth of Sparse Symmetric Matrices}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
31 booktitle = {Proceedings of the 24th ACM National Conference}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
32 publisher = {Brandon Press}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
33 pages = {157 -- 172}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
34 location = {New Jersey}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
35 year = {1969} |
| 6608 | 36 } |
| 37 | |
| 38 @BOOK{, | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
39 author = {Alan George and Joseph W. H. Liu}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
40 title = {Computer Solution of Large Sparse Positive Definite Systems}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
41 publisher = {Prentice Hall Series in Computational Mathematics}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
42 ISBN = {0-13-165274-5}, |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
43 year = {1981} |
| 6608 | 44 } |
| 45 | |
| 46 The algorithm represents a heuristic approach to the NP-complete minimum | |
| 47 bandwidth problem. | |
| 48 | |
| 6610 | 49 Written by Michael Weitzel <michael.weitzel@@uni-siegen.de> |
| 50 <weitzel@@ldknet.org> | |
| 6608 | 51 */ |
| 52 | |
| 53 #ifdef HAVE_CONFIG_H | |
|
21301
40de9f8f23a6
Use '#include "config.h"' rather than <config.h>.
Rik <rik@octave.org>
parents:
21200
diff
changeset
|
54 # include "config.h" |
| 6608 | 55 #endif |
| 56 | |
| 57 #include "ov.h" | |
| 58 #include "defun-dld.h" | |
| 59 #include "error.h" | |
|
21100
e39e05d90788
Switch gripe_XXX to either err_XXX or warn_XXX naming scheme.
Rik <rik@octave.org>
parents:
21024
diff
changeset
|
60 #include "errwarn.h" |
| 6608 | 61 #include "utils.h" |
|
8377
25bc2d31e1bf
improve OCTAVE_LOCAL_BUFFER
Jaroslav Hajek <highegg@gmail.com>
parents:
7650
diff
changeset
|
62 #include "oct-locbuf.h" |
| 6608 | 63 |
| 64 #include "ov-re-mat.h" | |
| 65 #include "ov-re-sparse.h" | |
| 66 #include "ov-cx-sparse.h" | |
| 67 #include "oct-sparse.h" | |
| 68 | |
| 69 // A node struct for the Cuthill-McKee algorithm | |
| 70 struct CMK_Node | |
| 71 { | |
| 72 // the node's id (matrix row index) | |
| 73 octave_idx_type id; | |
| 74 // the node's degree | |
| 75 octave_idx_type deg; | |
| 76 // minimal distance to the root of the spanning tree | |
| 77 octave_idx_type dist; | |
| 78 }; | |
| 79 | |
| 80 // A simple queue. | |
| 81 // Queues Q have a fixed maximum size N (rows,cols of the matrix) and are | |
| 82 // stored in an array. qh and qt point to queue head and tail. | |
| 83 | |
| 84 // Enqueue operation (adds a node "o" at the tail) | |
| 6959 | 85 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
86 inline static void |
| 6959 | 87 Q_enq (CMK_Node *Q, octave_idx_type N, octave_idx_type& qt, const CMK_Node& o) |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
88 { |
| 6959 | 89 Q[qt] = o; |
| 90 qt = (qt + 1) % (N + 1); | |
| 91 } | |
| 6608 | 92 |
| 93 // Dequeue operation (removes a node from the head) | |
| 6959 | 94 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
95 inline static CMK_Node |
| 6959 | 96 Q_deq (CMK_Node * Q, octave_idx_type N, octave_idx_type& qh) |
| 97 { | |
| 98 CMK_Node r = Q[qh]; | |
| 99 qh = (qh + 1) % (N + 1); | |
| 100 return r; | |
| 101 } | |
| 6608 | 102 |
| 103 // Predicate (queue empty) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
104 #define Q_empty(Q, N, qh, qt) ((qh) == (qt)) |
| 6608 | 105 |
| 106 // A simple, array-based binary heap (used as a priority queue for nodes) | |
| 107 | |
| 108 // the left descendant of entry i | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
109 #define LEFT(i) (((i) << 1) + 1) // = (2*(i)+1) |
| 6608 | 110 // the right descendant of entry i |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
111 #define RIGHT(i) (((i) << 1) + 2) // = (2*(i)+2) |
| 6608 | 112 // the parent of entry i |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
113 #define PARENT(i) (((i) - 1) >> 1) // = floor(((i)-1)/2) |
| 6608 | 114 |
| 115 // Builds a min-heap (the root contains the smallest element). A is an array | |
| 116 // with the graph's nodes, i is a starting position, size is the length of A. | |
| 6959 | 117 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
118 static void |
| 6959 | 119 H_heapify_min (CMK_Node *A, octave_idx_type i, octave_idx_type size) |
| 120 { | |
| 121 octave_idx_type j = i; | |
| 122 for (;;) | |
| 123 { | |
| 124 octave_idx_type l = LEFT(j); | |
| 125 octave_idx_type r = RIGHT(j); | |
| 126 | |
| 127 octave_idx_type smallest; | |
| 128 if (l < size && A[l].deg < A[j].deg) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
129 smallest = l; |
| 6959 | 130 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
131 smallest = j; |
| 6959 | 132 |
| 133 if (r < size && A[r].deg < A[smallest].deg) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
134 smallest = r; |
| 6959 | 135 |
| 136 if (smallest != j) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
137 { |
|
14862
bbdc822be2b9
smyrcm.cc: use std::swap instead of custom swap code.
Rik <octave@nomad.inbox5.com>
parents:
14854
diff
changeset
|
138 std::swap (A[j], A[smallest]); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
139 j = smallest; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
140 } |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
141 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
142 break; |
| 6959 | 143 } |
| 144 } | |
| 6608 | 145 |
| 146 // Heap operation insert. Running time is O(log(n)) | |
| 6959 | 147 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
148 static void |
| 6959 | 149 H_insert (CMK_Node *H, octave_idx_type& h, const CMK_Node& o) |
| 150 { | |
| 151 octave_idx_type i = h++; | |
| 152 | |
| 153 H[i] = o; | |
| 154 | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
155 if (i == 0) |
| 6959 | 156 return; |
| 157 do | |
| 158 { | |
| 159 octave_idx_type p = PARENT(i); | |
| 160 if (H[i].deg < H[p].deg) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
161 { |
|
14862
bbdc822be2b9
smyrcm.cc: use std::swap instead of custom swap code.
Rik <octave@nomad.inbox5.com>
parents:
14854
diff
changeset
|
162 std::swap (H[i], H[p]); |
| 6959 | 163 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
164 i = p; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
165 } |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
166 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
167 break; |
| 6959 | 168 } |
| 169 while (i > 0); | |
| 170 } | |
| 6608 | 171 |
| 172 // Heap operation remove-min. Removes the smalles element in O(1) and | |
| 173 // reorganizes the heap optionally in O(log(n)) | |
| 6959 | 174 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
175 inline static CMK_Node |
| 6959 | 176 H_remove_min (CMK_Node *H, octave_idx_type& h, int reorg/*=1*/) |
| 177 { | |
| 178 CMK_Node r = H[0]; | |
| 179 H[0] = H[--h]; | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
180 if (reorg) |
|
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
181 H_heapify_min (H, 0, h); |
| 6959 | 182 return r; |
| 183 } | |
| 6608 | 184 |
| 185 // Predicate (heap empty) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
186 #define H_empty(H, h) ((h) == 0) |
| 6608 | 187 |
| 188 // Helper function for the Cuthill-McKee algorithm. Tries to determine a | |
| 189 // pseudo-peripheral node of the graph as starting node. | |
| 6959 | 190 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
191 static octave_idx_type |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
192 find_starting_node (octave_idx_type N, const octave_idx_type *ridx, |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
193 const octave_idx_type *cidx, const octave_idx_type *ridx2, |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
194 const octave_idx_type *cidx2, octave_idx_type *D, |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
195 octave_idx_type start) |
| 6959 | 196 { |
| 197 CMK_Node w; | |
| 198 | |
| 199 OCTAVE_LOCAL_BUFFER (CMK_Node, Q, N+1); | |
| 200 boolNDArray btmp (dim_vector (1, N), false); | |
| 201 bool *visit = btmp.fortran_vec (); | |
| 202 | |
| 203 octave_idx_type qh = 0; | |
| 204 octave_idx_type qt = 0; | |
| 205 CMK_Node x; | |
| 206 x.id = start; | |
| 207 x.deg = D[start]; | |
| 208 x.dist = 0; | |
| 209 Q_enq (Q, N, qt, x); | |
| 210 visit[start] = true; | |
| 211 | |
| 212 // distance level | |
| 213 octave_idx_type level = 0; | |
| 214 // current largest "eccentricity" | |
| 215 octave_idx_type max_dist = 0; | |
| 216 | |
| 217 for (;;) | |
| 218 { | |
| 219 while (! Q_empty (Q, N, qh, qt)) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
220 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
221 CMK_Node v = Q_deq (Q, N, qh); |
| 6959 | 222 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
223 if (v.dist > x.dist || (v.id != x.id && v.deg > x.deg)) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
224 x = v; |
| 6959 | 225 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
226 octave_idx_type i = v.id; |
| 6959 | 227 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
228 // add all unvisited neighbors to the queue |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
229 octave_idx_type j1 = cidx[i]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
230 octave_idx_type j2 = cidx2[i]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
231 while (j1 < cidx[i+1] || j2 < cidx2[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
232 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
233 OCTAVE_QUIT; |
| 6959 | 234 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
235 if (j1 == cidx[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
236 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
237 octave_idx_type r2 = ridx2[j2++]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
238 if (! visit[r2]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
239 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
240 // the distance of node j is dist(i)+1 |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
241 w.id = r2; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
242 w.deg = D[r2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
243 w.dist = v.dist+1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
244 Q_enq (Q, N, qt, w); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
245 visit[r2] = true; |
| 6959 | 246 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
247 if (w.dist > level) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
248 level = w.dist; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
249 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
250 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
251 else if (j2 == cidx2[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
252 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
253 octave_idx_type r1 = ridx[j1++]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
254 if (! visit[r1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
255 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
256 // the distance of node j is dist(i)+1 |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
257 w.id = r1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
258 w.deg = D[r1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
259 w.dist = v.dist+1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
260 Q_enq (Q, N, qt, w); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
261 visit[r1] = true; |
| 6959 | 262 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
263 if (w.dist > level) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
264 level = w.dist; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
265 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
266 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
267 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
268 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
269 octave_idx_type r1 = ridx[j1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
270 octave_idx_type r2 = ridx2[j2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
271 if (r1 <= r2) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
272 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
273 if (! visit[r1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
274 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
275 w.id = r1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
276 w.deg = D[r1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
277 w.dist = v.dist+1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
278 Q_enq (Q, N, qt, w); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
279 visit[r1] = true; |
| 6959 | 280 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
281 if (w.dist > level) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
282 level = w.dist; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
283 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
284 j1++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
285 if (r1 == r2) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
286 j2++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
287 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
288 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
289 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
290 if (! visit[r2]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
291 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
292 w.id = r2; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
293 w.deg = D[r2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
294 w.dist = v.dist+1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
295 Q_enq (Q, N, qt, w); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
296 visit[r2] = true; |
| 6959 | 297 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
298 if (w.dist > level) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
299 level = w.dist; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
300 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
301 j2++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
302 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
303 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
304 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
305 } // finish of BFS |
| 6959 | 306 |
| 307 if (max_dist < x.dist) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
308 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
309 max_dist = x.dist; |
| 6959 | 310 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
311 for (octave_idx_type i = 0; i < N; i++) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
312 visit[i] = false; |
| 6959 | 313 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
314 visit[x.id] = true; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
315 x.dist = 0; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
316 qt = qh = 0; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
317 Q_enq (Q, N, qt, x); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
318 } |
| 6959 | 319 else |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
320 break; |
| 6959 | 321 } |
| 322 return x.id; | |
| 323 } | |
| 6608 | 324 |
|
18812
9ac2357f19bc
doc: Replace "non-zero" with "nonzero" to match existing usage.
Rik <rik@octave.org>
parents:
18100
diff
changeset
|
325 // Calculates the node's degrees. This means counting the nonzero elements |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
326 // in the symmetric matrix' rows. This works for non-symmetric matrices |
| 6608 | 327 // as well. |
| 6959 | 328 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
329 static octave_idx_type |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
330 calc_degrees (octave_idx_type N, const octave_idx_type *ridx, |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
331 const octave_idx_type *cidx, octave_idx_type *D) |
| 6959 | 332 { |
| 333 octave_idx_type max_deg = 0; | |
| 334 | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
335 for (octave_idx_type i = 0; i < N; i++) |
| 6959 | 336 D[i] = 0; |
| 337 | |
| 338 for (octave_idx_type j = 0; j < N; j++) | |
| 339 { | |
| 340 for (octave_idx_type i = cidx[j]; i < cidx[j+1]; i++) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
341 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
342 OCTAVE_QUIT; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
343 octave_idx_type k = ridx[i]; |
|
18812
9ac2357f19bc
doc: Replace "non-zero" with "nonzero" to match existing usage.
Rik <rik@octave.org>
parents:
18100
diff
changeset
|
344 // there is a nonzero element (k,j) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
345 D[k]++; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
346 if (D[k] > max_deg) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
347 max_deg = D[k]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
348 // if there is no element (j,k) there is one in |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
349 // the symmetric matrix: |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
350 if (k != j) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
351 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
352 bool found = false; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
353 for (octave_idx_type l = cidx[k]; l < cidx[k + 1]; l++) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
354 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
355 OCTAVE_QUIT; |
| 6959 | 356 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
357 if (ridx[l] == j) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
358 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
359 found = true; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
360 break; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
361 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
362 else if (ridx[l] > j) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
363 break; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
364 } |
| 6959 | 365 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
366 if (! found) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
367 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
368 // A(j,k) == 0 |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
369 D[j]++; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
370 if (D[j] > max_deg) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
371 max_deg = D[j]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
372 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
373 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
374 } |
| 6959 | 375 } |
| 376 return max_deg; | |
| 377 } | |
| 6608 | 378 |
| 379 // Transpose of the structure of a square sparse matrix | |
| 6959 | 380 |
| 6608 | 381 static void |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
382 transpose (octave_idx_type N, const octave_idx_type *ridx, |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
383 const octave_idx_type *cidx, octave_idx_type *ridx2, |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
384 octave_idx_type *cidx2) |
| 6959 | 385 { |
| 386 octave_idx_type nz = cidx[N]; | |
| 387 | |
| 388 OCTAVE_LOCAL_BUFFER (octave_idx_type, w, N + 1); | |
| 389 for (octave_idx_type i = 0; i < N; i++) | |
| 390 w[i] = 0; | |
| 391 for (octave_idx_type i = 0; i < nz; i++) | |
| 392 w[ridx[i]]++; | |
| 393 nz = 0; | |
| 394 for (octave_idx_type i = 0; i < N; i++) | |
| 395 { | |
| 396 OCTAVE_QUIT; | |
| 397 cidx2[i] = nz; | |
| 398 nz += w[i]; | |
| 399 w[i] = cidx2[i]; | |
| 400 } | |
| 401 cidx2[N] = nz; | |
| 402 w[N] = nz; | |
| 403 | |
| 404 for (octave_idx_type j = 0; j < N; j++) | |
| 405 for (octave_idx_type k = cidx[j]; k < cidx[j + 1]; k++) | |
| 406 { | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
407 OCTAVE_QUIT; |
|
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14862
diff
changeset
|
408 octave_idx_type q = w[ridx[k]]++; |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
409 ridx2[q] = j; |
| 6959 | 410 } |
| 411 } | |
| 6608 | 412 |
| 413 // An implementation of the Cuthill-McKee algorithm. | |
| 414 DEFUN_DLD (symrcm, args, , | |
|
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
415 "-*- texinfo -*-\n\ |
|
20853
1142cf6abc0d
2015 Code Sprint: remove class of function from docstring for all C++ files.
Rik <rik@octave.org>
parents:
20818
diff
changeset
|
416 @deftypefn {} {@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 | 423 problems. It works for both symmetric and asymmetric @var{S}.\n\ |
| 6608 | 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 | 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 | 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 | 435 Mathematics, ISBN 0-13-165274-5, 1981.\n\ |
| 6608 | 436 \n\ |
| 437 @seealso{colperm, colamd, symamd}\n\ | |
| 438 @end deftypefn") | |
| 439 { | |
|
20818
cef0448a6ed2
eliminate unnecessary uses of nargin
John W. Eaton <jwe@octave.org>
parents:
20790
diff
changeset
|
440 if (args.length () != 1) |
|
20790
c2d9556d51d0
eliminate return statements after calls to print_usage
John W. Eaton <jwe@octave.org>
parents:
20555
diff
changeset
|
441 print_usage (); |
| 6608 | 442 |
| 6959 | 443 octave_value arg = args(0); |
| 6608 | 444 |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
445 // the parameter of the matrix is converted into a sparse matrix |
| 6608 | 446 //(if necessary) |
| 447 octave_idx_type *cidx; | |
| 448 octave_idx_type *ridx; | |
| 449 SparseMatrix Ar; | |
| 450 SparseComplexMatrix Ac; | |
| 451 | |
| 452 if (arg.is_real_type ()) | |
| 453 { | |
| 6959 | 454 Ar = arg.sparse_matrix_value (); |
| 6608 | 455 // Note cidx/ridx are const, so use xridx and xcidx... |
| 456 cidx = Ar.xcidx (); | |
| 457 ridx = Ar.xridx (); | |
| 458 } | |
| 459 else | |
| 460 { | |
| 6959 | 461 Ac = arg.sparse_complex_matrix_value (); |
| 6608 | 462 cidx = Ac.xcidx (); |
| 463 ridx = Ac.xridx (); | |
| 464 } | |
| 465 | |
| 466 octave_idx_type nr = arg.rows (); | |
| 467 octave_idx_type nc = arg.columns (); | |
| 468 | |
| 469 if (nr != nc) | |
|
21110
3d0d84305600
Use err_square_matrix_required more widely.
Rik <rik@octave.org>
parents:
21100
diff
changeset
|
470 err_square_matrix_required ("symrcm", "S"); |
| 6608 | 471 |
| 472 if (nr == 0 && nc == 0) | |
|
20939
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
473 return ovl (NDArray (dim_vector (1, 0))); |
| 6959 | 474 |
| 6608 | 475 // sizes of the heaps |
| 476 octave_idx_type s = 0; | |
| 6959 | 477 |
| 6608 | 478 // 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
|
479 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
|
480 octave_idx_type qh = 0; |
| 6608 | 481 CMK_Node v, w; |
| 482 // dimension of the matrix | |
| 6959 | 483 octave_idx_type N = nr; |
| 484 | |
| 6608 | 485 OCTAVE_LOCAL_BUFFER (octave_idx_type, cidx2, N + 1); |
| 486 OCTAVE_LOCAL_BUFFER (octave_idx_type, ridx2, cidx[N]); | |
| 487 transpose (N, ridx, cidx, ridx2, cidx2); | |
| 488 | |
| 489 // the permutation vector | |
| 490 NDArray P (dim_vector (1, N)); | |
| 491 | |
| 492 // compute the node degrees | |
| 6959 | 493 OCTAVE_LOCAL_BUFFER (octave_idx_type, D, N); |
| 494 octave_idx_type max_deg = calc_degrees (N, ridx, cidx, D); | |
| 6608 | 495 |
| 496 // if none of the nodes has a degree > 0 (a matrix of zeros) | |
| 497 // the return value corresponds to the identity permutation | |
| 498 if (max_deg == 0) | |
| 499 { | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
500 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
|
501 P(i) = i; |
|
20939
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
502 |
|
b17fda023ca6
maint: Use new C++ archetype in more files.
Rik <rik@octave.org>
parents:
20853
diff
changeset
|
503 return ovl (P); |
| 6608 | 504 } |
| 505 | |
| 506 // a heap for the a node's neighbors. The number of neighbors is | |
| 507 // limited by the maximum degree max_deg: | |
| 6959 | 508 OCTAVE_LOCAL_BUFFER (CMK_Node, S, max_deg); |
| 6608 | 509 |
| 510 // a queue for the BFS. The array is always one element larger than | |
| 511 // the number of entries that are stored. | |
| 6959 | 512 OCTAVE_LOCAL_BUFFER (CMK_Node, Q, N+1); |
| 6608 | 513 |
| 514 // a counter (for building the permutation) | |
| 6959 | 515 octave_idx_type c = -1; |
| 6608 | 516 |
| 6959 | 517 // upper bound for the bandwidth (=quality of solution) |
| 6608 | 518 // initialize the bandwidth of the graph with 0. B contains the |
| 519 // the maximum of the theoretical lower limits of the subgraphs | |
| 520 // bandwidths. | |
| 6959 | 521 octave_idx_type B = 0; |
| 6608 | 522 |
| 523 // mark all nodes as unvisited; with the exception of the nodes | |
| 524 // 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
|
525 |
| 6608 | 526 boolNDArray btmp (dim_vector (1, N), false); |
| 527 bool *visit = btmp.fortran_vec (); | |
| 528 | |
| 529 do | |
| 530 { | |
| 531 // locate an unvisited starting node of the graph | |
| 6959 | 532 octave_idx_type i; |
| 6608 | 533 for (i = 0; i < N; i++) |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
534 if (! visit[i]) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
535 break; |
| 6608 | 536 |
| 537 // locate a probably better starting node | |
| 538 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
|
539 |
| 6608 | 540 // mark the node as visited and enqueue it (a starting node |
| 541 // for the BFS). Since the node will be a root of a spanning | |
| 542 // tree, its dist is 0. | |
| 543 v.deg = D[v.id]; | |
| 544 v.dist = 0; | |
| 545 visit[v.id] = true; | |
| 6959 | 546 Q_enq (Q, N, qt, v); |
| 6608 | 547 |
| 6959 | 548 // lower bound for the bandwidth of a subgraph |
| 6608 | 549 // keep a "level" in the spanning tree (= min. distance to the |
| 550 // root) for determining the bandwidth of the computed | |
| 551 // permutation P | |
| 6959 | 552 octave_idx_type Bsub = 0; |
| 6608 | 553 // min. dist. to the root is 0 |
| 6959 | 554 octave_idx_type level = 0; |
| 6608 | 555 // the root is the first/only node on level 0 |
| 6959 | 556 octave_idx_type level_N = 1; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
557 |
| 6677 | 558 while (! Q_empty (Q, N, qh, qt)) |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
559 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
560 v = Q_deq (Q, N, qh); |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
561 i = v.id; |
| 6608 | 562 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
563 c++; |
| 6608 | 564 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
565 // for computing the inverse permutation P where |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
566 // 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
|
567 // P(i) = c; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
568 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
569 // for computing permutation P where |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
570 // 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
|
571 P(c) = i; |
| 6608 | 572 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
573 // 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
|
574 s = 0; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
575 octave_idx_type j1 = cidx[i]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
576 octave_idx_type j2 = cidx2[i]; |
| 6608 | 577 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
578 OCTAVE_QUIT; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
579 while (j1 < cidx[i+1] || j2 < cidx2[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
580 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
581 OCTAVE_QUIT; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
582 if (j1 == cidx[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
583 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
584 octave_idx_type r2 = ridx2[j2++]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
585 if (! visit[r2]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
586 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
587 // the distance of node j is dist(i)+1 |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
588 w.id = r2; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
589 w.deg = D[r2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
590 w.dist = v.dist+1; |
|
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
591 H_insert (S, s, w); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
592 visit[r2] = true; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
593 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
594 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
595 else if (j2 == cidx2[i+1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
596 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
597 octave_idx_type r1 = ridx[j1++]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
598 if (! visit[r1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
599 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
600 w.id = r1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
601 w.deg = D[r1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
602 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
|
603 H_insert (S, s, w); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
604 visit[r1] = true; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
605 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
606 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
607 else |
|
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 octave_idx_type r1 = ridx[j1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
610 octave_idx_type r2 = ridx2[j2]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
611 if (r1 <= r2) |
|
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 if (! visit[r1]) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
614 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
615 w.id = r1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
616 w.deg = D[r1]; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
617 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
|
618 H_insert (S, s, w); |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
619 visit[r1] = true; |
|
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 j1++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
622 if (r1 == r2) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
623 j2++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
624 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
625 else |
|
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[r2]) |
|
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 = r2; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
630 w.deg = D[r2]; |
|
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[r2] = 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 j2++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
636 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
637 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
638 } |
| 6608 | 639 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
640 // 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
|
641 while (! H_empty (S, s)) |
|
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 OCTAVE_QUIT; |
| 6608 | 644 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
645 // 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
|
646 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
|
647 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
648 // entered the BFS a new level? |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
649 if (v.dist > level) |
|
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 // adjustment of bandwith: |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
652 // "[...] the minimum bandwidth that |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
653 // can be obtained [...] is the |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
654 // maximum number of nodes per level" |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
655 if (Bsub < level_N) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
656 Bsub = level_N; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
657 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
658 level = v.dist; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
659 // v is the first node on the new level |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
660 level_N = 1; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
661 } |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
662 else |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
663 { |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
664 // there is no new level but another node on |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
665 // this level: |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
666 level_N++; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
667 } |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
668 |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
669 // enqueue v in O(1) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
670 Q_enq (Q, N, qt, v); |
|
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 // synchronize the bandwidth with level_N once again: |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
674 if (Bsub < level_N) |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
675 Bsub = level_N; |
|
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
676 } |
| 6608 | 677 // finish of BFS. If there are still unvisited nodes in the graph |
| 678 // then it is split into CCs. The computed bandwidth is the maximum | |
| 679 // of all subgraphs. Update: | |
| 680 if (Bsub > B) | |
|
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9066
diff
changeset
|
681 B = Bsub; |
| 6608 | 682 } |
| 683 // are there any nodes left? | |
| 684 while (c+1 < N); | |
| 685 | |
| 686 // compute the reverse-ordering | |
| 687 s = N / 2 - 1; | |
| 6959 | 688 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
|
689 std::swap (P.elem (i), P.elem (j)); |
| 6608 | 690 |
| 691 // 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
|
692 return ovl (P+1); |
| 6608 | 693 } |