dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
rand.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_RAND_H
6#define DEJAVU_RAND_H
7
8#include "ir.h"
9#include "groups.h"
10
11namespace dejavu {namespace search_strategy {
12 // (need to nest namespaces due to C++ 14)
13
26 class random_ir {
27 private:
28 random_source& rng;
29 std::vector<int> heuristic_reroll;
30
31 timed_print& gl_printer;
32 groups::schreier_workspace& gl_schreierw;
33 groups::automorphism_workspace& gl_automorphism;
34
44 static void load_state_from_leaf(sgraph *g, ir::controller &local_state, ir::limited_save &start_from,
45 ir::stored_leaf *leaf) {
47 std::vector<int> base;
48 base.reserve(leaf->get_lab_or_base_size());
49 for(int i = 0; i < leaf->get_lab_or_base_size(); ++i) base.push_back(leaf->get_lab_or_base()[i]);
50 local_state.walk(g, start_from, base);
51 }
52
58 bool add_leaf_to_storage_and_group(sgraph *g, dejavu_hook *hook, groups::compressed_schreier &group,
59 ir::shared_leaves &leaf_storage, ir::controller &local_state,
60 ir::controller &other_state, ir::limited_save &root_save, bool uniform) {
61 dej_assert(g->v_size == local_state.c->cells);
62
63 // outer loop to handle hash collisions -- at most h_hash_col_limit will be checked and stored
64 for(int hash_offset = 0; hash_offset < h_hash_col_limit; ++hash_offset) {
65 // after first hash collision, we write a stronger invariant
66 if(hash_offset == 1) local_state.write_strong_invariant_quarter(g);
67
68 // after second hash collision, an even stronger one
69 if(hash_offset == 2) local_state.write_strong_invariant(g);
70
71 // first, test whether leaf with same hash has already been stored
72 const unsigned long hash_c = local_state.T->get_hash() + hash_offset; // '+hash_offset' is for hash
73 // collisions
74 auto other_leaf = leaf_storage.lookup_leaf(hash_c);
75
76 // if not, add leaf to leaf_storage
77 if (other_leaf == nullptr) {
78 ++s_leaves;
80 s_rolling_success = (9.0 * s_rolling_success + 0.0) / 10.0;
81 leaf_storage.add_leaf(hash_c, *local_state.c, local_state.base_vertex);
82 break;
83 }
84
85 // if there is a leaf with the same hash, load the leaf and test automorphism
86 gl_automorphism.reset();
87
88 if(other_leaf->get_store_type() == ir::stored_leaf::STORE_LAB) {
89 // sometimes, a lab array is already stored for the leaf
90 const int* lab = other_leaf->get_lab_or_base();
91 gl_automorphism.write_color_diff(local_state.c->vertex_to_col, lab);
92 } else {
93 // other times, it is not and we need to recompute the walk to this leaf
94 load_state_from_leaf(g, other_state, root_save, other_leaf);
95 gl_automorphism.write_color_diff(local_state.c->vertex_to_col, other_state.c->lab);
96 }
97
98 // certify whether we actually found an automorphism
99 const bool cert = local_state.certify(g, gl_automorphism);
100
101 if (cert) {
102 // We found an automorphism!
103 s_rolling_success = (9.0 * s_rolling_success + 1.0) / 10.0;
104 ++s_succeed;
105
106 // output the automorphism
107 if(hook) (*hook)(g->v_size, gl_automorphism.p(), gl_automorphism.nsupp(),
108 gl_automorphism.supp());
109
110 // sift automorphism into Schreier structure
111 bool sift = group.sift(gl_schreierw, gl_automorphism, uniform);
112 gl_automorphism.reset();
113
114 // if sifting changed the Schreier structure, consider sifting some more random elements to fill
115 // up the Schreier structure
116 if(sift && group.s_densegen() + group.s_sparsegen() > 1 && s_random_sift_success > -5) {
117 int fail = 3; // 3
118 bool any_changed = false;
119 while(fail >= 0) {
120 const bool sift_changed = group.sift_random(gl_schreierw, gl_automorphism, rng);
121 any_changed = sift_changed || any_changed;
122 fail -= !sift_changed;
123 }
124
125 s_random_sift_success += any_changed?1:-1;
126 s_random_sift_success = std::max(std::min(s_random_sift_success, 5), -5);
127 }
128
129 // reset automorphism workspace to identity, return result of sift
130 gl_automorphism.reset();
131 return sift;
132 }
133
134 // actually, this wasn't an automorphism: there was a collision for the value of the invariant, even
135 // though leaves are not equivalent
136 }
137 gl_automorphism.reset();
138 return false;
139 }
140
141 public:
142 // stats
143 double s_rolling_success = 0;
147 long s_trace_cost1 = 0;
148 int s_paths = 0;
151 int s_succeed = 0;
152 int s_leaves = 0;
154
156
157 // settings for heuristics
158 bool h_look_close = false;
159 const int h_hash_col_limit = 32;
160 bool h_sift_random = true;
162 int h_randomize_up_to = INT32_MAX;
164 void use_look_close(bool look_close = false) {
165 h_look_close = look_close;
166 }
167
175 groups::automorphism_workspace& automorphism, random_source& rgenerator) :
176 rng(rgenerator), gl_printer(printer), gl_schreierw(schreier), gl_automorphism(automorphism)
177 {}
178
183 s_paths = 0;
184 s_paths_fail1 = 0;
185 s_trace_cost1 = 0;
186 s_paths_failany = 0;
187 s_leaves = 0;
188 s_succeed = 0;
191 s_min_split_number = INT32_MAX;
192 }
193
195 return group.get_consecutive_success() >= 2;
196 }
197
198 static void
199 specific_walk(sgraph *g, ir::shared_tree &ir_tree, ir::controller &local_state, std::vector<int> &base_vertex) {
200 local_state.walk(g, *ir_tree.pick_node_from_level(0,0)->get_save(), base_vertex);
201 auto other_leaf = ir_tree.stored_leaves.lookup_leaf(local_state.T->get_hash());
202 if(other_leaf == nullptr) {
203 ir_tree.stored_leaves.add_leaf(local_state.T->get_hash(), *local_state.c, local_state.base_vertex);
204 }
205 }
206
224 void random_walks(sgraph *g, dejavu_hook *hook, std::function<ir::type_selector_hook> *selector,
225 ir::shared_tree &ir_tree, groups::compressed_schreier &group, ir::controller &local_state,
226 ir::controller& other_state, int fail_limit) {
227 local_state.use_reversible(false);
228 local_state.use_trace_early_out(false);
229 other_state.use_reversible(false);
230 other_state.use_trace_early_out(false);
231
232 // start from root of tree initially
233 ir::limited_save my_own_save;
234 ir::limited_save* root_save = ir_tree.pick_node_from_level(0, 0)->get_save();
235 ir::limited_save* start_from = root_save;
236
237 // other_state is used to retrieve leaves that are stored as walks of the tree
238 other_state.link_compare(&local_state);
239
240 // we want to record how expensive walks are
241 const int s_cell_initial = start_from->get_coloring()->cells;
242 double progress_initial = 1.0 * s_cell_initial / g->v_size;
243
244 const int target_level = ir_tree.get_finished_up_to();
245
246 int s_sifting_success = 0;
247
248 // continue until budget exhausted, or search successful
250 s_paths_failany < fail_limit) {
251 local_state.load_reduced_state(*start_from);
252
253 int could_start_from = group.finished_up_to_level();
254
255 // print progress, sometimes
256 if(s_paths_failany > 8 && (s_paths & 0x00000FFF) == 0x000000FE)
257 gl_printer.progress_current_method("random", "leaves", ir_tree.stat_leaves(), "f1", s_paths_fail1,
258 "compress", group.s_compression_ratio);
259
260 // can start from below the root if we finished Schreier table at the current root
261 if(local_state.s_base_pos <= could_start_from) {
262 while (local_state.s_base_pos <= could_start_from) {
263 local_state.move_to_child(g, group.base_point(local_state.s_base_pos));
264 }
265 dej_assert(local_state.T->trace_equal());
266 local_state.save_reduced_state(my_own_save); // from now on, we start from this save!
267 start_from = &my_own_save;
268
269 const int s_cells_now = start_from->get_coloring()->cells;
270 const double progress_now = 1.0 * s_cells_now / g->v_size;
271
272 if(progress_now - progress_initial > 0.1) {
273 gl_printer.progress_current_method("random", "root_cells", 1.0 * s_cells_now / g->v_size,
274 "base_pos", could_start_from,
275 "sift", s_sifting_success, "rsift", s_random_sift_success);
276 progress_initial = progress_now;
277 }
278 }
279
280 const int start_from_base_pos = local_state.s_base_pos;
281 int base_pos = local_state.s_base_pos;
282
283 // track whether current walk is base-aware and/or uniform
284 //bool base_aligned = true;
285 bool uniform = true;
286
287 //walk down the tree as long as we are not in a leaf
288 while (g->v_size != local_state.c->cells) {
289 const int col = (*selector)(local_state.c, base_pos);
290 const int col_sz = local_state.c->ptn[col] + 1;
291 const int rand = rng() % col_sz;
292 int choose_pos = col + rand;
293
294 // if we are beyond where we need to sift, and we don't want to sample uniformly at random, we
295 // stop picking random elements whatsoever
296 /*if(base_pos >= h_randomize_up_to && !h_sift_random && ir_tree.stored_leaves.s_leaves <= 1 &&
297 base_pos < static_cast<int>(local_state.compare_base_vertex->size())) {
298 uniform = false; // sampled leaf not uniform anymore now
299 choose_pos = col; // just pick first vertex of color
300
301 // or even better: let's choose the base vertex, if it's in the correct color
302 const int v_base = (*local_state.compare_base_vertex)[base_pos];
303 const int v_base_col = local_state.c->vertex_to_col[v_base];
304 if(col == v_base_col) choose_pos = local_state.c->vertex_to_lab[v_base];
305 }*/
306
307 // in the case where we are not succeeding in sifting randomly generated elements in the group
308 // itself, let's try to create sparse generators by trying to stick to the base after a few
309 // individualizations
310 if(base_pos > start_from_base_pos + 1 && g->v_size > 5000 && s_sifting_success >= 0 &&
312 base_pos < static_cast<int>(local_state.compare_base_vertex->size())) {
313 // or even better: let's choose the base vertex, if it's in the correct color
314 const int v_base = (*local_state.compare_base_vertex)[base_pos];
315 const int v_base_col = local_state.c->vertex_to_col[v_base];
316
317 if(col == v_base_col) {
318 uniform = false;
319 choose_pos = local_state.c->vertex_to_lab[v_base];
320 }
321 }
322
323 int v = local_state.c->lab[choose_pos];
324
325 // base-aware search: if we are still walking along the base, and the vertex we picked is in the
326 // same orbit as the base -- we might as well keep walking on the base, or choose a different vertex
327 if(group.finished_up_to_level() + 1 == base_pos && group.is_in_base_orbit(base_pos, v)
328 && ir_tree.stored_leaves.s_leaves <= 1) {
329 heuristic_reroll.clear();
330 for(int i = 0; i < col_sz; ++i) {
331 heuristic_reroll.push_back(local_state.c->lab[col + i]);
332 }
333 group.reduce_to_unfinished(gl_schreierw, heuristic_reroll, base_pos);
334 if(!heuristic_reroll.empty()) {
335 const int rand_reroll = rng() % static_cast<int>(heuristic_reroll.size());
336 v = heuristic_reroll[rand_reroll];
337 }
338 }
339
340 dej_assert(local_state.c->vertex_to_col[v] == col);
341 const int trace_pos_pre = local_state.T->get_position();
342 local_state.use_trace_early_out((base_pos == target_level) && !h_look_close);
343 local_state.move_to_child(g, v);
344
345 // keep track of some statistics for the first individualization (these statistics are used for
346 // decisions concerning breadth-first search)
347 if(base_pos == target_level) {
349 s_trace_cost1 += local_state.T->get_position() - trace_pos_pre;
350 s_paths_fail1 += !local_state.T->trace_equal();
352 (9.0 * s_rolling_first_level_success + (local_state.T->trace_equal())) / 10.0;
353 if(!h_look_close && !local_state.T->trace_equal()) break;
354 }
355
356 ++base_pos;
357 dej_assert(base_pos == local_state.s_base_pos);
358 }
359
360 ++s_paths;
361 if(base_pos == target_level) { // did not arrive in a leaf
363 continue;
364 }
365
366 // we arrived at a leaf... let's check whether we already have an equivalent leaf to form an
367 // automorphism -- and otherwise we just add this leaf to the storage
368 const bool sift = add_leaf_to_storage_and_group(g, hook, group, ir_tree.stored_leaves, local_state,
369 other_state, *root_save, uniform);
370 s_sifting_success += sift?1:-1;
371 s_sifting_success += sift && !uniform?1:0;
372 s_sifting_success = std::max(std::min(s_sifting_success, 10), -10);
373 }
374 }
375
392 void random_walks_from_tree(sgraph *g, dejavu_hook *hook, std::function<ir::type_selector_hook> *selector,
394 ir::controller &local_state, ir::controller& other_state, int fail_limit) {
395 local_state.use_reversible(false);
396 local_state.use_trace_early_out(false);
398 const int pick_from_level = ir_tree.get_finished_up_to();
399
400 // other_state is used to retrieve leaves that are stored as walks of the tree
401 other_state.link_compare(&local_state);
402
403 // continue until budget exhausted, or search successful
405 s_paths_failany < fail_limit) {
406
407 // print progress, sometimes
408 if((s_paths & 0x000000FF) == 0x000000FE)
409 gl_printer.progress_current_method("random", "leaves", ir_tree.stat_leaves(), "f1", s_paths_fail1,
410 "compress", group.s_compression_ratio);
411
412 // start walk from random node at current breadth-first level
413 auto node = ir_tree.pick_node_from_level(pick_from_level, rng());
414 local_state.load_reduced_state(*node->get_save());
415
416 int base_pos = local_state.s_base_pos;
417 const int start_from_base_pos = base_pos;
418
419 // now perform the random walk
420 while (g->v_size != local_state.c->cells) {
421 const int col = (*selector)(local_state.c, base_pos);
422 const int col_sz = local_state.c->ptn[col] + 1;
423 const int rand = rng() % col_sz;
424 int v = local_state.c->lab[col + rand];
425 const int trace_pos_pre = local_state.T->get_position();
426 local_state.use_trace_early_out((base_pos == start_from_base_pos) && !h_look_close);
427 local_state.move_to_child(g, v);
428
429 if(base_pos == start_from_base_pos) {
431 s_trace_cost1 += local_state.T->get_position() - trace_pos_pre;
432 s_paths_fail1 += !local_state.T->trace_equal();
434 (9.0 * s_rolling_first_level_success + (local_state.T->trace_equal())) / 10.0;
435 if(!h_look_close && !local_state.T->trace_equal()) break;
436 }
437 ++base_pos;
438 }
439
440 ++s_paths;
441 if(base_pos == start_from_base_pos) {
443 continue;
444 }
445
446 // we arrived at a leaf... let's check whether we already have an equivalent leaf to form an
447 // automorphism -- and otherwise we just add this leaf to the storage
448 add_leaf_to_storage_and_group(g, hook, group, ir_tree.stored_leaves, local_state, other_state,
449 *ir_tree.pick_node_from_level(0, 0)->get_save(), true);
450 }
451 }
452 };
453}}
454
455#endif //DEJAVU_RAND_H
Workspace for sparse automorphisms.
Definition: groups.h:68
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
dej_nodiscard int * p() const
Definition: groups.h:483
dej_nodiscard int * supp() const
Definition: groups.h:490
Compressed Schreier structure.
Definition: groups.h:1976
dej_nodiscard bool deterministic_abort_criterion() const
Definition: groups.h:2190
bool sift(schreier_workspace &w, automorphism_workspace &automorphism, bool uniform=false)
Definition: groups.h:2148
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 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 int s_densegen() const
Definition: groups.h:1998
dej_nodiscard bool probabilistic_abort_criterion() const
Definition: groups.h:2183
dej_nodiscard int finished_up_to_level() const
Definition: groups.h:2218
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
Auxiliary workspace used for Schreier computations.
Definition: groups.h:825
Reduced IR save state.
Definition: ir.h:47
coloring * get_coloring()
Definition: ir.h:69
Collection of leaves.
Definition: ir.h:1841
stored_leaf * lookup_leaf(unsigned long hash)
Definition: ir.h:1868
void add_leaf(unsigned long hash, coloring &c, std::vector< int > &base)
Definition: ir.h:1883
IR tree structure.
Definition: ir.h:1982
int stat_leaves() const
Definition: ir.h:2084
dej_nodiscard int get_finished_up_to() const
Definition: ir.h:2222
ir::tree_node * pick_node_from_level(const int level, int num)
Definition: ir.h:2216
shared_leaves stored_leaves
Definition: ir.h:1998
@ STORE_LAB
stores coloring of the leaf
Definition: ir.h:1802
@ STORE_BASE
stores only base of the leaf
Definition: ir.h:1803
int get_lab_or_base_size()
Definition: ir.h:1822
const int * get_lab_or_base()
Definition: ir.h:1818
dej_nodiscard stored_leaf_type get_store_type() const
Definition: ir.h:1826
dej_nodiscard int get_position() const
Definition: trace.h:316
dej_nodiscard unsigned long get_hash() const
Definition: trace.h:257
dej_nodiscard bool trace_equal() const
Definition: trace.h:272
limited_save * get_save()
Definition: ir.h:1941
Random number generation.
Definition: utility.h:104
IR search using random walks.
Definition: rand.h:26
static void specific_walk(sgraph *g, ir::shared_tree &ir_tree, ir::controller &local_state, std::vector< int > &base_vertex)
Definition: rand.h:199
static bool h_almost_done(groups::compressed_schreier &group)
Definition: rand.h:194
void random_walks_from_tree(sgraph *g, dejavu_hook *hook, std::function< ir::type_selector_hook > *selector, ir::shared_tree &ir_tree, groups::compressed_schreier &group, ir::controller &local_state, ir::controller &other_state, int fail_limit)
Definition: rand.h:392
void random_walks(sgraph *g, dejavu_hook *hook, std::function< ir::type_selector_hook > *selector, ir::shared_tree &ir_tree, groups::compressed_schreier &group, ir::controller &local_state, ir::controller &other_state, int fail_limit)
Definition: rand.h:224
random_ir(timed_print &printer, groups::schreier_workspace &schreier, groups::automorphism_workspace &automorphism, random_source &rgenerator)
Definition: rand.h:174
void use_look_close(bool look_close=false)
Definition: rand.h:164
Internal graph data structure.
Definition: graph.h:19
int v_size
Definition: graph.h:48
Prints information to the console.
Definition: utility.h:237
void progress_current_method(const std::string &print) const
Definition: utility.h:301
Definition: bfs.h:10
Controls movement in IR tree.
Definition: ir.h:130
std::vector< int > * compare_base_vertex
Definition: ir.h:141
void link_compare(controller *state)
Definition: ir.h:703
coloring * c
Definition: ir.h:132
void save_reduced_state(limited_save &state)
Definition: ir.h:883
void move_to_child(sgraph *g, int v)
Definition: ir.h:989
void walk(sgraph *g, ir::limited_save &start_from, std::vector< int > &vertices)
Definition: ir.h:1104
void use_reversible(const bool reversible)
Definition: ir.h:816
void use_trace_early_out(bool trace_early_out)
Definition: ir.h:831
void load_reduced_state(limited_save &state)
Definition: ir.h:893
void write_strong_invariant_quarter(const sgraph *g) const
Definition: ir.h:968
int get_number_of_splits()
Definition: ir.h:415
std::vector< int > base_vertex
Definition: ir.h:138
void write_strong_invariant(const sgraph *g) const
Definition: ir.h:948
bool certify(sgraph *g, groups::automorphism_workspace &automorphism)
Definition: ir.h:1123
#define dej_assert(expr)
Definition: utility.h:40
std::function< void(int, const int *, int, const int *)> dejavu_hook
Definition: utility.h:95