QUAD_MESH_RCM
Reverse Cuthill-McKee Node Reordering

QUAD_MESH_RCM is a C++ program which computes the reverse Cuthill-McKee (RCM) reordering for nodes in a mesh of 4-node quadrilaterals.

The user supplies a node file and an element file, containing the coordinates of the nodes, and the indices of the nodes that make up each element.

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 elements, and writes out new node and element files that correspond to the RCM permutation.

(Note that, internally, the program has to convert some data from 0-based to 1-based indexing in order to work with the RCM codes. Aside from some inelegant coding, the user should not notice any effects of this temporary adjustment.)

Usage:

quad_mesh_rcm 'prefix'

• 'prefix'_nodes.txt, the node coordinates;
• 'prefix'_elements.txt, the element definitions.
• 'prefix'_rcm_nodes.txt, the reordered node coordinates;
• 'prefix'_rcm_elements.txt, the reordered element definitions.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

QUAD_MESH_RCM is available in a C++ version and a FORTRAN version and a MATLAB version.

Related Data and Programs:

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.

MESH_DISPLAY, a MATLAB program which reads data defining a polygonal mesh and displays it, with optional numbering.

MESH_DISPLAY_OPENGL, a C++ program which reads files defining a polygonal mesh and displays an image using OpenGL.

QUAD_MESH, a data directory which defines a format for storing meshes of quadrilaterals over a 2D region.

QUAD_MESH, a C++ library which handles meshes of quadrilaterals over a 2D region;

RCM, a C++ library which carries out reverse Cuthill-McKee computations.

TET_MESH_RCM, a C++ program which applies the reverse Cuthill-McKee reordering to a tetrahedral mesh of nodes in 3D.

TRIANGULATION_RCM, a C++ program which reads files describing a triangulation of nodes in 2D, and applies the RCM algorithm to produce a renumbering of the triangulation with a reduced bandwidth.

Reference:

1. 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.
2. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0.
3. Alan George, Joseph Liu,
   Computer Solution of Large Sparse Positive Definite Matrices,
   Prentice Hall, 1981,
   ISBN: 0131652745,
   LC: QA188.G46
4. Norman Gibbs,
   Algorithm 509: A Hybrid Profile Reduction Algorithm,
   ACM Transactions on Mathematical Software,
   Volume 2, Number 4, December 1976, pages 378-387.
5. 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, 1976, pages 236-250.
6. Joseph ORourke,
   Computational Geometry,
   Second Edition,
   Cambridge, 1998,
   ISBN: 0521649765,
   LC: QA448.D38.

Source Code:

• quad_mesh_rcm.cpp, the source code.

Examples and Tests:

HOLE works with region of equal-sized squares, with some irregularities.

• hole_output.txt, the printed output from the command
  "quad_mesh_rcm ( 'hole' )"
• hole_nodes.txt, the node file.
• hole_elements.txt, the element file.
• hole_rcm_nodes.txt, the RCM reordered node file.
• hole_rcm_elements.txt, the RCM reordered element file.
• hole.png, an image of the mesh.

List of Routines:

• MAIN is the main program for QUAD_MESH_RCM.
• ADJ_BANDWIDTH computes the bandwidth of an adjacency matrix.
• ADJ_PERM_BANDWIDTH computes the bandwidth of a permuted adjacency matrix.
• ADJ_SET_Q4_MESH sets adjacencies in a triangulation.
• ADJ_SIZE_Q4_MESH counts adjacencies in a Q4 mesh.
• 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_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_MODP returns the nonnegative remainder of integer division.
• I4_SWAP switches two I4's.
• I4_WRAP forces an I4 to lie between given limits by wrapping.
• I4COL_COMPARE compares columns I and J of an I4COL.
• I4COL_SORT_A ascending sorts the columns of 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_HEAP_D reorders an array of integers into a descending heap.
• I4VEC_PRINT prints an I4VEC.
• I4VEC_REVERSE reverses the elements of an integer vector.
• I4VEC_SORT_HEAP_A ascending sorts an array of integers using heap sort.
• LEVEL_SET generates the connected level structure rooted at a given node.
• MESH_BASE_ZERO ensures that the element definition is zero-based.
• NEIGHBOR_ELEMENTS_Q4_MESH determines element neighbors in a Q4 mesh.
• 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.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.