rcm.h File Reference

---

Detailed Description

Version 0.9.1. September 24, 2005.

How to use the reverse Cuthill-McKee package

The main routine to call is genrcmi() (or genrcml() if you use long integers to store your graph information). The way genrcmi()/genrcml() works can be adjusted by setting the flags parameter. In most cases the `default' behavior will be just fine and the caller just sets flags to 0. Specific flags can be set by using the constants defined in rcm.h. Multiple flags are combined by binary or (the `|' operator in C).
The undirected graph genrcmi() should work on is passed in the form of the three parameters n, xadj and adj. The graph is expected to be stored in a compressed format similar to the compressed sparse row/column formats for matrices.
The main outputs is the new ordering of the nodes, to which the graph should be permuted. Notice that the output is only this new ordering. The graph, as passed in xadj and adj, is not modified by genrcmi(). The new ordering is stored in the caller-provided vector perm, i.e., perm[p] is the node to become node p after the permutation is actually applied to the graph.
Additionally two working arrays (mask and deg) are needed.

On default, genrcmi()/genrcml() expects indices to be zero based (as in C) and not one based (as in Fortran). This applies to xadj, adj and mask on input (to mask on input only if the RCM_USE_MASK flag is set) and to perm, mask and deg on ouput. If your data is one based (like in Fortran), set the RCM_FORTRAN_INDICES flag.

Further details can be found at the documentation for genrcmi().

Callable subroutines

Additionally to genrcmi()/genrcml(), two subroutines are declared non-static, i.e., can be used from outside of rcm.c. For more details we refer to the linked detail documentation of these functions. fnrooti() finds a pseudo-peripheral node (starting at any given node in the component) and rcmi() finds the RCM ordering, based on a given root for the rooted level set structure.

Definition in file rcm.h.

Go to the source code of this file.

Defines
#define	RCM_FORTRAN_INDICES   1
	Use Fortran style array indices. The default is to use C style (zero based) indices.
#define	RCM_C_INDICES   2
	Use C style array indices. This is the default setting.
#define	RCM_NO_SORT   4
	Do not use any sorting in the Cuthill-McKee algorithm. The default is to sort the nodes newly added to a level set from the same adjacency list by non-decreasing degree.
#define	RCM_INSERTION_SORT   8
	Use linear insertion sort instead of heapsort.
#define	RCM_NO_REVERSE   16
	Compute just a Cuthill-McKee ordering and skip the reversal.
#define	RCM_USE_MASK   32
	Use the values found in the mask arrays to filter vertices of the graph. Work only on nodes with a non-zero mask value.
#define	RCM_PREFIX
	Common prefix to be used for all functions declared in rcm.h, defaults to an empty definition (i.e., no prefix).
Functions
void	genrcmi (const int n, const int flags, const int *xadj, const int *adj, int *perm, signed char *mask, int *deg)
	Find the reverse Cuthill-McKee ordering for the graph provided in xadj and adj.
void	genrcml (const long n, const int flags, const long *xadj, const long *adj, long *perm, signed char *mask, long *deg)
	Version of genrcmi() for long data.
void	fnrooti (int *root, const int flags, const int *xadj, const int *adj, const int *deg, int *ccsize, signed char *mask, int *ls)
	Find a pseudo-peripheral node for the subgraph specified by root.
void	fnrootl (long *root, const int flags, const long *xadj, const long *adj, const long *deg, long *ccsize, signed char *mask, long *ls)
	Version of fnrooti() for long data.
void	rcmi (const int root, const int flags, const int *xadj, const int *adj, const int *deg, signed char *mask, int *perm, int *ccsize)
	Find a reverse Cuthill-McKee ordering of the connected component specified by root.
void	rcml (const long root, const int flags, const long *xadj, const long *adj, const long *deg, signed char *mask, long *perm, long *ccsize)
	Version of rcmi() for long data.

---

Define Documentation

#define RCM_FORTRAN_INDICES   1

