From a5e505fc1a8f7ae060f8f2604a8d5b6132851d34 Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jkentdobias@g.hmc.edu>
Date: Mon, 22 Aug 2016 10:42:36 -0400
Subject: made updating the dual clusters more efficient
---
src/break_edge.c | 31 ++++++++++++++++++++++---------
src/gen_laplacian.c | 16 ++++++++++++++--
src/instance.c | 3 ++-
3 files changed, 38 insertions(+), 12 deletions(-)
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);
}
diff --git a/src/gen_laplacian.c b/src/gen_laplacian.c
index 6f4263a..a282564 100644
--- a/src/gen_laplacian.c
+++ b/src/gen_laplacian.c
@@ -5,8 +5,7 @@ cholmod_sparse *gen_adjacency(const finst *instance, bool dual, bool breakv,
unsigned int pad, cholmod_common *c) {
unsigned int ne;
if (dual)
- ne = ((int)instance->network->num_edges -
- (int)instance->num_remaining_edges);
+ ne = ((int)instance->network->num_edges);
else {
ne = instance->num_remaining_edges;
if (!breakv && instance->network->boundary != TORUS_BOUND) {
@@ -58,6 +57,19 @@ cholmod_sparse *gen_adjacency(const finst *instance, bool dual, bool breakv,
ci[2 * count + 1] = v1;
ai[2 * count + 1] = 1;
+ count++;
+ } else if (dual) {
+ unsigned int v1 = etv[2 * i];
+ unsigned int v2 = etv[2 * i + 1];
+
+ ri[2 * count] = v1;
+ ci[2 * count] = v2;
+ ai[2 * count] = 0;
+
+ ri[2 * count + 1] = v2;
+ ci[2 * count + 1] = v1;
+ ai[2 * count + 1] = 0;
+
count++;
}
}
diff --git a/src/instance.c b/src/instance.c
index 5b3d8fb..098ed92 100644
--- a/src/instance.c
+++ b/src/instance.c
@@ -32,7 +32,8 @@ finst *create_instance(fnet *network, double inf, bool voltage_bound,
((double *)instance->boundary_cond->x)[network->bound_verts[0]] = 1;
}
- instance->adjacency = gen_adjacency(instance, false, false, 0, c);
+ if (network->boundary != TORUS_BOUND) instance->adjacency = gen_adjacency(instance, false, false, 0, c);
+ else instance->adjacency = gen_adjacency(instance, true, false, 0, c);
if (startnow) {
cholmod_sparse *laplacian = gen_laplacian(instance, c, true);
--
cgit v1.2.3-70-g09d2