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
|
#include "fracture.h"
bool break_edge(net_t *instance, unsigned int edge, cholmod_common *c) {
instance->fuses[edge] = true;
unsigned int v1 = instance->graph->ev_break[2 * edge];
unsigned int v2 = instance->graph->ev_break[2 * edge + 1];
if (instance->factor != NULL) update_factor(instance->factor, v1, v2, c);
if (instance->graph->boundary != TORUS_BOUND) {
unsigned int w1 = instance->graph->ev[2 * edge];
unsigned int w2 = instance->graph->ev[2 * edge + 1];
unsigned int tw1 = w1 > w2 ? w1 : w2;
unsigned int tw2 = w1 > w2 ? w2 : w1;
int_t *lap_p = (int_t *)instance->adjacency->p;
int_t *lap_i = (int_t *)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] = 0;
}
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] = 0;
}
int old_num_components = instance->num_components;
instance->num_components = update_components(
instance->adjacency, instance->marks, old_num_components, (int)tw1,
(int)tw2, 0);
}
if (instance->graph->boundary == TORUS_BOUND) {
unsigned int dw1 = instance->graph->dev[2 * edge];
unsigned int dw2 = instance->graph->dev[2 * edge + 1];
if (instance->dual_marks[dw1] == instance->dual_marks[dw2]) {
int **cycles = (int **)malloc(4*instance->graph->ne * sizeof(int *));
unsigned int num_cycles = find_cycles(instance->graph->ne, instance->fuses, instance->graph->dev, instance->graph->dvei, instance->graph->dve, cycles);
for (unsigned int i = 0; i < num_cycles; i++) {
int x_num_crossings = 0;
int y_num_crossings = 0;
int ee; unsigned int j = 0;
while ((ee = cycles[2*i][j]) >= 0) {
int side = cycles[2*i+1][j];
j++;
unsigned int v1, v2;
double v1x, v1y, v2x, v2y;
v1 = instance->graph->dev[2 * ee + !side];
v2 = instance->graph->dev[2 * ee + side];
v1x = instance->graph->dvx[2 * v1];
v1y = instance->graph->dvx[2 * v1 + 1];
v2x = instance->graph->dvx[2 * v2];
v2y = instance->graph->dvx[2 * v2 + 1];
double dx = v1x - v2x;
double dy = v1y - v2y;
if (((v1x > 0.5 && v2x < 0.5) || (v1x < 0.5 && v2x > 0.5)) && fabs(dx) < 0.5) {
x_num_crossings += dx > 0 ? 1 : -1;
}
if (((v1y > 0.5 && v2y < 0.5) || (v1y < 0.5 && v2y > 0.5)) && fabs(dy) < 0.5) {
y_num_crossings += dy > 0 ? 1 : -1;
}
}
if ((abs(y_num_crossings) == 0 && abs(x_num_crossings) > 0) || (abs(y_num_crossings) > 0 && abs(x_num_crossings) > 0 && num_cycles > 1)) {
instance->num_components = 2;
}
free(cycles[2*i]);
free(cycles[2*i+1]);
}
free(cycles);
}
unsigned int tw1 = dw1 > dw2 ? dw1 : dw2;
unsigned int tw2 = dw1 > dw2 ? dw2 : dw1;
int_t *lap_p = (int_t *)instance->adjacency->p;
int_t *lap_i = (int_t *)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);
}
return true;
}
|