Fortran and C/C++ use different array indexing. In Fortran indices are based on one, in C on zero. This means the first element in an array has index 1 in Fortran and index 0 in C. If the RCM_FORTRAN_INDICES flag is selected, an index 1 is interpreted to point to the first element of an array. Remarks: Internally all indices are zero based, as it is natural for a C program. RCM_FORTRAN_INDICES covers only input/output data. The use of pointer arithmetic (following the way f2c converts arrays from Fortran to C) allows the use of Fortran style indices without any slow down. Definition at line 101 of file rcm.h. Referenced by DEGREE(), FNROOT(), GENRCM(), GENRCM2(), RCM(), and ROOTLS().

#define RCM_C_INDICES   2

Using C style array indices is the default and there is no need to specify it. Of the two indexing related flags (RCM_FORTRAN_INDICES and RCM_C_INDICES), RCM_FORTRAN_INDICES takes the precedence, i.e. if both flags are set, Fortran style indices are used and no warning or error message is produced. The main purpose of RCM_C_INDICES is to help writing a Fortran interface. In a Fortran interface, using Fortran style indices would be the default and RCM_C_INDICES could be used to select C indices instead. See also: RCM_FORTRAN_INDICES Definition at line 121 of file rcm.h. Referenced by GENRCM2().

#define RCM_NO_SORT   4

In the Cuthill-McKee algorithm we construct a level set by scanning through the previous one. Adjacent nodes not yet used in this or any prior level set are added to the new one. The nodes added from the same level set are ordered by their degree. This sorting is suppressed if the RCM_NO_SORT flag is set. Definition at line 136 of file rcm.h. Referenced by RCM().

#define RCM_INSERTION_SORT   8

Changing the sorting routine does not only change the execution time, but can also change the permutation found. This is due to the fact that heapsort is not stable, i.e. nodes with the same degree may be exchanged by heapsort. On the other hand insertion sort kepp such nodes in their original order. Heapsort was choosen as the default sorting algorithm because it is much faster in the worst case and there are also real word examples showing a significant improvement in execution time over insertion sort. Finding a (symmetric) RCM ordering of the Stanford Web Matrix is more than 15 times faster if heapsort is used instead of insertion sort. The SPARSPAK implementation of RCM uses linear insertion sort and hence the RCM_INSERTION_FLAG can be used to get the exact same permutation SPARSPAK would find. This is mostly useful for the purpose of testing and comparison. Definition at line 163 of file rcm.h. Referenced by RCM().

#define RCM_PREFIX

Common prefix to be used for all functions declared in rcm.h. RCM_PREFIX is only defined if it is not defined before. A previous definition is left untouched. The default definition of RCM_PREFIX is empty, i.e., no prefix is attached to function names. This coincides with the behavior of rcm.c. The same definition for RCM_PREFIX must be used for rcm.h and rcm.c. Definition at line 195 of file rcm.h.

---

Function Documentation

void genrcmi (  const int  n, const int  flags, const int *  xadj, const int *  adj, int *  perm, signed char *  mask, int *  deg )

Find the reverse Cuthill-McKee ordering for the graph provided in xadj and adj. For each component of the graph fnrooti() finds a pseudo-peripheral node p. Then rcmi() generates the reverse Cuthill-McKee ordering for this blocked, using p as the root. Parameters: [in]  n  is the number of nodes/vertices in the graph. [in]  flags  are used to select variations of the way RCM works. Use 0 if no flag should be set. Otherwise use the bitwise OR of one or more of the supported flags: RCM_FORTRAN_INDICES, RCM_C_INDICES, RCM_NO_SORT, RCM_INSERTION_SORT, RCM_NO_REVERSE and RCM_USE_MASK. [in]  xadj  Pointers (indices) into adj. xadj[p] points to the start of the adjacency list for p. xadj[p+1]-1 points to the last element in the adjacency list for p. If the graph has n nodes, then xadj has to have n+1 entries. [in]  adj  The adjacency lists. The lists are stored in strictly increasing order without gaps. An entry in xadj is the index of the first entry in the associated adjacency list stored in adj. Hence the elements adjacent to node p are stored in adj in the block pointed to by xadj[p] (low-end, included) and xadj[p+1] (high-end, excluded). [in,out]  mask  The nodes numbered by RCM will have their mask values set to -1. The mask array is used to mark nodes already consumed by RCM. On output all nodes are consumed, i.e., all entries have been set to -1. If the flag RCM_USE_MASK is set, a slightly different algorithm is used. In this case a mask[p] value strictly greater than zero is used to indicate that the node p is not to be considered part of the graph. Notice that the algorithm is slightly slower, if the RCM_USE_MASK flag is set. [out]  perm  is used to store the reverse Cuthill-McKee ordering of the nodes in the graph. [out]  deg  Storage used for the degrees of the nodes in the graph. On output deg[p] will contain the degree of node p.

