/
Forward.c
276 lines (225 loc) · 6.76 KB
/
Forward.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
# include <stdio.h>
# include "Forward.h"
# include "utilities.h"
/*Funcion que calcula la cantidad de colores posibles
para un vertice*/
/*
Recibe un arreglo que representa un conjunto vectorial
con los colores posibles marcados con 1 y el tamano ese
arreglo
*/
int number_of_FCs(int* FC, int FC_size){
int n = 0;
int i = 0;
while(i<=FC_size){
if (FC[i]==1)
return 1;
++i;
}
return 0;
}
/*Funcion que revisa si ya se colorearon
todos los nodos del grafo*/
int complete_coloring(Graph* g, int n_of_vertex){
int cc = 1;
int i;
for(i=0; i < n_of_vertex; ++i)
if (g[i].color == -1)
cc = 0;
return cc;
}
/*Funcion que calcula el proximo color a utilizar*/
/*Recibe el conjunto de colores posibles y el registro con el
uso que tiene cada color hasta el momento*/
int nxt_color(int* FC, int FC_size, int* color_use_record){
int i = 0;
int nxt_color = 0;
int max_use = 0;
while (i<=FC_size){
if (FC[i]==1 && color_use_record[i] >= max_use){
nxt_color=i;
max_use = color_use_record[i];
}
++i;
}
return nxt_color;
}
/*Actualiza el color around de los vertices cuando se colorea un vertice
y su grado de saturacion tambien*/
void color_ca_and_satur(Graph * graph, int* satur_degree, int v_i, int color){
// Buscar los adyacentes a v_i
// Si el vértice ya fue coloreado entonces no actualizo
// su grado de saturación
int i;
int * adjacents = graph[v_i].adjacents;
satur_degree[v_i] = -1; //Por ya estoy coloreando v_i
for(i = 0; i < graph[v_i].adj_size; i++) {
if (satur_degree[adjacents[i]] != -1) {
// Quiero saber si el vértice adyacente a v_i tiene en su
// arreglo de colores adyacentes el color "color".
if (graph[adjacents[i]].color_around[color] == 0)
satur_degree[adjacents[i]] = 1;
graph[adjacents[i]].color_around[color]++;
}
}
}
/*Funcion que actualiza el color mas alto usado y el primer nodo con ese color
cuando se pone un color*/
/*Modifica el color mas alto usado y el primer nodo en tener ese color a traves
de efectos de borde, recibe apuntadores a ambos valores*/
void color_maxcolor(int* max_color, int* st_max_color, int depth, int v_i_color){
if (v_i_color > *max_color){
*max_color = v_i_color;
*st_max_color = depth;
}
}
/*Devuelve cual es el proximo vertice a colorear basado en el
grado de saturacion y en el grado de los vertices*/
int nxt_vertex(int * satur, int vertex_num, Graph* graph, tuple* deg_vert, int lower_bound){
int i;
int max_satur_degree = -1;
int nxt_vert;
for(i = 0; i < vertex_num; i++) {
if (max_satur_degree < satur[i]) {
max_satur_degree = satur[i];
nxt_vert = i;
}
}
if (repeated(max_satur_degree, satur, vertex_num, nxt_vert))
nxt_vert = break_tie(deg_vert,graph,vertex_num-lower_bound);
return nxt_vert;
}
/*Regenera el FC de un vertice*/
void genFC(int vert,
int* FC,
int FC_size,
Graph* graph,
int* satur_degree,
int upper_bound){
int i;
int* color_around = graph[vert].color_around;
for(i=0; i <= FC_size; ++i){
if (color_around[i]>0)
FC[i]=0;
else
FC[i]=1;//lookahead(vert,i,upper_bound,graph,satur_degree);
}
}
/*Procedimiento de lookahead para reducir el tamano del FC*/
int lookahead(int vert,
int color,
int upper_bound,
Graph* graph,
int* satur_degree){
int i;
int adj_satur;
int adj_num = graph[vert].adj_size;
int* adjs = graph[vert].adjacents;
//Recorro los vecinos del nodo
for (i=0; i<adj_num; ++i){
//Tomo la saturacion del vecino
adj_satur = satur_degree[adjs[i]];
//Si no tiene un nodo adyacente de menor rango
//con este color, aumento su saturacion
if (graph[adjs[i]].color_around[color] == 0)
adj_satur += 1;
//Si su saturacion es igual la cota superior
//menos uno, su FC sera vacio, devuelvo falso.
if (adj_satur == (upper_bound-1))
return 0;
}
//Si ningun vecino devolvio falso,
//devuelvo true.
return 1;
}
/*Calcula el nodo de menor rango con el color que se
se le pasa como primer argumento*/
int new_first_max_color(int color, int* trace, Graph* graph){
int i = 0;
while(graph[trace[i]].color != color){
++i;
}
return i;
}
/*
Funcion que actualiza mejor coloracion alcanzada
*/
void update_coloring(Graph* g, int n_of_vertex, int* coloring){
int i;
for (i=0; i<n_of_vertex; ++i){
coloring[i] = g[i].color;
}
}
/*Funcion Forward*/
void Forward(int* start_vert,
int* max_used_color,
int* first_max_color,
int* upper_bound,
int* trace,
int* depth,
int* satur_degree,
int* popularity,
tuple* deg_vert,
Graph* graph,
int n_of_vertex,
int* coloring,
int lower_bound){
int current_vert = *start_vert;
int max_color = *max_used_color;
int st_max_color = *first_max_color;
int ub = *upper_bound;
int dth = *depth;
int* FC = graph[current_vert].FC;
int FC_size = mix((ub-1),max((max_color+1),lower_bound));
int nxt_col = 0;
int num_of_colored = 1;
//Mientras: el FC no sea vacio Y
// no tenga una coloracion completa
/* while (number_of_FCs(FC,FC_size)>0 && */
/* ! complete_coloring(graph,n_of_vertex)){ */
while (number_of_FCs(FC,FC_size)>0 &&
(num_of_colored <= (n_of_vertex - lower_bound))) {
//Busco el siguiente color y coloreo el nodo
nxt_col = nxt_color(FC,FC_size,popularity);
graph[current_vert].color = nxt_col;
trace[dth] = current_vert;
++dth;
++num_of_colored;
if (num_of_colored > (n_of_vertex - lower_bound))
break;
//Actualizo las estructuras auxiliares
color_ca_and_satur(graph,satur_degree,current_vert,nxt_col);
color_maxcolor(&max_color,&st_max_color,(dth-1),nxt_col);
popularity[nxt_col] += 1;
//Busco el siguiente vertice a colorear y
//calculo su FC
current_vert = nxt_vertex(satur_degree,n_of_vertex,graph,deg_vert,lower_bound);
FC_size = mix((ub-1),max((max_color+1),lower_bound));
FC = graph[current_vert].FC;
genFC(current_vert,
FC,
FC_size,
graph,
satur_degree,
ub);
}
//Si tengo una coloracion completa, actualizo
//el upper_bound y el maximo color usado
// if (complete_coloring(graph,n_of_vertex)){
if (num_of_colored > (n_of_vertex - lower_bound)) {
*upper_bound = max_color;
*max_used_color = (max_color-1);
*first_max_color = new_first_max_color( (max_color-1) ,trace,graph);
*start_vert = st_max_color;
*depth = (dth-1);
update_coloring(graph,n_of_vertex,coloring);
}
//Si tengo que hacer backtrack, lo hago desde donde estoy.
//El upperbound no cambia ni el max_used_color
else{
*max_used_color = max_color;
*first_max_color = st_max_color;
*start_vert = current_vert;
*depth = (dth-1);
}
}