TET_MESH_RCM
Reverse Cuthill-McKee Node Reordering
TET_MESH_RCM
is a C++ program which
computes the reverse
Cuthill-McKee reordering for nodes in a tetrahedral mesh ("tet mesh").
The user supplies a node file and a tetrahedron file, containing
the coordinates of the nodes, and the indices of the nodes that
make up each tetrahedron. Either 4-node or 10-node tetrahedrons may
be used.
The program reads the data, computes the adjacency information,
carries out the RCM algorithm to get the permutation, applies
the permutation to the nodes and tetrahedrons, and writes out
new node and tetrahedron files that correspond to the RCM permutation.
Note that the node file would normally contain exactly 3 values
on each line, namely the X, Y and Z coordinates of the nodes.
However, this is not necessary. Extra information can be
included on each line, for instance, a "W" coordinate. Each
line should include the same number of items, but all will be
permuted correctly together. The program does not actually
need to know the coordinates of the nodes, so in fact, ANY data
(as long as it is real numeric data) associated with the nodes
can be listed in the node file, and will be correctly permuted.
Usage:
tet_mesh_rcm prefix
where prefix is the common file prefix:
-
prefix_nodes.txt, the node coordinates (input);
-
prefix_elements.txt, the element definitions (input).
-
prefix_rcm_nodes.txt, the reordered node coordinates (output);
-
prefix_rcm_elements.txt, the reordered element definitions (output).
The element definition file will list node indices. In C++, it may be
more natural to use 0-based indices. This program will accept an element
definition file that is 0-based or 1-based, and will convert a 1-based
input file so that it becomes 0-based internal to the program. The detection
of 1-based data is determined by the absence of the use of a 0 index, and
the use of an index equal to the number of nodes. This is an implicit
and fallible, but reasonable, way to handle this problem.
Licensing:
The computer code and data files made available on this web page
are distributed under
the GNU LGPL license.
Languages:
TET_MESH_RCM is available in
a C++ version and
a FORTRAN90 version and
a MATLAB version.
Related Data and Programs:
CVT_TET_MESH,
a FORTRAN90 program which
uses CVT techniques to compute a tet mesh in a region.
MESH_BANDWIDTH,
a C++ program which
returns the geometric bandwidth associated with a mesh of
elements of any order and in a space of arbitrary dimension.
QUAD_MESH_RCM,
a C++ program which
computes the reverse Cuthill-McKee (RCM) reordering for nodes in a mesh of 4-node
quadrilaterals.
RCM,
a C++ library which
carries out reverse Cuthill-McKee computations.
TABLE_TET_MESH,
a FORTRAN90 program which
can compute a tet mesh of a given set of points.
TEST_TET_MESH,
a FORTRAN90 library which
defines regions for which a tet mesh is desired.
TET_MESH,
a C++ library which
works with tet meshes.
TET_MESH_BOUNDARY,
a C++ program which
returns the nodes and faces of the boundary of a tetrahedral mesh,
which themselves form a 3D triangular mesh or "TRI_SURFACE".
TET_MESH_DISPLAY,
a MATLAB program which
can read in the node and tetra files defining a tet mesh and display a wireframe
image.
TET_MESH_DISPLAY_OPENGL,
a C++ program which
reads a tet mesh and displays the nodes and edges using OpenGL.
TET_MESH_L2Q,
a C++ program which
converts a linear to quadratic tet mesh.
TET_MESH_ORDER4,
a directory which
contains a description and examples of a tet mesh using order 4 elements.
TET_MESH_ORDER10,
a directory which
contains a description and examples of a tet mesh using order 10 elements.
TET_MESH_Q2L,
a C++ program which
converts a quadratic (10-node) to linear (4-node) tetrahedral mesh.
TET_MESH_QUALITY,
a C++ program which
computes the quality of a tetrahedral mesh.
TET_MESH_REFINE,
a C++ program which
can refine a tet mesh.
TET_MESH_TET_NEIGHBORS,
a C++ program which
computes the tetrahedron-to-tetrahedron
adjacency information.
TET_MESH_VOLUMES,
a C++ program which
computes the volume of each tetrahedron in a tet mesh;
TRIANGULATION_RCM,
a C++ program which
applies the reverse Cuthill-McKee reordering to a triangulation of 2D data.
Reference:
-
HL Crane, Norman Gibbs, William Poole, Paul Stockmeyer,
Algorithm 508:
Matrix Bandwidth and Profile Reduction,
ACM Transactions on Mathematical Software,
Volume 2, Number 4, December 1976, pages 375-377.
-
Herbert Edelsbrunner,
Geometry and Topology for Mesh Generation,
Cambridge, 2001,
ISBN: 0-521-79309-2,
LC: QA377.E36.
-
Alan George, Joseph Liu,
Computer Solution of Large Sparse Positive Definite Matrices,
Prentice Hall, 1981,
ISBN: 0131652745,
LC: QA188.G46
-
Norman Gibbs,
Algorithm 509:
A Hybrid Profile Reduction Algorithm,
ACM Transactions on Mathematical Software,
Volume 2, Number 4, December 1976, pages 378-387.
-
Norman Gibbs, William Poole, Paul Stockmeyer,
An Algorithm for Reducing the Bandwidth
and Profile of a Sparse Matrix,
SIAM Journal on Numerical Analysis,
Volume 13, Number 2, April 1976, pages 236-250.
-
Barry Joe,
GEOMPACK - a software package for the generation of meshes
using geometric algorithms,
Advances in Engineering Software,
Volume 13, 1991, pages 325-331.
-
Per-Olof Persson, Gilbert Strang,
A Simple Mesh Generator in MATLAB,
SIAM Review,
Volume 46, Number 2, June 2004, pages 329-345.
Source Code:
Examples and Tests:
CUBE4 is an order 4 tet mesh of a cube:
List of Routines:
-
MAIN is the main program for TET_MESH_RCM.
-
ADJ_BANDWIDTH computes the bandwidth of an adjacency matrix.
-
ADJ_PERM_BANDWIDTH computes the bandwidth of a permuted adjacency matrix.
-
ADJ_PRINT prints adjacency information.
-
ADJ_PRINT_SOME prints some adjacency information.
-
CH_CAP capitalizes a single character.
-
CH_EQI is true if two characters are equal, disregarding case.
-
CH_TO_DIGIT returns the integer value of a base 10 digit.
-
DEGREE computes the degrees of the nodes in the connected component.
-
FILE_COLUMN_COUNT counts the columns in the first line of a file.
-
FILE_EXIST reports whether a file exists.
-
FILE_ROW_COUNT counts the number of row records in a file.
-
GENRCM finds the reverse Cuthill-Mckee ordering for a general graph.
-
I4_MAX returns the maximum of two I4's.
-
I4_MIN returns the minimum of two I4's.
-
I4_SWAP switches two I4's.
-
I4COL_COMPARE compares columns I and J of an I4COL.
-
I4COL_SORT_A ascending sorts the columns of an I4COL.
-
I4COL_SORT2_A ascending sorts the elements of each column of an I4COL.
-
I4COL_SORTED_UNIQUE_COUNT counts unique elements in an I4COL.
-
I4COL_SWAP swaps two columns of an I4COL.
-
I4MAT_DATA_READ reads data from an I4MAT file.
-
I4MAT_HEADER_READ reads the header from an I4MAT file.
-
I4MAT_TRANSPOSE_PRINT_SOME prints some of an I4MAT, transposed.
-
I4MAT_WRITE writes an I4MAT file with no header.
-
I4VEC_PRINT prints an I4VEC.
-
I4VEC_REVERSE reverses the elements of an I4VEC.
-
LEVEL_SET generates the connected level structure rooted at a given node.
-
PERM_CHECK checks that a vector represents a permutation.
-
PERM_INVERSE3 produces the inverse of a given permutation.
-
R8COL_PERMUTE permutes an R8COL in place.
-
R8MAT_DATA_READ reads the data from an R8MAT file.
-
R8MAT_HEADER_READ reads the header from an R8MAT file.
-
R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
-
R8MAT_WRITE writes an R8MAT file with no header.
-
RCM renumbers a connected component by the reverse Cuthill McKee algorithm.
-
ROOT_FIND finds a pseudo-peripheral node.
-
S_LEN_TRIM returns the length of a string to the last nonblank.
-
S_TO_I4 reads an I4 from a string.
-
S_TO_I4VEC reads an I4VEC from a string.
-
S_TO_R8 reads an R8 from a string.
-
S_TO_R8VEC reads an R8VEC from a string.
-
S_WORD_COUNT counts the number of "words" in a string.
-
SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
-
TET_MESH_BASE_ZERO ensures that the element definition is zero-based.
-
TET_MESH_ORDER4_ADJ_COUNT counts the number of nodal adjacencies.
-
TET_MESH_ORDER4_ADJ_SET sets the nodal adjacency matrix.
-
TET_MESH_ORDER10_ADJ_COUNT counts the number of nodal adjacencies.
-
TET_MESH_ORDER10_ADJ_SET sets the nodal adjacency matrix.
-
TIMESTAMP prints the current YMDHMS date as a time stamp.
You can go up one level to
the C++ source codes.
Last revised on 08 March 2013.