void fnrooti (  int *  root, const int  flags, const int *  xadj, const int *  adj, const int *  deg, int *  ccsize, signed char *  mask, int *  ls )

Find a pseudo-peripheral node for the subgraph specified by root. Parameters: [in]  flags  are used to select variations of the way RCM works. Use 0 if no flag should be set. Otherwise use the bitwise OR of one or more RCM_* flags. fnrooti() supports the RCM_FORTRAN_INDICES flag. [in]  xadj  Pointers to the adjacency lists in adj. See the xadj parameter of genrcmi() for more details. [in]  adj  The adjacency lists. See the adj parameter of genrcmi() for more details. [in]  deg  The degrees of the nodes in the graph. [in,out]  root  On input the starting node for the search and representant of the connected component in which we look for a pseudo-peripheral node. On onput, it is the node found. [in]  mask  Used to keep track of found nodes in the traversal of the graph component. Nodes marked by having a non-zero mask value on input are considered to be removed from the graph. Although mask is modified during the running of fnroot, on output the values in mask will be the same as on input. [out]  ccsize  The size of the component rooted by root. ls Temporary storage used internally. See also: N. E. Gibbs, W. G. Poole, and P. K. Stockemeyer. An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM Journal of Numerical Analysis, 13(2):236-250, April 1976. Alan George and Joseph W. H. Liu. An implementation of a pseudoperipheral node finder. ACM Trans. Math. Softw., 5(3):284-295, 1979.

void rcmi (  const int  root, const int  flags, const int *  xadj, const int *  adj, const int *  deg, signed char *  mask, int *  perm, int *  ccsize )

Find a reverse Cuthill-McKee ordering of the connected component specified by root. The numbering process is to be started at the node root. Parameters: [in]  root  is the root node of the connected component and the starting node of the RCM ordering. [in]  flags  changes the way the function works. Use the value 0 to not set any flag. Multiple flags can be combined by using binary OR. The following flags are supported: RCM_FORTRAN_INDICES, RCM_NO_REVERSE, RCM_NO_SORT, RCM_INSERTION_SORT and RCM_USE_MASK. Other RCM_* flags are silently ignored. [in]  xadj  Pointers to the adjacency lists in adj. See the xadj parameter of genrcmi() for more details. [in]  adj  The adjacency lists. See the adj parameter of genrcmi() for more details. [in]  deg  An array of the node degrees. The array has to be filled by the caller, deg[p] is used for the degree of node p. No further checking is done. [in,out]  mask  The nodes numbered by RCM will have their mask values set to -1. The mask array is used to mark nodes in the component already consumed by RCM. Therefore on function entry mask[p] must be 0 for all nodes p in the same component as root. It is the responsibility of the caller to ensure this. If the flag RCM_USE_MASK is set, a slightly different algorithm is used. In this case a mask[p] value strictly greater than zero is used to indicate that the node p is not to be considered part of the graph. Notice that the degree of a node changes when a part of the graph is masked out. As the degrees (stored in deg) are supplied by the caller, the caller is responsible for setting the entries of deg correctly. [out]  perm  is used to store the reverse Cuthill-McKee ordering of the nodes in the component rooted by root. Only the first ccsize entries of perm are overwritten. [out]  ccsize  The size of the component found.

---