The R Project SVN R-packages

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
769 bates 1 
#include <Rdefines.h>
1820 bates 2 
#include "Metis/metis.h"
155 bates 3 
#include "Metis_utils.h"
4 
 
1381 bates 5 
 
6 
 
7 
/**
8 
 * Establish a fill-reducing permutation for the sparse symmetric
9 
 * matrix of order n represented by the column pointers Tp and row
10 
 * indices Ti.
11 
 *
12 
 * @param n  order of the sparse symmetric matrix
13 
 * @param Tp  column pointers (total length n + 1)
14 
 * @param Ti  row indices (total length Tp[n])
15 
 * @param Perm array of length n to hold the permutation
16 
 * @param iPerm array of length n to hold the inverse permutation
17 
 *
18 
 */
218 bates 19 
void ssc_metis_order(int n, const int Tp [], const int Ti [],
301 bates 20 
		     int Perm[], int iPerm[])
155 bates 21 
{
218 bates 22 
    int  j, num_flag = 0, options_flag = 0;
299 bates 23 
    idxtype
302 bates 24 
	*perm = Calloc(n, idxtype), /* in case idxtype != int */
25 
	*iperm = Calloc(n, idxtype),
299 bates 26 
	*xadj = Calloc(n+1, idxtype),
303 bates 27 
	*adj = Calloc(2 * (Tp[n] - n), idxtype);
155 bates 28 
 
1381 bates 29 
				/* check row indices for correct range */
30 
    for (j = 0; j < Tp[n]; j++)
31 
      if (Ti[j] < 0 || Ti[j] >= n)
32 
	error(_("row index Ti[%d] = %d is out of range [0,%d]"),
33 
	      j, Ti[j], n - 1);
155 bates 34 
				/* temporarily use perm to store lengths */
1381 bates 35 
    AZERO(perm, n);
155 bates 36 
    for (j = 0; j < n; j++) {
218 bates 37 
	int ip, p2 = Tp[j+1];
38 
	for (ip = Tp[j]; ip < p2; ip++) {
39 
	    int i = Ti[ip];
155 bates 40 
	    if (i != j) {
41 
		perm[i]++;
42 
		perm[j]++;
43 
	    }
44 
	}
45 
    }
46 
    xadj[0] = 0;
47 
    for (j = 0; j < n; j++) xadj[j+1] = xadj[j] + perm[j];
48 
				/* temporarily use perm to store pointers */
218 bates 49 
    Memcpy(perm, xadj, n);
155 bates 50 
    for (j = 0; j < n; j++) {
218 bates 51 
	int ip, p2 = Tp[j+1];
52 
	for (ip = Tp[j]; ip < p2; ip++) {
53 
	    int i = Ti[ip];
155 bates 54 
	    if (i != j) {
55 
		adj[perm[i]] = j;
56 
		adj[perm[j]] = i;
57 
		perm[i]++;
58 
		perm[j]++;
59 
	    }
60 
	}
61 
    }
62 
    METIS_NodeND(&n, xadj, adj, &num_flag, &options_flag, perm, iperm);
301 bates 63 
    for (j = 0; j < n; j++) {
303 bates 64 
	Perm[j] = (int) perm[j];
65 
	iPerm[j] = (int) iperm[j];
299 bates 66 
    }
301 bates 67 
    Free(iperm); Free(perm); Free(xadj); Free(adj);
299 bates 68 
}