From a5e505fc1a8f7ae060f8f2604a8d5b6132851d34 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Mon, 22 Aug 2016 10:42:36 -0400 Subject: made updating the dual clusters more efficient --- src/break_edge.c | 31 ++++++++++++++++++++++--------- 1 file changed, 22 insertions(+), 9 deletions(-) (limited to 'src/break_edge.c') diff --git a/src/break_edge.c b/src/break_edge.c index 0bd0277..7082b76 100644 --- a/src/break_edge.c +++ b/src/break_edge.c @@ -10,13 +10,9 @@ bool break_edge(finst *instance, unsigned int edge, cholmod_common *c) { update_factor(instance->factor, v1, v2, c); - - unsigned int w1 = instance->network->edges_to_verts[2 * edge]; - unsigned int w2 = instance->network->edges_to_verts[2 * edge + 1]; - unsigned int dw1 = instance->network->dual_edges_to_verts[2 * edge]; - unsigned int dw2 = instance->network->dual_edges_to_verts[2 * edge + 1]; - if (instance->network->boundary != TORUS_BOUND) { + unsigned int w1 = instance->network->edges_to_verts[2 * edge]; + unsigned int w2 = instance->network->edges_to_verts[2 * edge + 1]; unsigned int tw1 = w1 > w2 ? w1 : w2; unsigned int tw2 = w1 > w2 ? w2 : w1; @@ -42,6 +38,9 @@ bool break_edge(finst *instance, unsigned int edge, cholmod_common *c) { } if (instance->network->boundary == TORUS_BOUND) { + unsigned int dw1 = instance->network->dual_edges_to_verts[2 * edge]; + unsigned int dw2 = instance->network->dual_edges_to_verts[2 * edge + 1]; + if (instance->dual_marks[dw1] == instance->dual_marks[dw2]) { int **cycles = (int **)malloc(2*instance->network->num_edges * sizeof(int *)); unsigned int num_cycles = find_cycles(instance->network->num_edges, instance->fuses, instance->network->dual_edges_to_verts, instance->network->dual_verts_to_edges_ind, instance->network->dual_verts_to_edges, cycles); @@ -79,9 +78,23 @@ bool break_edge(finst *instance, unsigned int edge, cholmod_common *c) { free(cycles); } - unsigned int *tmp_marks = get_clusters(instance, c); - free(instance->dual_marks); - instance->dual_marks = tmp_marks; + unsigned int tw1 = dw1 > dw2 ? dw1 : dw2; + unsigned int tw2 = dw1 > dw2 ? dw2 : dw1; + + CHOL_INT *lap_p = (CHOL_INT *)instance->adjacency->p; + CHOL_INT *lap_i = (CHOL_INT *)instance->adjacency->i; + double *lap_x = (double *)instance->adjacency->x; + + for (int i = 0; i < lap_p[tw1 + 1] - lap_p[tw1]; i++) { + if (lap_i[lap_p[tw1] + i] == tw2) + lap_x[lap_p[tw1] + i] = 1; + } + for (int i = 0; i < lap_p[tw2 + 1] - lap_p[tw2]; i++) { + if (lap_i[lap_p[tw2] + i] == tw1) + lap_x[lap_p[tw2] + i] = 1; + } + + set_connected(instance->adjacency, instance->dual_marks, dw1, instance->dual_marks[v1], -1, 0); } -- cgit v1.2.3-70-g09d2