/
implicit_enum.c
125 lines (99 loc) · 3.39 KB
/
implicit_enum.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
# include "implicit_enum.h"
# include "Forward.h"
# include "backwards.h"
void color_clique(Graph* graph,
int* satur_degree, int* popularity,
int* clique, int vertex_num){
int current_vert;
int color;
int i;
int j = 0;
for (i=0; i<vertex_num; ++i){
if (clique[i]) {
color = j;
current_vert = i;
graph[current_vert].color = color;
color_ca_and_satur(graph,satur_degree,current_vert,color);
popularity[color] += 1;
++j;
}
}
}
void implicit_enum(int * upper_bound, int lower_bound,
int * members, Graph * graph,
tuple * deg_vert, int vertex_num) {
int i;
//Inicialización de arreglo de grados de saturación
int * satur_degree = (int *) malloc(sizeof(int)*vertex_num);
for(i = 0; i < vertex_num; i++)
satur_degree[i] = 0;
// Tabla de popularidad de un color
int * popularity = (int *) malloc(sizeof(int) * (*upper_bound));
for(i = 0; i < vertex_num; i++)
popularity[i] = 0;
// Se comienza por colorear la clique máxima encontrada
// por Brelaz+Interchange
color_clique(graph,satur_degree,popularity,members,vertex_num);
// Se aumenta la cota para hacer converger el algoritmo
// en caso de no encontrarse mejor coloracion que upper_bound
*upper_bound += 1;
// Se crea la traza que contiene la secuencia de vértices
// coloreados cuando se hace backtracking
int * trace = (int *) malloc(sizeof(int) * vertex_num);
for(i = 0; i < vertex_num; i++)
trace[i] = 0;
// Profundidad alcanzada en el árbol de backtrack
int * depth = (int *) malloc(sizeof(int));
*depth = 0;
// Máximo color utilizado hasta el momento
int * max_used_color = (int *) malloc(sizeof(int));
*max_used_color = 0;
// Posición en la traza del vértice con máximo color
int * vertex_max_color = (int *) malloc(sizeof(int));
*vertex_max_color = 0;
// Apuntador a la primera casilla de arreglo vértice-grado
tuple * base = deg_vert;
// Vértice de partida para forwards
int * current_vertex = (int *) malloc(sizeof(int));
*current_vertex = nxt_vertex(satur_degree,vertex_num,graph,base, lower_bound);
int FC_size = lower_bound+1;
int* FC = graph[*current_vertex].FC;
genFC(*current_vertex,
FC,
FC_size,
graph,
satur_degree,
*upper_bound);
// Coloración conseguida hasta el momento
int * coloring = (int *) malloc(sizeof(int) * vertex_num);
while(1) {
Forward(current_vertex,max_used_color,vertex_max_color,
upper_bound,trace, depth,satur_degree,popularity,
base,graph,vertex_num,coloring, lower_bound);
if (*upper_bound == lower_bound)
break;
else {
backwards(trace, max_used_color, vertex_max_color,
current_vertex, satur_degree, graph, base,
popularity, coloring, depth, *upper_bound,
lower_bound);
if (*current_vertex == -1)
// Ya no hay vértices para hacer backtrack
break;
}
}
// Se imprime el número cromático
printf("Numero cromatico: %d\n",*max_used_color);
printf("Vertice Color\n");
for (i=0; i<vertex_num; ++i){
printf("%d - %d\n",i,coloring[i]);
}
free(trace);
/* free(max_used_color); */
/* free(vertex_max_color); */
/* free(current_vertex); */
/* free(satur_degree); */
/* // free(popularity); */
/* free(coloring); */
/* free(depth); */
}