dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
preprocess.h
Go to the documentation of this file.
1// Copyright 2024 Markus Anders
2// This file is part of dejavu 2.0.
3// See LICENSE for extended copyright information.
4
5#ifndef SASSY_H
6#define SASSY_H
7
8#define SASSY_VERSION_MAJOR 2
9#define SASSY_VERSION_MINOR 0
10
11#include "graph.h"
12#include "ds.h"
13#include "refinement.h"
14#include "components.h"
15#include <vector>
16#include <iomanip>
17#include <ctime>
18
19namespace dejavu {
21
22 class preprocessor;
23 static preprocessor* save_preprocessor;
24
33 private:
37 enum preop { deg01, deg2ue, deg2ma, qcedgeflip, densify2, twins };
38
39 //inline static preprocessor* save_preprocessor;
40 dejavu_hook* saved_hook = nullptr;
41
42 dejavu::timed_print* print = nullptr;
43
44 coloring c;
45 dejavu::worklist automorphism;
46 dejavu::worklist automorphism_supp;
47
48 dejavu::worklist aux_automorphism;
49 dejavu::worklist aux_automorphism_supp;
50
51 bool layers_melded = false;
52
53 bool skipped_preprocessing = false;
54
56 dejavu::markset del_e;
57
58 std::vector<std::vector<int>> translation_layers;
59 std::vector<std::vector<int>> backward_translation_layers;
60
61 std::vector<int> backward_translation;
62 std::vector<std::vector<int>> recovery_strings;
63
64 std::vector<std::pair<int, int>> baked_recovery_string_pt;
65 std::vector<int> baked_recovery_string;
66
67 std::vector<std::vector<int>> add_edge_buff;
68 dejavu::worklist worklist_deg0;
69 dejavu::worklist worklist_deg1;
70 dejavu::markset add_edge_buff_act;
71 dejavu::ir::refinement* R1 = nullptr;
72
73 dejavu::markset touched_color_cache;
74
75 std::vector<int> g_old_v;
76 std::vector<int> g_old_e;
77 dejavu::worklist edge_scratch;
78
79 std::vector<int> translate_layer_fwd;
80 std::vector<int> translate_layer_bwd;
81
82 int edge_attached_information = 0;
83 std::vector<int> recovery_edge_attached;
84 std::vector<std::vector<std::tuple<int,int,int>>> recovery_edge_adjacent;
85
86 dejavu::worklist _automorphism;
87 dejavu::worklist _automorphism_supp;
88 std::vector<int> save_colmap;
89
90 dejavu::worklist before_move;
91
92 dejavu::ir::graph_decomposer* decomposer = nullptr;
93 int current_component = 0;
94
95 bool ir_quotient_component_init = false;
96
97 public:
99 int domain_size = 0;
100 bool h_deact_deg1 = false;
101 bool h_deact_deg2 = false;
103 preprocessor() = default;
105 R1 = R;
106 }
107
108 explicit preprocessor(dejavu::timed_print* printer) : print(printer) {};
109
110
111 // for a vertex v of reduced graph, return corresponding vertex of the original graph
112 int translate_back(int v) {
113 const int layers = static_cast<int>(translation_layers.size());
114 for (int l = layers - 1; l >= 0; --l) {
115 v = backward_translation_layers[l][v];
116 }
117 return v;
118 }
119
120 // keeps track of the group size generated by automorphisms found so far
122 grp_sz.multiply(n);
123 }
124
125 void inject_decomposer(dejavu::ir::graph_decomposer* new_decomposer, int component) {
126 decomposer = new_decomposer;
127 current_component = component;
128 }
129
130 private:
131 // combine translation layers
132 void meld_translation_layers() {
133 if (layers_melded)
134 return;
135 const int layers = static_cast<int>(translation_layers.size());
136 if(layers == 0) {
137 backward_translation_layers.emplace_back();
138 backward_translation_layers[0].reserve(domain_size);
139 for(int i = 0; i < domain_size; ++i) {
140 backward_translation_layers[0].push_back(i);
141 }
142 layers_melded = true;
143 return;
144 }
145
146
147 const int reduced_size = static_cast<int>(backward_translation_layers[layers - 1].size());
148 backward_translation.reserve(reduced_size);
149 for (int i = 0; i < reduced_size; ++i) backward_translation.push_back(i);
150 for (int i = 0; i < reduced_size; ++i) {
151 int next_v = i;
152 for (int l = layers - 1; l >= 0; --l) { // TODO inefficient
153 next_v = backward_translation_layers[l][next_v];
154 }
155 backward_translation[i] = next_v;
156 }
157 layers_melded = true;
158
159 baked_recovery_string.reserve(domain_size);
160 baked_recovery_string_pt.reserve(domain_size);
161
162 for (int i = 0; i < reduced_size; ++i) {
163 const int orig_i = backward_translation[i];
164 const int pt_start = static_cast<int>(baked_recovery_string.size());
165 for(auto v : recovery_strings[orig_i]) baked_recovery_string.push_back(v);
166 const int pt_end = static_cast<int>(baked_recovery_string.size());
167 baked_recovery_string_pt.emplace_back(pt_start, pt_end);
168 }
169 recovery_strings.clear();
170 }
171
172 int twins_partition_refinement(dejavu::sgraph *g, int *colmap, dejavu_hook* hook, bool false_twins) {
173 g->initialize_coloring(&c, colmap);
174 copy_coloring_to_colmap(&c, colmap);
175 del.reset();
176
177 dejavu::ds::worklist neighbour_colors(g->v_size);
178 dejavu::ds::markset is_neighbour(g->v_size);
179 workset_t<int> neighbours(g->v_size);
180 workspace scratch(2*g->v_size);
181
182 int removed_twins = 0;
183
184 for(int refine_with_v = 0; refine_with_v < g->v_size; ++refine_with_v) {
185 const int start_pt = g->v[refine_with_v];
186 const int end_pt = start_pt + g->d[refine_with_v];
187
188 neighbour_colors.reset();
189 neighbours.reset();
190
191 for(int j = start_pt; j < end_pt; ++j) {
192 const int neighbour = g->e[j];
193 const int neighbour_col = c.vertex_to_col[neighbour];
194
195 // singletons can not be split, so let's just ignore them
196 if (c.ptn[neighbour_col] == 0) continue;
197
198 if(neighbours.get(neighbour_col) == -1) {
199 neighbour_colors.push_back(neighbour_col);
200 // neighbours acts as the write position for degree 1 vertices of col in the scratchpad
201 neighbours.set(neighbour_col, 0);
202 }
203
204 // write vertex to scratchpad for later use
205 dej_assert(2*neighbour_col + neighbours.get(neighbour_col) < 2*g->v_size);
206 scratch[2*neighbour_col + neighbours.get(neighbour_col)] = neighbour;
207 neighbours.inc_nr(neighbour_col); // we reset neighbours later, use old_color_classes for reset
208 }
209
210 if(false_twins) {
211 // do same as above, but for myself
212 const int neighbour = refine_with_v;
213 const int neighbour_col = c.vertex_to_col[neighbour];
214
215 // singletons can not be split, so let's just ignore them
216 if (c.ptn[neighbour_col] > 0) {
217 if (neighbours.get(neighbour_col) == -1) {
218 neighbour_colors.push_back(neighbour_col);
219 // neighbours acts as the write position for degree 1 vertices of col in the scratchpad
220 neighbours.set(neighbour_col, 0);
221 }
222 // write vertex to scratchpad for later use
223 dej_assert(2 * neighbour_col + neighbours.get(neighbour_col) < 2 * g->v_size);
224 scratch[2 * neighbour_col + neighbours.get(neighbour_col)] = neighbour;
225 neighbours.inc_nr(neighbour_col);// we reset neighbours later, use old_color_classes for reset
226 }
227 }
228
229 for(int j = 0; j < neighbour_colors.cur_pos; ++j) {
230 const int deg0_col = neighbour_colors[j];
231 const int deg1_col_sz = neighbours.get(deg0_col); // - deg0_col
232 const int deg0_col_sz = (c.ptn[deg0_col] + 1) - deg1_col_sz;
233 const int deg1_col = deg0_col + deg0_col_sz;
234
235
236 dej_assert(c.vertex_to_col[c.lab[deg0_col]] == deg0_col);
237
238 // no split? done...
239 if (deg0_col == deg1_col) {
240 neighbours.set(deg0_col, -1);
241 dej_assert(c.vertex_to_col[c.lab[deg0_col]] == deg0_col);
242 continue;
243 }
244
245 // there is a split
246 ++c.cells;
247
248 // set ptn
249 c.ptn[deg0_col] = deg0_col_sz - 1;
250 c.ptn[deg1_col] = deg1_col_sz - 1;
251 c.ptn[deg1_col - 1] = 0;
252
253 int deg1_write_pos = deg1_col;
254 int deg1_read_pos = 2*deg0_col + neighbours.get(deg0_col) - 1;
255
256 // rearrange vertices of deg1 to the back of deg0 color
257 dej_assert(deg1_read_pos >= 2*deg0_col);
258
259 while (deg1_read_pos >= 2*deg0_col) {
260 dej_assert(deg1_read_pos < 2*g->v_size);
261 const int v = scratch[deg1_read_pos];
262 const int vertex_at_pos = c.lab[deg1_write_pos];
263 const int lab_pos = c.vertex_to_lab[v];
264
265 c.lab[deg1_write_pos] = v;
266 c.vertex_to_lab[v] = deg1_write_pos;
267 c.vertex_to_col[v] = deg1_col;
268
269 c.lab[lab_pos] = vertex_at_pos;
270 c.vertex_to_lab[vertex_at_pos] = lab_pos;
271
272 deg1_write_pos++;
273 deg1_read_pos--;
274 }
275
276 dej_assert(deg1_write_pos == deg1_col + deg1_col_sz);
277 dej_assert(c.vertex_to_col[c.lab[deg0_col]] == deg0_col);
278 dej_assert(c.vertex_to_col[c.lab[deg1_col]] == deg1_col);
279
280 // reset neighbours count to -1
281 neighbours.set(deg0_col, -1);
282 }
283
284 if(c.cells == g->v_size) return removed_twins;
285 }
286
287 for(int i = 0; i < g->v_size;) {
288 const int twin_class = i;
289 const int twin_class_sz = c.ptn[twin_class] + 1;
290 i += twin_class_sz;
291
292 if(twin_class_sz > 1) {
293 const int remaining_vertex = c.lab[twin_class];
294 const int orig_remaining_vertex = translate_back(remaining_vertex);
295 int group_size_calculation = 2;
296
297 // remove all but one twin of this class and output transposition automorphisms
298 for (int j = twin_class + 1; j < twin_class + twin_class_sz; ++j) {
299 const int vertex = c.lab[j];
300
301 // multiply group size
302 multiply_to_group_size(group_size_calculation);
303 ++group_size_calculation;
304
305 // transposition of remaining_vertex and vertex
306 _automorphism[vertex] = remaining_vertex;
307 _automorphism[remaining_vertex] = vertex;
308
309 dej_assert(colmap[vertex] == colmap[remaining_vertex]);
310
311 _automorphism_supp.push_back(vertex);
312 _automorphism_supp.push_back(remaining_vertex);
313
314 pre_hook(g->v_size, _automorphism.get_array(), _automorphism_supp.cur_pos,
315 _automorphism_supp.get_array(), hook);
316
317 reset_automorphism(_automorphism.get_array(), _automorphism_supp.cur_pos,
318 _automorphism_supp.get_array());
319 _automorphism_supp.reset();
320 }
321
322 for (int j = twin_class + 1; j < twin_class + twin_class_sz; ++j) {
323 const int vertex = c.lab[j];
324
325 // add to recovery string of remaining vertex
326 const int orig_other = translate_back(vertex);
327 recovery_strings[orig_remaining_vertex].push_back(orig_other);
328 for (int k = 0; k < static_cast<int>(recovery_strings[orig_other].size()); ++k) {
329 recovery_strings[orig_remaining_vertex].push_back(recovery_strings[orig_other][k]);
330 }
331
332 // remove vertex later
333 del.set(vertex);
334 ++removed_twins;
335 }
336
337 // color the remaining vertex appropriately with the size of the twin class
338 colmap[remaining_vertex] = colmap[remaining_vertex] + (twin_class_sz-1);
339 }
340 }
341
342 return removed_twins;
343 }
344
345 int remove_twins(dejavu::sgraph *g, int *colmap, dejavu_hook* hook) {
346 //coloring col;
347 g->initialize_coloring(&c, colmap);
348
349 dejavu::ds::markset test_twin(g->v_size);
350 std::vector<int> add_to_string;
351 dejavu::ds::worklist twin_counter(g->v_size);
352
353 dejavu::ds::markset potential_twin(g->v_size);
354 dejavu::ds::worklist potential_twin_counter(g->v_size);
355
356 dejavu::ds::markset touched(g->v_size);
357
358 std::vector<int> potential_twin_list;
359
360 del.reset();
361
362 int d_limit = std::max(static_cast<int>(sqrt(sqrt(g->v_size))), 8);
363
364 int s_twins = 0;
365 for(int i = 0; i < g->v_size; ++i) twin_counter[i] = 0;
366 // iterate over color classes
367 for(int i = 0; i < g->v_size;) {
368 const int color = i;
369 const int color_size = c.ptn[color] + 1;
370 i += color_size;
371
372 for(int j = 0; j < color_size; ++j) {
373 if(j == 2 && s_twins == 0) break;
374 const int vertex = c.lab[color + j];
375 if(g->d[vertex] > d_limit) break;
376
377 touched.set(vertex);
378 int twin_class_sz = 1;
379
380 bool limit_breached = false;
381
382 add_to_string.clear();
383 if(del.get(vertex)) continue;
384 test_twin.reset();
385 potential_twin.reset();
386 potential_twin_list.clear();
387 for(int k = 0; k < g->d[vertex]; ++k) {
388 const int neighbour = g->e[g->v[vertex] + k];
389 test_twin.set(neighbour);
390 if(g->d[neighbour] > d_limit) {
391 limit_breached = true;
392 break;
393 }
394 for(int l = 0; l < g->d[neighbour]; ++l) {
395 const int neighbour_neighbour = g->e[g->v[neighbour] + l];
396 if(touched.get(neighbour_neighbour)) continue;
397 if(potential_twin.get(neighbour_neighbour)) {
398 potential_twin_counter[neighbour_neighbour] += 1;
399 } else {
400 potential_twin.set(neighbour_neighbour);
401 potential_twin_counter[neighbour_neighbour] = 1;
402 potential_twin_list.push_back(neighbour_neighbour);
403 }
404 }
405 }
406 if(limit_breached) break;
407
408 //for(int jj = j+1; jj < color_size; ++jj) {
409 for(int other_vertex : potential_twin_list) {
410 bool is_twin = true;
411 //const int other_vertex = col.lab[color + jj];
412 if(potential_twin_counter[other_vertex] < g->d[vertex] - 1) continue;
413 if(vertex == other_vertex || del.get(other_vertex) ||
414 c.vertex_to_col[other_vertex] != c.vertex_to_col[vertex]) continue;
415 dej_assert(g->d[vertex] == g->d[other_vertex]);
416 for(int k = 0; k < g->d[other_vertex]; ++k) {
417 const int neighbour = g->e[g->v[other_vertex] + k];
418 if(neighbour == vertex) continue;
419 if(!test_twin.get(neighbour)) {
420 is_twin = false;
421 break;
422 }
423 }
424
425 if(is_twin) {
426 ++s_twins;
427 ++twin_counter[vertex];
428 dej_assert(vertex != other_vertex);
429 ++twin_class_sz;
430 multiply_to_group_size(twin_class_sz);
431 del.set(other_vertex);
432 add_to_string.push_back(other_vertex);
433
434 _automorphism[vertex] = other_vertex;
435 _automorphism[other_vertex] = vertex;
436 _automorphism_supp.push_back(vertex);
437 _automorphism_supp.push_back(other_vertex);
438
439 pre_hook(g->v_size, _automorphism.get_array(), _automorphism_supp.cur_pos,
440 _automorphism_supp.get_array(), hook);
441
442 reset_automorphism(_automorphism.get_array(), _automorphism_supp.cur_pos,
443 _automorphism_supp.get_array());
444 _automorphism_supp.reset();
445 }
446 }
447
448 dej_assert(!del.get(vertex));
449 dej_assert(twin_class_sz -1 == static_cast<int>(add_to_string.size()));
450 dej_assert(twin_counter[vertex] == static_cast<int>(add_to_string.size()));
451 const int orig_vertex = translate_back(vertex);
452 for(auto& other_vertex : add_to_string) {
453 dej_assert(del.get(other_vertex));
454 const int orig_other = translate_back(other_vertex);
455 dej_assert(static_cast<int>(recovery_strings[orig_vertex].size()) ==
456 static_cast<int>(recovery_strings[orig_other].size()));
457 recovery_strings[orig_vertex].push_back(orig_other);
458 for(int k = 0; k < static_cast<int>(recovery_strings[orig_other].size()); ++k) {
459 recovery_strings[orig_vertex].push_back(recovery_strings[orig_other][k]);
460 }
461 }
462 }
463
464 add_to_string.clear();
465 for(int j = 0; j < color_size; ++j) {
466 const int vertex = c.lab[color + j];
467 if(!del.get(vertex)) {
468 dej_assert(colmap[vertex] + twin_counter[vertex] < color + color_size);
469 colmap[vertex] = color + twin_counter[vertex];
470 add_to_string.push_back(vertex);
471 }
472 }
473 }
474
475 return s_twins;
476 }
477
478 // reset internal automorphism structure to the identity
479 static void reset_automorphism(int *rautomorphism, int nsupp, const int *supp) {
480 for (int i = 0; i < nsupp; ++i) {
481 rautomorphism[supp[i]] = supp[i];
482 }
483 };
484
485 // are vert1 and vert2 adjacent in g?
486 static bool is_adjacent(dejavu::sgraph*g, int vert1, int vert2) {
487 if(g->d[vert1] < g->d[vert2]) {
488 for(int i = 0; i < g->d[vert1]; ++i) {
489 if(g->e[g->v[vert1] + i] == vert2)
490 return true;
491 }
492 return false;
493 } else {
494 for(int i = 0; i < g->d[vert2]; ++i) {
495 if(g->e[g->v[vert2] + i] == vert1)
496 return true;
497 }
498 return false;
499 }
500 }
501
502 // check for degree 2 matchings between color classes and mark for deletion
503 void red_deg2_path_size_1(dejavu::sgraph *g, int *colmap) {
504 if (g->v_size <= 1 || h_deact_deg2)
505 return;
506
507 del.reset();
508
509 //coloring test_col;
510 g->initialize_coloring(&c, colmap);
511
512 assure_ir_quotient_init(g);
513
514 touched_color_cache.reset();
515
516 worklist_deg0.reset();
517 worklist_deg1.reset();
518
519 for (int i = 0; i < g->v_size; ++i) {
520 worklist_deg1.push_back(-1);
521 worklist_deg0.push_back(0);
522 }
523
524 add_edge_buff_act.reset();
525 //add_edge_buff.reserve(g->v_size);
526 //for (int i = 0; i < g->v_size; ++i)
527 // add_edge_buff.emplace_back(); // could do this smarter... i know how many edges end up here
528
529 for (int i = 0; i < g->v_size;) {
530 const int test_v = c.lab[i];
531 const int path_col_sz = c.ptn[i];
532 if (g->d[test_v] == 2) {
533 const int n1 = g->e[g->v[test_v] + 0];
534 const int n2 = g->e[g->v[test_v] + 1];
535 if (g->d[n1] != 2 && g->d[n2] != 2) {
536 // relevant path of length 1
537 const int col_n1 = c.vertex_to_col[n1];
538 const int col_n2 = c.vertex_to_col[n2];
539
540 const int col_sz_n1 = c.ptn[c.vertex_to_col[n1]];
541 const int col_sz_n2 = c.ptn[c.vertex_to_col[n2]];
542
543 if (col_sz_n1 != col_sz_n2 || col_sz_n1 != path_col_sz || col_n1 == col_n2) {
544 i += c.ptn[i] + 1;
545 continue;
546 }
547
548 bool already_matched_n1_n2 = false;
549
550 const int already_match_pt1 = g->v[c.lab[col_n1]];
551 const int already_match_pt2 = g->v[c.lab[col_n2]];
552
553 if (touched_color_cache.get(col_n1) && touched_color_cache.get(col_n2)) {
554 for (int j = 0; j < worklist_deg0[col_n1]; ++j) {
555 if (edge_scratch[already_match_pt1 + j] == col_n2)
556 already_matched_n1_n2 = true;
557 }
558 }
559
560 if (touched_color_cache.get(col_n1) && touched_color_cache.get(col_n2) &&
561 already_matched_n1_n2 && worklist_deg0[col_n1] == 1 && worklist_deg0[col_n2] == 1) {
562 // const bool matching_same_cols1 =
563 // test_col.vertex_to_col[worklist_deg1[n1]] == test_col.vertex_to_col[n2];
564 // const bool matching_same_cols2 =
565 // test_col.vertex_to_col[worklist_deg1[n2]] == test_col.vertex_to_col[n1];
566 // const bool match_same_cols = matching_same_cols1 && matching_same_cols2;
567
568 bool check_if_match = true;
569 for (int f = 0; f < c.ptn[i] + 1; ++f) {
570 const int _test_v = c.lab[i + f];
571 const int _n1 = g->e[g->v[_test_v] + 0];
572 const int _n2 = g->e[g->v[_test_v] + 1];
573 check_if_match = check_if_match && (worklist_deg1[_n1] == _n2);
574 if (!check_if_match)
575 break;
576 }
577
578 if (check_if_match) {
579 for (int f = 0; f < c.ptn[i] + 1; ++f) {
580 const int _test_v = c.lab[i + f];
581 del.set(_test_v);
582 }
583 for (int f = 0; f < c.ptn[i] + 1; ++f) {
584 const int _test_v = c.lab[i + f];
585 const int _n1 = g->e[g->v[_test_v] + 0];
586 const int _n2 = g->e[g->v[_test_v] + 1];
587 int can_n;
588 if (c.vertex_to_col[_n1] < c.vertex_to_col[_n2])
589 can_n = _n1;
590 else
591 can_n = _n2;
592 const int orig_test_v = translate_back(_test_v);
593 const int orig_n1 = translate_back(can_n);
594 recovery_strings[orig_n1].push_back(orig_test_v);
595 for (size_t s = 0; s < recovery_strings[orig_test_v].size(); ++s)
596 recovery_strings[orig_n1].push_back(
597 recovery_strings[orig_test_v][s]);
598 }
599 }
600
601
602 i += c.ptn[i] + 1;
603 continue;
604 }
605
606 if (touched_color_cache.get(col_n1) && touched_color_cache.get(col_n2) &&
607 already_matched_n1_n2) {
608 i += c.ptn[i] + 1;
609 continue;
610 }
611
612 const int col_endpoint2 = colmap[n2]; // colmap?
613 bool col_cycle = false;
614 for (int f = 0; f < g->d[n1]; ++f) {
615 const int col_other = colmap[g->e[g->v[n1] + f]];
616 if (col_other == col_endpoint2) {
617 col_cycle = true;
618 break;
619 }
620 }
621
622 if (col_cycle) {
623 i += c.ptn[i] + 1;
624 continue;
625 }
626
627 edge_scratch[already_match_pt1 + worklist_deg0[col_n1]] = col_n2;
628 // overwrites itself, need canonical vertex for color
629 edge_scratch[already_match_pt2 + worklist_deg0[col_n2]] = col_n1;
630 ++worklist_deg0[col_n1];
631 ++worklist_deg0[col_n2];
632
633 touched_color_cache.set(col_n1);
634 touched_color_cache.set(col_n2);
635
636 //const size_t debug_str_sz = recovery_strings[translate_back(test_v)].size();
637
638 for (int f = 0; f < c.ptn[i] + 1; ++f) {
639 const int _test_v = c.lab[i + f];
640 dej_assert(g->d[_test_v] == 2);
641 const int _n1 = g->e[g->v[_test_v] + 0];
642 const int _n2 = g->e[g->v[_test_v] + 1];
643 worklist_deg1[_n1] = _n2;
644 worklist_deg1[_n2] = _n1;
645 for (size_t t = 0; t < add_edge_buff[_n2].size(); ++t)
646 dej_assert(add_edge_buff[_n2][t] != _n1);
647 add_edge_buff[_n2].push_back(_n1);
648 add_edge_buff_act.set(_n2);
649 add_edge_buff[_n1].push_back(_n2);
650 add_edge_buff_act.set(_n1);
651 del.set(_test_v);
652
653 int can_n;
654 if (c.vertex_to_col[_n1] < c.vertex_to_col[_n2])
655 can_n = _n1;
656 else
657 can_n = _n2;
658 const int orig_test_v = translate_back(_test_v);
659 const int orig_n1 = translate_back(can_n);
660 //assert(debug_str_sz == recovery_strings[orig_test_v].size());
661 recovery_strings[orig_n1].push_back(orig_test_v);
662 for (size_t s = 0; s < recovery_strings[orig_test_v].size(); ++s) {
663 recovery_strings[orig_n1].push_back(recovery_strings[orig_test_v][s]);
664 }
665 }
666 }
667 }
668 i += c.ptn[i] + 1;
669 }
670
671 worklist_deg0.reset();
672 worklist_deg1.reset();
673 touched_color_cache.reset();
674 }
675
676 // in g, walk from 'start' (degree 2) until vertex of not-degree 2 is reached
677 // never walks to 'block', if adjacent to 'start'
678 // watch out! won't terminate on cycles
679 static int walk_cycle(dejavu::sgraph *g, const int start, const int block, dejavu::markset* path_done,
680 dejavu::worklist* path) {
681 int current_vertex = start;
682 int last_vertex = block;
683
684 int length = 1;
685
686 if(path) path->push_back(block);
687 if(path_done) path_done->set(block);
688
689 while(true) {
690 if (g->d[current_vertex] != 2) {
691 length = -1;
692 break;
693 }
694 ++length;
695
696 if(path) path->push_back(current_vertex);
697 if(path_done) path_done->set(current_vertex);
698
699 const int next_vertex1 = g->e[g->v[current_vertex] + 0];
700 const int next_vertex2 = g->e[g->v[current_vertex] + 1];
701 int next_vertex = next_vertex1;
702 if(next_vertex1 == last_vertex) next_vertex = next_vertex2;
703 if(next_vertex == block) break;
704
705 last_vertex = current_vertex;
706 current_vertex = next_vertex;
707 }
708
709 return length;
710 }
711
712 // in g, walk from 'start' (degree 2) until vertex of not-degree 2 is reached
713 // never walks to 'block', if adjacent to 'start'
714 // watch out! won't terminate on cycles
715 static std::pair<int, int> walk_to_endpoint(dejavu::sgraph *g, const int start, const int block,
716 dejavu::markset* path_done) {
717 int current_vertex = start;
718 int last_vertex = block;
719
720 while(g->d[current_vertex] == 2) {
721 if(path_done)
722 path_done->set(current_vertex);
723
724 const int next_vertex1 = g->e[g->v[current_vertex] + 0];
725 const int next_vertex2 = g->e[g->v[current_vertex] + 1];
726 int next_vertex = next_vertex1;
727 if(next_vertex1 == last_vertex)
728 next_vertex = next_vertex2;
729
730 last_vertex = current_vertex;
731 current_vertex = next_vertex;
732 }
733
734 return {current_vertex, last_vertex};
735 }
736
737 void order_edgelist(dejavu::sgraph *g) {
738 int k;
739 for(k = 1; k < g->v_size && g->v[k-1] <= g->v[k]; ++k);
740 if(k == g->v_size) return; // already ordered
741
742 memcpy(edge_scratch.get_array(), g->e, g->e_size*sizeof(int));
743 int epos = 0;
744 for(int i = 0; i < g->v_size; ++i) {
745 const int eptr = g->v[i];
746 const int deg = g->d[i];
747 g->v[i] = epos;
748 for(int j = eptr; j < eptr + deg; ++j) {
749 g->e[epos] = edge_scratch[j];
750 ++epos;
751 }
752 }
753 }
754
755 // in g, walk from 'start' (degree 2) until vertex of not-degree 2 is reached
756 // never walks to 'block', if adjacent to 'start'
757 // watch out! won't terminate on cycles
758 static int walk_to_endpoint_collect_path(dejavu::sgraph *g, const int start, const int block,
759 dejavu::worklist* path) {
760 int current_vertex = start;
761 int last_vertex = block;
762
763 while(g->d[current_vertex] == 2) {
764 if(path)
765 path->push_back(current_vertex);
766
767 const int next_vertex1 = g->e[g->v[current_vertex] + 0];
768 const int next_vertex2 = g->e[g->v[current_vertex] + 1];
769 int next_vertex = next_vertex1;
770 if(next_vertex1 == last_vertex)
771 next_vertex = next_vertex2;
772
773 last_vertex = current_vertex;
774 current_vertex = next_vertex;
775 }
776
777 dej_assert(g->d[current_vertex] != 2);
778 return current_vertex;
779 }
780
781 // color-wise degree2 unique endpoint algorithm
782 void red_deg2_unique_endpoint(dejavu::sgraph *g, int *colmap) {
783 if (g->v_size <= 1 || h_deact_deg2)
784 return;
785
786 dejavu::markset color_test(g->v_size);
787 dejavu::markset color_unique(g->v_size);
788
789 //coloring col;
790 g->initialize_coloring(&c, colmap);
791
792 add_edge_buff_act.reset();
793 for (int i = 0; i < g->v_size; ++i) {
794 add_edge_buff[i].clear();
795 }
796
797 del.reset();
798
799 worklist_deg1.reset();
800
801 dejavu::worklist endpoint_cnt(g->v_size);
802 for (int i = 0; i < g->v_size; ++i) {
803 endpoint_cnt.push_back(0);
804 }
805
806 dejavu::markset path_done(g->v_size);
807 dejavu::worklist color_pos(g->v_size);
808 dejavu::worklist filter(g->v_size);
809 dejavu::worklist path_list(g->v_size);
810 dejavu::worklist path(g->v_size);
811 dejavu::worklist connected_paths(g->e_size);
812 dejavu::worklist connected_endpoints(g->e_size);
813
814 for (int i = 0; i < g->v_size; ++i) {
815 if(g->d[i] == 2) {
816 if(path_done.get(i))
817 continue;
818 const int n1 = g->e[g->v[i] + 0];
819 const int n2 = g->e[g->v[i] + 1];
820 // n1 or n2 is endpoint? then walk to other endpoint and collect information...
821 if(g->d[n1] != 2) {
822 const auto other_endpoint = walk_to_endpoint(g, i, n1, &path_done);
823 if(other_endpoint.first == n1) // big self-loop
824 continue;
825 connected_paths[g->v[n1] + endpoint_cnt[n1]] = i;
826 connected_endpoints[g->v[n1] + endpoint_cnt[n1]] = other_endpoint.first;
827 ++endpoint_cnt[n1];
828 connected_paths[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] =
829 other_endpoint.second;
830 connected_endpoints[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] = n1;
831 ++endpoint_cnt[other_endpoint.first];
832 dej_assert(other_endpoint.first != n1);
833 dej_assert(g->d[other_endpoint.first] != 2);
834 dej_assert(n1 != other_endpoint.first);
835 } else if(g->d[n2] != 2) {
836 const auto other_endpoint = walk_to_endpoint(g, i, n2, &path_done);
837 if(other_endpoint.first == n2) // big self-loop
838 continue;
839 connected_paths[g->v[n2] + endpoint_cnt[n2]] = i;
840 connected_endpoints[g->v[n2] + endpoint_cnt[n2]] = other_endpoint.first;
841 ++endpoint_cnt[n2];
842 connected_paths[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] =
843 other_endpoint.second;
844 connected_endpoints[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] = n2;
845 ++endpoint_cnt[other_endpoint.first];
846 dej_assert(other_endpoint.first != n2);
847 dej_assert(g->d[other_endpoint.first] != 2);
848 dej_assert(n2 != other_endpoint.first);
849 }
850 }
851 }
852
853 path_done.reset();
854
855 // iterate over color classes
856 for(int i = 0; i < g->v_size;) {
857 const int color = i;
858 const int color_size = c.ptn[color] + 1;
859 i += color_size;
860 const int test_vertex = c.lab[color];
861 const int endpoints = endpoint_cnt[test_vertex];
862
863 for(int j = 0; j < color_size; ++j) {
864 dej_assert(endpoint_cnt[c.lab[color + j]] == endpoints);
865 }
866
867 if(endpoints == 0) continue;
868
869
870 color_test.reset();
871 color_unique.reset();
872
873 // check which neighbouring paths have unique color
874 for(int j = 0; j < endpoints; ++j) {
875 const int neighbour = connected_paths[g->v[test_vertex] + j];
876 const int neighbour_col = c.vertex_to_col[neighbour];
877 if(color_test.get(neighbour_col)) {
878 color_unique.set(neighbour_col); // means "not unique"
879 }
880 color_test.set(neighbour_col);
881 }
882
883 filter.reset();
884 // filter to indices with unique colors
885 for(int j = 0; j < endpoints; ++j) {
886 const int neighbour = connected_paths[g->v[test_vertex] + j];
887 const int neighbour_col = c.vertex_to_col[neighbour];
888 if(!color_unique.get(neighbour_col)) { // if unique
889 filter.push_back(j); // add index to filter
890 }
891 }
892
893 path.reset();
894 color_test.reset();
895 color_unique.reset();
896
897 // check which neighbouring endpoints have unique color and are NOT connected to `color`
898 for(int j = 0; j < g->d[test_vertex]; ++j) {
899 const int neighbour = g->e[g->v[test_vertex] + j];
900 const int neighbour_col = c.vertex_to_col[neighbour];
901 color_test.set(neighbour_col);
902 }
903
904 // also self-connections of color are forbidden
905 color_test.set(color);
906
907 for(int k = 0; k < filter.cur_pos; ++k) {
908 const int j = filter[k];
909 const int neighbour_endpoint = connected_endpoints[g->v[test_vertex] + j];
910 const int neighbour_col = c.vertex_to_col[neighbour_endpoint];
911 if(color_test.get(neighbour_col)) {
912 color_unique.set(neighbour_col);
913 }
914 color_test.set(neighbour_col);
915 }
916
917 // filter to indices with unique colors
918 int write_pos = 0;
919 for(int k = 0; k < filter.cur_pos; ++k) {
920 const int j = filter[k];
921 const int neighbour = connected_endpoints[g->v[test_vertex] + j];
922 const int neighbour_col = c.vertex_to_col[neighbour];
923 if(!color_unique.get(neighbour_col)) {
924 filter[write_pos] = j;
925 ++write_pos;
926 }
927 }
928 filter.cur_pos = write_pos;
929
930
931 // encode filter into color_unique, such that we can detect corresponding neighbours for all vertices
932 // of color class
933 color_unique.reset();
934 for(int k = 0; k < filter.cur_pos; ++k) {
935 const int j = filter[k];
936 const int filter_to_col = c.vertex_to_col[connected_paths[g->v[test_vertex] + j]];
937 color_unique.set(filter_to_col);
938 filter[k] = filter_to_col;
939 //color_unique.set(col.vertex_to_col[connected_endpoints[filter[k]]]);
940 }
941
942 // order colors here already to access color_pos in O(1) later
943 filter.sort();
944 for(int k = 0; k < filter.cur_pos; ++k) {
945 color_pos[filter[k]] = k;
946 }
947
948 const int num_paths = filter.cur_pos;
949
950 #if defined(DEJDEBUG) && !defined(NDEBUG)
951 int reduced_verts = 0;
952 int reduced_verts_last = 0;
953 #endif
954
955 // do next steps for all vertices in color classes...
956 for(int j = 0; j < color_size; ++j) {
957 const int vertex = c.lab[color + j];
958
959 int sanity_check = 0;
960 // paths left in filter (color_unique) are now collected for reduction
961 color_test.reset();
962 for(int k = 0; k < g->d[vertex]; ++k) {
963 const int neighbour = g->e[g->v[vertex] + k];
964 const int neighbour_col = c.vertex_to_col[neighbour];
965 if(color_unique.get(neighbour_col)) {
966 const int pos = color_pos[neighbour_col];
967 path_list[pos] = neighbour;
968 ++sanity_check;
969 dej_assert(!color_test.get(neighbour_col));
970 color_test.set(neighbour_col);
971 }
972 }
973
974 dej_assert(sanity_check == num_paths);
975
976 for(int k = 0; k < num_paths; ++k) {
977 const int path_start_vertex = path_list[k];
978 dej_assert(g->d[path_start_vertex] == 2);
979 if(path_done.get(path_start_vertex)) {
980 continue;
981 }
982
983 // get path and endpoint
984 path.reset();
985 const int other_endpoint =
986 walk_to_endpoint_collect_path(g, path_start_vertex, vertex, &path);
987 dej_assert(path.cur_pos > 0);
988 dej_assert(vertex != other_endpoint);
989 dej_assert(other_endpoint != path_start_vertex);
990
991 // mark path for deletion
992 for(int l = 0; l < path.cur_pos; ++l) {
993 const int del_v = path[l];
994 dej_assert(g->d[del_v] == 2);
995 dej_assert(!del.get(del_v));
996 del.set(del_v);
997 dej_assert(!path_done.get(del_v));
998 path_done.set(del_v);
999 }
1000
1001 // connect endpoints of path with new edge
1002 dej_assert(!is_adjacent(g, vertex, other_endpoint));
1003 add_edge_buff[other_endpoint].push_back(vertex);
1004 add_edge_buff_act.set(other_endpoint);
1005 add_edge_buff[vertex].push_back(other_endpoint);
1006 add_edge_buff_act.set(vertex);
1007
1008 // write path into recovery_strings
1009 const int unique_endpoint_orig = translate_back(vertex);
1010 // attach all represented vertices of path to unique_endpoint_orig in canonical fashion
1011 // path.sort_after_map(colmap); // should not be necessary
1012 recovery_strings[unique_endpoint_orig].reserve(
1013 2*(recovery_strings[unique_endpoint_orig].size() + path.cur_pos));
1014 for (int l = 0; l < path.cur_pos; ++l) {
1015 dej_assert(path[l] >= 0);
1016 dej_assert(path[l] < g->v_size);
1017 const int path_v_orig = translate_back(path[l]);
1018 dej_assert(path_v_orig >= 0);
1019 dej_assert(path_v_orig < domain_size);
1020 recovery_strings[unique_endpoint_orig].push_back(path_v_orig);
1021 recovery_strings[unique_endpoint_orig].insert(
1022 recovery_strings[unique_endpoint_orig].end(),
1023 recovery_strings[path_v_orig].begin(),
1024 recovery_strings[path_v_orig].end());
1025 }
1026 }
1027
1028 #if defined(DEJDEBUG) && !defined(NDEBUG)
1029 reduced_verts = static_cast<int>(recovery_strings[translate_back(vertex)].size());
1030 if(j > 0) {
1031 dej_assert(reduced_verts == reduced_verts_last);
1032 }
1033 reduced_verts_last = reduced_verts;
1034 #endif
1035 }
1036 }
1037 }
1038
1048 void recovery_attach_to_edge(int v1, int v2, std::vector<int>& recovery) {
1049 const int pos = static_cast<int>(recovery_edge_attached.size());
1050 dej_assert(recovery.size() != 0);
1051 const int len = static_cast<int>(recovery.size());
1052 ++edge_attached_information;
1053 if(len == 1) {
1054 // special code for stored path of length 1 (does not use recovery_edge_attached)
1055 recovery_edge_adjacent[v1].emplace_back(v2, recovery[0], len);
1056 recovery_edge_adjacent[v2].emplace_back(v1, recovery[0], len);
1057 } else {
1058 // general-purpose code for longer paths
1059 for (int i = 0; i < len; ++i) { recovery_edge_attached.push_back(recovery[i]); }
1060 recovery_edge_adjacent[v1].emplace_back(v2, pos, len);
1061 recovery_edge_adjacent[v2].emplace_back(v1, pos, len);
1062 }
1063 }
1064
1074 void recovery_attached_edges_to_automorphism(int v, int* aut, dejavu::ds::worklist* aut_supp,
1075 dejavu::ds::worklist* help_array1,
1076 dejavu::ds::worklist* help_array2) {
1077 if(recovery_edge_adjacent[v].empty()) return;
1078 const int v_map = aut[v];
1079
1080 for(auto & j : recovery_edge_adjacent[v]) {
1081 const int other = std::get<0>(j);
1082 const int id = std::get<1>(j);
1083
1084 dej_assert(other != v);
1085 const int other_map = aut[other];
1086
1087 (*help_array2)[other_map] = id;
1088 }
1089
1090 dej_assert(recovery_edge_adjacent[v].size() == recovery_edge_adjacent[v_map].size());
1091
1092 for(auto & j : recovery_edge_adjacent[v_map]) {
1093 const int other_map = std::get<0>(j);
1094 const int id = std::get<1>(j);
1095 const int len = std::get<2>(j);
1096
1097 dej_assert(other_map != v_map);
1098 const int orig_id = (*help_array2)[other_map];
1099 if(id == orig_id) continue;
1100
1101 // endpoints of the mapped edges:
1102 // e1: v -> v_map
1103 // e2: other -> other_map
1104 // aut maps e1 -> e2
1105
1106 if(len == 1) {
1107 // special code for stored path of length 1 (does not use recovery_edge_attached)
1108 const int v_from = orig_id;
1109 const int v_to = id;
1110 if (v_from != v_to && aut[v_from] == v_from) {
1111 aut[v_from] = v_to;
1112 aut_supp->push_back(v_from);
1113 }
1114 } else {
1115 // general-purpose code for longer paths
1116 for (int k = 0; k < len; ++k) {
1117 const int v_from = recovery_edge_attached[orig_id + k];
1118 const int v_to = recovery_edge_attached[id + k];
1119 if (v_from != v_to && aut[v_from] == v_from) {
1120 aut[v_from] = v_to;
1121 aut_supp->push_back(v_from);
1122 }
1123 }
1124 }
1125 }
1126 }
1127
1134 void red_deg2_densify(dejavu::sgraph *g, int *colmap) {
1135 if (g->v_size <= 1 || h_deact_deg2) return;
1136
1137 dejavu::markset color_test(g->v_size);
1138 dejavu::markset color_unique(g->v_size);
1139
1140 //coloring col;
1141 g->initialize_coloring(&c, colmap);
1142 add_edge_buff_act.reset();
1143 for (int i = 0; i < g->v_size; ++i) {
1144 add_edge_buff[i].clear();
1145 }
1146
1147 del.reset();
1148 worklist_deg1.reset();
1149
1150 dejavu::worklist endpoint_cnt(g->v_size);
1151 for (int i = 0; i < g->v_size; ++i) endpoint_cnt.push_back(0);
1152
1153 dejavu::markset path_done(g->v_size);
1154 dejavu::worklist color_pos(g->v_size);
1155 dejavu::worklist color_deg(g->v_size);
1156 dejavu::worklist hub_vertex_position(g->v_size);
1157 dejavu::worklist color_canonical_v(g->v_size);
1158 dejavu::worklist filter(g->v_size);
1159 dejavu::worklist path_list(g->v_size);
1160 dejavu::worklist path(g->v_size);
1161 dejavu::worklist connected_paths(g->e_size);
1162 dejavu::worklist connected_endpoints(g->e_size);
1163 dejavu::markset duplicate_endpoints(g->v_size);
1164
1165 // collect and count endpoints
1166 int total_paths = 0;
1167
1168 for (int i = 0; i < g->v_size; ++i) {
1169 if(g->d[i] == 2) {
1170 hub_vertex_position[i] = -1;
1171 if(!recovery_strings[translate_back(i)].empty()) {
1172 path_done.set(i); // not ideal...
1173 }
1174 if(path_done.get(i))
1175 continue;
1176 const int n1 = g->e[g->v[i] + 0];
1177 const int n2 = g->e[g->v[i] + 1];
1178 // n1 or n2 is endpoint? then walk to other endpoint and collect information...
1179 if(g->d[n1] != 2) {
1180 const auto other_endpoint = walk_to_endpoint(g, i, n1, &path_done);
1181 if(other_endpoint.first == n1) // big self-loop
1182 continue;
1183 connected_paths[g->v[n1] + endpoint_cnt[n1]] = i;
1184 connected_endpoints[g->v[n1] + endpoint_cnt[n1]] = other_endpoint.first;
1185 ++endpoint_cnt[n1];
1186 connected_paths[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] =
1187 other_endpoint.second;
1188 connected_endpoints[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] = n1;
1189 ++endpoint_cnt[other_endpoint.first];
1190 dej_assert(other_endpoint.first != n1);
1191 dej_assert(g->d[other_endpoint.first] != 2);
1192 dej_assert(n1 != other_endpoint.first);
1193 ++total_paths;
1194 } else if(g->d[n2] != 2) {
1195 const auto other_endpoint = walk_to_endpoint(g, i, n2, &path_done);
1196 if(other_endpoint.first == n2) // big self-loop
1197 continue;
1198 connected_paths[g->v[n2] + endpoint_cnt[n2]] = i;
1199 connected_endpoints[g->v[n2] + endpoint_cnt[n2]] = other_endpoint.first;
1200 ++endpoint_cnt[n2];
1201 connected_paths[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] =
1202 other_endpoint.second;
1203 connected_endpoints[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] = n2;
1204 ++endpoint_cnt[other_endpoint.first];
1205 dej_assert(other_endpoint.first != n2);
1206 dej_assert(g->d[other_endpoint.first] != 2);
1207 dej_assert(n2 != other_endpoint.first);
1208 ++total_paths;
1209 }
1210 }
1211 }
1212
1213 // let's not apply this reduction unless there is a substantial amount of degree 2 vertices -- performing
1214 // the technique adds some bloat to the lifting process, so we should not overdo it
1215 if(total_paths < g->v_size/10) return;
1216
1217 recovery_edge_adjacent.resize(domain_size);
1218 path_done.reset();
1219
1220 // iterate over color classes
1221 for(int i = 0; i < g->v_size;) {
1222 const int color = i;
1223 const int color_size = c.ptn[color] + 1;
1224 i += color_size;
1225 const int test_vertex = c.lab[color];
1226 const int endpoints = endpoint_cnt[test_vertex];
1227
1228 for(int j = 0; j < color_size; ++j) {
1229 dej_assert(endpoint_cnt[c.lab[color + j]] == endpoints);
1230 }
1231
1232 // only want to look at endpoints of paths
1233 if(endpoints == 0) continue;
1234
1235 color_test.reset();
1236 color_unique.reset();
1237
1238 // only interested in paths with non-unique color, otherwise we could use unique endpoint algorithm
1239 // check which neighbouring paths have non-unique color
1240 for(int j = 0; j < endpoints; ++j) {
1241 const int neighbour = connected_paths[g->v[test_vertex] + j];
1242
1243 dej_assert(g->d[neighbour] == 2);
1244 const int neighbour_col = c.vertex_to_col[neighbour];
1245 if(color_test.get(neighbour_col) && !path_done.get(neighbour)) {
1246 ++color_deg[neighbour_col];
1247 color_unique.set(neighbour_col); // means "not unique"
1248 } else {
1249 color_deg[neighbour_col] = 1;
1250 }
1251 color_test.set(neighbour_col);
1252 }
1253
1254 // Make sure there are no duplicate endpoints, i.e., paths going from the same vertex to the same
1255 // vertex!
1256 bool duplicate_endpoint_flag = false;
1257 for(int j = 0; j < color_size; ++j) {
1258 const int endpt_test_vertex = c.lab[color + j];
1259 duplicate_endpoints.reset();
1260 duplicate_endpoints.set(endpt_test_vertex); // no self-loops! tricky case
1261 dej_assert(endpoint_cnt[endpt_test_vertex] == endpoints);
1262 for (int k = 0; k < endpoints; ++k) {
1263 const int endpoint = connected_endpoints[g->v[endpt_test_vertex] + k];
1264 if(duplicate_endpoints.get(endpoint)) {
1265 duplicate_endpoint_flag = true;
1266 break;
1267 }
1268 duplicate_endpoints.set(endpoint);
1269 }
1270 if(duplicate_endpoint_flag) break;
1271 }
1272
1273 // There were duplicate endpoints, so we should stop with this color class!
1274 if(duplicate_endpoint_flag) continue;
1275
1276 filter.reset();
1277 // Filter to indices with non-unique colors
1278 for(int j = 0; j < endpoints; ++j) {
1279 const int neighbour = connected_paths[g->v[test_vertex] + j];
1280 dej_assert(g->d[neighbour] == 2);
1281 const int neighbour_col = c.vertex_to_col[neighbour];
1282 const int endpoint = connected_endpoints[g->v[test_vertex] + j];
1283 dej_assert(g->d[endpoint] != 2);
1284 const int endpoint_col = c.vertex_to_col[endpoint];
1285 const int endpoint_col_sz = c.ptn[endpoint_col] + 1;
1286 if(color_unique.get(neighbour_col) && color != endpoint_col &&
1287 endpoint_col_sz >= color_size) { // if unique
1288 filter.push_back(j); // add index to filter
1289 }
1290 }
1291
1292
1293 path.reset();
1294 color_test.reset();
1295 color_unique.reset();
1296
1297 int use_pos = 0;
1298 for(int k = 0; k < filter.cur_pos; ++k) {
1299 const int filter_col = c.vertex_to_col[connected_paths[g->v[test_vertex] + filter[k]]];
1300 if(!color_unique.get(filter_col)) {
1301 color_pos[filter_col] = use_pos;
1302 color_unique.set(filter_col);
1303 use_pos += color_deg[filter_col];
1304 }
1305 }
1306
1307 const int num_paths = filter.cur_pos;
1308
1309 // do next steps for all vertices in color classes...
1310 for(int j = 0; j < color_size; ++j) {
1311 const int vertex = c.lab[color + j];
1312
1313 // reset color_deg to 0
1314 for(int k = 0; k < filter.cur_pos; ++k) {
1315 const int filter_col = c.vertex_to_col[connected_paths[g->v[test_vertex] + filter[k]]];
1316 color_deg[filter_col] = 0;
1317 }
1318
1319 int sanity_check_num_paths = 0;
1320
1321 for(int k = 0; k < g->d[vertex]; ++k) {
1322 const int neighbour = g->e[g->v[vertex] + k];
1323 const int neighbour_col = c.vertex_to_col[neighbour];
1324 if(color_unique.get(neighbour_col)) {
1325 const int pos = color_pos[neighbour_col] + color_deg[neighbour_col];
1326 path_list[pos] = neighbour;
1327 dej_assert(g->d[neighbour] == 2);
1328 color_canonical_v[neighbour_col] = neighbour; // "hub vertex" used to emulate all the paths
1329 ++color_deg[neighbour_col];
1330 ++sanity_check_num_paths;
1331 }
1332 }
1333
1334 dej_assert(num_paths == sanity_check_num_paths);
1335
1336 for(int k = 0; k < num_paths; ++k) {
1337 const int path_start_vertex = path_list[k];
1338 dej_assert(g->d[path_start_vertex] == 2);
1339 if(path_done.get(path_start_vertex)) {
1340 continue;
1341 }
1342
1343 // get path and endpoint
1344 path.reset();
1345 const int other_endpoint = walk_to_endpoint_collect_path(g, path_start_vertex, vertex, &path);
1346 dej_assert(path.cur_pos > 0);
1347 dej_assert(vertex != other_endpoint);
1348 dej_assert(other_endpoint != path_start_vertex);
1349
1350
1351 const int hub_vertex = color_canonical_v[c.vertex_to_col[path_start_vertex]];
1352 dej_assert(hub_vertex >= 0);
1353 dej_assert(!del.get(hub_vertex));
1354 dej_assert(g->d[hub_vertex] == 2);
1355 dej_assert(is_adjacent(g, hub_vertex, vertex));
1356
1357 // mark path for deletion
1358 for(int l = 0; l < path.cur_pos; ++l) {
1359 const int del_v = path[l];
1360 dej_assert(g->d[del_v] == 2);
1361 dej_assert(!del.get(del_v));
1362 del.set(del_v);
1363 dej_assert(!path_done.get(del_v));
1364 path_done.set(del_v);
1365 }
1366 del.unset(hub_vertex); // don't delete canonical vertex
1367 dej_assert(!del.get(hub_vertex));
1368
1369 // connect endpoints of path to hub vertex (the canonical vertex)
1370 // make sure not do double up on hub_vertex original path
1371 if(!is_adjacent(g, hub_vertex, other_endpoint)) {
1372 add_edge_buff[other_endpoint].push_back(hub_vertex);
1373 add_edge_buff_act.set(other_endpoint);
1374 add_edge_buff[hub_vertex].push_back(other_endpoint);
1375 add_edge_buff_act.set(hub_vertex);
1376 }
1377
1378 // write path into recovery_strings
1379 const int hub_vertex_orig = translate_back(hub_vertex);
1380
1381 // mark hub vertex in recovery string such that it gets mapped to nothing
1382 // TODO should this be handled by translate_back? we can "translate_back" to \epsilon?
1383 // TODO just collect hub vertices and "handle this at the end"?
1384 if(recovery_strings[hub_vertex_orig].empty())
1385 recovery_strings[hub_vertex_orig].push_back(INT32_MAX);
1386
1387 std::vector<int> recovery;
1388 for (int l = 0; l < path.cur_pos; ++l) {
1389 dej_assert(path[l] >= 0);
1390 dej_assert(path[l] < g->v_size);
1391 const int path_v_orig = translate_back(path[l]);
1392 //if(hub_vertex_orig == path_v_orig) continue;
1393 dej_assert(path_v_orig >= 0);
1394 dej_assert(path_v_orig < domain_size);
1395 recovery.push_back(path_v_orig);
1396 dej_assert(path_v_orig != hub_vertex_orig? recovery_strings[path_v_orig].size() == 0: true);
1397 }
1398
1399 recovery_attach_to_edge(translate_back(vertex), translate_back(other_endpoint), recovery);
1400 }
1401 }
1402 }
1403 }
1404
1405 void red_deg2_densifysc1(dejavu::sgraph *g, int *colmap) {
1406 if (g->v_size <= 1 || h_deact_deg2) return;
1407
1408 //coloring col;
1409 g->initialize_coloring(&c, colmap);
1410 add_edge_buff_act.reset();
1411 for (int i = 0; i < g->v_size; ++i) add_edge_buff[i].clear();
1412
1413 del.reset();
1414 worklist_deg1.reset();
1415
1416 dejavu::worklist endpoint_cnt(g->v_size);
1417 for (int i = 0; i < g->v_size; ++i) endpoint_cnt.push_back(0);
1418
1419 dejavu::markset path_done(g->v_size);
1420 dejavu::worklist filter(g->v_size);
1421 dejavu::worklist path_list(g->v_size);
1422 dejavu::worklist path(g->v_size);
1423 dejavu::worklist connected_paths(g->e_size);
1424 dejavu::worklist connected_endpoints(g->e_size);
1425 dejavu::markset duplicate_endpoints(g->v_size);
1426
1427 // collect and count endpoints
1428 int total_paths = 0;
1429
1430 for (int i = 0; i < g->v_size; ++i) {
1431 if(g->d[i] == 2) {
1432 if(path_done.get(i))
1433 continue;
1434 const int n1 = g->e[g->v[i] + 0];
1435 const int n2 = g->e[g->v[i] + 1];
1436 // n1 or n2 is endpoint? then walk to other endpoint and collect information...
1437 if(g->d[n1] != 2 && g->d[n2] != 2) { // only want paths of length 1
1438 const auto other_endpoint = walk_to_endpoint(g, i, n1, &path_done);
1439 if(other_endpoint.first == n1) // big self-loop
1440 continue;
1441 connected_paths[g->v[n1] + endpoint_cnt[n1]] = i;
1442 connected_endpoints[g->v[n1] + endpoint_cnt[n1]] = other_endpoint.first;
1443 ++endpoint_cnt[n1];
1444 connected_paths[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] =
1445 other_endpoint.second;
1446 connected_endpoints[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] = n1;
1447 ++endpoint_cnt[other_endpoint.first];
1448 dej_assert(other_endpoint.first != n1);
1449 dej_assert(g->d[other_endpoint.first] != 2);
1450 dej_assert(n1 != other_endpoint.first);
1451 ++total_paths;
1452 }
1453 }
1454 }
1455
1456 // let's not apply this reduction unless there is a substantial amount of degree 2 vertices -- performing
1457 // the technique adds some bloat to the lifting process, so we should not overdo it
1458 if(total_paths < g->v_size/10) return;
1459
1460 recovery_edge_adjacent.resize(domain_size);
1461 path_done.reset();
1462
1463 // iterate over color classes
1464 for(int i = 0; i < g->v_size;) {
1465 const int color = i;
1466 const int color_size = c.ptn[color] + 1;
1467 i += color_size;
1468 const int test_vertex = c.lab[color];
1469 const int endpoints = endpoint_cnt[test_vertex];
1470
1471 for(int j = 0; j < color_size; ++j) {
1472 dej_assert(endpoint_cnt[c.lab[color + j]] == endpoints);
1473 }
1474
1475 // only want to look at endpoints of paths
1476 if(endpoints == 0) continue;
1477
1478 // only interested in paths with non-unique color, otherwise we could use unique endpoint algorithm
1479 // check which neighbouring paths have non-unique color
1480 int color_deg_single = 0;
1481 bool only_one = true;
1482 int relevant_neighbour_color = -1;
1483 for(int j = 0; j < endpoints; ++j) {
1484 const int neighbour = connected_paths[g->v[test_vertex] + j];
1485 const int endpoint = connected_endpoints[g->v[test_vertex] + j];
1486 dej_assert(g->d[endpoint] != 2);
1487 dej_assert(g->d[neighbour] == 2);
1488 const int endpoint_col = c.vertex_to_col[endpoint];
1489 const int neighbour_col = c.vertex_to_col[neighbour];
1490 if(!path_done.get(neighbour) && endpoint_col == color) {
1491 if(relevant_neighbour_color == -1) {
1492 relevant_neighbour_color = neighbour_col;
1493 }
1494 only_one = only_one && (relevant_neighbour_color == neighbour_col);
1495 color_deg_single += 1;
1496 }
1497 }
1498
1499 if(!only_one || color_deg_single == 0) continue;
1500
1501 bool duplicate_endpoint_flag = false;
1502 // Make sure there is no self-connection to own color already!
1503 for(int j = g->v[test_vertex]; j < g->v[test_vertex] + g->d[test_vertex]; ++j) {
1504 const int neighbour = g->e[j];
1505 if(c.vertex_to_col[neighbour] == color) {
1506 duplicate_endpoint_flag = true;
1507 break;
1508 }
1509 }
1510
1511 // Make sure there are no duplicate endpoints, i.e., paths going from the same vertex to the same
1512 // vertex!
1513 for(int j = 0; j < color_size; ++j) {
1514 const int endpt_test_vertex = c.lab[color + j];
1515 duplicate_endpoints.reset();
1516 duplicate_endpoints.set(endpt_test_vertex); // no self-loops! tricky case
1517 dej_assert(endpoint_cnt[endpt_test_vertex] == endpoints);
1518 for (int k = 0; k < endpoints; ++k) {
1519 const int neighbour = connected_paths[g->v[endpt_test_vertex] + k];
1520 const int neighbour_col = c.vertex_to_col[neighbour];
1521 if(neighbour_col != relevant_neighbour_color) continue;
1522 dej_assert(g->d[neighbour] == 2);
1523 const int endpoint = connected_endpoints[g->v[endpt_test_vertex] + k];
1524 dej_assert(c.vertex_to_col[endpoint] == color);
1525 if(duplicate_endpoints.get(endpoint)) {
1526 duplicate_endpoint_flag = true;
1527 break;
1528 }
1529 duplicate_endpoints.set(endpoint);
1530 }
1531 if(duplicate_endpoint_flag) break;
1532 }
1533
1534 // There were duplicate endpoints, so we should stop with this color class!
1535 if(duplicate_endpoint_flag) continue;
1536
1537 filter.reset();
1538 // Filter to indices with non-unique colors
1539 for(int j = 0; j < endpoints; ++j) {
1540 const int neighbour = connected_paths[g->v[test_vertex] + j];
1541 dej_assert(g->d[neighbour] == 2);
1542 const int neighbour_col = c.vertex_to_col[neighbour];
1543 if(neighbour_col == relevant_neighbour_color) { // if unique
1544 dej_assert(neighbour_col == relevant_neighbour_color);
1545 filter.push_back(j); // add index to filter
1546 }
1547 }
1548
1549 path.reset();
1550 const int num_paths = filter.cur_pos;
1551
1552 // do next steps for all vertices in color classes...
1553 for(int j = 0; j < color_size; ++j) {
1554 const int vertex = c.lab[color + j];
1555
1556 // reset color_deg to 0
1557 int next_pos = 0;
1558 int sanity_check_num_paths = 0;
1559
1560 for(int k = 0; k < g->d[vertex]; ++k) {
1561 const int neighbour = g->e[g->v[vertex] + k];
1562 const int neighbour_col = c.vertex_to_col[neighbour];
1563 if(neighbour_col == relevant_neighbour_color) {
1564 const int pos = next_pos;
1565 path_list[pos] = neighbour;
1566 dej_assert(g->d[neighbour] == 2);
1567 ++next_pos;
1568 ++sanity_check_num_paths;
1569 }
1570 }
1571
1572 dej_assert(num_paths == sanity_check_num_paths);
1573
1574 for(int k = 0; k < num_paths; ++k) {
1575 const int path_start_vertex = path_list[k];
1576 dej_assert(g->d[path_start_vertex] == 2);
1577 if(path_done.get(path_start_vertex)) {
1578 continue;
1579 }
1580
1581 // get path and endpoint
1582 path.reset();
1583 const int other_endpoint = walk_to_endpoint_collect_path(g, path_start_vertex, vertex, &path);
1584 dej_assert(path.cur_pos > 0);
1585 dej_assert(vertex != other_endpoint);
1586 dej_assert(other_endpoint != path_start_vertex);
1587
1588 // mark path for deletion
1589 for(int l = 0; l < path.cur_pos; ++l) {
1590 const int del_v = path[l];
1591 dej_assert(g->d[del_v] == 2);
1592 dej_assert(!del.get(del_v));
1593 del.set(del_v);
1594 dej_assert(!path_done.get(del_v));
1595 path_done.set(del_v);
1596 }
1597
1598 // connect endpoints of path to hub vertex (the canonical vertex)
1599 // make sure not do double up on hub_vertex original path
1600 if(!is_adjacent(g, vertex, other_endpoint)) {
1601 add_edge_buff[other_endpoint].push_back(vertex);
1602 add_edge_buff_act.set(other_endpoint);
1603 add_edge_buff[vertex].push_back(other_endpoint);
1604 add_edge_buff_act.set(vertex);
1605 }
1606
1607 // write path into recovery_strings
1608 std::vector<int> recovery;
1609 for (int l = 0; l < path.cur_pos; ++l) {
1610 dej_assert(path[l] >= 0);
1611 dej_assert(path[l] < g->v_size);
1612 const int path_v_orig = translate_back(path[l]);
1613 dej_assert(path_v_orig >= 0);
1614 dej_assert(path_v_orig < domain_size);
1615 recovery.push_back(path_v_orig);
1616 for(int f = 0; f < static_cast<int>(recovery_strings[path_v_orig].size()); ++f) {
1617 recovery.push_back(recovery_strings[path_v_orig][f]);
1618 }
1619 }
1620
1621 recovery_attach_to_edge(translate_back(vertex), translate_back(other_endpoint), recovery);
1622 }
1623 }
1624 }
1625 }
1626
1627 // color cycles according to their size
1628 // remove uniform colored cycles
1629 bool red_deg2_color_cycles(dejavu::sgraph *g, int *colmap) {
1630 //coloring col;
1631 g->initialize_coloring(&c, colmap);
1632 for(int i = 0; i < g->v_size; ++i) {
1633 colmap[i] = c.vertex_to_col[i];
1634 }
1635
1636 int cycles_recolored = 0;
1637
1638 dejavu::markset path_done(g->v_size);
1639 dejavu::worklist path(g->v_size);
1640
1641 for (int i = 0; i < g->v_size; ++i) {
1642 if(g->d[i] == 2) {
1643 if(path_done.get(i))
1644 continue;
1645 const int n1 = g->e[g->v[i] + 0];
1646 const int n2 = g->e[g->v[i] + 1];
1647
1648 if(g->d[n1] != 2 || g->d[n2] != 2)
1649 continue;
1650
1651 path.reset();
1652 const int cycle_length = walk_cycle(g, i, n1, &path_done, &path);
1653 if(cycle_length == -1) {
1654 continue;
1655 } else {
1656 cycles_recolored += 1;
1657 for(int j = 0; j < path.cur_pos; ++j) {
1658 colmap[path[j]] = colmap[path[j]] + g->v_size * cycle_length; // maybe this should receive a more elegant solution
1659 }
1660 }
1661 }
1662 }
1663
1664 if(cycles_recolored > 0) {
1665 g->initialize_coloring(&c, colmap);
1666 bool has_discrete = false;
1667 for(int i = 0; i < g->v_size && !has_discrete; ) {
1668 const int col_sz = c.ptn[i] + 1;
1669 has_discrete = has_discrete || (col_sz == 1);
1670 i += col_sz;
1671 }
1672 for(int i = 0; i < g->v_size; ++i) {
1673 colmap[i] = c.vertex_to_col[i];
1674 }
1675 return has_discrete;
1676 }
1677 return false;
1678 }
1679
1680 void red_deg2_trivial_connect(dejavu::sgraph *g, int *colmap) {
1681 if (g->v_size <= 1 || h_deact_deg2)
1682 return;
1683
1684 dejavu::ds::markset color_test(g->v_size);
1685
1686 dejavu::ds::markset color_unique(g->v_size);
1687
1688 //coloring col;
1689 g->initialize_coloring(&c, colmap);
1690
1691 add_edge_buff_act.reset();
1692 for (int i = 0; i < g->v_size; ++i) add_edge_buff[i].clear();
1693
1694 del.reset();
1695
1696 worklist_deg1.reset();
1697
1698 dejavu::ds::worklist endpoint_cnt(g->v_size);
1699 for (int i = 0; i < g->v_size; ++i) endpoint_cnt.push_back(0);
1700
1701 dejavu::ds::markset path_done(g->v_size);
1702 dejavu::ds::worklist color_pos(g->v_size);
1703 dejavu::ds::worklist not_unique(2*g->v_size);
1704 dejavu::ds::worklist not_unique_analysis(g->v_size);
1705 dejavu::ds::worklist path_list(g->v_size);
1707 dejavu::ds::worklist connected_paths(g->e_size);
1708 dejavu::ds::worklist connected_endpoints(g->e_size);
1709 dejavu::ds::worklist neighbour_list(g->v_size);
1710 dejavu::ds::worklist neighbour_to_endpoint(g->v_size);
1711
1712 for (int i = 0; i < g->v_size; ++i) {
1713 if(g->d[i] == 2) {
1714 if(path_done.get(i))
1715 continue;
1716 const int n1 = g->e[g->v[i] + 0];
1717 const int n2 = g->e[g->v[i] + 1];
1718 // n1 or n2 is endpoint? then walk to other endpoint and collect information...
1719 if(g->d[n1] != 2) {
1720 const auto other_endpoint = walk_to_endpoint(g, i, n1, &path_done);
1721 if(other_endpoint.first == n1) // big self-loop
1722 continue;
1723 connected_paths[g->v[n1] + endpoint_cnt[n1]] = i;
1724 connected_endpoints[g->v[n1] + endpoint_cnt[n1]] = other_endpoint.first;
1725 ++endpoint_cnt[n1];
1726 connected_paths[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] =
1727 other_endpoint.second;
1728 connected_endpoints[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] = n1;
1729 ++endpoint_cnt[other_endpoint.first];
1730 dej_assert(other_endpoint.first != n1);
1731 dej_assert(g->d[other_endpoint.first] != 2);
1732 dej_assert(n1 != other_endpoint.first);
1733 } else if(g->d[n2] != 2) {
1734 const auto other_endpoint = walk_to_endpoint(g, i, n2, &path_done);
1735 if(other_endpoint.first == n2) // big self-loop
1736 continue;
1737 connected_paths[g->v[n2] + endpoint_cnt[n2]] = i;
1738 connected_endpoints[g->v[n2] + endpoint_cnt[n2]] = other_endpoint.first;
1739 ++endpoint_cnt[n2];
1740 connected_paths[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] =
1741 other_endpoint.second;
1742 connected_endpoints[g->v[other_endpoint.first] + endpoint_cnt[other_endpoint.first]] = n2;
1743 ++endpoint_cnt[other_endpoint.first];
1744 dej_assert(other_endpoint.first != n2);
1745 dej_assert(g->d[other_endpoint.first] != 2);
1746 dej_assert(n2 != other_endpoint.first);
1747 }
1748 }
1749 }
1750
1751 path_done.reset();
1752
1753 // iterate over color classes
1754 for(int i = 0; i < g->v_size;) {
1755 const int color = i;
1756 const int color_size = c.ptn[color] + 1;
1757 i += color_size;
1758 const int test_vertex = c.lab[color];
1759 const int endpoints = endpoint_cnt[test_vertex];
1760
1761 if (endpoints == 0) {
1762 continue;
1763 }
1764
1765 color_test.reset();
1766 color_unique.reset();
1767
1768 // check which neighbouring paths have unique color
1769 for (int j = 0; j < endpoints; ++j) {
1770 const int neighbour = connected_paths[g->v[test_vertex] + j];
1771 const int neighbour_col = c.vertex_to_col[neighbour];
1772 if (color_test.get(neighbour_col)) {
1773 color_unique.set(neighbour_col); // means "not unique"
1774 }
1775 color_test.set(neighbour_col);
1776 }
1777
1778 not_unique.reset();
1779 // filter to indices with unique colors
1780 for (int j = 0; j < endpoints; ++j) {
1781 const int neighbour = connected_paths[g->v[test_vertex] + j];
1782 const int neighbour_col = c.vertex_to_col[neighbour];
1783 if (color_unique.get(neighbour_col)) { // if not unique
1784 not_unique.push_back(neighbour);
1785 dej_assert(connected_endpoints[g->v[test_vertex] + j] >= 0);
1786 dej_assert(connected_endpoints[g->v[test_vertex] + j] < g->v_size);
1787 not_unique.push_back(connected_endpoints[g->v[test_vertex] + j]);
1788 }
1789 }
1790
1791 color_test.reset();
1792 color_unique.reset();
1793
1794 // remove trivial connections
1795 for (int kk = 0; kk < not_unique.cur_pos; kk += 2) {
1796 const int endpoint = not_unique[kk + 1];
1797 const int endpoint_col = c.vertex_to_col[endpoint];
1798 const int neighbour = not_unique[kk];
1799 const int neighbour_col = c.vertex_to_col[neighbour];
1800 not_unique_analysis[endpoint_col] = 0;
1801 not_unique_analysis[neighbour_col] = 0;
1802 }
1803 for (int kk = 0; kk < not_unique.cur_pos; kk += 2) {
1804 const int endpoint = not_unique[kk + 1];
1805 const int endpoint_col = c.vertex_to_col[endpoint];
1806 const int neighbour = not_unique[kk];
1807 const int neighbour_col = c.vertex_to_col[neighbour];
1808 ++not_unique_analysis[endpoint_col];
1809 ++not_unique_analysis[neighbour_col];
1810 }
1811 for (int kk = 0; kk < not_unique.cur_pos; kk += 2) {
1812 const int neighbour = not_unique[kk];
1813 const int neighbour_col = c.vertex_to_col[neighbour];
1814 const int endpoint = not_unique[kk + 1];
1815 const int endpoint_col = c.vertex_to_col[endpoint];
1816 path.reset();
1817 if (!color_test.get(endpoint_col)) {
1818 color_test.set(endpoint_col);
1819 if (not_unique_analysis[endpoint_col] == not_unique_analysis[neighbour_col] &&
1820 not_unique_analysis[endpoint_col] == c.ptn[endpoint_col] + 1) {
1821 // check that path endpoints dont contain duplicates
1822 bool all_unique = true;
1823 color_unique.reset();
1824 for (int jj = 1; jj < not_unique.cur_pos; jj += 2) {
1825 const int _endpoint = not_unique[jj];
1826 const int _endpoint_col = c.vertex_to_col[endpoint];
1827 if (_endpoint_col == endpoint_col) {
1828 if (color_unique.get(_endpoint)) {
1829 all_unique = false;
1830 break;
1831 }
1832 color_unique.set(_endpoint);
1833 }
1834 }
1835
1836 // test_vertex connects to all vertices of endpoint_col!
1837 if (all_unique && color < endpoint_col) {
1838 const int path_col = c.vertex_to_col[neighbour];
1839 dej_assert(c.ptn[path_col] + 1 == (not_unique_analysis[endpoint_col] * color_size));
1840 dej_assert(c.ptn[endpoint_col] + 1 == not_unique_analysis[endpoint_col]);
1841
1842
1843 int endpoint_neighbour_col = -1;
1844
1845 for(int jjj = 0; jjj < color_size; ++jjj ) {
1846 const int col1_vertj = c.lab[color + jjj];
1847
1848 // now go through and remove paths...
1849 neighbour_list.reset();
1850 for (int jj = 0; jj < g->d[col1_vertj]; ++jj) {
1851 const int _neighbour = g->e[g->v[col1_vertj] + jj];
1852 const int _neighbour_col = c.vertex_to_col[_neighbour];
1853 //const int _neighbour_col_sz = col.ptn[_neighbour_col] + 1;
1854
1855 if (_neighbour_col == path_col) {
1856 neighbour_list.push_back(_neighbour);
1857 const auto other_endpoint =
1858 walk_to_endpoint(g, _neighbour, col1_vertj, nullptr);
1859 neighbour_to_endpoint[_neighbour] = other_endpoint.first;
1860 if(endpoint_neighbour_col == -1) {
1861 endpoint_neighbour_col = c.vertex_to_col[other_endpoint.second];
1862 }
1863 }
1864 }
1865
1866 neighbour_list.sort_after_map(neighbour_to_endpoint.get_array());
1867
1868 // now go through and remove paths...
1869 for (int jj = 0; jj < neighbour_list.cur_pos; ++jj) {
1870 const int _neighbour = neighbour_list[jj];
1871
1872 path.reset();
1873 int _endpoint = walk_to_endpoint_collect_path(g, _neighbour,
1874 col1_vertj,
1875 &path);
1876
1877 // mark path for deletion
1878 for (int l = 0; l < path.cur_pos; ++l) {
1879 const int del_v = path[l];
1880 dej_assert(g->d[del_v] == 2);
1881 dej_assert(!del.get(del_v));
1882 del.set(del_v);
1883 dej_assert(!path_done.get(del_v));
1884 path_done.set(del_v);
1885 }
1886
1887 const int vert_orig = translate_back(col1_vertj);
1888
1889 // TODO removed vertices must not contain negative values, need additional check
1890 // TODO or think about how to lift these properly
1891 recovery_strings[vert_orig].reserve(
1892 recovery_strings[vert_orig].size() +
1893 path.cur_pos);
1894 for (int l = 0; l < path.cur_pos; ++l) {
1895 dej_assert(path[l] >= 0);
1896 dej_assert(path[l] < g->v_size);
1897 const int path_v_orig = translate_back(path[l]);
1898 dej_assert(path_v_orig >= 0);
1899 dej_assert(path_v_orig < domain_size);
1900 recovery_strings[vert_orig].push_back(path_v_orig);
1901 for(size_t rsi = 0; rsi < recovery_strings[path_v_orig].size(); ++rsi) {
1902 recovery_strings[vert_orig].push_back(
1903 recovery_strings[path_v_orig][rsi]);
1904 }
1905 }
1906
1907
1908 // write path into recovery_string of _endpoint
1909 const int endpoint_orig = translate_back(_endpoint);
1910 recovery_strings[endpoint_orig].reserve(
1911 recovery_strings[endpoint_orig].size() +
1912 path.cur_pos);
1913 for (int l = 0; l < path.cur_pos; ++l) {
1914 dej_assert(path[l] >= 0);
1915 dej_assert(path[l] < g->v_size);
1916 const int path_v_orig = translate_back(path[l]);
1917 dej_assert(path_v_orig >= 0);
1918 dej_assert(path_v_orig < domain_size);
1919 recovery_strings[endpoint_orig].push_back(-path_v_orig);
1920 for(size_t rsi = 0; rsi < recovery_strings[path_v_orig].size(); ++rsi) {
1921 recovery_strings[endpoint_orig].push_back(
1922 -abs(recovery_strings[path_v_orig][rsi]));
1923 }
1924 }
1925
1926 dej_assert(c.vertex_to_col[_endpoint] == endpoint_col);
1927 }
1928 }
1929 }
1930 }
1931 }
1932 }
1933 }
1934 }
1935
1936 // reduce vertices of degree 1 and 0, outputs corresponding automorphisms
1937 void red_deg10_assume_cref(dejavu::sgraph *g, int *colmap, dejavu_hook* hook) {
1938 if (h_deact_deg1) return;
1939
1940 g_old_v.clear();
1941 g_old_v.reserve(g->v_size);
1942 bool has_01 = false;
1943 for (int i = 0; i < g->v_size; ++i) {
1944 const int d = g->d[i];
1945 has_01 = has_01 || (d == 0) || (d == 1);
1946 g_old_v.push_back(d);
1947 }
1948 if(!has_01) return;
1949
1950 worklist_deg0.reset();
1951 worklist_deg1.reset();
1952
1953 dejavu::markset is_parent(g->v_size);
1954 dejavu::worklist pair_match(g->v_size);
1955 dejavu::worklist parentlist(g->v_size);
1956 dejavu::worklist childcount(g->v_size);
1957 for (int i = 0; i < g->v_size; ++i)
1958 childcount.push_back(0);
1959
1960 dejavu::worklist childcount_prev(g->v_size);
1961 for (int i = 0; i < g->v_size; ++i)
1962 childcount_prev.push_back(0);
1963
1965 dejavu::worklist map(g->v_size);
1966
1967 dej_assert(_automorphism_supp.cur_pos == 0);
1968
1969 g->initialize_coloring(&c, colmap);
1970 for (int i = 0; i < c.domain_size;) {
1971 const int v = c.lab[i];
1972 switch (g_old_v[v]) {
1973 case 0:
1974 worklist_deg0.push_back(v);
1975 break;
1976 case 1:
1977 if (c.ptn[c.vertex_to_col[v]] > 0)
1978 worklist_deg1.push_back(v);
1979 break;
1980 default:
1981 break;
1982 }
1983 i += c.ptn[i] + 1;
1984 }
1985
1986 while (!worklist_deg1.empty()) {
1987 const int v_child = worklist_deg1.pop_back();
1988 if (del.get(v_child))
1989 continue;
1990 if (g_old_v[v_child] != 1)
1991 continue;
1992
1993 const int v_child_col = c.vertex_to_col[v_child];
1994 const int child_col_sz = c.ptn[v_child_col] + 1;
1995 bool is_pairs = false;
1996 bool permute_parents_instead = false;
1997 if (child_col_sz == 1) {
1998 del.set(v_child);
1999 continue;
2000 } else {
2001 parentlist.reset();
2002 is_parent.reset();
2003 //int last_parent_child_count = -1;
2004 for (int i = v_child_col; i < v_child_col + child_col_sz; ++i) {
2005 int child = c.lab[i];
2006
2007 // search for parent
2008 const int e_pos_child = g->v[child];
2009 int parent = g->e[e_pos_child];
2010
2011 if (is_pairs && del.get(child))
2012 continue;
2013
2014 int search_parent = 0;
2015 while (del.get(parent)) {
2016 ++search_parent;
2017 parent = g->e[e_pos_child + search_parent];
2018 }
2019
2020 dej_assert(is_pairs ? c.vertex_to_col[parent] == c.vertex_to_col[child] : true);
2021 if (c.vertex_to_col[parent] == c.vertex_to_col[child]) {
2022 is_pairs = true;
2023 del.set(child);
2024 del.set(parent);
2025 pair_match[child] = parent;
2026 pair_match[parent] = child;
2027 if (parent < child) {
2028 parentlist.push_back(parent);
2029 } else {
2030 parentlist.push_back(child);
2031 }
2032 continue;
2033 }
2034
2035 del.set(child);
2036
2037 // save canonical info for parent
2038 edge_scratch[g->v[parent] + childcount[parent]] = child;
2039
2040 ++childcount[parent];
2041
2042 if (!is_parent.get(parent)) {
2043 is_parent.set(parent);
2044 childcount_prev[parent] = childcount[parent] - 1;
2045 parentlist.push_back(parent);
2046 }
2047
2048 // adjust parent degree
2049 g_old_v[parent] -= 1;
2050 if (g_old_v[parent] == 1 && i == v_child_col) {
2051 worklist_deg1.push_back(parent);
2052 } else if (g_old_v[parent] == 0 && i == v_child_col) {
2053 worklist_deg0.push_back(parent);
2054 }
2055
2056 dej_assert(g_old_v[parent] >= 0);
2057 }
2058 }
2059
2060 if (is_pairs) {
2061 for (int j = 0; j < parentlist.cur_pos; ++j) {
2062 const int first_pair_parent = parentlist[j];
2063 const int pair_from = first_pair_parent;
2064 const int pair_to = pair_match[pair_from];
2065
2066 stack1.reset();
2067 map.reset();
2068 map.push_back(pair_from);
2069 stack1.push_back(std::pair<int, int>(g->v[pair_from], g->v[pair_from] + childcount[pair_from]));
2070 while (!stack1.empty()) {
2071 std::pair<int, int> from_to = stack1.pop_back();
2072 int from = from_to.first;
2073 const int to = from_to.second;
2074 for (int f = from; f < to; ++f) {
2075 const int next = edge_scratch[f];
2076 //const int next = g->e[f];
2077 const int from_next = g->v[next];
2078 const int to_next = g->v[next] + childcount[next];
2079 map.push_back(next);
2080 dej_assert(next != pair_to);
2081 if (from_next != to_next)
2082 stack1.push_back(std::pair<int, int>(from_next, to_next));
2083 }
2084 }
2085
2087
2088 dej_assert(c.vertex_to_col[pair_from] == c.vertex_to_col[pair_to]);
2089 dej_assert(pair_from != pair_to);
2090 int pos = 0;
2091
2092 //automorphism_supp.reset();
2093 // descending shared_tree of child_to while writing automorphism
2094 stack1.reset();
2095 dej_assert(map[pos] != pair_to);
2096 const int v_to_1 = pair_to;
2097 const int v_from_1 = map[pos];
2098 dej_assert(automorphism[v_to_1] == v_to_1);
2099 dej_assert(automorphism[v_from_1] == v_from_1);
2100
2101 _automorphism[v_from_1] = v_to_1;
2102 _automorphism[v_to_1] = v_from_1;
2103 _automorphism_supp.push_back(v_from_1);
2104 _automorphism_supp.push_back(v_to_1);
2105
2106 ++pos;
2107 // child_to and child_from could have canonical strings when translated back
2108 dej_assert(childcount[pair_to] == childcount[pair_from]);
2109 stack1.push_back(std::pair<int, int>(g->v[pair_to], g->v[pair_to] + childcount[pair_to]));
2110 while (!stack1.empty()) {
2111 std::pair<int, int> from_to = stack1.pop_back();
2112 int from = from_to.first;
2113 const int to = from_to.second;
2114 for (int f = from; f < to; ++f) {
2115 const int next = edge_scratch[f];
2116 //const int next = g->e[f];
2117 const int from_next = g->v[next];
2118 const int to_next = g->v[next] + childcount[next];
2119 ++from;
2120 dej_assert(next >= 0);
2121 dej_assert(next < g->v_size);
2122 dej_assert(map[pos] != next);
2123
2124 const int v_to_2 = next;
2125 const int v_from_2 = map[pos];
2126
2127 dej_assert(_automorphism[v_to_2] == v_to_2);
2128 dej_assert(_automorphism[v_from_2] == v_from_2);
2129 _automorphism[v_from_2] = v_to_2;
2130 _automorphism[v_to_2] = v_from_2;
2131 _automorphism_supp.push_back(v_from_2);
2132 _automorphism_supp.push_back(v_to_2);
2133
2134 ++pos;
2135 if (from_next != to_next) // there was a semicolon here, should have been bug
2136 stack1.push_back(std::pair<int, int>(from_next, to_next));
2137 }
2138 }
2139
2140 dej_assert(pos == map.cur_pos);
2141
2142 dej_assert(g_old_v[pair_to] == 1);
2143 dej_assert(g_old_v[pair_from] == 1);
2144 dej_assert(del.get(pair_to));
2145 dej_assert(del.get(pair_from));
2146
2147 pre_hook(g->v_size, _automorphism.get_array(), _automorphism_supp.cur_pos,
2148 _automorphism_supp.get_array(), hook);
2149
2150 reset_automorphism(_automorphism.get_array(), _automorphism_supp.cur_pos,
2151 _automorphism_supp.get_array());
2152 _automorphism_supp.reset();
2153 }
2154
2155 for (int j = 0; j < parentlist.cur_pos; ++j) {
2156 const int first_pair_parent = parentlist[j];
2157 const int pair_from = first_pair_parent;
2158 const int pair_to = pair_match[pair_from];
2159
2160 const int original_parent = translate_back(first_pair_parent);
2161 const int original_pair_to = translate_back(pair_to);
2162 recovery_strings[original_parent].push_back(original_pair_to);
2163 for (size_t s = 0; s < recovery_strings[original_pair_to].size(); ++s)
2164 recovery_strings[original_parent].push_back(
2165 recovery_strings[original_pair_to][s]);
2166
2167 // also write stack of original_pair_to to canonical recovery string of original_parent, since
2168 // recovery_strings has not been updated with progress made in this routine
2169 stack1.reset();
2170 stack1.push_back(std::pair<int, int>(g->v[pair_to], g->v[pair_to] + childcount[pair_to]));
2171 while (!stack1.empty()) {
2172 std::pair<int, int> from_to = stack1.pop_back();
2173 int from = from_to.first;
2174 const int to = from_to.second;
2175 for (int f = from; f < to; ++f) {
2176 const int next = edge_scratch[f];
2177 //const int next = g->e[f];
2178 const int from_next = g->v[next];
2179 const int to_next = g->v[next] + childcount[next];
2180 const int orig_next = translate_back(next);
2181 recovery_strings[original_parent].push_back(orig_next);
2182 for (size_t s = 0; s < recovery_strings[orig_next].size(); ++s)
2183 recovery_strings[original_parent].push_back(
2184 recovery_strings[orig_next][s]);
2185 if (from_next != to_next)
2186 stack1.push_back(std::pair<int, int>(from_next, to_next));
2187 }
2188 }
2189 }
2190
2191 permute_parents_instead = true;
2192 }
2193
2194 while (!parentlist.empty()) {
2195 int parent, childcount_from, childcount_to, child_from;
2196 if (!permute_parents_instead) {
2197 parent = parentlist.pop_back();
2198 childcount_from = childcount_prev[parent];
2199 childcount_to = childcount[parent];
2200 } else {
2201 parent = -1;
2202 childcount_from = 0;
2203 childcount_to = parentlist.cur_pos;
2204 }
2205 // automorphism 1: long cycle (c1 ... cn)
2206 dej_assert(childcount_to - childcount_from > 0);
2207 if (childcount_to - childcount_from == 1) {
2208 if (permute_parents_instead)
2209 break;
2210 continue;
2211 }
2212 if (!permute_parents_instead) {
2213 child_from = edge_scratch[g->v[parent] + childcount_from];
2214 //child_from = g->e[g->v[parent] + childcount_from];
2215 } else {
2216 child_from = parentlist[0];
2217 }
2218
2219 // descending shared_tree of child_from while writing map
2220 stack1.reset();
2221 map.reset();
2222 map.push_back(child_from);
2223 stack1.push_back(std::pair<int, int>(g->v[child_from], g->v[child_from] + childcount[child_from]));
2224 while (!stack1.empty()) {
2225 std::pair<int, int> from_to = stack1.pop_back();
2226 int from = from_to.first;
2227 const int to = from_to.second;
2228 for (int f = from; f < to; ++f) {
2229 const int next = edge_scratch[f];
2230 //const int next = g->e[f];
2231 const int from_next = g->v[next];
2232 const int to_next = g->v[next] + childcount[next];
2233 map.push_back(next);
2234 dej_assert(next != parent);
2235 if (from_next != to_next)
2236 stack1.push_back(std::pair<int, int>(from_next, to_next));
2237 }
2238 }
2239 int j = 2;
2240 for (int i = childcount_from + 1; i < childcount_to; ++i) {
2242 ++j;
2243 int child_to;
2244 if (!permute_parents_instead) {
2245 child_to = edge_scratch[g->v[parent] + i];
2246 //child_to = g->e[g->v[parent] + i];
2247 } else {
2248 child_to = parentlist[i];
2249 }
2250 dej_assert(c.vertex_to_col[child_from] == c.vertex_to_col[child_to]);
2251 dej_assert(child_from != child_to);
2252 int pos = 0;
2253
2254 _automorphism_supp.reset();
2255
2256 // descending shared_tree of child_to while writing automorphism
2257 stack1.reset();
2258 dej_assert(map[pos] != child_to);
2259
2260 const int v_to_1 = child_to;
2261 const int v_from_1 = map[pos];
2262 dej_assert(_automorphism[v_to_1] == v_to_1);
2263 dej_assert(_automorphism[v_from_1] == v_from_1);
2264 _automorphism[v_from_1] = v_to_1;
2265 _automorphism[v_to_1] = v_from_1;
2266 _automorphism_supp.push_back(v_from_1);
2267 _automorphism_supp.push_back(v_to_1);
2268
2269 ++pos;
2270 // child_to and child_from could have canonical strings when translated back
2271 dej_assert(childcount[child_to] == childcount[child_from]);
2272 stack1.push_back(std::pair<int, int>(g->v[child_to], g->v[child_to] + childcount[child_to]));
2273 while (!stack1.empty()) {
2274 std::pair<int, int> from_to = stack1.pop_back();
2275 int from = from_to.first;
2276 const int to = from_to.second;
2277 for (int f = from; f < to; ++f) {
2278 const int next = edge_scratch[f];
2279 //const int next = g->e[f];
2280 const int from_next = g->v[next];
2281 const int to_next = g->v[next] + childcount[next];
2282 ++from;
2283 dej_assert(next >= 0);
2284 dej_assert(next < g->v_size);
2285 dej_assert(map[pos] != next);
2286
2287 const int v_to_2 = next;
2288 const int v_from_2 = map[pos];
2289 dej_assert(_automorphism[v_to_2] == v_to_2);
2290 dej_assert(_automorphism[v_from_2] == v_from_2);
2291 _automorphism[v_from_2] = v_to_2;
2292 _automorphism[v_to_2] = v_from_2;
2293 _automorphism_supp.push_back(v_from_2);
2294 _automorphism_supp.push_back(v_to_2);
2295
2296 ++pos;
2297 if (from_next != to_next) // there was a semicolon here, should have been bug
2298 stack1.push_back(std::pair<int, int>(from_next, to_next));
2299 }
2300 }
2301
2302 dej_assert(pos == map.cur_pos);
2303 dej_assert(g_old_v[child_to] == 1);
2304 dej_assert(g_old_v[child_from] == 1);
2305 dej_assert(del.get(child_to));
2306 dej_assert(del.get(child_from));
2307
2308 pre_hook(g->v_size, _automorphism.get_array(), _automorphism_supp.cur_pos,
2309 _automorphism_supp.get_array(), hook);
2310
2311 reset_automorphism(_automorphism.get_array(), _automorphism_supp.cur_pos,
2312 _automorphism_supp.get_array());
2313 _automorphism_supp.reset();
2314 }
2315 if (permute_parents_instead) {
2316 break; // :-)
2317 }
2318 }
2319 parentlist.reset();
2320 }
2321
2322 if (g->v_size > 1) {
2323 // search for parents that still remain in the graph, and rewrite childlist structure into canonical string
2324 for (int _i = 0; _i < g->v_size; ++_i) {
2325 if (!del.get(_i) && childcount[_i] > 0 && c.ptn[c.vertex_to_col[_i]] > 0) {
2326 // should it be childcount[_i] > 0 or childcount[_i] >= 0? was childcount[_i] >= 0 but that doesnt make sense?
2327 stack1.reset();
2328 stack1.push_back(std::pair<int, int>(g->v[_i], g->v[_i] + childcount[_i]));
2329 const int orig_i = translate_back(_i);
2330 recovery_strings[orig_i].reserve(
2331 recovery_strings[orig_i].size() + childcount[_i]);
2332 while (!stack1.empty()) {
2333 std::pair<int, int> from_to = stack1.pop_back();
2334 int from = from_to.first;
2335 const int to = from_to.second;
2336 if (from == to) {
2337 continue;
2338 } else {
2339 const int next = edge_scratch[from];
2340 //const int next = g->e[from];
2341 const int from_next = g->v[next];
2342 const int to_next = g->v[next] + childcount[next];
2343 ++from;
2344 const int orig_next = translate_back(next);
2345 recovery_strings[orig_i].push_back(orig_next);
2346 // write canonical recovery string of orig_next into orig_i, since it is now represented by
2347 // orig_i
2348 dej_assert(next != _i);
2349 dej_assert(orig_next != orig_i);
2350 for (size_t j = 0; j < recovery_strings[orig_next].size(); ++j)
2351 recovery_strings[orig_i].push_back(
2352 recovery_strings[orig_next][j]);
2353 stack1.push_back(std::pair<int, int>(from, to));
2354 stack1.push_back(std::pair<int, int>(from_next, to_next));
2355 }
2356 }
2357 }
2358 }
2359 }
2360
2361
2362 while (!worklist_deg0.empty()) {
2363 const int v_child = worklist_deg0.pop_back();
2364 if (del.get(v_child))
2365 continue;
2366 dej_assert(g_old_v[v_child] == 0);
2367
2368 is_parent.reset();
2369 const int v_child_col = c.vertex_to_col[v_child];
2370 const int child_col_sz = c.ptn[v_child_col] + 1;
2371 const int parent_from = c.lab[v_child_col];
2372 del.set(parent_from);
2373
2374 if (child_col_sz == 1)
2375 continue;
2376 int j = 2;
2377 for (int i = v_child_col + 1; i < v_child_col + child_col_sz; ++i) {
2379 ++j;
2380 const int parent_to = c.lab[i];
2381 dej_assert(g_old_v[parent_to] == 0);
2382 del.set(parent_to);
2383
2384 dej_assert(parent_from != parent_to);
2385
2386 dej_assert(_automorphism_supp.cur_pos == 0);
2387
2388 _automorphism[parent_to] = parent_from;
2389 _automorphism[parent_from] = parent_to;
2390 _automorphism_supp.push_back(parent_from);
2391 _automorphism_supp.push_back(parent_to);
2392
2393 pre_hook(g->v_size, _automorphism.get_array(), _automorphism_supp.cur_pos,
2394 _automorphism_supp.get_array(), hook);
2395
2396 reset_automorphism(_automorphism.get_array(), _automorphism_supp.cur_pos,
2397 _automorphism_supp.get_array());
2398 _automorphism_supp.reset();
2399 }
2400 }
2401 }
2402
2403 // perform edge flips according to quotient graph
2404 void red_quotient_edge_flip(dejavu::sgraph *g, int *colmap) { // TODO could still optimize further ...
2405 if (g->v_size <= 1) return;
2406
2407 del_e.reset();
2408 worklist_deg0.reset(); // serves as the "test vector"
2409
2410 //coloring test_col;
2411 g->initialize_coloring(&c, colmap);
2412
2413 for (int y = 0; y < g->v_size; ++y) worklist_deg0[y] = 0;
2414
2415 for (int i = 0; i < g->v_size;) {
2416 int v = c.lab[i];
2417 for (int f = g->v[v]; f < g->v[v] + g->d[v]; ++f) {
2418 const int v_neigh = g->e[f];
2419 worklist_deg0[c.vertex_to_col[v_neigh]] += 1;
2420 }
2421
2422 for (int ii = 0; ii < c.ptn[i] + 1; ++ii) {
2423 const int vx = c.lab[i + ii];
2424 bool skipped_none = true;
2425 for (int f = g->v[vx]; f < g->v[vx] + g->d[vx]; ++f) {
2426 const int v_neigh = g->e[f];
2427 if (worklist_deg0[c.vertex_to_col[v_neigh]] ==
2428 c.ptn[c.vertex_to_col[v_neigh]] + 1) {
2429 del_e.set(f); // mark edge for deletion (reverse edge is handled later automatically)
2430 skipped_none = false;
2431 }
2432 }
2433 if(skipped_none) break;
2434 }
2435
2436 for (int f = g->v[v]; f < g->v[v] + g->d[v]; ++f) {
2437 const int v_neigh = g->e[f];
2438 worklist_deg0[c.vertex_to_col[v_neigh]] = 0;
2439 }
2440
2441 i += c.ptn[i] + 1;
2442 }
2443 }
2444
2445 static void copy_coloring_to_colmap(const coloring *c, int *colmap) {
2446 for (int i = 0; i < c->domain_size; ++i) {
2447 colmap[i] = c->vertex_to_col[i];
2448 }
2449 }
2450
2451 // deletes vertices marked in 'del'
2452 // assumes that g->v points to g->e in ascending order
2453 void perform_del(dejavu::sgraph *g, int *colmap) {
2454 // copy some stuff
2455 g_old_v.clear();
2456 translate_layer_fwd.clear();
2457 translate_layer_bwd.clear();
2458
2459 translate_layer_bwd.reserve(backward_translation_layers[backward_translation_layers.size() - 1].size());
2460 translate_layer_fwd.reserve(g->v_size);
2461 for (size_t i = 0; i < backward_translation_layers[backward_translation_layers.size() - 1].size(); ++i)
2462 translate_layer_bwd.push_back(
2463 backward_translation_layers[backward_translation_layers.size() - 1][i]); // TODO this is shit
2464
2465 // create translation array from old graph to new graph vertices
2466 int cnt = 0;
2467 int new_vsize = 0;
2468 // int pos_now = 0;
2469 for (int i = 0; i < g->v_size; ++i) {
2470 if (!del.get(i)) {
2471 translate_layer_fwd.push_back(cnt);
2472 const int translate_back = translate_layer_bwd[translate_layer_fwd.size() - 1];
2473 backward_translation_layers[backward_translation_layers.size() - 1][cnt] = translate_back;
2474 ++cnt;
2475 ++new_vsize;
2476 } else {
2477 translate_layer_fwd.push_back(-1);
2478 }
2479 }
2480
2481 if (new_vsize == 0 || new_vsize == 1) {
2482 g->v_size = 0;
2483 g->e_size = 0;
2484 return;
2485 }
2486
2487 backward_translation_layers[backward_translation_layers.size() - 1].resize(cnt);
2488
2489 g_old_v.reserve(g->v_size);
2490 for (int i = 0; i < g->v_size; ++i) {
2491 g_old_v.push_back(g->v[i]);
2492 }
2493
2494 // make graph smaller using the translation array
2495 int epos = 0;
2496 for (int i = 0; i < g->v_size; ++i) {
2497 const int old_v = i;
2498 const int new_v = translate_layer_fwd[i];
2499
2500 if (new_v >= 0) {
2501 int new_d = 0;
2502 dej_assert(new_v < new_vsize);
2503 g->v[new_v] = epos;
2504 for (int j = g_old_v[old_v]; j < g_old_v[old_v] + g->d[old_v]; ++j) {
2505 const int ve = g->e[j]; // assumes ascending order!
2506 const int new_ve = translate_layer_fwd[ve];
2507 if (new_ve >= 0) {
2508 dej_assert(new_ve < new_vsize);
2509 dej_assert(new_ve >= 0);
2510 ++new_d;
2511 dej_assert(j >= epos);
2512 g->e[epos] = new_ve; // assumes ascending order!
2513 ++epos;
2514 }
2515 }
2516
2517 g_old_v[old_v] = new_d;
2518 }
2519 }
2520
2521 for (int i = 0; i < g->v_size; ++i) {
2522 const int old_v = i;
2523 const int new_v = translate_layer_fwd[i];
2524 dej_assert(old_v >= new_v);
2525 if (new_v >= 0) {
2526 dej_assert(old_v >= 0);
2527 dej_assert(new_v >= 0);
2528 dej_assert(old_v < g->v_size);
2529 dej_assert(new_v < new_vsize);
2530 colmap[new_v] = colmap[old_v];
2531 }
2532 }
2533
2534 for (int i = 0; i < g->v_size; ++i) {
2535 const int old_v = i;
2536 const int new_v = translate_layer_fwd[i];
2537 if (new_v >= 0) {
2538 g->d[new_v] = g_old_v[old_v];
2539 }
2540 }
2541
2542 dej_assert(new_vsize <= g->v_size);
2543 dej_assert(epos <= g->e_size);
2544
2545 g->e_size = epos;
2546 g->v_size = new_vsize;
2547 del.reset();
2548 }
2549
2550 // deletes vertices marked in 'del'
2551 // assumes that g->v points to g->e in ascending order
2552 void perform_del_edge(dejavu::sgraph *g) {
2553 if (g->v_size <= 1)
2554 return;
2555
2556 // int pre_esize = g->e_size;
2557 // copy some stuff
2558 g_old_v.clear();
2559 g_old_v.reserve(g->v_size);
2560
2561 for (int i = 0; i < g->v_size; ++i) {
2562 g_old_v.push_back(g->v[i]);
2563 }
2564
2565 // create translation array from old graph to new graph vertices
2566 // int cnt = 0;
2567 int new_vsize = g->v_size;
2568
2569 // make graph smaller using the translation array
2570 int epos = 0;
2571 for (int i = 0; i < g->v_size; ++i) {
2572 const int old_v = i;
2573 const int new_v = old_v;
2574
2575 if (new_v >= 0) {
2576 int new_d = 0;
2577 g->v[new_v] = epos;
2578 for (int j = g_old_v[old_v]; j < g_old_v[old_v] + g->d[old_v]; ++j) {
2579 const int ve = g->e[j];
2580 const int new_ve = ve;
2581 if (!del_e.get(j)) {
2582 dej_assert(new_ve < new_vsize);
2583 dej_assert(new_ve >= 0);
2584 ++new_d;
2585 g->e[epos] = new_ve;
2586 ++epos;
2587 }
2588 }
2589
2590 g->d[new_v] = new_d;
2591 }
2592 }
2593
2594 g->e_size = epos;
2595 g->v_size = new_vsize;
2596 }
2597
2598 // deletes vertices marked in 'del'
2599 // for vertices v where add_edge_buff_act[v] is set, in turn adds edges add_edge_buff_act[v]
2600 // assumes that g->v points to g->e in ascending order
2601 // assumes that degree of a vertex stays the same or gets smaller
2602 void perform_del_add_edge(dejavu::sgraph *g, int *colmap) {
2603 if (g->v_size <= 1)
2604 return;
2605
2606 // copy some stuff
2607 g_old_v.clear();
2608 translate_layer_fwd.clear();
2609 translate_layer_bwd.clear();
2610
2611 for (size_t i = 0; i < backward_translation_layers[backward_translation_layers.size() - 1].size(); ++i)
2612 translate_layer_bwd.push_back(backward_translation_layers[backward_translation_layers.size() - 1][i]);
2613
2614 // create translation array from old graph to new graph vertices
2615 int cnt = 0;
2616 int new_vsize = 0;
2617 for (int i = 0; i < g->v_size; ++i) {
2618 worklist_deg0[i] = colmap[i];
2619 if (!del.get(i)) {
2620 translate_layer_fwd.push_back(cnt);
2621 const int translate_back = translate_layer_bwd[translate_layer_fwd.size() - 1];
2622 backward_translation_layers[backward_translation_layers.size() - 1][cnt] = translate_back;
2623 ++cnt;
2624 ++new_vsize;
2625 } else {
2626 //translation_layers[fwd_ind].push_back(-1);
2627 translate_layer_fwd.push_back(-1);
2628 }
2629 }
2630
2631 if (new_vsize == g->v_size)
2632 return;
2633
2634 if (new_vsize == 0 || new_vsize == 1) {
2635 g->v_size = 0;
2636 g->e_size = 0;
2637 return;
2638 }
2639
2640 g_old_v.reserve(g->v_size);
2641
2642 for (int i = 0; i < g->v_size; ++i) {
2643 g_old_v.push_back(g->v[i]);
2644 }
2645
2646 backward_translation_layers[backward_translation_layers.size() - 1].resize(cnt);
2647
2648 // make graph smaller using the translation array
2649 int epos = 0;
2650 for (int i = 0; i < g->v_size; ++i) {
2651 const int old_v = i;
2652 const int new_v = translate_layer_fwd[old_v];
2653
2654 if (new_v >= 0) {
2655 int new_d = 0;
2656 g->v[new_v] = epos;
2657 for (int j = g_old_v[old_v]; j < g_old_v[old_v] + g->d[old_v]; ++j) {
2658 const int ve = g->e[j];
2659 const int new_ve = translate_layer_fwd[ve];
2660 if (new_ve >= 0) {
2661 dej_assert(new_ve < new_vsize);
2662 dej_assert(new_ve >= 0);
2663 ++new_d;
2664 g->e[epos] = new_ve;
2665 ++epos;
2666 }
2667 }
2668 if (add_edge_buff_act.get(old_v)) {
2669 while (!add_edge_buff[old_v].empty()) {
2670 const int edge_to_old = add_edge_buff[old_v].back();
2671 add_edge_buff[old_v].pop_back();
2672 //const int edge_to_old = add_edge_buff[old_v];
2673 dej_assert(add_edge_buff_act.get(edge_to_old));
2674 //const int edge_to_new = translation_layers[fwd_ind][edge_to_old];
2675 const int edge_to_new = translate_layer_fwd[edge_to_old];
2676 dej_assert(edge_to_old >= 0);
2677 dej_assert(edge_to_old <= domain_size);
2678 dej_assert(edge_to_new >= 0);
2679 dej_assert(edge_to_new <= new_vsize);
2680 ++new_d;
2681 g->e[epos] = edge_to_new;
2682 ++epos;
2683 }
2684 }
2685 g_old_v[old_v] = new_d;
2686 }
2687 }
2688
2689 for (int i = 0; i < g->v_size; ++i) {
2690 const int old_v = i;
2691 const int new_v = translate_layer_fwd[i];
2692 if (new_v >= 0) {
2693 g->d[new_v] = g_old_v[old_v];
2694 }
2695 }
2696
2697 g->e_size = epos;
2698
2699 // adapt colmap for remaining vertices
2700 for (int i = 0; i < g->v_size; ++i) {
2701 const int old_v = i;
2702 //const int new_v = translation_layers[fwd_ind][i];
2703 const int new_v = translate_layer_fwd[i];
2704 dej_assert(new_v < new_vsize);
2705 if (new_v >= 0) {
2706 dej_assert(colmap[old_v] >= 0);
2707 //assert(colmap[old_v] < domain_size);
2708 //colmap[new_v] = colmap[old_v];
2709 colmap[new_v] = worklist_deg0[old_v];
2710 }
2711 }
2712
2713 g->v_size = new_vsize;
2714
2715 for (int i = 0; i < g->v_size; ++i) {
2716 dej_assert(g->d[i] > 0 ? g->v[i] < g->e_size : true);
2717 dej_assert(g->d[i] > 0 ? g->v[i] >= 0 : true);
2718 dej_assert(g->d[i] >= 0);
2719 dej_assert(g->d[i] < g->v_size);
2720 }
2721 for (int i = 0; i < g->e_size; ++i) {
2722 dej_assert(g->e[i] < g->v_size);
2723 dej_assert(g->e[i] >= 0);
2724 }
2725
2726 add_edge_buff_act.reset();
2727 del.reset();
2728 }
2729
2730 // deletes vertices marked in 'del'
2731 // for vertices v where add_edge_buff_act[v] is set, in turn adds edges add_edge_buff_act[v]
2732 // assumes that g->v points to g->e in ascending order
2733 // assumes that degree of a vertex stays the same or gets smaller
2734 void perform_del_add_edge_general(dejavu::sgraph *g, int *colmap) {
2735 if (g->v_size <= 1)
2736 return;
2737
2738 // copy some stuff
2739 g_old_v.clear();
2740 g_old_e.clear();
2741 translate_layer_fwd.clear();
2742 translate_layer_bwd.clear();
2743
2744 for (size_t i = 0; i < backward_translation_layers[backward_translation_layers.size() - 1].size(); ++i)
2745 translate_layer_bwd.push_back(backward_translation_layers[backward_translation_layers.size() - 1][i]);
2746
2747 // create translation array from old graph to new graph vertices
2748 int cnt = 0;
2749 int new_vsize = 0;
2750 for (int i = 0; i < g->v_size; ++i) {
2751 worklist_deg0[i] = colmap[i];
2752 if (!del.get(i)) {
2753 translate_layer_fwd.push_back(cnt);
2754 const int translate_back = translate_layer_bwd[translate_layer_fwd.size() - 1];
2755 backward_translation_layers[backward_translation_layers.size() - 1][cnt] = translate_back;
2756 ++cnt;
2757 ++new_vsize;
2758 } else {
2759 //translation_layers[fwd_ind].push_back(-1);
2760 translate_layer_fwd.push_back(-1);
2761 }
2762 }
2763
2764 if (new_vsize == g->v_size)
2765 return;
2766
2767 if (new_vsize == 0 || new_vsize == 1) {
2768 g->v_size = 0;
2769 g->e_size = 0;
2770 return;
2771 }
2772
2773 g_old_v.reserve(g->v_size);
2774
2775 for (int i = 0; i < g->v_size; ++i) {
2776 g_old_v.push_back(g->v[i]);
2777 }
2778 for (int i = 0; i < g->e_size; ++i) {
2779 g_old_e.push_back(g->e[i]);
2780 }
2781
2782 backward_translation_layers[backward_translation_layers.size() - 1].resize(cnt);
2783
2784 // make graph smaller using the translation array
2785 int epos = 0;
2786 for (int i = 0; i < g->v_size; ++i) {
2787 const int old_v = i;
2788 const int new_v = translate_layer_fwd[old_v];
2789
2790 if (new_v >= 0) {
2791 int new_d = 0;
2792 g->v[new_v] = epos;
2793 for (int j = g_old_v[old_v]; j < g_old_v[old_v] + g->d[old_v]; ++j) {
2794 const int ve = g_old_e[j];
2795 const int new_ve = translate_layer_fwd[ve];
2796 if (new_ve >= 0) {
2797 dej_assert(new_ve < new_vsize);
2798 dej_assert(new_ve >= 0);
2799 ++new_d;
2800 g->e[epos] = new_ve;
2801 ++epos;
2802 }
2803 }
2804 if (add_edge_buff_act.get(old_v)) {
2805 while (!add_edge_buff[old_v].empty()) {
2806 const int edge_to_old = add_edge_buff[old_v].back();
2807 add_edge_buff[old_v].pop_back();
2808 //const int edge_to_old = add_edge_buff[old_v];
2809 dej_assert(add_edge_buff_act.get(edge_to_old));
2810 //const int edge_to_new = translation_layers[fwd_ind][edge_to_old];
2811 const int edge_to_new = translate_layer_fwd[edge_to_old];
2812 dej_assert(edge_to_old >= 0);
2813 dej_assert(edge_to_old <= domain_size);
2814 dej_assert(edge_to_new >= 0);
2815 dej_assert(edge_to_new <= new_vsize);
2816 ++new_d;
2817 g->e[epos] = edge_to_new;
2818 ++epos;
2819 }
2820 }
2821 g_old_v[old_v] = new_d;
2822 }
2823 }
2824
2825 for (int i = 0; i < g->v_size; ++i) {
2826 const int old_v = i;
2827 const int new_v = translate_layer_fwd[i];
2828 if (new_v >= 0) {
2829 g->d[new_v] = g_old_v[old_v];
2830 }
2831 }
2832
2833 g->e_size = epos;
2834
2835 // adapt colmap for remaining vertices
2836 for (int i = 0; i < g->v_size; ++i) {
2837 const int old_v = i;
2838 //const int new_v = translation_layers[fwd_ind][i];
2839 const int new_v = translate_layer_fwd[i];
2840 dej_assert(new_v < new_vsize);
2841 if (new_v >= 0) {
2842 dej_assert(colmap[old_v] >= 0);
2843 //assert(colmap[old_v] < domain_size);
2844 //colmap[new_v] = colmap[old_v];
2845 colmap[new_v] = worklist_deg0[old_v];
2846 }
2847 }
2848
2849 g->v_size = new_vsize;
2850
2851 for (int i = 0; i < g->v_size; ++i) {
2852 dej_assert(g->d[i] > 0 ? g->v[i] < g->e_size : true);
2853 dej_assert(g->d[i] > 0 ? g->v[i] >= 0 : true);
2854 dej_assert(g->d[i] >= 0);
2855 dej_assert(g->d[i] < g->v_size);
2856 }
2857 for (int i = 0; i < g->e_size; ++i) {
2858 dej_assert(g->e[i] < g->v_size);
2859 dej_assert(g->e[i] >= 0);
2860 }
2861
2862 add_edge_buff_act.reset();
2863 del.reset();
2864 }
2865
2866 // marks all discrete vertices in 'del'
2867 void mark_discrete_for_deletion(dejavu::sgraph *g, int *colmap) {
2868 //int discrete_cnt = 0;
2869 worklist_deg0.reset();
2870 for (int i = 0; i < domain_size; ++i) {
2871 worklist_deg0.push_back(0);
2872 }
2873 for (int i = 0; i < g->v_size; ++i) {
2874 dej_assert(colmap[i] < domain_size);
2875 worklist_deg0[colmap[i]]++;
2876 }
2877 for (int i = 0; i < g->v_size; ++i) {
2878 if (worklist_deg0[colmap[i]] == 1)
2879 del.set(i);
2880 }
2881 worklist_deg0.reset();
2882 }
2883
2884 // deletes all discrete vertices
2885 void perform_del_discrete(dejavu::sgraph *g, int *colmap) {
2886 if (g->v_size <= 1)
2887 return;
2888
2889 int discrete_cnt = 0;
2890 worklist_deg0.reset();
2891 for (int i = 0; i < domain_size; ++i) {
2892 worklist_deg0.push_back(0);
2893 }
2894 for (int i = 0; i < g->v_size; ++i) {
2895 dej_assert(colmap[i] < domain_size);
2896 worklist_deg0[colmap[i]]++;
2897 }
2898 for (int i = 0; i < g->v_size; ++i) {
2899 discrete_cnt += (worklist_deg0[colmap[i]] == 1);
2900 }
2901 if (discrete_cnt == g->v_size) {
2902 g->v_size = 0;
2903 g->e_size = 0;
2904 return;
2905 }
2906 if (discrete_cnt == 0) {
2907 return;
2908 }
2909
2910 // copy some stuff
2911 g_old_v.clear();
2912 translate_layer_fwd.clear();
2913 translate_layer_bwd.clear();
2914
2915 for (size_t i = 0; i < backward_translation_layers[backward_translation_layers.size() - 1].size(); ++i)
2916 translate_layer_bwd.push_back(backward_translation_layers[backward_translation_layers.size() - 1][i]);
2917
2918 g_old_v.reserve(g->v_size);
2919
2920 for (int i = 0; i < g->v_size; ++i) {
2921 g_old_v.push_back(g->v[i]);
2922 }
2923
2924 // create translation array from old graph to new graph vertices
2925 int cnt = 0;
2926 int new_vsize = 0;
2927 for (int i = 0; i < g->v_size; ++i) {
2928 if (worklist_deg0[colmap[i]] != 1) {
2929 translate_layer_fwd.push_back(cnt);
2930 const int translate_back = translate_layer_bwd[translate_layer_fwd.size() - 1];
2931 backward_translation_layers[backward_translation_layers.size() - 1][cnt] = translate_back;
2932 ++cnt;
2933 ++new_vsize;
2934 } else {
2935 translate_layer_fwd.push_back(-1);
2936 }
2937 }
2938
2939 backward_translation_layers[backward_translation_layers.size() - 1].resize(cnt);
2940
2941 // make graph smaller using the translation array
2942 int epos = 0;
2943 for (int i = 0; i < g->v_size; ++i) {
2944 const int old_v = i;
2945 const int new_v = translate_layer_fwd[i];
2946
2947 if (new_v >= 0) {
2948 int new_d = 0;
2949 dej_assert(new_v < new_vsize);
2950 g->v[new_v] = epos;
2951 for (int j = g_old_v[old_v]; j < g_old_v[old_v] + g->d[old_v]; ++j) {
2952 const int ve = g->e[j]; // assumes ascending order!
2953 const int new_ve = ve>=0?translate_layer_fwd[ve]:-1;
2954 if (new_ve >= 0) {
2955 dej_assert(new_ve < new_vsize);
2956 dej_assert(new_ve >= 0);
2957 ++new_d;
2958 dej_assert(j >= epos);
2959 g->e[epos] = new_ve; // assumes ascending order!
2960 ++epos;
2961 }
2962 }
2963
2964 g_old_v[old_v] = new_d;
2965 }
2966 }
2967
2968 for (int i = 0; i < g->v_size; ++i) {
2969 const int old_v = i;
2970 const int new_v = translate_layer_fwd[i];
2971 dej_assert(old_v >= new_v);
2972 if (new_v >= 0) {
2973 dej_assert(old_v >= 0);
2974 dej_assert(new_v >= 0);
2975 dej_assert(old_v < g->v_size);
2976 dej_assert(new_v < new_vsize);
2977 colmap[new_v] = colmap[old_v];
2978 }
2979 }
2980
2981 for (int i = 0; i < g->v_size; ++i) {
2982 const int old_v = i;
2983 const int new_v = translate_layer_fwd[i];
2984 if (new_v >= 0) {
2985 g->d[new_v] = g_old_v[old_v];
2986 }
2987 }
2988
2989 dej_assert(new_vsize <= g->v_size);
2990 dej_assert(epos <= g->e_size);
2991
2992 g->e_size = epos;
2993 g->v_size = new_vsize;
2994 del.reset();
2995 }
2996
2997 // given automorphism of reduced graph, reconstructs automorphism of the original graph
2998 // does not optimize for consecutive calls
2999 void pre_hook(int, const int *_aut, int _supp, const int *_aut_supp, dejavu_hook* hook) {
3000 if(hook == nullptr)
3001 return;
3002
3003 automorphism_supp.reset();
3004
3005 bool use_aux_auto = false;
3006
3007 for (int i = 0; i < _supp; ++i) {
3008 const int v_from = _aut_supp[i];
3009 const int orig_v_from = translate_back(v_from);
3010 const int v_to = _aut[v_from];
3011 dej_assert(v_from != v_to);
3012 const int orig_v_to = translate_back(v_to);
3013 dej_assert(v_from >= 0);
3014 dej_assert(v_to >= 0);
3015 dej_assert(orig_v_from < domain_size);
3016 dej_assert(orig_v_from >= 0);
3017 dej_assert(orig_v_to < domain_size);
3018 dej_assert(orig_v_to >= 0);
3019
3020 const bool added_vertex = !recovery_strings[orig_v_from].empty() &&
3021 recovery_strings[orig_v_from][0] == INT32_MAX;
3022
3023 dej_assert(automorphism[orig_v_from] == orig_v_from || added_vertex);
3024
3025 if(!added_vertex) {
3026 automorphism[orig_v_from] = orig_v_to;
3027 automorphism_supp.push_back(orig_v_from);
3028 } else {
3029 dej_assert(recovery_strings[orig_v_to].size() == 1);
3030 }
3031
3032 dej_assert(recovery_strings[orig_v_to].size() == recovery_strings[orig_v_from].size());
3033
3034 for (size_t j = 0; j < recovery_strings[orig_v_to].size(); ++j) {
3035 const int v_from_t = recovery_strings[orig_v_from][j];
3036 const int v_to_t = recovery_strings[orig_v_to][j];
3037 dej_assert((v_from_t == INT32_MAX) == (v_to_t == INT32_MAX));
3038 if(v_from_t == INT32_MAX) continue;
3039
3040 dej_assert(v_from_t > 0?v_to_t >= 0:true);
3041 dej_assert(v_to_t > 0?v_from_t >= 0:true);
3042 dej_assert(v_from_t < 0?v_to_t <= 0:true);
3043 dej_assert(v_to_t < 0?v_from_t <= 0:true);
3044 if(v_from_t >= 0 && v_to_t >= 0) {
3045 dej_assert(automorphism[v_from_t] == v_from_t);
3046 automorphism[v_from_t] = v_to_t;
3047 automorphism_supp.push_back(v_from_t);
3048 } else {
3049 const int abs_v_from_t = abs(v_from_t);
3050 const int abs_v_to_t = abs(v_to_t);
3051
3052 dej_assert(aux_automorphism[abs_v_from_t] == abs_v_from_t);
3053 aux_automorphism[abs_v_from_t] = abs_v_to_t;
3054 aux_automorphism_supp.push_back(abs_v_from_t);
3055
3056 use_aux_auto = true;
3057 }
3058 }
3059 }
3060
3061 if(use_aux_auto) {
3062 for(int i = 0; i < aux_automorphism_supp.cur_pos; ++i) {
3063 const int v_from = aux_automorphism_supp[i];
3064 before_move[v_from] = automorphism[aux_automorphism[v_from]];
3065 }
3066 for(int i = 0; i < aux_automorphism_supp.cur_pos; ++i) {
3067 const int v_from = aux_automorphism_supp[i];
3068 if(automorphism[v_from] == v_from) {
3069 automorphism_supp.push_back(v_from);
3070 }
3071 dej_assert(automorphism[v_from] != before_move[v_from]);
3072 automorphism[v_from] = before_move[v_from];
3073 }
3074 reset_automorphism(aux_automorphism.get_array(), aux_automorphism_supp.cur_pos,
3075 aux_automorphism_supp.get_array());
3076 aux_automorphism_supp.reset();
3077 }
3078
3079 const int end_pos = automorphism_supp.cur_pos;
3080
3081 if(!recovery_edge_attached.empty()) {
3082 for (int i = 0; i < end_pos; ++i) {
3083 recovery_attached_edges_to_automorphism(automorphism_supp[i], automorphism.get_array(),
3084 &automorphism_supp, &aux_automorphism, &before_move);
3085 }
3086 }
3087
3088 if(hook != nullptr)
3089 (*hook)(domain_size, automorphism.get_array(), automorphism_supp.cur_pos, automorphism_supp.get_array());
3090 reset_automorphism(automorphism.get_array(), automorphism_supp.cur_pos, automorphism_supp.get_array());
3091 automorphism_supp.reset();
3092 }
3093
3094 public:
3095 // given automorphism of reduced graph, reconstructs automorphism of the original graph
3096 void
3097 pre_hook_buffered(int _n, const int *_aut, int _supp, const int *_aut_supp, dejavu_hook* hook) {
3098 if(hook == nullptr) {
3099 return;
3100 }
3101
3102 meld_translation_layers();
3103 // TODO what this should really do is bake recovery_strings into a single string, and edge attachmenets to
3104 // TODO a proper non-linked graph structure
3105
3106 automorphism_supp.reset();
3107 bool use_aux_auto = false;
3108
3109 if(_supp >= 0) {
3110 for (int i = 0; i < _supp; ++i) {
3111 const int _v_from = _aut_supp[i];
3112 const int v_from = decomposer==nullptr?_v_from:decomposer->map_back(current_component, _v_from);
3113 dej_assert(v_from >= 0 && v_from < domain_size);
3114 const int orig_v_from = backward_translation[v_from];
3115 const int _v_to = _aut[_v_from];
3116 const int v_to = decomposer==nullptr?_v_to:decomposer->map_back(current_component, _v_to);
3117 dej_assert(v_from != v_to);
3118 const int orig_v_to = backward_translation[v_to];
3119 dej_assert((unsigned int)v_from < backward_translation.size());
3120 dej_assert(v_from >= 0);
3121 dej_assert((unsigned int)v_to < backward_translation.size());
3122 dej_assert(v_to >= 0);
3123 dej_assert(orig_v_from < domain_size);
3124 dej_assert(orig_v_from >= 0);
3125 dej_assert(orig_v_to < domain_size);
3126 dej_assert(orig_v_to >= 0);
3127 dej_assert(automorphism[orig_v_from] == orig_v_from);
3128 const int to_recovery_string_start_pt = baked_recovery_string_pt[v_to].first;
3129 const int to_recovery_string_end_pt = baked_recovery_string_pt[v_to].second;
3130 const int to_recovery_string_size = to_recovery_string_end_pt - to_recovery_string_start_pt;
3131 const int from_recovery_string_start_pt = baked_recovery_string_pt[v_from].first;
3132 if(to_recovery_string_size == 0 || baked_recovery_string[to_recovery_string_start_pt] != INT32_MAX) {
3133 automorphism[orig_v_from] = orig_v_to;
3134 automorphism_supp.push_back(orig_v_from);
3135 }
3136
3137 dej_assert((baked_recovery_string_pt[v_from].second - from_recovery_string_start_pt) ==
3138 to_recovery_string_size);
3139
3140 for (int j = 0; j < to_recovery_string_size; ++j) {
3141 const int v_from_t = baked_recovery_string[from_recovery_string_start_pt + j];
3142 const int v_to_t = baked_recovery_string[to_recovery_string_start_pt + j];
3143
3144 if(v_from_t == INT32_MAX) continue;
3145
3146 dej_assert(abs(v_from_t) >= 0);
3147 dej_assert(abs(v_from_t) < domain_size);
3148 dej_assert(abs(v_to_t) >= 0);
3149 dej_assert(abs(v_to_t) < domain_size);
3150
3151 dej_assert(v_from_t > 0?v_to_t >= 0:true);
3152 dej_assert(v_to_t > 0?v_from_t >= 0:true);
3153 dej_assert(v_from_t < 0?v_to_t <= 0:true);
3154 dej_assert(v_to_t < 0?v_from_t <= 0:true);
3155 if(v_from_t >= 0 && v_to_t >= 0) {
3156 dej_assert(automorphism[v_from_t] == v_from_t);
3157 automorphism[v_from_t] = v_to_t;
3158 automorphism_supp.push_back(v_from_t);
3159 } else {
3160 const int abs_v_from_t = abs(v_from_t);
3161 const int abs_v_to_t = abs(v_to_t);
3162
3163 aux_automorphism[abs_v_from_t] = abs_v_to_t;
3164 aux_automorphism_supp.push_back(abs_v_from_t);
3165
3166 use_aux_auto = true;
3167 }
3168 }
3169 }
3170 } else {
3171 for (int i = 0; i < _n; ++i) {
3172 const int _v_from = i;
3173 const int v_from = decomposer==nullptr?_v_from:decomposer->map_back(current_component, _v_from);
3174 const int orig_v_from = backward_translation[v_from];
3175 const int _v_to = _aut[_v_from];
3176 const int v_to = decomposer==nullptr?_v_to:decomposer->map_back(current_component, _v_to);
3177 if(v_from == v_to)
3178 continue;
3179 const int orig_v_to = backward_translation[v_to];
3180 dej_assert((unsigned int)v_from < backward_translation.size());
3181 dej_assert(v_from >= 0);
3182 dej_assert((unsigned int)v_to < backward_translation.size());
3183 dej_assert(v_to >= 0);
3184 dej_assert(orig_v_from < domain_size);
3185 dej_assert(orig_v_from >= 0);
3186 dej_assert(orig_v_to < domain_size);
3187 dej_assert(orig_v_to >= 0);
3188 dej_assert(automorphism[orig_v_from] == orig_v_from);
3189
3190 const int to_recovery_string_start_pt = baked_recovery_string_pt[v_to].first;
3191 const int to_recovery_string_end_pt = baked_recovery_string_pt[v_to].second;
3192 const int to_recovery_string_size = to_recovery_string_end_pt - to_recovery_string_start_pt;
3193 const int from_recovery_string_start_pt = baked_recovery_string_pt[v_from].first;
3194
3195 if(to_recovery_string_size == 0 || baked_recovery_string[to_recovery_string_start_pt] != INT32_MAX) {
3196 automorphism[orig_v_from] = orig_v_to;
3197 automorphism_supp.push_back(orig_v_from);
3198 }
3199
3200 dej_assert((baked_recovery_string_pt[v_from].second - from_recovery_string_start_pt) ==
3201 to_recovery_string_size);
3202
3203 for (int j = 0; j < to_recovery_string_size; ++j) {
3204 const int v_from_t = baked_recovery_string[from_recovery_string_start_pt + j];
3205 const int v_to_t = baked_recovery_string[to_recovery_string_start_pt + j];
3206
3207 if(v_from_t == INT32_MAX) continue;
3208
3209 dej_assert(v_from_t > 0?v_to_t >= 0:true);
3210 dej_assert(v_to_t > 0?v_from_t >= 0:true);
3211 dej_assert(v_from_t < 0?v_to_t <= 0:true);
3212 dej_assert(v_to_t < 0?v_from_t <= 0:true);
3213 if(v_from_t >= 0 && v_to_t >= 0) {
3214 dej_assert(automorphism[v_from_t] == v_from_t);
3215 automorphism[v_from_t] = v_to_t;
3216 automorphism_supp.push_back(v_from_t);
3217 } else {
3218 const int abs_v_from_t = abs(v_from_t);
3219 const int abs_v_to_t = abs(v_to_t);
3220
3221 aux_automorphism[abs_v_from_t] = abs_v_to_t;
3222 aux_automorphism_supp.push_back(abs_v_from_t);
3223
3224 use_aux_auto = true;
3225 }
3226 }
3227 }
3228 }
3229
3230 if(use_aux_auto) {
3231 for(int i = 0; i < aux_automorphism_supp.cur_pos; ++i) {
3232 const int v_from = aux_automorphism_supp[i];
3233 before_move[v_from] = automorphism[aux_automorphism[v_from]];
3234 }
3235 for(int i = 0; i < aux_automorphism_supp.cur_pos; ++i) {
3236 const int v_from = aux_automorphism_supp[i];
3237 if(automorphism[v_from] == v_from)
3238 automorphism_supp.push_back(v_from);
3239 automorphism[v_from] = before_move[v_from];
3240 }
3241 reset_automorphism(aux_automorphism.get_array(), aux_automorphism_supp.cur_pos,
3242 aux_automorphism_supp.get_array());
3243 aux_automorphism_supp.reset();
3244 }
3245
3246 const int end_pos = automorphism_supp.cur_pos;
3247
3248 if(edge_attached_information > 0) {
3249 for (int i = 0; i < end_pos; ++i) {
3250 recovery_attached_edges_to_automorphism(automorphism_supp[i], automorphism.get_array(),
3251 &automorphism_supp, &aux_automorphism, &before_move);
3252 }
3253 }
3254
3255 if(hook != nullptr) {
3256 (*hook)(domain_size, automorphism.get_array(), automorphism_supp.cur_pos, automorphism_supp.get_array());
3257 }
3258 reset_automorphism(automorphism.get_array(), automorphism_supp.cur_pos, automorphism_supp.get_array());
3259 automorphism_supp.reset();
3260 }
3261
3262 private:
3263
3264 // initialize some data structures
3265 void assure_ir_quotient_init(dejavu::sgraph *g) {
3266 if (!ir_quotient_component_init) {
3267 touched_color_cache.initialize(g->v_size);
3268 ir_quotient_component_init = true;
3269 }
3270 }
3271
3272 // deletes edges connected to discrete vertices, and marks discrete vertices for deletion later
3273 void del_discrete_edges_inplace(dejavu::sgraph *g, coloring *col) {
3274 int rem_edges = 0;
3275 int discrete_vert = 0;
3276 del.reset();
3277 for (int i = 0; i < col->domain_size;) {
3278 const int col_sz = col->ptn[i];
3279 if (col_sz == 0) {
3280 ++discrete_vert;
3281 del.set(col->lab[i]);
3282 }
3283 i += col_sz + 1;
3284 }
3285
3286 for (int v = 0; v < g->v_size; ++v) {
3287 if (del.get(v)) {
3288 dej_assert(col->ptn[col->vertex_to_col[v]] == 0);
3289 rem_edges += g->d[v];
3290 g->d[v] = 0;
3291 continue;
3292 }
3293
3294 for (int n = g->v[v]; n < g->v[v] + g->d[v];) {
3295 const int neigh = g->e[n];
3296 dej_assert(neigh >= 0 && neigh < g->v_size);
3297 if (del.get(neigh)) { // neigh == -1
3298 const int swap_neigh = g->e[g->v[v] + g->d[v] - 1];
3299 //g->e[g->v[v] + g->d[v] - 1] = neigh; // removed this operation because unnecessary?
3300 g->e[n] = swap_neigh;
3301 --g->d[v];
3302 ++rem_edges;
3303 } else {
3304 ++n;
3305 }
3306 }
3307 }
3308 dej_assert(rem_edges % 2 == 0);
3309 }
3310
3311 void order_according_to_color(dejavu::sgraph *g, int* colmap) {
3312 bool in_order = true;
3313 for(int i = 0; i < g->v_size-1 && in_order; ++i) in_order = in_order && (colmap[i] <= colmap[i+1]);
3314 if(in_order) {
3315 order_edgelist(g);
3316 return;
3317 }
3318
3319 g->initialize_coloring(&c, colmap);
3320 dejavu::worklist old_arr(g->v_size);
3321
3322 std::memcpy(old_arr.get_array(), g->v, g->v_size*sizeof(int));
3323 for(int j = 0; j < g->v_size; ++j) {
3324 g->v[j] = old_arr[c.lab[j]];
3325 }
3326
3327 std::memcpy(old_arr.get_array(), g->d, g->v_size*sizeof(int));
3328 for(int j = 0; j < g->v_size; ++j) {
3329 old_arr[j] = g->d[j];
3330 }
3331 for(int j = 0; j < g->v_size; ++j) {
3332 g->d[j] = old_arr[c.lab[j]];
3333 }
3334
3335
3336 for(int i = 0; i < g->v_size; ++i) {
3337 colmap[i] = c.vertex_to_col[c.lab[i]];
3338 }
3339
3340 for(int i = 0; i < g->v_size; ++i) {
3341 const int map_to = c.lab[i];
3342 old_arr[map_to] = i; // iso^-1
3343 }
3344
3345 for(int j = 0; j < g->e_size; ++j) {
3346 g->e[j] = old_arr[g->e[j]];
3347 }
3348
3349 dej_assert((int)backward_translation_layers[backward_translation_layers.size() - 1].size() == g->v_size);
3350 for(int i = 0; i < g->v_size; ++i) {
3351 old_arr[i] = backward_translation_layers[backward_translation_layers.size() - 1][i];
3352 }
3353
3354 for(int i = 0; i < g->v_size; ++i) {
3355 backward_translation_layers[backward_translation_layers.size() - 1][i] = old_arr[c.lab[i]];
3356 }
3357
3358 order_edgelist(g);
3359 }
3360
3361 public:
3362
3370 void reduce(dejavu::static_graph *g, dejavu_hook* hook, std::vector<preop> *schedule = nullptr) {
3371 reduce(g->get_sgraph(), g->get_coloring(), hook, schedule);
3372 }
3373
3382 void reduce(dejavu::sgraph *g, int *colmap, dejavu_hook* hook, const std::vector<preop> *schedule = nullptr) {
3383 const std::vector<preop> default_schedule =
3384 {deg01, qcedgeflip, deg01, twins, deg2ma, deg2ue, densify2}; // deg2ma, deg2ue, densify2
3385 // deg01, qcedgeflip, deg2ma, deg2ue, redloop, densify2
3386 //deg01, qcedgeflip, deg2ma, deg2ue, probe2qc, deg2ma, probeqc, deg2ma, redloop, densify2
3387
3388 if(schedule == nullptr) schedule = &default_schedule;
3389 if(print) print->print_header();
3390
3391 domain_size = g->v_size;
3392 saved_hook = hook;
3393 save_preprocessor = this;
3394 if(g->v_size == 0)
3395 return;
3396 g->dense = !(g->e_size < g->v_size || g->e_size / g->v_size < g->v_size / (g->e_size / g->v_size));
3397
3398 const int test_d = g->d[0];
3399 int k;
3400 for (k = 0; k < (g->v_size) && (g->d[k] == test_d); ++k);
3401
3402 int test_col = colmap[0];
3403 int l;
3404 for (l = 1; l < (g->v_size) && (colmap[l] == test_col); ++l);
3405
3406 if(k == g->v_size && l == g->v_size) {
3407 // graph is regular
3408 skipped_preprocessing = true;
3409 if(print) print->timer_print("regular", g->v_size, g->e_size);
3410 return;
3411 }
3412
3413 backward_translation_layers.emplace_back();
3414 const size_t back_ind = backward_translation_layers.size() - 1;
3415 translation_layers.emplace_back();
3416 backward_translation_layers[back_ind].reserve(g->v_size);
3417 for (int i = 0; i < g->v_size; ++i) backward_translation_layers[back_ind].push_back(i);
3418 edge_scratch.allocate(g->e_size);
3419
3420 if(g->v_size > 64) order_according_to_color(g, colmap);
3421 else order_edgelist(g);
3422 if(print) print->timer_print("order", g->v_size, g->e_size);
3423 g->initialize_coloring(&c, colmap);
3424
3425 const int pre_v_size = g->v_size;
3426 const int pre_e_size = g->e_size;
3427 const int pre_cells = c.cells;
3428
3429 dejavu::ir::refinement R_stack;
3430 if(R1 == nullptr) R1 = &R_stack;
3431
3432 R1->refine_coloring_first(g, &c, -1);
3433 const bool color_refinement_effective = pre_cells != c.cells;
3434
3435 if (c.cells == g->v_size) {
3436 //PRINT("(prep-red) graph is discrete");
3437 g->v_size = 0;
3438 g->e_size = 0;
3439 if(print) print->timer_print("discrete", g->v_size, g->e_size);
3440 return;
3441 }
3442
3443 add_edge_buff.clear();
3444 add_edge_buff.reserve(domain_size);
3445 for (int i = 0; i < domain_size; ++i)
3446 add_edge_buff.emplace_back(); // do this smarter... i know how many edges end up here
3447 add_edge_buff_act.initialize(domain_size);
3448
3449 translate_layer_fwd.reserve(g->v_size);
3450
3451 automorphism.allocate(g->v_size);
3452 for (int i = 0; i < g->v_size; ++i) {
3453 automorphism.push_back(i);
3454 }
3455 automorphism_supp.allocate(g->v_size);
3456 aux_automorphism.allocate(g->v_size);
3457 for (int i = 0; i < g->v_size; ++i) {
3458 aux_automorphism.push_back(i);
3459 }
3460 aux_automorphism_supp.allocate(g->v_size);
3461 _automorphism.allocate(g->v_size);
3462 _automorphism_supp.allocate(g->v_size);
3463 for (int i = 0; i < g->v_size; ++i)
3464 _automorphism[i] = i;
3465
3466 before_move.allocate(domain_size);
3467
3468 worklist_deg0.allocate(g->v_size);
3469 worklist_deg1.allocate(g->v_size);
3470
3471 domain_size = g->v_size;
3472
3473 // assumes colmap is array of length g->v_size
3474 del = dejavu::markset();
3475 del.initialize(g->v_size);
3476
3477 recovery_strings.reserve(g->v_size);
3478 for (int j = 0; j < domain_size; ++j) recovery_strings.emplace_back();
3479
3480 // eliminate degree 1 + 0 and discrete vertices
3481 del_discrete_edges_inplace(g, &c);
3482
3483 bool has_deg_0 = false;
3484 bool has_deg_1 = false;
3485 bool has_deg_2 = false;
3486 bool has_discrete = false;
3487 bool graph_changed = false;
3488 int count_deg0 = 0;
3489 int count_deg1 = 0;
3490 int count_deg2 = 0;
3491 int count_discrete = 0;
3492
3493 for (int i = 0; i < c.domain_size;) {
3494 const int v = c.lab[i];
3495 const int col_sz = c.ptn[i] + 1;
3496 switch (g->d[v]) {
3497 case 0:
3498 count_deg0 += col_sz;
3499 break;
3500 case 1:
3501 count_deg1 += col_sz;
3502 break;
3503 case 2:
3504 count_deg2 += col_sz;
3505 break;
3506 default:
3507 break;
3508 }
3509 count_discrete += (col_sz == 1);
3510 i += col_sz;
3511 }
3512 copy_coloring_to_colmap(&c, colmap);
3513 if(print) print->timer_print("colorref", g->v_size, c.cells);
3514
3515 //if(!has_deg_0 && !has_deg_1 && !has_deg_2 && !has_discrete) return;
3516 has_deg_0 = (count_deg0 > 4);
3517 has_deg_1 = (count_deg1 > 8);
3518 has_deg_2 = (count_deg2 > 128); /*< if there's only very few, there's really no point... */
3519 has_discrete = (count_discrete > 4);
3520
3521 if(!has_deg_0 && !has_deg_1 && !has_deg_2 && !has_discrete) return;
3522
3523 if (schedule != nullptr) {
3524 del_e = dejavu::markset();
3525 del_e.initialize(g->e_size);
3526
3527 for (size_t pc = 0; pc < schedule->size(); ++pc) {
3528 if (g->v_size <= 1) {
3529 return;
3530 }
3531 preop next_op = (*schedule)[pc];
3532 const int pre_v = g->v_size;
3533 const int pre_e = g->e_size;
3534 switch (next_op) {
3535 case preop::deg01: {
3536 if(!has_deg_0 && !has_deg_1 && !has_discrete && !graph_changed) break;
3537 red_deg10_assume_cref(g, colmap, hook);
3538 perform_del(g, colmap);
3539 if(print) print->timer_print("deg01", g->v_size, g->e_size);
3540
3541 if(!(g->v_size == pre_v_size && g->e_size == pre_e_size && !color_refinement_effective)) {
3542 order_according_to_color(g, colmap);
3543 if(print) print->timer_print("order", g->v_size, g->e_size);
3544 }
3545 dej_assert(_automorphism_supp.cur_pos == 0);
3546 break;
3547 }
3548 case preop::deg2ma: {
3549 if(!has_deg_2 && !graph_changed) break;
3550 red_deg2_path_size_1(g, colmap);
3551 perform_del_add_edge(g, colmap);
3552 if(print) print->timer_print("deg2ma", g->v_size, g->e_size);
3553 dej_assert(_automorphism_supp.cur_pos == 0);
3554
3555 break;
3556 }
3557
3558 case preop::twins: {
3559 // check for twins and mark them for deletion
3560 //int s_twins = remove_twins(g, colmap, hook);
3561 const int s_twins_true = twins_partition_refinement(g, colmap, hook, false);
3562 if(s_twins_true > 0) perform_del(g, colmap);
3563 const int s_twins_false = twins_partition_refinement(g, colmap, hook, true);
3564 if(s_twins_false > 0) perform_del(g, colmap);
3565 const int s_twins = s_twins_true + s_twins_false;
3566
3567 if(s_twins > 0) {
3568 // might distinguish vertices, so let's apply color refinement again
3569 g->initialize_coloring(&c, colmap);
3570 R_stack.refine_coloring_first(g, &c);
3571 copy_coloring_to_colmap(&c, colmap);
3572
3573 dej_assert(_automorphism_supp.cur_pos == 0);
3574
3575 // twins can re-activate other routines, so let's start over...
3576 if(s_twins >= 16) pc = 0;
3577 }
3578
3579 if(print) print->timer_print("twins", g->v_size, g->e_size);
3580 break;
3581 }
3582 case preop::deg2ue: {
3583 if(!has_deg_2 && !graph_changed) break;
3584
3585 has_discrete = red_deg2_color_cycles(g, colmap);
3586
3587 red_deg2_unique_endpoint(g, colmap);
3588 perform_del_add_edge(g, colmap);
3589
3590 red_deg2_trivial_connect(g, colmap);
3591 perform_del_add_edge(g, colmap);
3592 if(has_discrete) {
3593 perform_del_discrete(g, colmap);
3594 }
3595
3596 if(print) print->timer_print("deg2ue", g->v_size, g->e_size);
3597 dej_assert(_automorphism_supp.cur_pos == 0);
3598 break;
3599 }
3600 case preop::densify2: {
3601 if(!has_deg_2 && !graph_changed) break;
3602 red_deg2_densify(g, colmap);
3603 perform_del_add_edge_general(g, colmap);
3604
3605 red_deg2_densifysc1(g, colmap);
3606 perform_del_add_edge_general(g, colmap);
3607
3608 if(print) print->timer_print("densify2", g->v_size, g->e_size);
3609 dej_assert(_automorphism_supp.cur_pos == 0);
3610 break;
3611 }
3612 case preop::qcedgeflip: {
3613 red_quotient_edge_flip(g, colmap);
3614 perform_del_edge(g);
3615
3616 if(print) print->timer_print("qcedgeflip", g->v_size, g->e_size);
3617 break;
3618 }
3619 }
3620 graph_changed = graph_changed || pre_v != g->v_size || pre_e != g->e_size;
3621 }
3622 }
3623
3624 skipped_preprocessing = g->v_size == domain_size;
3625 }
3626
3628 saved_hook = hook;
3629 }
3630
3631 // bliss usage specific:
3632#if defined(BLISS_VERSION_MAJOR) && defined(BLISS_VERSION_MINOR)
3633#if ( BLISS_VERSION_MAJOR >= 1 || BLISS_VERSION_MINOR >= 76 )
3634 void bliss_hook(unsigned int n, const unsigned int *aut) {
3635 auto p = save_preprocessor;
3636 p->pre_hook_buffered(n, (const int *) aut, -1, nullptr, p->saved_hook);
3637 }
3638#else
3639 static inline void bliss_hook(void *user_param, unsigned int n, const unsigned int *aut) {
3640 auto p = (preprocessor *) user_param;
3641 p->pre_hook_buffered(n, (const int *) aut, -1, nullptr, p->saved_hook);
3642 }
3643#endif
3644#else
3645 static inline void bliss_hook(void *user_param, unsigned int n, const unsigned int *aut) {
3646 auto p = (preprocessor *) user_param;
3647 p->pre_hook_buffered(n, (const int *) aut, -1, nullptr, p->saved_hook);
3648 }
3649#endif
3650 // Traces usage specific:
3651 static inline void traces_hook(int, int* aut, int n) {
3652 auto p = save_preprocessor;
3653 p->pre_hook_buffered(n, (const int *) aut, -1, nullptr, p->saved_hook);
3654 }
3655
3657 save_preprocessor = this;
3658 }
3659
3660 // nauty usage specific:
3661 static inline void nauty_hook(int, int* aut, int*, int, int, int n) {
3662 auto p = save_preprocessor;
3663 p->pre_hook_buffered(n, (const int *) aut, -1, nullptr, p->saved_hook);
3664 }
3665
3667 save_preprocessor = this;
3668 }
3669
3670 // saucy usage specific:
3671 static inline int saucy_hook(int n, const int* aut, int nsupp, int* supp, void* user_param) {
3672 auto p = (preprocessor *) user_param;
3673 p->pre_hook_buffered(n, (const int *) aut, nsupp, supp, p->saved_hook);
3674 return true;
3675 }
3676
3677 // dejavu usage specific
3678 static inline void _dejavu_hook(int n, const int* aut, int nsupp, const int* supp) {
3679 auto p = save_preprocessor;
3680 if(p->skipped_preprocessing && !p->decomposer) {
3681 if(p->saved_hook != nullptr) {
3682 (*p->saved_hook)(n, aut, nsupp, supp);
3683 }
3684 return;
3685 }
3686 p->pre_hook_buffered(n, (const int *) aut, nsupp, supp, p->saved_hook);
3687 }
3688 };
3689}
3690#endif //SASSY_H
Stores big numbers.
Definition: utility.h:138
void multiply(int number)
Definition: utility.h:165
Vertex coloring for a graph.
Definition: coloring.h:23
Set specialized for quick resets.
Definition: ds.h:546
bool get(int pos)
Definition: ds.h:605
void reset()
Definition: ds.h:634
void initialize(int size)
Definition: ds.h:588
void set(int pos)
Definition: ds.h:616
void unset(int pos)
Definition: ds.h:626
T * get_array() const
Definition: ds.h:280
void allocate(int size)
Definition: ds.h:166
void push_back(T value)
Definition: ds.h:177
Decomposes graphs and manages decomposition information.
Definition: components.h:110
int map_back(int component, int vertex)
Definition: components.h:124
Color refinement and related algorithms.
Definition: refinement.h:143
void refine_coloring_first(sgraph *g, coloring *c, int init_color_class=-1)
Definition: refinement.h:284
preprocessor for symmetry detection
Definition: preprocess.h:32
static void nauty_hook(int, int *aut, int *, int, int, int n)
Definition: preprocess.h:3661
static void traces_hook(int, int *aut, int n)
Definition: preprocess.h:3651
preprocessor(dejavu::ir::refinement *R)
Definition: preprocess.h:104
void multiply_to_group_size(int n)
Definition: preprocess.h:121
int translate_back(int v)
Definition: preprocess.h:112
void inject_decomposer(dejavu::ir::graph_decomposer *new_decomposer, int component)
Definition: preprocess.h:125
static int saucy_hook(int n, const int *aut, int nsupp, int *supp, void *user_param)
Definition: preprocess.h:3671
static void bliss_hook(void *user_param, unsigned int n, const unsigned int *aut)
Definition: preprocess.h:3645
void traces_save_my_preprocessor()
Definition: preprocess.h:3656
preprocessor(dejavu::timed_print *printer)
Definition: preprocess.h:108
void reduce(dejavu::static_graph *g, dejavu_hook *hook, std::vector< preop > *schedule=nullptr)
Definition: preprocess.h:3370
dejavu::big_number grp_sz
Definition: preprocess.h:98
static void _dejavu_hook(int n, const int *aut, int nsupp, const int *supp)
Definition: preprocess.h:3678
void nauty_save_my_preprocessor()
Definition: preprocess.h:3666
void reduce(dejavu::sgraph *g, int *colmap, dejavu_hook *hook, const std::vector< preop > *schedule=nullptr)
Definition: preprocess.h:3382
void save_my_hook(dejavu_hook *hook)
Definition: preprocess.h:3627
void pre_hook_buffered(int _n, const int *_aut, int _supp, const int *_aut_supp, dejavu_hook *hook)
Definition: preprocess.h:3097
Internal graph data structure.
Definition: graph.h:19
int * e
Definition: graph.h:46
int e_size
Definition: graph.h:49
void initialize_coloring(ds::coloring *c, int *vertex_to_col)
Definition: graph.h:61
int v_size
Definition: graph.h:48
int * v
Definition: graph.h:44
bool dense
Definition: graph.h:51
int * d
Definition: graph.h:45
Graph with static number of vertices and edges.
Definition: graph.h:292
int * get_coloring()
Definition: graph.h:433
dejavu::sgraph * get_sgraph()
Definition: graph.h:428
Prints information to the console.
Definition: utility.h:237
void timer_print(const std::string &proc, const std::string &p1, const std::string &p2)
Definition: utility.h:264
void print_header() const
Definition: utility.h:249
Definition: bfs.h:10
#define dej_assert(expr)
Definition: utility.h:40
std::function< void(int, const int *, int, const int *)> dejavu_hook
Definition: utility.h:95