1#include "BSprivate.h"
2
3/*+ BSido_color - Do a local IDO coloring
4
5	Input Parameters:
6.   ido_queue - the nodes to color
7.   n_queue - the length of the ido_queue
8.   A - the sparse matrix
9.   local_color - the local coloring
10.   global_color - the colors of global nodes adjacent to each processor
11.   local_ptr - array of pointers indicating which neighbors in
12.               each row are local neighbors (on this processor)
13.   global_ptr - array of pointers indicating which neighbors in
14.                each row are global neighbors (not on this processor)
15.   color_template - used to figure out what colors are around a node
16.   ido_degree - the ido degree of each node
17.   ido_queue_ptr - a work vector (should be 0's)
18.   ido_deg_ptr - a work vector
19.   procinfo - the usual processor info
20
21	Output Parameters:
22.   ido_degree - the updated ido degree of nodes
23+*/
24void BSido_color(int *ido_queue, int n_queue, BSspmat *A, int *local_color,
25	int **global_color, int *local_ptr, int *global_ptr, int *color_template,
26	int *ido_degree, int *ido_queue_ptr, int *ido_deg_ptr, BSprocinfo *procinfo)
27{
28	BSsprow	**local_col_array;
29	int	*row_ptr;
30	BSsprow	*t_node;
31	int i, j;
32	int max_ido_deg, deg, l_vtx, t_color;
33	int p1, p2, v1, v2;
34
35	local_col_array = A->rows;
36
37	/* Get ido_degrees and store as key in ido_queue_ptr */
38
39	ido_queue_ptr[0] = 0;
40	for (i=0; i<n_queue; i++)
41	{
42		l_vtx = ido_queue[i];
43		ido_queue_ptr[i] = ido_degree[l_vtx];
44	}
45
46	/* Sort ido_queue by ido_degree; sorts both ido_queue_ptr & ido_queue */
47
48	BSheap_sorthl1(n_queue,ido_queue_ptr,ido_queue); CHKERR(0);
49
50	/* Construct ido_deg_ptrs for ido_queue */
51
52	max_ido_deg = ido_queue_ptr[0];
53	ido_queue_ptr[0] = 0;
54	deg = max_ido_deg;
55	for (i=1; i<n_queue; i++) {
56		while (ido_queue_ptr[i] != deg) {
57			ido_deg_ptr[deg] = i-1;
58			deg--;
59		}
60		ido_queue_ptr[i] = 0;
61	}
62	ido_deg_ptr[deg] = n_queue - 1;
63
64	/* Construct ido_queue_ptrs */
65
66	for (i=0; i<n_queue; i++) {
67		l_vtx = ido_queue[i];
68		ido_queue_ptr[l_vtx] = i;
69	}
70
71	/* Main loop */
72
73	for (i=0; i<n_queue; i++) {
74		l_vtx = ido_queue[i];
75		t_node = local_col_array[l_vtx];
76		row_ptr = t_node->col;
77
78		/* Check global adjacent nodes & mark unusable colors */
79
80		for (j=0; j<global_ptr[l_vtx]; j++) {
81			t_color = global_color[l_vtx][j];
82			color_template[t_color] = l_vtx;
83		}
84
85		/* Check local nodes and update their degree or mark unusable colors */
86
87		for (j=local_ptr[l_vtx]; j<t_node->length; j++) {
88			(*A->map->fglobal2local)
89				(1,&(row_ptr[j]),&v1,procinfo,A->map);CHKERR(0);
90			if (v1 < 0) {
91				MY_SETERRC(COLOR_ERROR,"Bad global to local translation\n");
92			}
93			t_color = local_color[v1];
94			if (t_color == NO_COLOR) {
95				ido_degree[v1]++;
96				p1 = ido_queue_ptr[v1];
97				if(p1 > i) {
98					if (ido_degree[v1] > max_ido_deg) {
99						max_ido_deg = ido_degree[v1];
100						p2 = i+1;
101						ido_deg_ptr[max_ido_deg] = p2;
102					}
103					else {
104						ido_deg_ptr[ido_degree[v1]]++;
105						p2 = ido_deg_ptr[ido_degree[v1]];
106					}
107					if (p1 != p2) {
108						v2 = ido_queue[p2];
109						ido_queue[p1] = v2;
110						ido_queue[p2] = v1;
111						ido_queue_ptr[v1] = p2;
112						ido_queue_ptr[v2] = p1;
113					}
114				}
115			}
116			else
117			{
118				color_template[t_color] = l_vtx;
119			}
120		}
121		while ((ido_deg_ptr[max_ido_deg] == i) && (max_ido_deg > 0)) max_ido_deg--;
122
123		/* Choose t_color */
124
125		t_color = 0;
126		while (color_template[t_color] == l_vtx)
127			t_color++;
128		local_color[l_vtx] = t_color;
129	}
130
131	/* Clean up ido_queue_ptr */
132
133	for (i=0; i<n_queue; i++)
134	{
135		l_vtx = ido_queue[i];
136		ido_queue_ptr[l_vtx] = 0;
137	}
138
139}
140