Blender V5.3
uvedit_clipboard_graph_iso.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2019 Stefano Quer
2 * SPDX-FileCopyrightText: 2022 Blender Authors
3 *
4 * SPDX-License-Identifier: GPL-3.0-or-later
5 *
6 * Originally 6846114 from https://github.com/stefanoquer/graphISO/blob/master/v3
7 * graphISO: Tools to compute the Maximum Common Subgraph between two graphs.
8 */
9
13
15
16#include "BLI_assert.hh"
17
18#include "MEM_guardedalloc.h"
19
20#include <algorithm>
21#include <climits>
22
23namespace blender {
24
25#define L 0
26#define R 1
27#define LL 2
28#define RL 3
29#define ADJ 4
30#define P 5
31#define W 6
32#define IRL 7
33
34#define BDS 8
35
37{
38 this->n = n;
41
42 /* \note Allocation of `n * n` bytes total! */
43
44 for (int i = 0; i < n; i++) {
45 /* Caution, are you trying to change the representation of adjmat?
46 * Consider `Vector<std::pair<int, int>> adjmat;` instead.
47 * Better still is to use a different algorithm. See for example:
48 * https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/beatcs09.pdf
49 */
50 adjmat[i] = MEM_new_array_zeroed<uint8_t>(n * sizeof *adjmat[i], __func__);
51 }
52 degree = nullptr;
53}
54
56{
57 for (int i = 0; i < n; i++) {
58 MEM_delete(adjmat[i]);
59 }
60 MEM_delete(adjmat);
61 MEM_delete(label);
62 if (degree) {
63 MEM_delete(degree);
64 }
65}
66
67void GraphISO::add_edge(int v, int w)
68{
69 BLI_assert(v != w);
70 adjmat[v][w] = 1;
71 adjmat[w][v] = 1;
72}
73
74void GraphISO::calculate_degrees() const
75{
76 if (degree) {
77 return;
78 }
80 for (int v = 0; v < n; v++) {
81 int row_count = 0;
82 for (int w = 0; w < n; w++) {
83 if (adjmat[v][w]) {
84 row_count++;
85 }
86 }
87 degree[v] = row_count;
88 }
89}
90
92 public:
94 {
95 this->g = g;
96 }
97 const GraphISO *g;
98
99 bool operator()(int i, int j) const
100 {
101 return g->degree[i] < g->degree[j];
102 }
103};
104
106{
107 calculate_degrees();
108
109 int *vv = MEM_new_array_uninitialized<int>(n, __func__);
110 for (int i = 0; i < n; i++) {
111 vv[i] = i;
112 }
113 /* Currently ordering iso_verts by degree.
114 * Instead should order iso_verts by frequency of degree. */
115 GraphISO_DegreeCompare compare_obj(this);
116 std::sort(vv, vv + n, compare_obj);
117
118 GraphISO *subg = new GraphISO(n);
119 for (int i = 0; i < n; i++) {
120 for (int j = 0; j < n; j++) {
121 subg->adjmat[i][j] = adjmat[vv[i]][vv[j]];
122 }
123 }
124 for (int i = 0; i < n; i++) {
125 subg->label[i] = label[vv[i]];
126 }
127 subg->calculate_degrees();
128
129 MEM_delete(vv);
130 return subg;
131}
132
133static void update_incumbent(uint8_t cur[][2], int inc[][2], int cur_pos, int *inc_pos)
134{
135 if (cur_pos > *inc_pos) {
136 *inc_pos = cur_pos;
137 for (int i = 0; i < cur_pos; i++) {
138 inc[i][L] = cur[i][L];
139 inc[i][R] = cur[i][R];
140 }
141 }
142}
143
144static void add_bidomain(uint8_t domains[][BDS],
145 int *bd_pos,
146 uint8_t left_i,
147 uint8_t right_i,
148 uint8_t left_len,
149 uint8_t right_len,
150 uint8_t is_adjacent,
151 uint8_t cur_pos)
152{
153 domains[*bd_pos][L] = left_i;
154 domains[*bd_pos][R] = right_i;
155 domains[*bd_pos][LL] = left_len;
156 domains[*bd_pos][RL] = right_len;
157 domains[*bd_pos][ADJ] = is_adjacent;
158 domains[*bd_pos][P] = cur_pos;
159 domains[*bd_pos][W] = UINT8_MAX;
160 domains[*bd_pos][IRL] = right_len;
161 (*bd_pos)++;
162}
163
164static int calc_bound(const uint8_t domains[][BDS], int bd_pos, int cur_pos)
165{
166 int bound = 0;
167 for (int i = bd_pos - 1; i >= 0 && domains[i][P] == cur_pos; i--) {
168 bound += std::min(domains[i][LL], domains[i][IRL]);
169 }
170 return bound;
171}
172
173static int partition(uint8_t *arr, int start, int len, const uint8_t *adjrow)
174{
175 int i = 0;
176 for (int j = 0; j < len; j++) {
177 if (adjrow[arr[start + j]]) {
178 std::swap(arr[start + i], arr[start + j]);
179 i++;
180 }
181 }
182 return i;
183}
184
185static void generate_next_domains(uint8_t domains[][BDS],
186 int *bd_pos,
187 int cur_pos,
188 uint8_t *left,
189 uint8_t *right,
190 uint8_t v,
191 uint8_t w,
192 int inc_pos,
193 uint8_t **adjmat0,
194 uint8_t **adjmat1)
195{
196 int i;
197 int bd_backup = *bd_pos;
198 int bound = 0;
199 uint8_t *bd;
200 for (i = *bd_pos - 1, bd = &domains[i][L]; i >= 0 && bd[P] == cur_pos - 1;
201 i--, bd = &domains[i][L])
202 {
203
204 uint8_t l_len = partition(left, bd[L], bd[LL], adjmat0[v]);
205 uint8_t r_len = partition(right, bd[R], bd[RL], adjmat1[w]);
206
207 if (bd[LL] - l_len && bd[RL] - r_len) {
208 add_bidomain(domains,
209 bd_pos,
210 bd[L] + l_len,
211 bd[R] + r_len,
212 bd[LL] - l_len,
213 bd[RL] - r_len,
214 bd[ADJ],
215 uint8_t(cur_pos));
216 bound += std::min(bd[LL] - l_len, bd[RL] - r_len);
217 }
218 if (l_len && r_len) {
219 add_bidomain(domains, bd_pos, bd[L], bd[R], l_len, r_len, true, uint8_t(cur_pos));
220 bound += std::min(l_len, r_len);
221 }
222 }
223 if (cur_pos + bound <= inc_pos) {
224 *bd_pos = bd_backup;
225 }
226}
227
229{
231 uint8_t idx = UINT8_MAX;
232 if (bd[RL] != bd[IRL]) {
233 return left[bd[L] + bd[LL]];
234 }
235 for (uint8_t i = 0; i < bd[LL]; i++) {
236 if (left[bd[L] + i] < min) {
237 min = left[bd[L] + i];
238 idx = i;
239 }
240 }
241 std::swap(left[bd[L] + idx], left[bd[L] + bd[LL] - 1]);
242 bd[LL]--;
243 bd[RL]--;
244 return min;
245}
246
247static uint8_t find_min_value(const uint8_t *arr, uint8_t start_idx, uint8_t len)
248{
249 uint8_t min_v = UINT8_MAX;
250 for (int i = 0; i < len; i++) {
251 min_v = std::min(arr[start_idx + i], min_v);
252 }
253 return min_v;
254}
255
256static void select_bidomain(uint8_t domains[][BDS],
257 int bd_pos,
258 const uint8_t *left,
259 int current_matching_size,
260 bool connected)
261{
262 int i;
263 int min_size = INT_MAX;
264 int min_tie_breaker = INT_MAX;
265 int best = INT_MAX;
266 uint8_t *bd;
267 for (i = bd_pos - 1, bd = &domains[i][L]; i >= 0 && bd[P] == current_matching_size;
268 i--, bd = &domains[i][L])
269 {
270 if (connected && current_matching_size > 0 && !bd[ADJ]) {
271 continue;
272 }
273 int len = bd[LL] > bd[RL] ? bd[LL] : bd[RL];
274 if (len < min_size) {
275 min_size = len;
276 min_tie_breaker = find_min_value(left, bd[L], bd[LL]);
277 best = i;
278 }
279 else if (len == min_size) {
280 int tie_breaker = find_min_value(left, bd[L], bd[LL]);
281 if (tie_breaker < min_tie_breaker) {
282 min_tie_breaker = tie_breaker;
283 best = i;
284 }
285 }
286 }
287 if (best != INT_MAX && best != bd_pos - 1) {
288 uint8_t tmp[BDS];
289 for (i = 0; i < BDS; i++) {
290 tmp[i] = domains[best][i];
291 }
292 for (i = 0; i < BDS; i++) {
293 domains[best][i] = domains[bd_pos - 1][i];
294 }
295 for (i = 0; i < BDS; i++) {
296 domains[bd_pos - 1][i] = tmp[i];
297 }
298 }
299}
300
301static uint8_t select_next_w(const uint8_t *right, uint8_t *bd)
302{
304 uint8_t idx = UINT8_MAX;
305 for (uint8_t i = 0; i < bd[RL] + 1; i++) {
306 if ((right[bd[R] + i] > bd[W] || bd[W] == UINT8_MAX) && right[bd[R] + i] < min) {
307 min = right[bd[R] + i];
308 idx = i;
309 }
310 }
311 if (idx == UINT8_MAX) {
312 bd[RL]++;
313 }
314 return idx;
315}
316
317static void maximum_common_subgraph_internal(int incumbent[][2],
318 int *inc_pos,
319 uint8_t **adjmat0,
320 int n0,
321 uint8_t **adjmat1,
322 int n1,
323 bool *r_search_abandoned)
324{
325 int min = std::min(n0, n1);
326
329 uint8_t *left = MEM_new_array_uninitialized<uint8_t>(n0, __func__);
330 uint8_t *right = MEM_new_array_uninitialized<uint8_t>(n1, __func__);
331
332 uint8_t v, w, *bd;
333 int bd_pos = 0;
334 for (int i = 0; i < n0; i++) {
335 left[i] = i;
336 }
337 for (int i = 0; i < n1; i++) {
338 right[i] = i;
339 }
340 add_bidomain(domains, &bd_pos, 0, 0, n0, n1, 0, 0);
341
342 int iteration_count = 0;
343
344 while (bd_pos > 0) {
345 if (iteration_count++ > 10000000) {
346 /* Unlikely to find a solution, may as well give up.
347 * Can occur with moderate sized inputs where the graph has lots of symmetry, e.g. a cube
348 * subdivided 3x times.
349 */
350 *r_search_abandoned = true;
351 *inc_pos = 0;
352 break;
353 }
354 bd = &domains[bd_pos - 1][L];
355 if (calc_bound(domains, bd_pos, bd[P]) + bd[P] <= *inc_pos ||
356 (bd[LL] == 0 && bd[RL] == bd[IRL]))
357 {
358 bd_pos--;
359 }
360 else {
361 const bool connected = false;
362 select_bidomain(domains, bd_pos, left, domains[bd_pos - 1][P], connected);
363 v = select_next_v(left, bd);
364 if ((bd[W] = select_next_w(right, bd)) != UINT8_MAX) {
365 w = right[bd[R] + bd[W]]; /* Swap the W after the bottom of the current right domain. */
366 right[bd[R] + bd[W]] = right[bd[R] + bd[RL]];
367 right[bd[R] + bd[RL]] = w;
368 bd[W] = w; /* Store the W used for this iteration. */
369 cur[bd[P]][L] = v;
370 cur[bd[P]][R] = w;
371 update_incumbent(cur, incumbent, bd[P] + uint8_t(1), inc_pos);
373 domains, &bd_pos, bd[P] + 1, left, right, v, w, *inc_pos, adjmat0, adjmat1);
374 }
375 }
376 }
377
378 MEM_delete(cur);
379 MEM_delete(domains);
380 MEM_delete(right);
381 MEM_delete(left);
382}
383
384static bool check_automorphism(const GraphISO *g0,
385 const GraphISO *g1,
386 int solution[][2],
387 int *solution_length)
388{
389 if (g0->n != g1->n) {
390 return false;
391 }
392 for (int i = 0; i < g0->n; i++) {
393 if (g0->label[i] != g1->label[i]) {
394 return false;
395 }
396 for (int j = 0; j < g0->n; j++) {
397 if (g0->adjmat[i][j] != g1->adjmat[i][j]) {
398 return false;
399 }
400 }
401 solution[i][0] = i;
402 solution[i][1] = i;
403 }
404 *solution_length = g0->n;
405 return true;
406}
407
409 GraphISO *g1_input,
410 int solution[][2],
411 int *solution_length,
412 bool *r_search_abandoned)
413{
414 if (check_automorphism(g0_input, g1_input, solution, solution_length)) {
415 return true;
416 }
417
418 int n0 = g0_input->n;
419 int n1 = g1_input->n;
420
421 int min_size = std::min(n0, n1);
422 if (min_size >= UINT8_MAX - 2) {
423 return false;
424 }
425
426 GraphISO *g0 = g0_input->sort_vertices_by_degree();
427 GraphISO *g1 = g1_input->sort_vertices_by_degree();
428
429 int sol_len = 0;
431 solution, &sol_len, g0->adjmat, n0, g1->adjmat, n1, r_search_abandoned);
432 *solution_length = sol_len;
433
434 bool result = (sol_len == n0);
435 if (result) {
436 for (int i = 0; i < sol_len; i++) {
437 solution[i][0] = g0->label[solution[i][0]]; /* Index from input. */
438 solution[i][1] = g1->label[solution[i][1]];
439 }
440 }
441
442 delete g1;
443 delete g0;
444
445 return result;
446}
447
448} // namespace blender
#define UINT8_MAX
Read Blender memory allocation and freeing.
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
GraphISO * sort_vertices_by_degree() const
#define INT_MAX
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str)
Definition mallocn.cc:129
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
#define R
#define L
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static uint8_t select_next_v(uint8_t *left, uint8_t *bd)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static bool check_automorphism(const GraphISO *g0, const GraphISO *g1, int solution[][2], int *solution_length)
bool ED_uvedit_clipboard_maximum_common_subgraph(GraphISO *g0_input, GraphISO *g1_input, int solution[][2], int *solution_length, bool *r_search_abandoned)
static void maximum_common_subgraph_internal(int incumbent[][2], int *inc_pos, uint8_t **adjmat0, int n0, uint8_t **adjmat1, int n1, bool *r_search_abandoned)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static void generate_next_domains(uint8_t domains[][BDS], int *bd_pos, int cur_pos, uint8_t *left, uint8_t *right, uint8_t v, uint8_t w, int inc_pos, uint8_t **adjmat0, uint8_t **adjmat1)
static int calc_bound(const uint8_t domains[][BDS], int bd_pos, int cur_pos)
static void update_incumbent(uint8_t cur[][2], int inc[][2], int cur_pos, int *inc_pos)
static void add_bidomain(uint8_t domains[][BDS], int *bd_pos, uint8_t left_i, uint8_t right_i, uint8_t left_len, uint8_t right_len, uint8_t is_adjacent, uint8_t cur_pos)
unsigned char uint8_t
Definition BKE_text.h:79
static uint8_t find_min_value(const uint8_t *arr, uint8_t start_idx, uint8_t len)
static void select_bidomain(uint8_t domains[][BDS], int bd_pos, const uint8_t *left, int current_matching_size, bool connected)
static uint8_t select_next_w(const uint8_t *right, uint8_t *bd)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static int partition(uint8_t *arr, int start, int len, const uint8_t *adjrow)
#define min(a, b)
Definition sort.cc:38