44 for (
int i = 0; i <
n; i++) {
57 for (
int i = 0; i <
n; i++) {
74void GraphISO::calculate_degrees()
const
80 for (
int v = 0;
v <
n;
v++) {
82 for (
int w = 0;
w <
n;
w++) {
110 for (
int i = 0; i <
n; i++) {
116 std::sort(vv, vv +
n, compare_obj);
119 for (
int i = 0; i <
n; i++) {
120 for (
int j = 0; j <
n; j++) {
124 for (
int i = 0; i <
n; i++) {
127 subg->calculate_degrees();
135 if (cur_pos > *inc_pos) {
137 for (
int i = 0; i < cur_pos; i++) {
138 inc[i][
L] = cur[i][
L];
139 inc[i][
R] = cur[i][
R];
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;
160 domains[*bd_pos][
IRL] = right_len;
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]);
176 for (
int j = 0; j <
len; j++) {
177 if (adjrow[arr[start + j]]) {
178 std::swap(arr[start + i], arr[start + j]);
197 int bd_backup = *bd_pos;
200 for (i = *bd_pos - 1, bd = &domains[i][
L]; i >= 0 && bd[
P] == cur_pos - 1;
201 i--, bd = &domains[i][
L])
207 if (bd[
LL] - l_len && bd[
RL] - r_len) {
216 bound += std::min(bd[
LL] - l_len, bd[
RL] - r_len);
218 if (l_len && r_len) {
220 bound += std::min(l_len, r_len);
223 if (cur_pos + bound <= inc_pos) {
232 if (bd[
RL] != bd[
IRL]) {
233 return left[bd[
L] + bd[
LL]];
236 if (left[bd[
L] + i] <
min) {
237 min = left[bd[
L] + i];
241 std::swap(left[bd[
L] + idx], left[bd[
L] + bd[
LL] - 1]);
250 for (
int i = 0; i <
len; i++) {
251 min_v = std::min(arr[start_idx + i], min_v);
259 int current_matching_size,
267 for (i = bd_pos - 1, bd = &domains[i][
L]; i >= 0 && bd[
P] == current_matching_size;
268 i--, bd = &domains[i][
L])
270 if (connected && current_matching_size > 0 && !bd[
ADJ]) {
274 if (
len < min_size) {
279 else if (
len == min_size) {
281 if (tie_breaker < min_tie_breaker) {
282 min_tie_breaker = tie_breaker;
287 if (best !=
INT_MAX && best != bd_pos - 1) {
289 for (i = 0; i <
BDS; i++) {
290 tmp[i] = domains[best][i];
292 for (i = 0; i <
BDS; i++) {
293 domains[best][i] = domains[bd_pos - 1][i];
295 for (i = 0; i <
BDS; i++) {
296 domains[bd_pos - 1][i] = tmp[i];
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];
323 bool *r_search_abandoned)
325 int min = std::min(n0, n1);
334 for (
int i = 0; i < n0; i++) {
337 for (
int i = 0; i < n1; i++) {
342 int iteration_count = 0;
345 if (iteration_count++ > 10000000) {
350 *r_search_abandoned =
true;
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]))
361 const bool connected =
false;
365 w = right[bd[
R] + bd[
W]];
366 right[bd[
R] + bd[
W]] = right[bd[
R] + bd[
RL]];
367 right[bd[
R] + bd[
RL]] =
w;
373 domains, &bd_pos, bd[
P] + 1, left, right,
v,
w, *inc_pos, adjmat0, adjmat1);
387 int *solution_length)
389 if (g0->
n != g1->
n) {
392 for (
int i = 0; i < g0->
n; i++) {
396 for (
int j = 0; j < g0->
n; j++) {
404 *solution_length = g0->
n;
411 int *solution_length,
412 bool *r_search_abandoned)
418 int n0 = g0_input->
n;
419 int n1 = g1_input->
n;
421 int min_size = std::min(n0, n1);
431 solution, &sol_len, g0->
adjmat, n0, g1->
adjmat, n1, r_search_abandoned);
432 *solution_length = sol_len;
434 bool result = (sol_len == n0);
436 for (
int i = 0; i < sol_len; i++) {
437 solution[i][0] = g0->
label[solution[i][0]];
438 solution[i][1] = g1->
label[solution[i][1]];
Read Blender memory allocation and freeing.
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
GraphISO_DegreeCompare(const GraphISO *g)
bool operator()(int i, int j) const
GraphISO * sort_vertices_by_degree() const
void add_edge(int v, int w)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
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)
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)