#include	"BSprivate.h"

/*+ BSfnd_inode - Find and number the identical nodes (i-nodes)

    Input Parameters:
.   A - The sparse matrix
.   max_inode_size - the limit on the number of nodes in an i-node
.   procinfo - the usual processor info

    Returns:
    a numbering of the nodes in which if two nodes have the same
    number, then they are in the same i-node

    Notes:
    This only finds i-nodes local to a processor

+*/
BSnumbering	*BSfnd_inode(BSspmat *A, int max_inode_size, BSprocinfo *procinfo)
{
	int	n;
	BSsprow	**rows;
	BSnumbering	*numbering;
	int	*used;
	int	i, j, k;
	int	cur_num, cur_size;
	BSsprow *cur_row;
	BSsprow *neighbor_row;
	int	neighbor;
	int	same;

	n = A->num_rows;
	rows = A->rows;
	numbering = BSalloc_numbering(n); CHKERRN(0);

	if (procinfo->single) {
		for	(i=0;i<n;i++) numbering->numbers[i] = i;
		return(numbering);
	}

	MY_MALLOCN(used,(int *),sizeof(int)*n,1);
	for	(i=0;i<n;i++) used[i] = FALSE;

	cur_num = 0;

	/* go over every node in my partition */
	for	(i=0;i<n;i++) {
		/* if node is already numbered then skip it */
		if (used[i]) continue;

		/* examine nodes that this node is connected to 
		   to check if that node is identical, do not examine
		   nodes that are not in my partition
		*/
		numbering->numbers[i] = cur_num;
		used[i] = TRUE;
		cur_row = rows[i];
		cur_size = 1;
		for (j=0;j<cur_row->length;j++) {
			/* don't look at myself */
			if (j == cur_row->diag_ind) continue;
			/* if inode is too big, then stop checking */
			if (cur_size >= max_inode_size) break;
			/* if neighbor is in my partition */
			(*A->map->fglobal2local)(1,&(cur_row->col[j]),
				&neighbor,procinfo,A->map); CHKERRN(0);

			if (neighbor >= 0) {
				/* continue if the neighbor is already numbered */
				if (used[neighbor]) continue;

				neighbor_row = rows[neighbor];
				/* if neighbor has same number of nz */
				if (neighbor_row->length == cur_row->length) {
					/* check if the rows are the same */
					same = TRUE;
					for (k=0;k<cur_row->length;k++) {
						if (neighbor_row->col[k] != cur_row->col[k]) {
							same = FALSE;
							break;
						}
					}
					if (same) {
						numbering->numbers[neighbor] = cur_num;
						used[neighbor] = TRUE;
						cur_size++;
					}
				}
			}
		}
		cur_num++;
	}

	MY_FREEN(used);

	return(numbering);
}