From 6f6467f0aa74795412f623d5efd4a975b028fdea Mon Sep 17 00:00:00 2001 From: "yu.dongliang" <18588496441@163.com> Date: Wed, 1 Nov 2023 14:15:25 +0800 Subject: [PATCH] ses_cross_graph.c --- Makefile | 1 + ses_core.h | 1 + ses_cross_graph.c | 398 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 400 insertions(+) create mode 100644 ses_cross_graph.c diff --git a/Makefile b/Makefile index bc29d85..4405e05 100644 --- a/Makefile +++ b/Makefile @@ -2,6 +2,7 @@ CFILES += main.c CFILES += scf_eda.pb-c.c CFILES += scf_eda_pb.c CFILES += ses_layout.c +CFILES += ses_cross_graph.c CFILES += ses_utils.c CFILES += ses_steps.c diff --git a/ses_core.h b/ses_core.h index 300e8a1..539c21b 100644 --- a/ses_core.h +++ b/ses_core.h @@ -16,6 +16,7 @@ struct ses_edge_s ScfEcomponent* c; scf_vector_t* crosses; + intptr_t color; }; struct ses_flow_s diff --git a/ses_cross_graph.c b/ses_cross_graph.c new file mode 100644 index 0000000..c12690f --- /dev/null +++ b/ses_cross_graph.c @@ -0,0 +1,398 @@ +#include"ses_core.h" + +static intptr_t __cross_color_select(ses_edge_t* edge, scf_vector_t* colors) +{ + ses_edge_t* cross; + + int i; + int j; + + for (i = 0; i < colors->size; ) { + + intptr_t c = (intptr_t)(colors->data[i]); + + for (j = 0; j < edge->crosses->size; j++) { + cross = edge->crosses->data[j]; + + if (c == cross->color) + goto next; + } + + return c; +next: + i++; + } + + return 0; +} + +static int __cross_color_del(scf_vector_t* colors, intptr_t color) +{ + return scf_vector_del(colors, (void*)color); +} + +static int __cross_kcolor_check(scf_vector_t* graph) +{ + ses_edge_t* edge; + + int i; + for (i = 0; i < graph->size; i++) { + edge = graph->data[i]; + + if (0 == edge->color) + return -1; + } + + return 0; +} + +static int __cross_graph_add(scf_vector_t* graph, ses_edge_t* edge) +{ + ses_edge_t* cross; + + int i; + + for (i = 0; i < edge->crosses->size; i++) { + cross = edge->crosses->data[i]; + + if (scf_vector_find(graph, cross)) { + + int ret = scf_vector_add_unique(cross->crosses, edge); + if (ret < 0) + return ret; + } + } + + return scf_vector_add(graph, edge); +} + +static int __cross_graph_del(scf_vector_t* graph, ses_edge_t* edge) +{ + ses_edge_t* cross; + + int i; + + for (i = 0; i < edge->crosses->size; i++) { + cross = edge->crosses->data[i]; + + scf_vector_del(cross->crosses, edge); + } + + return scf_vector_del(graph, edge); +} + +static int __cross_kcolor_delete(scf_vector_t* graph, int k, scf_vector_t* deleted) +{ + ses_edge_t* edge; + + while (graph->size > 0) { + + int n_deleted = 0; + int i = 0; + + while (i < graph->size) { + edge = graph->data[i]; + + scf_logd("graph->size: %d, crosses: %d, k: %d, edge: %p\n", + graph->size, edge->crosses->size, k, edge); + + if (edge->crosses->size >= k) { + i++; + continue; + } + + if (0 != __cross_graph_del(graph, edge)) { + scf_loge("\n"); + return -1; + } + + if (0 != scf_vector_add(deleted, edge)) { + scf_loge("\n"); + return -1; + } + + n_deleted++; + } + + if (0 == n_deleted) + break; + } + + return 0; +} + +static int __cross_kcolor_fill(scf_vector_t* graph, int k, scf_vector_t* colors, scf_vector_t* deleted) +{ + scf_logd("graph->size: %d\n", graph->size); + + scf_vector_t* __colors; + ses_edge_t* edge; + ses_edge_t* cross; + + int i; + int j; + + for (i = deleted->size - 1; i >= 0; i--) { + edge = deleted->data[i]; + + if (edge->crosses->size >= k); + + __colors = scf_vector_clone(colors); + if (!__colors) + return -ENOMEM; + + scf_logd("edge: %p, crosses: %d, k: %d\n", edge, edge->crosses->size, k); + + for (j = 0; j < edge->crosses->size; j++) { + cross = edge->crosses->data[j]; + + if (cross->color > 0) { + int ret = __cross_color_del(__colors, cross->color); + if (ret < 0) + goto error; + + if (0 != edge->color && edge->color == cross->color) { + scf_logd("edge: %p, cross: %p, color: %#lx:%#lx\n", edge, cross, edge->color, cross->color); + edge->color = 0; + } + } + + if (0 != scf_vector_add(cross->crosses, edge)) + goto error; + } + + assert(__colors->size >= 0); + + if (0 == edge->color) { + edge->color = __cross_color_select(edge, __colors); + + if (0 == edge->color) { + edge->color = -1; + scf_logd("__colors->size: %d\n", __colors->size); + } + } + + if (0 != scf_vector_add(graph, edge)) + goto error; + + scf_vector_free(__colors); + __colors = NULL; + } + + return 0; + +error: + scf_vector_free(__colors); + return -1; +} + +static int __cross_kcolor_find_not_neighbor(scf_vector_t* graph, int k, ses_edge_t** pp0, ses_edge_t** pp1) +{ + assert(graph->size >= k); + + ses_edge_t* edge0; + ses_edge_t* edge1; + + int i; + int j; + + for (i = 0; i < graph->size; i++) { + edge0 = graph->data[i]; + + if (edge0->crosses->size > k) + continue; + + edge1 = NULL; + + for (j = i + 1; j < graph->size; j++) { + edge1 = graph->data[j]; + + if (!scf_vector_find(edge0->crosses, edge1)) { + assert(!scf_vector_find(edge1->crosses, edge0)); + break; + } + + edge1 = NULL; + } + + if (edge1) { + *pp0 = edge0; + *pp1 = edge1; + return 0; + } + } + + return -1; +} + +static ses_edge_t* __cross_max_neighbors(scf_vector_t* graph) +{ + ses_edge_t* max = NULL; + ses_edge_t* edge = NULL; + + int n = 0; + int i; + + for (i = 0; i < graph->size; i++) { + edge = graph->data[i]; + + if (!max || n < edge->crosses->size) { + max = edge; + n = edge->crosses->size; + } + } + + return max; +} + +static void __cross_kcolor_process_conflict(scf_vector_t* graph) +{ + ses_edge_t* edge0; + ses_edge_t* edge1; + + int i; + int j; + + for (i = 0; i < graph->size - 1; i++) { + edge0 = graph->data[i]; + + if (0 == edge0->color) + continue; + + for (j = i + 1; j < graph->size; j++) { + + edge1 = graph->data[j]; + + if (0 == edge1->color) + continue; + + if (edge0->color != edge0->color) + continue; + + if (edge0->crosses->size > edge1->crosses->size) + edge1->color = 0; + else + edge0->color = 0; + } + } +} + +static int __cross_graph_kcolor(scf_vector_t* graph, int k, scf_vector_t* colors) +{ + scf_vector_t* deleted = scf_vector_alloc(); + scf_vector_t* __colors = NULL; + ses_edge_t* edge0 = NULL; + ses_edge_t* edge1 = NULL; + ses_edge_t* max = NULL; + + if (!deleted) + return -ENOMEM; + + scf_logd("graph->size: %d, k: %d\n", graph->size, k); + + int ret = __cross_kcolor_delete(graph, k, deleted); + if (ret < 0) + goto error; + + if (0 == __cross_kcolor_check(graph)) { + + ret = __cross_kcolor_fill(graph, k, colors, deleted); + if (ret < 0) + goto error; + + scf_vector_free(deleted); + deleted = NULL; + return 0; + } + + assert(graph->size > 0); + assert(graph->size >= k); + + if (0 == __cross_kcolor_find_not_neighbor(graph, k, &edge0, &edge1)) { + + __colors = scf_vector_clone(colors); + if (!__colors) { + ret = -ENOMEM; + goto error; + } + + edge0->color = __cross_color_select(edge0, __colors); + if (0 == edge0->color) + goto overflow; + edge1->color = edge0->color; + + ret = __cross_color_del(__colors, edge0->color); + if (ret < 0) + goto error; + assert(!scf_vector_find(__colors, (void*)edge0->color)); + + ret = __cross_graph_del(graph, edge0); + if (ret < 0) + goto error; + + ret = __cross_graph_del(graph, edge1); + if (ret < 0) + goto error; + + ret = __cross_graph_kcolor(graph, k - 1, __colors); + if (ret < 0) + goto error; + + ret = __cross_graph_add(graph, edge0); + if (ret < 0) + goto error; + + ret = __cross_graph_add(graph, edge1); + if (ret < 0) + goto error; + + scf_vector_free(__colors); + __colors = NULL; + + } else { + +overflow: + max = __cross_max_neighbors(graph); + assert(max); + + ret = __cross_graph_del(graph, max); + if (ret < 0) + goto error; + max->color = -1; + + ret = __cross_graph_kcolor(graph, k, colors); + if (ret < 0) + goto error; + + ret = __cross_graph_add(graph, max); + if (ret < 0) + goto error; + } + + ret = __cross_kcolor_fill(graph, k, colors, deleted); + if (ret < 0) + goto error; + + scf_vector_free(deleted); + deleted = NULL; + return 0; + +error: + if (__colors) + scf_vector_free(__colors); + + scf_vector_free(deleted); + return ret; +} + +int ses_cross_graph_kcolor(scf_vector_t* graph, int k, scf_vector_t* colors) +{ + if (!graph || !colors || 0 == colors->size) { + scf_loge("\n"); + return -EINVAL; + } + + __cross_kcolor_process_conflict(graph); + + return __cross_graph_kcolor(graph, k, colors); +} -- 2.25.1