BlockSolve95/src/BSsdo_color.c

#include "BSprivate.h"

/*+ BSsdo_color - Do a local IDO coloring

	Input Parameters:
.   sdo_queue - the nodes to color
.   n_queue - the length of the sdo_queue
.   A - the sparse matrix
.   local_color - the local coloring
.   global_color - the colors of global nodes adjacent to each processor
.   local_ptr - array of pointers indicating which neighbors in
.               each row are local neighbors (on this processor)
.   global_ptr - array of pointers indicating which neighbors in
.                each row are global neighbors (not on this processor)
.   color_template - used to figure out what colors are around a node
.   sdo_degree - a work vector
.   sdo_queue_ptr - a work vector
.   sdo_deg_ptr - a work vector
.   procinfo - the usual processor info

+*/
void BSsdo_color(int *sdo_queue, int n_queue, BSspmat *A, int *local_color,
		 int **global_color, int *local_ptr, int *global_ptr,
		 int *color_template, int *sdo_degree, int *sdo_queue_ptr,
		 int *sdo_deg_ptr, BSprocinfo *procinfo)
{
	BSsprow	**local_col_array;
	int	*row_ptr, *adj_row_ptr;
	BSsprow	*t_node, *adj_node;
	int i, j, k;
	int max_sdo_deg, deg, l_vtx, t_color;
	int adj_vertex, adj_adj_vertex;
	int update;
	int tmp_ptr, tmp_vertex;
	int	*in_group;
	int	n = A->num_rows;

	/* Set-up */
	MY_MALLOC(in_group,(int *),sizeof(int)*A->num_rows,1);

	local_col_array = A->rows;

	/* Initialize sdo_degree to be -1 for all nodes */
	/* this indicates that a node is NOT in the sdo_queue */
	for (i=0;i<A->num_rows;i++) {
		in_group[i] = -1;
	}

	/* Compute sdo_degrees and store as key in sdo_queue_ptr */

	for (i=0; i<n_queue; i++) {
		l_vtx = sdo_queue[i];
		in_group[l_vtx] = 1;
		sdo_queue_ptr[i] = 0;

		/* Check for global adjacent nodes and update sdo degree */

		for (j=0; j<global_ptr[l_vtx]; j++) {

			t_color = global_color[l_vtx][j];

			if(color_template[t_color] != n + l_vtx) {
				color_template[t_color] = n + l_vtx;
				sdo_queue_ptr[i]++;
			}
		}

		/* Check local nodes */

		t_node = local_col_array[l_vtx];
		row_ptr = t_node->col;

		for (j=local_ptr[l_vtx]; j<t_node->length; j++) {
			(*A->map->fglobal2local)
				(1,&(row_ptr[j]),&adj_vertex,procinfo,A->map);CHKERR(0);

			t_color = local_color[adj_vertex];
			if (t_color == NO_COLOR) {
			}
			else {
				if(color_template[t_color] != n + l_vtx) {
					color_template[t_color] = n + l_vtx;
					sdo_queue_ptr[i]++;
				}
			}
		}
		sdo_degree[l_vtx] = sdo_queue_ptr[i];
	}

	/* Sort sdo_queue by sdo_degree */

	BSheap_sorthl1(n_queue,sdo_queue_ptr,sdo_queue); CHKERR(0);

	/* Construct sdo_deg_ptrs for sdo_queue */

	max_sdo_deg = sdo_queue_ptr[0];
	sdo_queue_ptr[0] = 0;
	deg = max_sdo_deg;
	for (i=1; i<n_queue; i++) {

		while (sdo_queue_ptr[i] != deg) {
			sdo_deg_ptr[deg] = i-1;
			deg--;
		}
		sdo_queue_ptr[i] = 0;
	}

	sdo_deg_ptr[deg] = n_queue - 1;

	/* Construct sdo_queue_ptrs */

	for (i=0; i<n_queue; i++) {
		l_vtx = sdo_queue[i];
		sdo_queue_ptr[l_vtx] = i;
	}

	/* Main elimination loop */

	for (i=0; i<n_queue; i++) {

		l_vtx = sdo_queue[i];

		t_node = local_col_array[l_vtx];
		row_ptr = t_node->col;

		/* Mark colors of adjacent global vertices */

		for (j=0; j<global_ptr[l_vtx]; j++) {
			t_color = global_color[l_vtx][j];
			color_template[t_color] = l_vtx;
		}

		/* Mark colors of adjacent local vertices */
		for (j=local_ptr[l_vtx]; j<t_node->length; j++) {
			(*A->map->fglobal2local)
				(1,&(row_ptr[j]),&adj_vertex,procinfo,A->map);CHKERR(0);
			t_color = local_color[adj_vertex];
			if (t_color == NO_COLOR) {
			}
			else {
				color_template[t_color] = l_vtx;
			}
		}

		/* Choose t_color */

		t_color = 0;
		while (color_template[t_color] == l_vtx) {
			t_color++;
		}

		/* delete vertex from queue, update deg pointers */
		while ((sdo_deg_ptr[max_sdo_deg] == i) && (max_sdo_deg > 0)) {
			max_sdo_deg--;
		}

		/* Update adjacent vertices */
		for (j=local_ptr[l_vtx]; j<t_node->length; j++) {
			(*A->map->fglobal2local)
				(1,&(row_ptr[j]),&adj_vertex,procinfo,A->map);CHKERR(0);
			/* do not update chosen vertex */

			if(l_vtx == adj_vertex) {
				MY_SETERRC(COLOR1_ERROR,"Adjacent to self\n");
			}

			/* Update sat_degree of adjacent vertices if required */

			else if ((in_group[adj_vertex] != -1) && (local_color[adj_vertex] == NO_COLOR)) {
				update = TRUE;
				adj_node = local_col_array[adj_vertex];
				adj_row_ptr = adj_node->col;
				k=0;
				while ((k<global_ptr[adj_vertex])&&(update==TRUE)) {

					/* if tmp_color here, no need to promote */

					if(global_color[adj_vertex][k] == t_color) {
						update = FALSE;
					}
					k++;
				}
				k=local_ptr[adj_vertex];
				while ((k<adj_node->length)&&(update==TRUE)) {

					/* if tmp_color new, promote adj_vertex in queue */

					(*A->map->fglobal2local) (1,&(adj_row_ptr[k]),
						&adj_adj_vertex,procinfo,A->map);CHKERR(0);
					if(local_color[adj_adj_vertex] == t_color) {
						update = FALSE;
					}
					k++;
				}
				if(update) {
					sdo_degree[adj_vertex]++;

					/* if sdo_degree > max_sdo_deg */

					if (sdo_degree[adj_vertex] > max_sdo_deg) {
						max_sdo_deg++;

						if(max_sdo_deg != sdo_degree[adj_vertex]){
							MY_SETERRC(COLOR1_ERROR,"Max degree wrong\n");
						}
						sdo_deg_ptr[max_sdo_deg] = i+1;
					}
					else {
						sdo_deg_ptr[sdo_degree[adj_vertex]]++;
					}

					/* swap positions, if required */

					if (sdo_queue_ptr[adj_vertex] !=
							  sdo_deg_ptr[sdo_degree[adj_vertex]])
					{
						tmp_ptr = sdo_deg_ptr[sdo_degree[adj_vertex]];
						tmp_vertex = sdo_queue[tmp_ptr];
						sdo_queue[sdo_queue_ptr[adj_vertex]] = tmp_vertex;
						sdo_queue_ptr[tmp_vertex] = sdo_queue_ptr[adj_vertex];
						sdo_queue[tmp_ptr] = adj_vertex;
						sdo_queue_ptr[adj_vertex] = tmp_ptr;
					}
				}
				/* End if(update) */
			}
			/* End Update sdo_degree */
		}
		/* End of update adjacent vertices, mark new color */

		local_color[l_vtx] = t_color;
	}
	/* End of main elimination loop */

	/* Clean up sdo_queue_ptr */

	for (i=0; i < n_queue; i++)
	{
		l_vtx = sdo_queue[i];
		sdo_queue_ptr[l_vtx] = 0;
	}

	MY_FREE(in_group);
}