dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
groups.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 DEJAVU_GROUPS_H
6#define DEJAVU_GROUPS_H
7
8#include "ds.h"
9#include "utility.h"
10#include "coloring.h"
11#include "graph.h"
12#include "trace.h"
13
14namespace dejavu {
15
21 namespace groups {
22
23 using namespace dejavu::ds;
24
31 static void reset_automorphism(int *automorphism, worklist *support) {
32 for (int i = 0; i < support->cur_pos; ++i) {
33 automorphism[(*support)[i]] = (*support)[i];
34 }
35 support->reset();
36 }
37
50 static void color_diff_automorphism(int domain_size, const int *vertex_to_col, const int *col_to_vertex,
51 int *automorphism, worklist *support) {
52 support->reset();
53 for (int v1 = 0; v1 < domain_size; ++v1) {
54 const int col = vertex_to_col[v1];
55 const int v2 = col_to_vertex[col];
56 if (v1 != v2) {
57 automorphism[v1] = v2;
58 support->push_back(v1);
59 }
60 }
61 }
62
69 worklist automorphism;
70 worklist automorphism_supp;
71 int domain_size = 0;
72 bool support01 = false;
73
74 workspace inverse_automorphism;
75 bool have_inverse_automorphism = false;
76
80 void update_inverse_automorphism() {
81 if(!have_inverse_automorphism) {
82 for (int i = 0; i < domain_size; ++i) {
83 const int j = automorphism[i];
84 inverse_automorphism[j] = i;
85 }
86 have_inverse_automorphism = true;
87 }
88 }
89
93 void invalidate_inverse_automorphism() {
94 have_inverse_automorphism = false;
95 }
96 public:
102 explicit automorphism_workspace(int domain_sz = 0) {
103 automorphism.allocate(domain_sz);
104 for (int i = 0; i < domain_sz; ++i) {
105 automorphism[i] = i;
106 }
107 automorphism_supp.allocate(domain_sz);
108 inverse_automorphism.allocate(domain_sz);
109 invalidate_inverse_automorphism();
110 this->domain_size = domain_sz;
111 }
112
118 void resize(int new_domain_size) {
119 automorphism.resize(new_domain_size);
120 for (int i = 0; i < new_domain_size; ++i) {
121 automorphism[i] = i;
122 }
123 automorphism_supp.resize(new_domain_size);
124 automorphism_supp.reset();
125 inverse_automorphism.resize(new_domain_size);
126 invalidate_inverse_automorphism();
127 this->domain_size = new_domain_size;
128 }
129
135 inline int &operator[](int point) const {
136 dej_assert(point >= 0);
137 dej_assert(point < domain_size);
138 return automorphism[point];
139 }
140
148 void set_support01(const bool new_support01) {
149 this->support01 = new_support01;
150 }
151
160 void write_color_diff(const int *vertex_to_col, const int *col_to_vertex) {
161 color_diff_automorphism(domain_size, vertex_to_col, col_to_vertex, automorphism.get_array(),
162 &automorphism_supp);
163 invalidate_inverse_automorphism();
164 }
165
170 // rewrite support
171 if (!support01) {
172 automorphism_supp.reset();
173 for (int i = 0; i < domain_size; ++i) {
174 if (i != automorphism[i])
175 automorphism_supp.push_back(i);
176 }
177 } else {
178 automorphism_supp.reset();
179 int i;
180 for (i = 0; i < domain_size; ++i) {
181 if (i != automorphism[i]) break;
182 }
183 automorphism_supp.cur_pos = (i != domain_size);
184 }
185 }
186
196 void apply(automorphism_workspace& other, int pwr = 1) {
197 #ifndef dej_nothreadlocal
198 thread_local worklist scratch_apply1;
199 thread_local worklist scratch_apply2;
200 thread_local markset scratch_apply3;
201 #else
202 static worklist scratch_apply1;
203 static worklist scratch_apply2;
204 static markset scratch_apply3;
205 #endif
206 scratch_apply1.allocate(domain_size);
207 scratch_apply2.allocate(domain_size);
208 scratch_apply3.initialize(domain_size);
209
210 apply(scratch_apply1, scratch_apply2, scratch_apply3, other, pwr);
211 }
212
225 void apply(worklist &scratch_apply1, worklist &scratch_apply2, markset &scratch_apply3,
226 automorphism_workspace& other, int pwr = 1) {
227 if(!other.support01 && other.nsupp() <= domain_size / 4) {
228 apply_sparse(scratch_apply1, scratch_apply2, scratch_apply3, other.p(), other.supp(),
229 other.nsupp(), pwr);
230 } else {
231 apply(scratch_apply1, scratch_apply2, scratch_apply3, other.p(), pwr);
232
233 }
234 }
235
248 void apply(worklist &scratch_apply1, worklist &scratch_apply2, markset &scratch_apply3,
249 const int *p, int pwr = 1) {
250 if (pwr == 0) return;
251 if (pwr <= 5) {
252 if (pwr == 1)
253 for (int i = 0; i < domain_size; ++i) automorphism[i] = p[automorphism[i]];
254 else if (pwr == 2)
255 for (int i = 0; i < domain_size; ++i) automorphism[i] = p[p[automorphism[i]]];
256 else if (pwr == 3)
257 for (int i = 0; i < domain_size; ++i) automorphism[i] = p[p[p[automorphism[i]]]];
258 else if (pwr == 4)
259 for (int i = 0; i < domain_size; ++i) automorphism[i] = p[p[p[p[automorphism[i]]]]];
260 else if (pwr == 5)
261 for (int i = 0; i < domain_size; ++i) automorphism[i] = p[p[p[p[p[automorphism[i]]]]]];
262 } else if (pwr <= 19) {
263 // apply other automorphism
264 for (int j = 0; j < domain_size; ++j) {
265 scratch_apply1[j] = p[p[p[j]]];
266 }
267 for (; pwr >= 6; pwr -= 6)
268 for (int j = 0; j < domain_size; ++j)
269 automorphism[j] = scratch_apply1[scratch_apply1[automorphism[j]]];
270
271 if (pwr == 1)
272 for (int i = 0; i < domain_size; ++i) automorphism[i] = p[automorphism[i]];
273 else if (pwr == 2)
274 for (int i = 0; i < domain_size; ++i) automorphism[i] = p[p[automorphism[i]]];
275 else if (pwr == 3)
276 for (int i = 0; i < domain_size; ++i) automorphism[i] = scratch_apply1[automorphism[i]];
277 else if (pwr == 4)
278 for (int i = 0; i < domain_size; ++i) automorphism[i] = p[scratch_apply1[automorphism[i]]];
279 else if (pwr == 5)
280 for (int i = 0; i < domain_size; ++i) automorphism[i] = p[p[scratch_apply1[automorphism[i]]]];
281 } else {
282 // 1 cycle at a time
283
284 scratch_apply3.reset();
285 for (int i = 0; i < domain_size; ++i) {
286 if (scratch_apply3.get(i)) continue;
287 if (p[i] == i)
288 scratch_apply2[i] = i;
289 else {
290 int cyclen = 1;
291 scratch_apply1[0] = i;
292 for (int j = p[i]; j != i; j = p[j]) {
293 scratch_apply1[cyclen++] = j;
294 scratch_apply3.set(j);
295 }
296 int kk = pwr % cyclen;
297 for (int j = 0; j < cyclen; ++j) {
298 scratch_apply2[scratch_apply1[j]] = scratch_apply1[kk];
299 if (++kk == cyclen) kk = 0;
300 }
301 }
302 }
303 for (int i = 0; i < domain_size; ++i) automorphism[i] = scratch_apply2[automorphism[i]];
304 scratch_apply3.reset();
305 }
306
307 // rewrite support
309 invalidate_inverse_automorphism();
310 }
311
312 void apply_sparse(worklist &scratch_apply1, worklist &scratch_apply2, markset &scratch_apply3,
313 const int *p, const int* support, const int nsupport, int pwr = 1) {
314 if (pwr == 0) return;
315 // sparse version only implemented for pwr <= 6 right now
316 if(pwr <= 6) {
317 // we need the inverse automorphism for the algorithm
318 update_inverse_automorphism();
319 scratch_apply1.reset();
320 scratch_apply2.reset();
321
322 switch(pwr) {
323 case 1:
324 for (int k = 0; k < nsupport; ++k) {
325 const int i = support[k];
326 dej_assert(automorphism[inverse_automorphism[i]] == i);
327 const int inv_i = inverse_automorphism[i];
328 const int p_i = p[i];
329 automorphism[inv_i] = p_i;
330 scratch_apply1.push_back(inv_i);
331 scratch_apply2.push_back(p_i);
332 }
333 break;
334 case 2:
335 for (int k = 0; k < nsupport; ++k) {
336 const int i = support[k];
337 dej_assert(automorphism[inverse_automorphism[i]] == i);
338 const int inv_i = inverse_automorphism[i];
339 const int p_i = p[p[i]];
340 automorphism[inv_i] = p_i;
341 scratch_apply1.push_back(inv_i);
342 scratch_apply2.push_back(p_i);
343 }
344 break;
345 case 3:
346 for (int k = 0; k < nsupport; ++k) {
347 const int i = support[k];
348 dej_assert(automorphism[inverse_automorphism[i]] == i);
349 const int inv_i = inverse_automorphism[i];
350 const int p_i = p[p[p[i]]];
351 automorphism[inv_i] = p_i;
352 scratch_apply1.push_back(inv_i);
353 scratch_apply2.push_back(p_i);
354 }
355 break;
356 case 4:
357 for (int k = 0; k < nsupport; ++k) {
358 const int i = support[k];
359 dej_assert(automorphism[inverse_automorphism[i]] == i);
360 const int inv_i = inverse_automorphism[i];
361 const int p_i = p[p[p[p[i]]]];
362 automorphism[inv_i] = p_i;
363 scratch_apply1.push_back(inv_i);
364 scratch_apply2.push_back(p_i);
365 }
366 break;
367 case 5:
368 for (int k = 0; k < nsupport; ++k) {
369 const int i = support[k];
370 dej_assert(automorphism[inverse_automorphism[i]] == i);
371 const int inv_i = inverse_automorphism[i];
372 const int p_i = p[p[p[p[p[i]]]]];
373 automorphism[inv_i] = p_i;
374 scratch_apply1.push_back(inv_i);
375 scratch_apply2.push_back(p_i);
376 }
377 break;
378 case 6:
379 for (int k = 0; k < nsupport; ++k) {
380 const int i = support[k];
381 dej_assert(automorphism[inverse_automorphism[i]] == i);
382 const int inv_i = inverse_automorphism[i];
383 const int p_i = p[p[p[p[p[p[i]]]]]];
384 automorphism[inv_i] = p_i;
385 scratch_apply1.push_back(inv_i);
386 scratch_apply2.push_back(p_i);
387 }
388 break;
389 default:
390 dej_assert(false); // unreachable
391 break;
392 }
393
394 // fix inverse automorphism
395 for (int k = 0; k < scratch_apply1.size(); ++k)
396 inverse_automorphism[scratch_apply2[k]] = scratch_apply1[k];
397 scratch_apply1.reset();
398 scratch_apply2.reset();
399 } else {
400 // otherwise just use dense version...
401 apply(scratch_apply1, scratch_apply2, scratch_apply3, p, pwr);
402 }
403
404 // rewrite support
406 }
407
408
420 void write_singleton(const std::vector<int> *singletons1, const std::vector<int> *singletons2,
421 const int pos_start, const int pos_end) {
422 for (int i = pos_start; i < pos_end; ++i) {
423 const int from = (*singletons1)[i];
424 const int to = (*singletons2)[i];
425 dej_assert(automorphism[from] == from);
426 if (from != to) {
427 automorphism_supp.push_back(from);
428 automorphism[from] = to;
429 }
430 }
431 invalidate_inverse_automorphism();
432 }
433
439 void cycle_completion(markset& scratch_set) {
440 scratch_set.reset();
441 for(int i = 0; i < automorphism_supp.size(); ++i) {
442 const int v = automorphism_supp[i];
443 if(scratch_set.get(v)) continue;
444 int v_next = automorphism[v];
445 while(v_next != v) {
446 if(scratch_set.get(v_next)) break;
447 scratch_set.set(v_next);
448 if(v_next == automorphism[v_next]) {
449 automorphism_supp.push_back(v_next);
450 automorphism[v_next] = v;
451 }
452 v_next = automorphism[v_next];
453 }
454 }
455 invalidate_inverse_automorphism();
456 }
457
463 void write_single_map(const int from, const int to) {
464 dej_assert(automorphism[from] == from);
465 if (from != to) {
466 automorphism_supp.push_back(from);
467 automorphism[from] = to;
468 }
469 invalidate_inverse_automorphism();
470 }
471
475 void reset() {
476 invalidate_inverse_automorphism();
477 reset_automorphism(automorphism.get_array(), &automorphism_supp);
478 }
479
483 dej_nodiscard int *p() const {
484 return automorphism.get_array();
485 }
486
490 dej_nodiscard int* supp() const {
491 return automorphism_supp.get_array();
492 }
493
497 dej_nodiscard int nsupp() const {
498 return automorphism_supp.cur_pos;
499 }
500 };
501
507 class orbit {
508 int sz = 0;
509 worklist map_arr;
510 worklist orb_sz;
511 public:
512
519 int find_orbit(const int v) {
520 dej_assert(v >= 0);
521 dej_assert(v < sz);
522 int last_map;
523 int next_map = v;
524 do {
525 last_map = next_map;
526 next_map = map_arr[last_map];
527 } while(next_map != last_map);
528 map_arr[v] = next_map;
529 return next_map;
530 }
531
538 int orbit_size(const int v) {
539 dej_assert(v >= 0);
540 dej_assert(v < sz);
541 return orb_sz[find_orbit(v)];
542 }
543
550 dej_nodiscard bool represents_orbit(const int v) const {
551 return v == map_arr[v];
552 }
553
560 void combine_orbits(const int v1, const int v2) {
561 dej_assert(v1 >= 0);
562 dej_assert(v2 >= 0);
563 dej_assert(v1 < sz);
564 dej_assert(v2 < sz);
565 if(v1 == v2) return;
566 const int orbit1 = find_orbit(v1);
567 const int orbit2 = find_orbit(v2);
568 if(orbit1 == orbit2) return;
569 if(orbit1 < orbit2) {
570 map_arr[orbit2] = orbit1;
571 orb_sz[orbit1] += orb_sz[orbit2];
572 } else {
573 map_arr[orbit1] = orbit2;
574 orb_sz[orbit2] += orb_sz[orbit1];
575 }
576 }
577
578
586 bool are_in_same_orbit(const int v1, const int v2) {
587 dej_assert(v1 >= 0);
588 dej_assert(v2 >= 0);
589 dej_assert(v1 < sz);
590 dej_assert(v2 < sz);
591 if(v1 == v2) return true;
592 const int orbit1 = find_orbit(v1);
593 const int orbit2 = find_orbit(v2);
594 return (orbit1 == orbit2);
595 }
596
601 void reset() {
602 for(int v = 0; v < sz; ++v) {
603 map_arr[v] = v;
604 orb_sz[v] = 1;
605 }
606 }
607
613 void add_automorphism_to_orbit(const int* p, const int nsupp, const int* supp) {
614 for (int i = 0; i < nsupp; ++i) {
615 combine_orbits(p[supp[i]], supp[i]);
616 }
617 }
618
625 const int nsupp = aut.nsupp();
626 const int* supp = aut.supp();
627 const int* p = aut.p();
628 for (int i = 0; i < nsupp; ++i) {
629 combine_orbits(p[supp[i]], supp[i]);
630 }
631 }
632
638 void initialize(int domain_size) {
639 if(sz == domain_size) {
640 reset();
641 return;
642 }
643 sz = domain_size;
644 map_arr.allocate(domain_size);
645 orb_sz.allocate(domain_size);
646 for(int i = 0; i < domain_size; ++i) {
647 map_arr.push_back(i);
648 orb_sz.push_back(1);
649 }
650 }
651
657 explicit orbit(int domain_size) {
658 initialize(domain_size);
659 }
660
661 orbit() = default;
662 orbit(const orbit& other) {
663 sz = other.sz;
664 map_arr = other.map_arr;
665 orb_sz = other.orb_sz;
666 }
667
668
669
670 bool operator==(orbit& other_orbit) {
671 bool comp = (other_orbit.sz == sz) ;
672 for(int i = 0; i < sz && comp; ++i)
673 comp = comp && (find_orbit(i) == other_orbit.find_orbit(i));
674 return comp;
675 }
676 };
677
684 int *loaded_automorphism = nullptr;
685 public:
686 void load(int *automorphism) {
687 loaded_automorphism = automorphism;
688 }
689
690 int *p() {
691 return loaded_automorphism;
692 }
693 };
694
699 public:
702 };
703
704 private:
705 worklist data;
706 int domain_size = 0;
708
709 public:
714 return store_type;
715 }
716
725 if (store_type == STORE_SPARSE) {
726 space.reset();
727 int first_of_cycle = 0;
728 for (int i = 0; i < data.size(); ++i) {
729 const int j = abs(data[i]) - 1;
730 const bool is_last = data[i] < 0;
731 dej_assert(i == data.size() - 1 ? is_last : true);
732 if (is_last) {
733 space.write_single_map(j, abs(data[first_of_cycle]) - 1);
734 first_of_cycle = i + 1;
735 } else {
736 dej_assert(i + 1 < data.size());
737 space.write_single_map(j, abs(data[i + 1]) - 1);
738 }
739 }
740 loader.load(space.p());
741 } else {
742 // store_type == STORE_DENSE
743 loader.load(data.get_array());
744 }
745 }
746
747 void load(automorphism_workspace &automorphism) {
748 if (store_type == STORE_SPARSE) {
749 automorphism.reset();
750 int first_of_cycle = 0;
751 for (int i = 0; i < data.size(); ++i) {
752 const int j = abs(data[i]) - 1;
753 const bool is_last = data[i] < 0;
754 dej_assert(i == data.size() - 1 ? is_last : true);
755 if (is_last) {
756 automorphism.write_single_map(j, abs(data[first_of_cycle]) - 1);
757 first_of_cycle = i + 1;
758 } else {
759 dej_assert(i + 1 < data.size());
760 automorphism.write_single_map(j, abs(data[i + 1]) - 1);
761 }
762 }
763 } else {
764 automorphism.reset();
765 for(int i = 0; i < domain_size; ++i) {
766 const int v_from = i;
767 const int v_to = data.get_array()[i];
768 if(v_from != v_to) automorphism.write_single_map(v_from, v_to);
769 }
770 }
771 }
772
778 void store(int new_domain_size, automorphism_workspace &automorphism, markset &helper) {
779 domain_size = new_domain_size;
780 dej_assert(data.empty());
781
782 int support = 0;
783 for (int i = 0; i < domain_size; ++i) support += (automorphism.p()[i] != i);
784
785 // decide whether to store dense or sparse representation
786 if (support < domain_size / 4) {
787 store_type = STORE_SPARSE;
788 helper.reset();
789
790 data.allocate(support);
791 for (int i = 0; i < domain_size; ++i) {
792 if (automorphism.p()[i] == i) continue;
793 const int j = i;
794 if (helper.get(j)) continue;
795 helper.set(j);
796 int map_j = automorphism.p()[j];
797 dej_assert(map_j != j);
798 while (!helper.get(map_j)) {
799 data.push_back(map_j + 1);
800 helper.set(map_j);
801 map_j = automorphism.p()[map_j];
802 }
803 dej_assert(map_j == j);
804 data.push_back(-(j + 1));
805 }
806 helper.reset();
807 dej_assert(data.size() == support);
808 } else {
809 store_type = STORE_DENSE;
810 data.allocate(domain_size);
811 data.set_size(domain_size);
812 memcpy(data.get_array(), automorphism.p(), domain_size * sizeof(int));
813 dej_assert(data.size() == domain_size);
814 }
815 }
816 };
817
826 public:
832 explicit schreier_workspace(int new_domain_size) : scratch_auto(new_domain_size) {
833 scratch1.initialize(new_domain_size);
834 scratch2.initialize(new_domain_size);
835 scratch_apply1.allocate(new_domain_size);
836 scratch_apply2.allocate(new_domain_size);
837 scratch_apply3.initialize(new_domain_size);
838 }
839
848 };
849
855 std::vector<stored_automorphism *> generators;
856 int domain_size = 0;
857 public:
861 generating_set() = default;
864
869 void initialize(int new_domain_size) {
870 this->domain_size = new_domain_size;
871 }
872
881 generators.emplace_back(new stored_automorphism);
882 const auto num = generators.size() - 1;
883 generators[num]->store(domain_size, automorphism, w.scratch2);
884
885 s_stored_sparse += (generators[num]->get_store_type() ==
887 s_stored_dense += (generators[num]->get_store_type() ==
889
890 return static_cast<int>(num);
891 }
892
893 void remove_generator(size_t num) {
894 dej_assert(num >= 0);
895 dej_assert(num < generators.size());
896 delete generators[num];
897 generators[num] = nullptr;
898 }
899
906 void filter(schreier_workspace& w, std::vector<int> &fix_points) {
907 for(int test_pt : fix_points) {
908 for(size_t j = 0; j < generators.size(); ++j) {
909 const auto gen = generators[j];
910 if(gen == nullptr) continue;
911 gen->load(w.loader, w.scratch_auto);
912 if(w.loader.p()[test_pt] != test_pt) remove_generator(j);
914 }
915 }
917 }
918
923 std::vector<stored_automorphism *> new_gens;
924 for(auto gen : generators) {
925 if(gen) new_gens.push_back(gen);
926 }
927 generators.swap(new_gens);
928 }
929
937 return generators[num];
938 }
939
940 stored_automorphism* operator[](const size_t num) const {
941 return get_generator(num);
942 }
943
947 dej_nodiscard int size() const {
948 return static_cast<int>(generators.size());
949 }
950
951 void clear() {
952 for(auto & generator : generators) {
953 delete generator;
954 }
955 generators.clear();
956 }
957
959 clear();
960 }
961 };
962
969 /*enum stored_transversal_type {
970 STORE_DENSE, STORE_SPARSE
971 };*/
972 int fixed = -1;
973 int sz_upb = INT32_MAX;
974 int level = -1;
975 bool finished = false;
976
977 std::vector<int> fixed_orbit;
978 std::vector<int> fixed_orbit_to_perm;
979 std::vector<int> fixed_orbit_to_pwr;
981 //stored_transversal_type store_type = STORE_SPARSE; /**< whether above structures are stored dense or sparse */
982
988 void load_orbit_to_scratch(schreier_workspace &w) const {
989 w.scratch1.reset();
990 for (int p : fixed_orbit) {
991 w.scratch1.set(p);
992 }
993 }
994
1004 void add_to_fixed_orbit(const int vertex, const int perm, const int pwr) {
1005 fixed_orbit.push_back(vertex);
1006 fixed_orbit_to_perm.push_back(perm);
1007 fixed_orbit_to_pwr.push_back(pwr);
1008 }
1009
1023 static void apply_perm(schreier_workspace &w, automorphism_workspace &automorphism,
1024 generating_set &generators, const int gen_num, const int pwr) {
1025 // load perm into workspace
1026 auto generator = generators[gen_num];
1027
1028 // apply generator
1029 dej_assert(pwr >= 0);
1030 if (pwr > 0) { // use generator
1031 generator->load(w.loader, w.scratch_auto);
1032 // multiply
1033 if(generator->get_store_type() == stored_automorphism::STORE_DENSE) {
1034 automorphism.apply(w.scratch_apply1, w.scratch_apply2, w.scratch_apply3, w.loader.p(), pwr);
1035 } else {
1037 w.scratch_auto.supp(), w.scratch_auto.nsupp(), pwr);
1038 }
1039 w.scratch_auto.reset();
1040 }
1041 }
1042
1043 public:
1044
1048 dej_nodiscard int size() const {
1049 return (int) fixed_orbit.size();
1050 }
1051
1052 void set_size_upper_bound(const int new_sz_upb) {
1053 sz_upb = new_sz_upb;
1054 }
1055
1057 return sz_upb;
1058 }
1065 dej_nodiscard int find_point(const int p) const {
1066 for (size_t i = 0; i < fixed_orbit.size(); ++i) {
1067 if (p == fixed_orbit[i]) {
1068 return (int) i;
1069 }
1070 }
1071 return -1;
1072 }
1073
1080 void reduce_to_unfinished(schreier_workspace &w, std::vector<int> &selection) {
1081 load_orbit_to_scratch(w);
1082 int back_swap = (int) selection.size() - 1;
1083 int front_pt;
1084 for (front_pt = 0; front_pt <= back_swap;) {
1085 if (!w.scratch1.get(selection[front_pt])) {
1086 ++front_pt;
1087 } else {
1088 selection[front_pt] = selection[back_swap];
1089 --back_swap;
1090 }
1091 }
1092 selection.resize(front_pt);
1093 w.scratch1.reset();
1094 }
1095
1100 return finished;
1101 }
1102
1107 return fixed;
1108 }
1109
1110 dej_nodiscard const std::vector<int>& get_fixed_orbit() {
1111 return fixed_orbit;
1112 }
1113
1114 dej_nodiscard const std::vector<int>& get_generators() {
1115 return fixed_orbit_to_perm;
1116 }
1117
1125 void initialize(const int fixed_vertex, const int new_level, const int new_sz_upb) {
1126 dej_assert(fixed_vertex >= 0);
1127 dej_assert(new_level >= 0);
1128 fixed = fixed_vertex;
1129 this->level = new_level;
1130 this->sz_upb = new_sz_upb;
1131 add_to_fixed_orbit(fixed_vertex, -1, 0);
1132 }
1133
1142 automorphism_workspace &automorphism) {
1143 if (finished) return false; // Already finished transversal? Nothing to do, then!
1144
1145 // load orbit of this transversal to our workspace, such that we have random access to points in O(1)
1146 load_orbit_to_scratch(w);
1147 bool changed = false; /*< we changed this transversal? */
1148 int gen_num = -1; /*< the generator we added to extend this transversal, -1 means no generator */
1149
1150 // watch out, we may enlarge fixed_orbit in the loop below
1151 for (int i = 0; i < static_cast<int>(fixed_orbit.size()); ++i) {
1152 const int p = fixed_orbit[i];
1153 int j = automorphism.p()[p];
1154 dej_assert(j >= 0);
1155 if (j == p || w.scratch1.get(j)) continue;
1156
1157 int pwr = 0; // power we save in Schreier vector
1158 for (int jj = j; !w.scratch1.get(jj); jj = automorphism.p()[jj]) {
1159 ++pwr;
1160 }
1161
1162 while (!w.scratch1.get(j)) {
1163 // we change this transversal
1164 changed = true;
1165
1166 // add generator to generating set (once)
1167 if (gen_num == -1) gen_num = generators.add_generator(w, automorphism);
1168
1169 // add entry to transversal
1170 add_to_fixed_orbit(j, gen_num, pwr);
1171 w.scratch1.set(j);
1172
1173 // we check out the entire cycle of j now
1174 j = automorphism.p()[j];
1175 --pwr;
1176 }
1177 }
1178
1179 // We reached upper bound for the size of this transversal? Then mark transversal as "finished"!
1180 if (sz_upb == (int) fixed_orbit.size() && !finished) {
1181 finished = true;
1182 }
1183
1184 dej_assert(sz_upb >= (int) fixed_orbit.size());
1185
1186 // reset our workspace
1187 w.scratch1.reset();
1188 return changed;
1189 }
1190
1199 automorphism_workspace &automorphism) const {
1200 int fixed_map = automorphism.p()[fixed]; // Where is fixed mapped to?
1201
1202 // as long as `fixed` is not yet fixed, we apply automorphisms from the transversal as prescribed by
1203 // the Schreier vector
1204 while (fixed != fixed_map) {
1205 const int pos = find_point(fixed_map); // Where are we storing the information for `fixed_map`?
1206 dej_assert(pos >= 0);
1207 const int perm = fixed_orbit_to_perm[pos]; // generator to apply for `fixed_map`
1208 const int pwr = fixed_orbit_to_pwr[pos]; // power to use for `fixed_map`
1209 apply_perm(w, automorphism, generators, perm, pwr);
1210 fixed_map = automorphism.p()[fixed]; // Fixed now? Or we need to go again?
1211 }
1212 dej_assert(automorphism.p()[fixed] == fixed);
1213 return automorphism.nsupp() == 0;
1214 }
1215 };
1216
1225 private:
1226 int domain_size = -1;
1227 int finished_up_to = -1;
1228
1229 generating_set generators;
1230 std::vector<shared_transversal> transversals;
1231 std::vector<int> stabilized_generators;
1232
1233 bool init = false;
1234
1235 public:
1237 int h_error_bound = 10;
1244 return generators.s_stored_sparse;
1245 }
1246
1251 return generators.s_stored_dense;
1252 }
1253
1262 void initialize(const int new_domain_size, std::vector<int> &base, std::vector<int> &base_sizes,
1263 int stop = INT32_MAX) {
1264 stop = std::min(static_cast<int>(base.size()), stop);
1265 dej_assert(static_cast<int>(base.size()) >= stop);
1266 domain_size = new_domain_size;
1267 dej_assert(this->domain_size > 0);
1268 generators.initialize(domain_size);
1269 generators.clear();
1270 transversals.reserve(stop);
1271 transversals.clear();
1272 finished_up_to = -1;
1273
1274 for (int i = 0; i < stop && i < static_cast<int>(base.size()); ++i) {
1275 transversals.emplace_back();
1276 transversals[i].initialize(base[i], i, base_sizes[i]);
1277 }
1278 init = true;
1279 }
1280
1282 std::vector<int> &new_base, int err = 10, bool resift_generators = false) {
1283 dej_assert(init);
1284 const int old_size = static_cast<int>(transversals.size());
1285 const int new_size = static_cast<int>(new_base.size());
1286
1287 // compare with stored base, keep whatever is possible
1288 int keep_until = 0;
1289 for (; keep_until < old_size && keep_until < new_size; ++keep_until) {
1290 if (transversals[keep_until].get_fixed_point() != new_base[keep_until]) break;
1291 }
1292
1293 if (keep_until == new_size) return;
1294
1295 finished_up_to = -1;
1296 transversals.resize(new_size);
1297
1298
1299 for (int i = 0; i < keep_until; ++i) { transversals[i].set_size_upper_bound(INT32_MAX); }
1300 for (int i = keep_until; i < new_size; ++i) {
1301 transversals[i] = shared_transversal();
1302 dej_assert(new_base[i] >= 0);
1303 transversals[i].initialize(new_base[i], i, INT32_MAX);
1304 }
1305
1306 std::vector<int> stabilized_generators_copy;
1307 stabilized_generators_copy.swap(stabilized_generators);
1308 stabilized_generators.clear();
1309
1310 if(resift_generators) {
1311 for (int gen_id : stabilized_generators_copy) sift_generator(w, automorphism, gen_id, true);
1312 }
1313 sift_random(w, automorphism, rng, err);
1314 }
1315
1317 random_source& rng, int err) {
1318 int fail = err;
1319 bool any_changed = false;
1320 while(fail >= 0) {
1321 const bool sift_changed = sift_random(w, automorphism, rng, true);
1322 any_changed = sift_changed || any_changed;
1323 fail -= !sift_changed;
1324 }
1325 }
1326
1335 bool reset(int new_domain_size, schreier_workspace& w, std::vector<int> &new_base,
1336 std::vector<int> &new_base_sizes, const int stop, bool keep_old, bool remove_generators,
1337 std::vector<int> &global_fixed_points) {
1338 const int old_size = static_cast<int>(transversals.size());
1339 if(!init || new_domain_size != domain_size) {
1340 initialize(new_domain_size, new_base, new_base_sizes, stop);
1341 return false;
1342 }
1343 const int new_size = stop;
1344
1345 // compare with stored base, keep whatever is possible
1346 int keep_until = 0;
1347 if(remove_generators) generators.clear();
1348 if(keep_old) {
1349 for (; keep_until < old_size && keep_until < new_size; ++keep_until) {
1350 if (transversals[keep_until].get_fixed_point() != new_base[keep_until]) break;
1351 }
1352 } else {
1353 //generators.clear();
1354 generators.filter(w, global_fixed_points);
1355 }
1356
1357 if(keep_until == new_size && new_size == old_size) return false;
1358
1359 finished_up_to = -1;
1360
1361 transversals.resize(new_size);
1362 //transversals.set_size(new_size);
1363
1364
1365 for(int i = 0; i < keep_until; ++i) {
1366 transversals[i].set_size_upper_bound(new_base_sizes[i]);
1367 }
1368 for (int i = keep_until; i < stop; ++i) {
1369 //if(i < old_size) delete transversals[i];
1370 transversals[i] = shared_transversal();
1371 dej_assert(new_base[i] >= 0);
1372 transversals[i].initialize(new_base[i], i, new_base_sizes[i]);
1373 }
1374
1375 stabilized_generators.clear();
1376
1377 return true;
1378 }
1379
1387 void determine_potential_individualization(std::vector<std::pair<int, int>>* save_to_individualize,
1388 coloring* root_coloring) {
1389 for (int i = base_size()-1; i >= 0; --i) {
1390 const int corresponding_root_color_sz =
1391 root_coloring->ptn[root_coloring->vertex_to_col[transversals[i].get_fixed_point()]] + 1;
1392 if(transversals[i].size() >= corresponding_root_color_sz && corresponding_root_color_sz > 1) {
1393 save_to_individualize->emplace_back(transversals[i].get_fixed_point(), corresponding_root_color_sz);
1394 }
1395 }
1396 }
1397
1402 dej_nodiscard int base_point(int pos) const {
1403 return transversals[pos].get_fixed_point();
1404 }
1405
1410 return static_cast<int>(transversals.size());
1411 }
1412
1420 bool is_in_fixed_orbit(const int base_pos, const int v) {
1421 if (base_pos >= base_size()) return false;
1422 if(v < 0) return false;
1423 dej_assert(base_pos >= 0);
1424 dej_assert(base_pos < base_size());
1425 const int search = transversals[base_pos].find_point(v);
1426 return search != -1;
1427 }
1428
1429 const std::vector<int>& get_fixed_orbit(const int base_pos) {
1430 dej_assert(base_pos >= 0);
1431 dej_assert(base_pos < base_size());
1432 return transversals[base_pos].get_fixed_orbit();
1433 }
1434
1435 const std::vector<int>& get_stabilizer_generators(const int base_pos) {
1436 dej_assert(base_pos >= 0);
1437 dej_assert(base_pos < base_size());
1438 return transversals[base_pos].get_generators();
1439 }
1440
1441 const std::vector<int>& get_stabilized_generators() {
1442 return stabilized_generators;
1443 }
1444
1445 dej_nodiscard int get_fixed_orbit_size(const int base_pos) {
1446 if (base_pos >= static_cast<int>(transversals.size())) return 0;
1447 return transversals[base_pos].size();
1448 }
1449
1458 void reduce_to_unfinished(schreier_workspace &w, std::vector<int> &selection, int base_pos) {
1459 transversals[base_pos].reduce_to_unfinished(w, selection);
1460 }
1461
1468 dej_nodiscard bool is_finished(const int base_pos) const {
1469 return transversals[base_pos].is_finished();
1470 }
1471
1479 bool sift(schreier_workspace &w, automorphism_workspace &automorphism, bool uniform = false,
1480 bool keep_at_end = false) {
1481 bool changed = false; /*< keeps track of whether we changed the Schreier structure while sifting */
1482
1483 automorphism.set_support01(true); // we don't need to track full support
1484 for (int level = 0; level < static_cast<int>(transversals.size()); ++level) { // sift level-by-level
1485 // first, we try to extend the transversal using the new automorphism
1486 changed = transversals[level].extend_with_automorphism(w, generators, automorphism)
1487 || changed;
1488
1489 // secondly, we fix the point of this transversal in automorphism
1490 const bool identity = transversals[level].fix_automorphism(w, generators, automorphism);
1491 if (identity) break; // if automorphism is the identity now, no need to sift further
1492 }
1493
1494 if(automorphism.nsupp() != 0 && keep_at_end) {
1495 const int gen_id = generators.add_generator(w, automorphism);
1496 stabilized_generators.push_back(gen_id);
1497 }
1498
1499 // keep track of how far this Schreier structure is finished (matches given upper bounds)
1500 for (int level = finished_up_to + 1; level < static_cast<int>(transversals.size()); ++level) {
1501 if (finished_up_to == level - 1 && transversals[level].is_finished()) {
1502 ++finished_up_to;
1503 } else {
1504 break;
1505 }
1506 }
1507
1508 // reset the automorphism_workspace
1509 automorphism.set_support01(false);
1510 automorphism.update_support();
1511 automorphism.reset();
1512
1513 if(uniform) record_sift_result(changed); // uniform automorphisms count towards abort criterion
1514
1515 return changed;
1516 }
1517
1526 random_source& rng) {
1527 automorphism.reset();
1528
1529 const int random_mult = static_cast<int>(rng() % 7); // 7
1530 const int num_mult = 1 + (random_mult);
1531 for(int i = 0; i < num_mult; ++i) {
1532 // load generator
1533 const int next_gen_num = static_cast<int>(rng() % generators.size());
1534 dej_assert(next_gen_num >= 0);
1535 dej_assert(next_gen_num < generators.size());
1536 auto next_gen = generators[next_gen_num];
1537 dej_assert(next_gen != nullptr);
1538 next_gen->load(w.loader, w.scratch_auto);
1539
1540 // multiply
1541 automorphism.apply(w.scratch_apply1, w.scratch_apply2, w.scratch_apply3, w.loader.p(), 1);
1542 w.scratch_auto.reset();
1543 }
1544 }
1545
1546 void load_generator(automorphism_workspace& automorphism, int generator) {
1547 auto next_gen = generators[generator];
1548 next_gen->load(automorphism);
1549 }
1550
1559 random_source& rng, bool keep_at_end = false) {
1560 if(generators.size() <= 0) return false;
1561 automorphism.reset();
1562 automorphism.set_support01(true);
1563 generate_random(w, automorphism, rng);
1564 const bool added_generator = sift(w, automorphism, false, keep_at_end);
1565 return added_generator;
1566 }
1567
1568 bool sift_generator(schreier_workspace &w, automorphism_workspace& automorphism, int generator,
1569 bool keep_at_end = false) {
1570 if(generators.size() <= 0) return false;
1571 automorphism.reset();
1572 automorphism.set_support01(true);
1573 load_generator(automorphism, generator);
1574 const bool added_generator = sift(w, automorphism, false, keep_at_end);
1575 return added_generator;
1576 }
1577
1583 void record_sift_result(const bool changed) {
1584 if(!changed) {
1586 } else {
1587 if(s_consecutive_success > 0) {
1588 ++h_error_bound;
1590 }
1591 }
1592 }
1593
1599 }
1600
1606 }
1607
1612 return (finished_up_to_level() + 1 == base_size());
1613 }
1614
1620 return finished_up_to;
1621 }
1622
1627 s_grp_sz.mantissa = 1.0;
1628 s_grp_sz.exponent = 0;
1629 // multiply the sizes of the individual levels in the Schreier table
1630 for (auto & transversal : transversals) s_grp_sz.multiply(transversal.size());
1631 }
1632 };
1633
1644 private:
1645 int h_domain_size = -1;
1646 random_schreier_internal schreier;
1648 automorphism_workspace ws_auto;
1649 schreier_workspace ws_schreier;
1650 random_source rng;
1652 markset auxiliary_set;
1654 int h_error_bound = 10;
1655 bool init = false;
1657 public:
1662 return schreier.s_sparsegen() + schreier.s_densegen();
1663 }
1664
1672 void get_generator(int i, automorphism_workspace& automorphism) {
1673 schreier.load_generator(automorphism, i);
1674 }
1675
1684 explicit random_schreier(int domain_size, int error = 10, bool true_random = false, int seed = 0) :
1685 ws_auto(domain_size), ws_schreier(domain_size), rng(true_random, seed),
1686 auxiliary_set(domain_size) {
1687 h_error_bound = error;
1688 h_domain_size = domain_size;
1689 }
1690
1696 void set_base(std::vector<int> &new_base, bool resift_generators = false) {
1697 if(!init) {
1698 std::vector<int> base_sizes;
1699 base_sizes.reserve(new_base.size());
1700 for(int i = 0; i < static_cast<int>(new_base.size()); ++i) base_sizes.push_back(INT32_MAX);
1701 schreier.initialize(h_domain_size, new_base, base_sizes);
1702 init = true;
1703 } else schreier.set_base(ws_schreier, ws_auto, rng, new_base, h_error_bound, resift_generators);
1704 sift_random();
1705 }
1706
1711 schreier.sift_random(ws_schreier, ws_auto, rng, h_error_bound);
1712 }
1713
1718 return schreier.base_size();
1719 }
1720
1725 dej_nodiscard int get_fixed_point(int pos) const {
1726 return schreier.base_point(pos);
1727 }
1728
1736 bool is_in_fixed_orbit(const int base_pos, const int v) {
1737 return schreier.is_in_fixed_orbit(base_pos, v);
1738 }
1739
1745 dej_nodiscard int get_fixed_orbit_size(const int base_pos) {
1746 return schreier.get_fixed_orbit_size(base_pos);
1747 }
1748
1755 const std::vector<int>& get_fixed_orbit(const int base_pos) {
1756 return schreier.get_fixed_orbit(base_pos);
1757 }
1758
1765 void get_stabilizer_orbit(int base_pos, orbit& orbit_partition) {
1766 auxiliary_set.initialize(get_number_of_generators());
1767 auxiliary_set.reset();
1768 orbit_partition.reset();
1769
1770 // TODO this can be done much more efficiently...
1771 for(int j = base_pos; j < schreier.base_size(); ++j) {
1772 const std::vector<int> &generators = schreier.get_stabilizer_generators(j);
1773 for (auto i: generators) {
1774 if (i < 0) continue;
1776 if (auxiliary_set.get(i)) continue;
1777 auxiliary_set.set(i);
1778 schreier.load_generator(ws_auto, i);
1779 orbit_partition.add_automorphism_to_orbit(ws_auto);
1780 }
1781 }
1782
1783 for(auto i : schreier.get_stabilized_generators()) {
1784 schreier.load_generator(ws_auto, i);
1785 orbit_partition.add_automorphism_to_orbit(ws_auto);
1786 }
1787 }
1788
1797 std::vector<int> get_stabilizer_generators(int base_pos) {
1798 auxiliary_set.initialize(get_number_of_generators());
1799 auxiliary_set.reset();
1800 std::vector<int> all_generators;
1801
1802 // TODO this can be done much more efficiently...
1803 for(int j = base_pos; j < schreier.base_size(); ++j) {
1804 const std::vector<int> &generators = schreier.get_stabilizer_generators(j);
1805 for (auto i: generators) {
1806 if (i < 0) continue;
1808 if (auxiliary_set.get(i)) continue;
1809 auxiliary_set.set(i);
1810 all_generators.push_back(i);
1811 }
1812 }
1813
1814 for(auto i : schreier.get_stabilized_generators()) {
1815 if (auxiliary_set.get(i)) continue;
1816 auxiliary_set.set(i);
1817 all_generators.push_back(i);
1818 }
1819
1820 return all_generators;
1821 }
1822
1832 bool sift(automorphism_workspace &automorphism, bool known_in_group = false) {
1833 return sift(h_domain_size, automorphism.p(), automorphism.nsupp(), automorphism.supp(), known_in_group);
1834 }
1835
1845 bool sift(int, const int *p, int nsupp, const int *supp, bool known_in_group = false) {
1846 ws_auto.reset();
1847 for(int i = 0; i < h_domain_size; ++i) dej_assert(ws_auto.p()[i] == i);
1848
1849 for(int i = 0; i < nsupp; ++i) {
1850 const int v_from = supp[i];
1851 const int v_to = p[v_from];
1852 if(v_from != v_to) ws_auto.write_single_map(v_from, v_to);
1853 }
1854
1855 const bool result = schreier.sift(ws_schreier, ws_auto, false, !known_in_group);
1856 ws_auto.reset();
1857 return result;
1858 }
1859
1865 sift_random();
1866 schreier.compute_group_size();
1867 return schreier.s_grp_sz;
1868 }
1869 };
1870
1875 std::vector<int> map_to_small;
1876 std::vector<int> map_to_big;
1877 bool do_compress = false;
1878 int s_vertices_active = 0;
1879 int domain_size = 0;
1880
1881 void reset() {
1882 s_compression_ratio = 1.0;
1883 do_compress = false;
1884 }
1885 public:
1887
1894 void determine_compression_map(coloring& c, std::vector<int>& base, int stop) {
1895 do_compress = true;
1896 domain_size = c.domain_size;
1897
1898 markset color_was_added(c.domain_size);
1899 markset test_vertices_active(c.domain_size);
1900
1901 color_was_added.reset();
1902 test_vertices_active.reset();
1903
1904 s_vertices_active = 0;
1905
1906 for(int i = 0; i < stop; ++i) {
1907 const int base_vertex = base[i];
1908 const int col = c.vertex_to_col[base_vertex];
1909 if(!color_was_added.get(col)) {
1910 color_was_added.set(col);
1911 const int col_sz = c.ptn[col] + 1;
1912 s_vertices_active += col_sz;
1913 for(int j = 0; j < col_sz; ++j) {
1914 const int add_v = c.lab[col + j];
1915 test_vertices_active.set(add_v);
1916 }
1917 }
1918 }
1919
1920 map_to_small.resize(c.domain_size);
1921 map_to_big.resize(s_vertices_active);
1922 int next_active_v_maps_to = 0;
1923 for(int v = 0; v < c.domain_size; ++v) {
1924 if(test_vertices_active.get(v)) {
1925 map_to_small[v] = next_active_v_maps_to;
1926 map_to_big[next_active_v_maps_to] = v;
1927 ++next_active_v_maps_to;
1928 } else {
1929 map_to_small[v] = -1;
1930 }
1931 }
1932 s_compression_ratio = 1.0;
1933 if(domain_size > 0) s_compression_ratio = 1.0 * s_vertices_active / domain_size;
1934 }
1935
1940 return s_vertices_active;
1941 }
1942
1947 return domain_size;
1948 }
1949
1955 int compress(int v) {
1956 if(!do_compress) return v;
1957 return map_to_small[v];
1958 }
1959
1965 int decompress(int v) {
1966 if(!do_compress) return v;
1967 return map_to_big[v];
1968 }
1969 };
1970
1977 private:
1978 random_schreier_internal internal_schreier;
1979 domain_compressor* compressor;
1980 automorphism_workspace compressed_automorphism;
1981 std::vector<int> original_base;
1982 std::vector<int> original_base_sizes;
1983
1984 public:
1985 double h_min_compression_ratio = 0.4; /*< only use compression if at least this ratio can be achieved */
1987
1992 return internal_schreier.s_sparsegen();
1993 }
1994
1999 return internal_schreier.s_densegen();
2000 }
2001
2010 bool reset(domain_compressor* new_compressor, int new_domain_size, schreier_workspace& w,
2011 std::vector<int> &new_base, std::vector<int> &new_base_sizes, const int stop, bool keep_old,
2012 std::vector<int> &global_fixed_points) {
2013 bool remove_generators = (compressor != nullptr);
2014
2015 compressor = new_compressor;
2016 // do not use compression at all if ration too bad (to save on translation cost, and such that keep_old
2017 // works for difficult graphs)
2018 if(compressor != nullptr &&
2019 compressor->s_compression_ratio > h_min_compression_ratio) compressor = nullptr;
2020
2021 remove_generators = remove_generators || (compressor != nullptr);
2022
2023 if(compressor != nullptr) {
2024 // need more management if we are using compression
2025 original_base = new_base;
2026 original_base_sizes = new_base_sizes;
2027 compressed_automorphism.resize(compressor->compressed_domain_size());
2028 keep_old = false;
2029 std::vector<int> new_basec;
2030 new_basec.reserve(new_base.size());
2031 for (int i = 0; i < static_cast<int>(new_base.size()); ++i)
2032 new_basec.push_back(compressor->compress(new_base[i]));
2033
2035 return internal_schreier.reset(new_compressor->compressed_domain_size(), w, new_basec,
2036 new_base_sizes, stop, keep_old, remove_generators,
2037 global_fixed_points);
2038 } else {
2039 // we are not using compression, so simply use the Schreier structure normally
2040 s_compression_ratio = 1.0;
2041 return internal_schreier.reset(new_domain_size, w, new_base,
2042 new_base_sizes, stop, keep_old, remove_generators,
2043 global_fixed_points);
2044 }
2045 }
2046
2054 void determine_potential_individualization(std::vector<std::pair<int, int>>* save_to_individualize,
2055 coloring* root_coloring) {
2056 if(compressor == nullptr) {
2057 internal_schreier.determine_potential_individualization(save_to_individualize, root_coloring);
2058 return;
2059 }
2060
2061 for (int i = base_size()-1; i >= 0; --i) {
2062 const int corresponding_root_color_sz = root_coloring->ptn[root_coloring->vertex_to_col[original_base[i]]] + 1;
2063 if(internal_schreier.get_fixed_orbit_size(i) >= corresponding_root_color_sz && corresponding_root_color_sz > 1) {
2064 save_to_individualize->emplace_back(original_base[i], corresponding_root_color_sz);
2065 }
2066 }
2067 }
2068
2073 dej_nodiscard int base_point(int pos) const {
2074 if(compressor != nullptr) {
2075 return original_base[pos];
2076 } else {
2077 return internal_schreier.base_point(pos);
2078 }
2079 }
2080
2085 return internal_schreier.base_size();
2086 }
2087
2095 bool is_in_base_orbit(const int base_pos, const int v) {
2096 int v_translate = compressor != nullptr? compressor->compress(v) : v;
2097 return internal_schreier.is_in_fixed_orbit(base_pos, v_translate);
2098 }
2099
2108 void reduce_to_unfinished(schreier_workspace &w, std::vector<int> &selection, int base_pos) {
2109 if(compressor != nullptr) {
2110 for(int i = 0; i < static_cast<int>(selection.size()); ++i) {
2111 dej_assert(compressor->compress(selection[i]) >= 0);
2112 selection[i] = compressor->compress(selection[i]);
2113 }
2114 }
2115 internal_schreier.reduce_to_unfinished(w, selection, base_pos);
2116 if(compressor != nullptr) {
2117 for(int i = 0; i < static_cast<int>(selection.size()); ++i) {
2118 selection[i] = compressor->decompress(selection[i]);
2119 dej_assert(selection[i] >= 0);
2120 }
2121 }
2122
2123 }
2124
2125 void compress_automorphism(automorphism_workspace &automorphism, automorphism_workspace &automorphism_compress) {
2126 automorphism_compress.reset();
2127
2128 const int support = automorphism.nsupp();
2129 for(int i = 0; i < support; ++i) {
2130 const int vsupport = automorphism.supp()[i];
2131 const int vsupportc = compressor->compress(vsupport);
2132 const int vmapsto = automorphism.p()[vsupport];
2133 const int vmapstoc = compressor->compress(vmapsto);
2134 if(vsupportc >= 0) {
2135 dej_assert(vmapstoc >= 0);
2136 automorphism_compress.write_single_map(vsupportc, vmapstoc);
2137 }
2138 }
2139 }
2140
2148 bool sift(schreier_workspace &w, automorphism_workspace &automorphism, bool uniform = false) {
2149 if(compressor != nullptr) {
2150 compress_automorphism(automorphism, compressed_automorphism);
2151 return internal_schreier.sift(w, compressed_automorphism, uniform);
2152 } else {
2153 return internal_schreier.sift(w, automorphism, uniform);
2154 }
2155 }
2156
2165 random_source& rng) {
2166 if(compressor != nullptr) {
2167 return internal_schreier.sift_random(w, compressed_automorphism, rng);
2168 } else {
2169 return internal_schreier.sift_random(w, automorphism, rng);
2170 }
2171 }
2172
2177 internal_schreier.reset_probabilistic_criterion();
2178 }
2179
2184 return internal_schreier.probabilistic_abort_criterion();
2185 }
2186
2191 return internal_schreier.deterministic_abort_criterion();
2192 }
2193
2198 return internal_schreier.probabilistic_abort_criterion() ||
2199 internal_schreier.deterministic_abort_criterion();
2200 }
2201
2202 void set_error_bound(int error_bound) {
2203 internal_schreier.h_error_bound = error_bound;
2204 }
2205
2207 return internal_schreier.s_consecutive_success;
2208 }
2209
2211 return internal_schreier.s_grp_sz;
2212 }
2213
2219 return internal_schreier.finished_up_to_level();
2220 }
2221
2226 internal_schreier.compute_group_size();
2227 }
2228 };
2229 }
2230}
2231
2232#endif //DEJAVU_GROUPS_H
Stores big numbers.
Definition: utility.h:138
long double mantissa
Definition: utility.h:140
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
dej_nodiscard bool empty() const
Definition: ds.h:206
T * get_array() const
Definition: ds.h:280
void allocate(int size)
Definition: ds.h:166
void set_size(const int size)
Definition: ds.h:215
void resize(const int size)
Definition: ds.h:248
dej_nodiscard int size() const
Definition: ds.h:222
void push_back(T value)
Definition: ds.h:177
Fixed-size integer array, 0-initialized.
Definition: ds.h:326
void resize(const int size)
Definition: ds.h:413
void allocate(int size)
Definition: ds.h:396
Workspace for sparse automorphisms.
Definition: groups.h:68
void set_support01(const bool new_support01)
Definition: groups.h:148
void cycle_completion(markset &scratch_set)
Definition: groups.h:439
void write_color_diff(const int *vertex_to_col, const int *col_to_vertex)
Definition: groups.h:160
dej_nodiscard int nsupp() const
Definition: groups.h:497
void apply_sparse(worklist &scratch_apply1, worklist &scratch_apply2, markset &scratch_apply3, const int *p, const int *support, const int nsupport, int pwr=1)
Definition: groups.h:312
dej_nodiscard int * p() const
Definition: groups.h:483
void apply(worklist &scratch_apply1, worklist &scratch_apply2, markset &scratch_apply3, automorphism_workspace &other, int pwr=1)
Definition: groups.h:225
void apply(worklist &scratch_apply1, worklist &scratch_apply2, markset &scratch_apply3, const int *p, int pwr=1)
Definition: groups.h:248
dej_nodiscard int * supp() const
Definition: groups.h:490
int & operator[](int point) const
Definition: groups.h:135
void resize(int new_domain_size)
Definition: groups.h:118
void apply(automorphism_workspace &other, int pwr=1)
Definition: groups.h:196
void write_singleton(const std::vector< int > *singletons1, const std::vector< int > *singletons2, const int pos_start, const int pos_end)
Definition: groups.h:420
void write_single_map(const int from, const int to)
Definition: groups.h:463
automorphism_workspace(int domain_sz=0)
Definition: groups.h:102
Compressed Schreier structure.
Definition: groups.h:1976
bool reset(domain_compressor *new_compressor, int new_domain_size, schreier_workspace &w, std::vector< int > &new_base, std::vector< int > &new_base_sizes, const int stop, bool keep_old, std::vector< int > &global_fixed_points)
Definition: groups.h:2010
dej_nodiscard bool deterministic_abort_criterion() const
Definition: groups.h:2190
void determine_potential_individualization(std::vector< std::pair< int, int > > *save_to_individualize, coloring *root_coloring)
Definition: groups.h:2054
bool sift(schreier_workspace &w, automorphism_workspace &automorphism, bool uniform=false)
Definition: groups.h:2148
dej_nodiscard int base_size() const
Definition: groups.h:2084
bool is_in_base_orbit(const int base_pos, const int v)
Definition: groups.h:2095
dej_nodiscard int get_consecutive_success() const
Definition: groups.h:2206
dej_nodiscard big_number get_group_size() const
Definition: groups.h:2210
dej_nodiscard int base_point(int pos) const
Definition: groups.h:2073
bool sift_random(schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng)
Definition: groups.h:2164
dej_nodiscard bool any_abort_criterion() const
Definition: groups.h:2197
dej_nodiscard int s_densegen() const
Definition: groups.h:1998
void compress_automorphism(automorphism_workspace &automorphism, automorphism_workspace &automorphism_compress)
Definition: groups.h:2125
dej_nodiscard bool probabilistic_abort_criterion() const
Definition: groups.h:2183
dej_nodiscard int finished_up_to_level() const
Definition: groups.h:2218
void set_error_bound(int error_bound)
Definition: groups.h:2202
dej_nodiscard int s_sparsegen() const
Definition: groups.h:1991
void reduce_to_unfinished(schreier_workspace &w, std::vector< int > &selection, int base_pos)
Definition: groups.h:2108
Stores a link to an automorphism.
Definition: groups.h:683
void load(int *automorphism)
Definition: groups.h:686
Compresses vertex set to smaller window.
Definition: groups.h:1874
dej_nodiscard int decompressed_domain_size() const
Definition: groups.h:1946
dej_nodiscard int compressed_domain_size() const
Definition: groups.h:1939
void determine_compression_map(coloring &c, std::vector< int > &base, int stop)
Definition: groups.h:1894
Stores a generating set.
Definition: groups.h:854
int add_generator(schreier_workspace &w, automorphism_workspace &automorphism)
Definition: groups.h:880
void filter(schreier_workspace &w, std::vector< int > &fix_points)
Definition: groups.h:906
generating_set(const generating_set &)=delete
dej_nodiscard int size() const
Definition: groups.h:947
stored_automorphism * operator[](const size_t num) const
Definition: groups.h:940
dej_nodiscard stored_automorphism * get_generator(const size_t num) const
Definition: groups.h:936
void initialize(int new_domain_size)
Definition: groups.h:869
generating_set & operator=(const generating_set &)=delete
void remove_generator(size_t num)
Definition: groups.h:893
Orbit partition.
Definition: groups.h:507
bool are_in_same_orbit(const int v1, const int v2)
Definition: groups.h:586
orbit(int domain_size)
Definition: groups.h:657
int orbit_size(const int v)
Definition: groups.h:538
void initialize(int domain_size)
Definition: groups.h:638
void combine_orbits(const int v1, const int v2)
Definition: groups.h:560
void add_automorphism_to_orbit(groups::automorphism_workspace &aut)
Definition: groups.h:624
dej_nodiscard bool represents_orbit(const int v) const
Definition: groups.h:550
int find_orbit(const int v)
Definition: groups.h:519
orbit(const orbit &other)
Definition: groups.h:662
bool operator==(orbit &other_orbit)
Definition: groups.h:670
void add_automorphism_to_orbit(const int *p, const int nsupp, const int *supp)
Definition: groups.h:613
void sift_random(schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng, int err)
Definition: groups.h:1316
const std::vector< int > & get_stabilized_generators()
Definition: groups.h:1441
bool sift_generator(schreier_workspace &w, automorphism_workspace &automorphism, int generator, bool keep_at_end=false)
Definition: groups.h:1568
dej_nodiscard int base_point(int pos) const
Definition: groups.h:1402
void determine_potential_individualization(std::vector< std::pair< int, int > > *save_to_individualize, coloring *root_coloring)
Definition: groups.h:1387
dej_nodiscard bool probabilistic_abort_criterion() const
Definition: groups.h:1604
dej_nodiscard int base_size() const
Definition: groups.h:1409
dej_nodiscard int finished_up_to_level() const
Definition: groups.h:1619
void record_sift_result(const bool changed)
Definition: groups.h:1583
dej_nodiscard int get_fixed_orbit_size(const int base_pos)
Definition: groups.h:1445
const std::vector< int > & get_stabilizer_generators(const int base_pos)
Definition: groups.h:1435
dej_nodiscard int s_densegen() const
Definition: groups.h:1250
bool sift(schreier_workspace &w, automorphism_workspace &automorphism, bool uniform=false, bool keep_at_end=false)
Definition: groups.h:1479
bool is_in_fixed_orbit(const int base_pos, const int v)
Definition: groups.h:1420
bool sift_random(schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng, bool keep_at_end=false)
Definition: groups.h:1558
dej_nodiscard int s_sparsegen() const
Definition: groups.h:1243
void set_base(schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng, std::vector< int > &new_base, int err=10, bool resift_generators=false)
Definition: groups.h:1281
const std::vector< int > & get_fixed_orbit(const int base_pos)
Definition: groups.h:1429
dej_nodiscard bool is_finished(const int base_pos) const
Definition: groups.h:1468
bool reset(int new_domain_size, schreier_workspace &w, std::vector< int > &new_base, std::vector< int > &new_base_sizes, const int stop, bool keep_old, bool remove_generators, std::vector< int > &global_fixed_points)
Definition: groups.h:1335
void generate_random(schreier_workspace &w, automorphism_workspace &automorphism, random_source &rng)
Definition: groups.h:1525
void initialize(const int new_domain_size, std::vector< int > &base, std::vector< int > &base_sizes, int stop=INT32_MAX)
Definition: groups.h:1262
void load_generator(automorphism_workspace &automorphism, int generator)
Definition: groups.h:1546
void reduce_to_unfinished(schreier_workspace &w, std::vector< int > &selection, int base_pos)
Definition: groups.h:1458
dej_nodiscard bool deterministic_abort_criterion() const
Definition: groups.h:1611
API for the dejavu Schreier structure.
Definition: groups.h:1643
std::vector< int > get_stabilizer_generators(int base_pos)
Definition: groups.h:1797
const std::vector< int > & get_fixed_orbit(const int base_pos)
Definition: groups.h:1755
void get_stabilizer_orbit(int base_pos, orbit &orbit_partition)
Definition: groups.h:1765
void get_generator(int i, automorphism_workspace &automorphism)
Definition: groups.h:1672
dej_nodiscard int get_fixed_orbit_size(const int base_pos)
Definition: groups.h:1745
bool sift(int, const int *p, int nsupp, const int *supp, bool known_in_group=false)
Definition: groups.h:1845
random_schreier(int domain_size, int error=10, bool true_random=false, int seed=0)
Definition: groups.h:1684
bool is_in_fixed_orbit(const int base_pos, const int v)
Definition: groups.h:1736
bool sift(automorphism_workspace &automorphism, bool known_in_group=false)
Definition: groups.h:1832
dej_nodiscard int get_fixed_point(int pos) const
Definition: groups.h:1725
dej_nodiscard int get_number_of_generators() const
Definition: groups.h:1661
dej_nodiscard int base_size() const
Definition: groups.h:1717
void set_base(std::vector< int > &new_base, bool resift_generators=false)
Definition: groups.h:1696
Auxiliary workspace used for Schreier computations.
Definition: groups.h:825
dense_sparse_arbiter loader
Definition: groups.h:840
schreier_workspace(int new_domain_size)
Definition: groups.h:832
automorphism_workspace scratch_auto
Definition: groups.h:847
A transversal in a Schreier structure.
Definition: groups.h:968
void set_size_upper_bound(const int new_sz_upb)
Definition: groups.h:1052
dej_nodiscard const std::vector< int > & get_generators()
Definition: groups.h:1114
bool fix_automorphism(schreier_workspace &w, generating_set &generators, automorphism_workspace &automorphism) const
Definition: groups.h:1198
dej_nodiscard bool is_finished() const
Definition: groups.h:1099
dej_nodiscard const std::vector< int > & get_fixed_orbit()
Definition: groups.h:1110
dej_nodiscard int get_fixed_point() const
Definition: groups.h:1106
void reduce_to_unfinished(schreier_workspace &w, std::vector< int > &selection)
Definition: groups.h:1080
void initialize(const int fixed_vertex, const int new_level, const int new_sz_upb)
Definition: groups.h:1125
dej_nodiscard int find_point(const int p) const
Definition: groups.h:1065
bool extend_with_automorphism(schreier_workspace &w, generating_set &generators, automorphism_workspace &automorphism)
Definition: groups.h:1141
dej_nodiscard int size() const
Definition: groups.h:1048
dej_nodiscard int get_size_upper_bound() const
Definition: groups.h:1056
Stores an automorphism in a dense or sparse manner, dynamically.
Definition: groups.h:698
@ STORE_SPARSE
stored in minimal encoding size of automorphism
Definition: groups.h:701
@ STORE_DENSE
stored densely, in size O(domain_size)
Definition: groups.h:700
stored_automorphism_type get_store_type()
Definition: groups.h:713
void store(int new_domain_size, automorphism_workspace &automorphism, markset &helper)
Definition: groups.h:778
void load(dense_sparse_arbiter &loader, automorphism_workspace &space)
Definition: groups.h:724
void load(automorphism_workspace &automorphism)
Definition: groups.h:747
Random number generation.
Definition: utility.h:104
General-purpose datastructures.
Definition: coloring.h:13
Definition: bfs.h:10
#define dej_assert(expr)
Definition: utility.h:40
#define dej_nodiscard
Definition: utility.h:46