#include	"BSprivate.h"

/*+ BSfnd_clique - Find and number the cliques

    Input Parameters:
.   A - The sparse matrix
.   size_limit - the limit on the number of rows in the clique
.   weight - the weight (in rows) of each node in the graph
.   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 clique

    Notes:
    This only finds cliques local to a processor

+*/
BSnumbering	*BSfnd_clique(BSspmat *A, int size_limit, int *weight,
				BSprocinfo *procinfo)
{
	int	n;
	BSsprow	**rows;
	BSnumbering	*numbering;
	int	*used;
	int	i, j, k, l;
	int	cur_num;
	BSsprow *cur_row;
	BSsprow *neighbor_row;
	int	neighbor;
	int	connected, found;
	int	*list, list_len;
	int	cur_weight;

	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];
		MY_MALLOCN(list,(int *),sizeof(int)*cur_row->length,2+i);
		list_len = 0;
		cur_weight = weight[i];
		for (j=0;j<cur_row->length;j++) {
			/* don't look at myself */
			if (j == cur_row->diag_ind) continue;
			/* if over my limit, then stop looking */
			if (cur_weight >= size_limit) 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 is connected to everyone in current clique */
				connected = TRUE;
				for (k=0;k<list_len;k++) {
					found = FALSE;
					for (l=0;l<neighbor_row->length;l++) {
						if (list[k] == neighbor_row->col[l]) {
							found = TRUE;
							break;
						}
					}
					if (!found) {
						connected = FALSE;
						break;
					}
				}
				if ((connected) && 
					((cur_weight + weight[neighbor]) <= size_limit)) {
					cur_weight += weight[neighbor];
					list[list_len] = cur_row->col[j];
					list_len++;
					numbering->numbers[neighbor] = cur_num;
					used[neighbor] = TRUE;
				}
			}
		}
		MY_FREEN(list);
		cur_num++;
	}

	MY_FREEN(used);
	return(numbering);
}