From 2b2517a7bf6f0cf65ad249f2d329643eb355fac1 Mon Sep 17 00:00:00 2001 From: "yu.dongliang" <18588496441@163.com> Date: Fri, 3 Nov 2023 21:54:55 +0800 Subject: [PATCH] ses_graph.c --- Makefile | 2 +- ses_core.h | 15 +- ses_cross_graph.c | 395 ---------------------------------------------- ses_graph.c | 382 ++++++++++++++++++++++++++++++++++++++++++++ ses_graph.h | 83 ++++++++++ ses_layout.c | 121 +++++--------- ses_utils.c | 26 --- 7 files changed, 505 insertions(+), 519 deletions(-) delete mode 100644 ses_cross_graph.c create mode 100644 ses_graph.c create mode 100644 ses_graph.h diff --git a/Makefile b/Makefile index 4405e05..2dddcd7 100644 --- a/Makefile +++ b/Makefile @@ -2,7 +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_graph.c CFILES += ses_utils.c CFILES += ses_steps.c diff --git a/ses_core.h b/ses_core.h index 39be787..0a5bef3 100644 --- a/ses_core.h +++ b/ses_core.h @@ -3,22 +3,14 @@ #include"scf_vector.h" #include"scf_eda_pb.h" +#include"ses_graph.h" typedef struct ses_step_s ses_step_t; typedef struct ses_path_s ses_path_t; typedef struct ses_flow_s ses_flow_t; typedef struct ses_info_s ses_info_t; -typedef struct ses_edge_s ses_edge_t; typedef struct ses_ctx_s ses_ctx_t; -struct ses_edge_s -{ - ScfEcomponent* c; - - scf_vector_t* crosses; - intptr_t color; -}; - struct ses_flow_s { scf_vector_t* paths; @@ -117,15 +109,10 @@ void ses_flow_v_pos(ses_flow_t* flow, double a, double ja); void ses_flow_v_neg(ses_flow_t* flow, double a, double ja); void ses_flow_jr (ses_flow_t* flow); -ses_edge_t* ses_edge_alloc(ScfEcomponent* c); -void ses_edge_free (ses_edge_t* edge); - ses_ctx_t* ses_ctx_alloc(); void ses_ctx_free (ses_ctx_t* ctx); -int ses_cross_graph_kcolor(scf_vector_t* graph, int k, scf_vector_t* colors); - int ses_layout_board (ScfEboard* b); int ses_steps_analyse(ScfEfunction* f, int64_t ns, int64_t count); diff --git a/ses_cross_graph.c b/ses_cross_graph.c deleted file mode 100644 index 493a526..0000000 --- a/ses_cross_graph.c +++ /dev/null @@ -1,395 +0,0 @@ -#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_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 void __cross_color_del(scf_vector_t* colors, intptr_t color) -{ - scf_vector_del(colors, (void*)color); - - assert(!scf_vector_find(colors, (void*)color)); -} - -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) { - __cross_color_del(__colors, cross->color); - - 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; - } - - 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; - - scf_loge("c%ld->color: %ld, c%ld->color: %ld\n", edge0->c->id, edge0->color, edge1->c->id, edge1->color); - 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_logw("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; - - __cross_color_del(__colors, 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); -} diff --git a/ses_graph.c b/ses_graph.c new file mode 100644 index 0000000..2817b27 --- /dev/null +++ b/ses_graph.c @@ -0,0 +1,382 @@ +#include"ses_graph.h" + +ses_vertex_t* ses_vertex_alloc() +{ + ses_vertex_t* v = calloc(1, sizeof(ses_vertex_t)); + if (!v) + return NULL; + + v->edges = scf_vector_alloc(); + if (!v->edges) { + free(v); + return NULL; + } + + return v; +} + +void ses_vertex_free(ses_vertex_t* v) +{ + if (v) { + if (v->edges) + scf_vector_free(v->edges); + + free(v); + } +} + +static intptr_t __color_select(ses_vertex_t* v, scf_vector_t* colors) +{ + ses_vertex_t* v2; + + int i; + int j; + + for (i = 0; i < colors->size; ) { + + intptr_t c = (intptr_t)(colors->data[i]); + + for (j = 0; j < v->edges->size; j++) { + v2 = v->edges->data[j]; + + if (c == v2->color) + goto next; + } + + return c; +next: + i++; + } + + return 0; +} + +static int __kcolor_check(scf_vector_t* graph) +{ + ses_vertex_t* v; + + int i; + for (i = 0; i < graph->size; i++) { + v = graph->data[i]; + + if (0 == v->color) + return -1; + } + + return 0; +} + +static void __color_del(scf_vector_t* colors, intptr_t color) +{ + scf_vector_del(colors, (void*)color); + + assert(!scf_vector_find(colors, (void*)color)); +} + +static int __graph_add(scf_vector_t* graph, ses_vertex_t* v) +{ + ses_vertex_t* v2; + + int i; + + for (i = 0; i < v->edges->size; i++) { + v2 = v->edges->data[i]; + + if (scf_vector_find(graph, v2)) { + + int ret = scf_vector_add_unique(v2->edges, v); + if (ret < 0) + return ret; + } + } + + return scf_vector_add(graph, v); +} + +static int __graph_del(scf_vector_t* graph, ses_vertex_t* v) +{ + ses_vertex_t* v2; + + int i; + + for (i = 0; i < v->edges->size; i++) { + v2 = v->edges->data[i]; + + scf_vector_del(v2->edges, v); + } + + return scf_vector_del(graph, v); +} + +static int __kcolor_delete(ses_graph_t* graph, int k, scf_vector_t* deleted) +{ + ses_vertex_t* v; + + while (graph->size > 0) { + + int n_deleted = 0; + int i = 0; + + while (i < graph->size) { + v = graph->data[i]; + + scf_logd("graph->size: %d, edges: %d, k: %d, v: %p\n", + graph->size, v->edges->size, k, v); + + if (v->edges->size >= k) { + i++; + continue; + } + + if (0 != __graph_del(graph, v)) { + scf_loge("\n"); + return -1; + } + + if (0 != scf_vector_add(deleted, v)) { + scf_loge("\n"); + return -1; + } + + n_deleted++; + } + + if (0 == n_deleted) + break; + } + + return 0; +} + +static int __kcolor_fill(ses_graph_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_vertex_t* v; + ses_vertex_t* v2; + + int i; + int j; + + for (i = deleted->size - 1; i >= 0; i--) { + v = deleted->data[i]; + + if (v->edges->size >= k); + + __colors = scf_vector_clone(colors); + if (!__colors) + return -ENOMEM; + + scf_logd("v: %p, edges: %d, k: %d\n", v, v->edges->size, k); + + for (j = 0; j < v->edges->size; j++) { + v2 = v->edges->data[j]; + + if (v2->color > 0) { + __color_del(__colors, v2->color); + + if (0 != v->color && v->color == v2->color) { + scf_logd("v: %p, v2: %p, color: %#lx:%#lx\n", v, v2, v->color, v2->color); + v->color = 0; + } + } + + if (0 != scf_vector_add(v2->edges, v)) + goto error; + } + + assert(__colors->size >= 0); + + if (0 == v->color) { + v->color = __color_select(v, __colors); + + if (0 == v->color) + v->color = -1; + } + + if (0 != scf_vector_add(graph, v)) + goto error; + + scf_vector_free(__colors); + __colors = NULL; + } + + return 0; + +error: + scf_vector_free(__colors); + return -1; +} + +static int __find_not_neighbor(scf_vector_t* graph, int k, ses_vertex_t** pp0, ses_vertex_t** pp1) +{ + assert(graph->size >= k); + + ses_vertex_t* v0; + ses_vertex_t* v1; + + int i; + int j; + + for (i = 0; i < graph->size; i++) { + v0 = graph->data[i]; + + if (v0->edges->size > k) + continue; + + v1 = NULL; + + for (j = i + 1; j < graph->size; j++) { + v1 = graph->data[j]; + + if (!scf_vector_find(v0->edges, v1)) { + assert(!scf_vector_find(v1->edges, v0)); + break; + } + + v1 = NULL; + } + + if (v1) { + *pp0 = v0; + *pp1 = v1; + return 0; + } + } + + return -1; +} + +static ses_vertex_t* __max_neighbors(scf_vector_t* graph) +{ + ses_vertex_t* max = NULL; + ses_vertex_t* v = NULL; + + int n = 0; + int i; + + for (i = 0; i < graph->size; i++) { + v = graph->data[i]; + + if (!max || n < v->edges->size) { + max = v; + n = v->edges->size; + } + } + + return max; +} + +static int __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_vertex_t* v0 = NULL; + ses_vertex_t* v1 = NULL; + ses_vertex_t* max = NULL; + + if (!deleted) + return -ENOMEM; + + scf_logw("graph->size: %d, k: %d\n", graph->size, k); + + int ret = __kcolor_delete(graph, k, deleted); + if (ret < 0) + goto error; + + if (0 == __kcolor_check(graph)) { + + ret = __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 == __find_not_neighbor(graph, k, &v0, &v1)) { + + __colors = scf_vector_clone(colors); + if (!__colors) { + ret = -ENOMEM; + goto error; + } + + v0->color = __color_select(v0, __colors); + if (0 == v0->color) + goto overflow; + v1->color = v0->color; + + __color_del(__colors, v0->color); + + ret = __graph_del(graph, v0); + if (ret < 0) + goto error; + + ret = __graph_del(graph, v1); + if (ret < 0) + goto error; + + ret = __graph_kcolor(graph, k - 1, __colors); + if (ret < 0) + goto error; + + ret = __graph_add(graph, v0); + if (ret < 0) + goto error; + + ret = __graph_add(graph, v1); + if (ret < 0) + goto error; + + scf_vector_free(__colors); + __colors = NULL; + + } else { + +overflow: + max = __max_neighbors(graph); + assert(max); + + ret = __graph_del(graph, max); + if (ret < 0) + goto error; + max->color = -1; + + ret = __graph_kcolor(graph, k, colors); + if (ret < 0) + goto error; + + ret = __graph_add(graph, max); + if (ret < 0) + goto error; + } + + ret = __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_graph_kcolor(ses_graph_t* graph, int k, scf_vector_t* colors) +{ + if (!graph || !colors || 0 == colors->size) + return -EINVAL; + + return __graph_kcolor(graph, k, colors); +} diff --git a/ses_graph.h b/ses_graph.h new file mode 100644 index 0000000..5e96889 --- /dev/null +++ b/ses_graph.h @@ -0,0 +1,83 @@ +#ifndef SES_GRAPH_H +#define SES_GRAPH_H + +#include"scf_vector.h" + +typedef struct ses_vertex_s ses_vertex_t; +typedef scf_vector_t ses_graph_t; + +struct ses_vertex_s +{ + scf_vector_t* edges; + + intptr_t color; + + void* data; +}; + +ses_vertex_t* ses_vertex_alloc(); +void ses_vertex_free (ses_vertex_t* v); + +int ses_graph_kcolor(ses_graph_t* graph, int k, scf_vector_t* colors); + + +static int ses_vertex_cmp_edges(const void* v0, const void* v1) +{ + const ses_vertex_t* sv0 = *(const ses_vertex_t**)v0; + const ses_vertex_t* sv1 = *(const ses_vertex_t**)v1; + + if (sv0->edges->size > sv1->edges->size) + return -1; + if (sv0->edges->size < sv1->edges->size) + return 1; + return 0; +} + +static int ses_vertex_cmp(const void* v0, const void* v1) +{ + const ses_vertex_t* sv0 = v0; + const ses_vertex_t* sv1 = v1; + + if (sv0->data == sv1->data) + return 0; + return -1; +} + +static ses_vertex_t* ses_vertex_add(scf_vector_t* edges, void* data) +{ + ses_vertex_t tmp = {NULL, 0, data}; + ses_vertex_t* v = scf_vector_find_cmp(edges, &tmp, ses_vertex_cmp); + + if (!v) { + v = ses_vertex_alloc(); + if (!v) + return NULL; + v->data = data; + + if (scf_vector_add(edges, v) < 0) { + ses_vertex_free(v); + return NULL; + } + } + + return v; +} + +static int ses_vertex_connect(ses_vertex_t* v0, ses_vertex_t* v1) +{ + if (!scf_vector_find_cmp(v0->edges, v1, ses_vertex_cmp)) { + + if (scf_vector_add(v0->edges, v1) < 0) + return -ENOMEM; + } + + if (!scf_vector_find_cmp(v1->edges, v0, ses_vertex_cmp)) { + + if (scf_vector_add(v1->edges, v0) < 0) + return -ENOMEM; + } + + return 0; +} + +#endif diff --git a/ses_layout.c b/ses_layout.c index 3d27ed7..f702e84 100644 --- a/ses_layout.c +++ b/ses_layout.c @@ -716,51 +716,10 @@ static inline void __ses_flip_pos(ScfEcomponent* c) } } -static inline int edge_cmp(const void* v0, const void* v1) +static int __ses_get_crosses(ScfEfunction* f, int d, scf_vector_t* crosses) { - const ses_edge_t* edge0 = v0; - const ses_edge_t* edge1 = v1; - - if (edge0->c == edge1->c) - return 0; - return -1; -} - -static inline ses_edge_t* __ses_edge_add(scf_vector_t* edges, ScfEcomponent* c) -{ - ses_edge_t tmp = {c, NULL}; - ses_edge_t* edge = scf_vector_find_cmp(edges, &tmp, edge_cmp); - - if (!edge) { - edge = ses_edge_alloc(c); - if (!edge) - return NULL; - - if (scf_vector_add(edges, edge) < 0) { - ses_edge_free(edge); - return NULL; - } - } - - return edge; -} - -static inline int edge_cmp_crosses(const void* v0, const void* v1) -{ - const ses_edge_t* edge0 = *(const ses_edge_t**)v0; - const ses_edge_t* edge1 = *(const ses_edge_t**)v1; - - if (edge0->crosses->size > edge1->crosses->size) - return -1; - if (edge0->crosses->size < edge1->crosses->size) - return 1; - return 0; -} - -static int __ses_get_crosses(ScfEfunction* f, int d, scf_vector_t* edges) -{ - ses_edge_t* edge0; - ses_edge_t* edge1; + ses_vertex_t* edge0; + ses_vertex_t* edge1; ScfEcomponent* c0; ScfEcomponent* c1; @@ -811,23 +770,16 @@ static int __ses_get_crosses(ScfEfunction* f, int d, scf_vector_t* edges) if ((y0 < y2 && y2 < y1 && y1 < y3) || (y2 < y0 && y0 < y3 && y3 < y1)) { - edge0 = __ses_edge_add(edges, c0); + edge0 = ses_vertex_add(crosses, c0); if (!edge0) return -ENOMEM; - edge1 = __ses_edge_add(edges, c1); + edge1 = ses_vertex_add(crosses, c1); if (!edge1) return -ENOMEM; - if (!scf_vector_find_cmp(edge0->crosses, edge1, edge_cmp)) { - if (scf_vector_add(edge0->crosses, edge1) < 0) - return -ENOMEM; - } - - if (!scf_vector_find_cmp(edge1->crosses, edge0, edge_cmp)) { - if (scf_vector_add(edge1->crosses, edge0) < 0) - return -ENOMEM; - } + if (ses_vertex_connect(edge0, edge1) < 0) + return -ENOMEM; goto next; } } @@ -839,27 +791,25 @@ next: } } - scf_vector_qsort(edges, edge_cmp_crosses); + scf_vector_qsort(crosses, ses_vertex_cmp_edges); #if 1 - size_t n_crosses = 0; - - for (i = 0; i < edges->size; i++) { - edge0 = edges->data[i]; + for (i = 0; i < crosses->size; i++) { + edge0 = crosses->data[i]; + c0 = edge0->data; - scf_logw("c%ld\n", edge0->c->id); + scf_logw("c%ld\n", c0->id); - for (j = 0; j < edge0->crosses->size; j++) { - edge1 = edge0->crosses->data[j]; + for (j = 0; j < edge0->edges->size; j++) { + edge1 = edge0->edges->data[j]; + c1 = edge1->data; - scf_logi("j: %ld, c%ld\n", j, edge1->c->id); + scf_logi("j: %ld, c%ld\n", j, c1->id); } printf("\n"); - - n_crosses += edge0->crosses->size; } - scf_loge("edge->size: %d, n_crosses: %ld\n\n", edges->size, n_crosses); + scf_loge("crosses->size: %d\n\n", crosses->size); #endif return 0; @@ -1251,10 +1201,12 @@ static void __ses_mov_pos(ScfEfunction* f, int d) int ses_cross(ScfEfunction* f, int d) { - scf_vector_t* graph = scf_vector_alloc(); - scf_vector_t* colors = scf_vector_alloc(); + ScfEcomponent* c; + + ses_vertex_t* vc; - ses_edge_t* edge; + scf_vector_t* graph = scf_vector_alloc(); + scf_vector_t* colors = scf_vector_alloc(); intptr_t N = 2; intptr_t i; @@ -1263,10 +1215,10 @@ int ses_cross(ScfEfunction* f, int d) scf_loge("\n"); __ses_get_crosses(f, d, graph); - if (0 < graph->size) { - edge = graph->data[0]; + if (0 < graph->size) { + vc = graph->data[0]; - N = edge->crosses->size; + N = vc->edges->size; } for (j = N; j >= 0; j--) { @@ -1274,16 +1226,17 @@ int ses_cross(ScfEfunction* f, int d) for (i = 1; i <= j; i++) scf_vector_add(colors, (void*)i); - int ret = ses_cross_graph_kcolor(graph, j, colors); + int ret = ses_graph_kcolor(graph, j, colors); if (ret < 0) { scf_loge("**********\n"); } for (i = 0; i < graph->size; i++) { - edge = graph->data[i]; + vc = graph->data[i]; - if (edge->color < 0) { - scf_loge("j: %ld, i: %ld, c%ld->color: %ld\n", j, i, edge->c->id, edge->color); + if (vc->color < 0) { + c = vc->data; + scf_loge("j: %ld, i: %ld, c%ld->color: %ld\n", j, i, c->id, vc->color); break; } } @@ -1292,10 +1245,11 @@ int ses_cross(ScfEfunction* f, int d) break; for (i = 0; i < graph->size; i++) { - edge = graph->data[i]; + vc = graph->data[i]; - edge->c->color = edge->color; - edge->color = 0; + c = vc->data; + c->color = vc->color; + vc->color = 0; } scf_vector_clear(colors, NULL); @@ -1303,12 +1257,13 @@ int ses_cross(ScfEfunction* f, int d) } for (i = 0; i < graph->size; i++) { - edge = graph->data[i]; + vc = graph->data[i]; - scf_logi("j: %ld, i: %ld, c%ld->color: %ld\n", j, i, edge->c->id, edge->c->color); + c = vc->data; + scf_logi("j: %ld, i: %ld, c%ld->color: %ld\n", j, i, c->id, c->color); } - scf_vector_clear(graph, ( void (*)(void*) )ses_edge_free); + scf_vector_clear(graph, ( void (*)(void*) )ses_vertex_free); scf_vector_free(graph); scf_vector_free(colors); } diff --git a/ses_utils.c b/ses_utils.c index 07d1e39..b098854 100644 --- a/ses_utils.c +++ b/ses_utils.c @@ -1,31 +1,5 @@ #include"ses_core.h" -ses_edge_t* ses_edge_alloc(ScfEcomponent* c) -{ - ses_edge_t* edge = calloc(1, sizeof(ses_edge_t)); - if (!edge) - return NULL; - - edge->crosses = scf_vector_alloc(); - if (!edge->crosses) { - free(edge); - return NULL; - } - - edge->c = c; - return edge; -} - -void ses_edge_free(ses_edge_t* edge) -{ - if (edge) { - if (edge->crosses) - scf_vector_free(edge->crosses); - - free(edge); - } -} - ses_flow_t* ses_flow_alloc() { ses_flow_t* flow = calloc(1, sizeof(ses_flow_t)); -- 2.25.1