dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
dejavu::search_strategy::random_ir Class Reference

IR search using random walks. More...

#include <rand.h>

Public Member Functions

void use_look_close (bool look_close=false)
 
 random_ir (timed_print &printer, groups::schreier_workspace &schreier, groups::automorphism_workspace &automorphism, random_source &rgenerator)
 
void reset_statistics ()
 
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)
 
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)
 

Static Public Member Functions

static bool h_almost_done (groups::compressed_schreier &group)
 
static void specific_walk (sgraph *g, ir::shared_tree &ir_tree, ir::controller &local_state, std::vector< int > &base_vertex)
 

Public Attributes

double s_rolling_success = 0
 
double s_rolling_first_level_success = 1.0
 
long s_trace_cost1 = 0
 
int s_paths = 0
 
int s_paths_fail1 = 0
 
int s_paths_failany = 0
 
int s_succeed = 0
 
int s_leaves = 0
 
int s_min_split_number = 0
 
int s_random_sift_success = 0
 
bool h_look_close = false
 
const int h_hash_col_limit = 32
 
bool h_sift_random = true
 
int h_sift_random_lim = 8
 
int h_randomize_up_to = INT32_MAX
 

Detailed Description

IR search using random walks.

Performs random walks of the IR shared_tree, sifting resulting automorphisms into the given Schreier structure. If the Schreier structure is complete with respect to the base, or the probabilistic abort criterion satisfied, the process terminates. The algorithm guarantees to find all automorphisms up to the specified error bound.

Alternatively, a limit for the amount of discovered differing leaves can be set.

Objects contain a local workspace which contain datastructures only used for random_ir, as well as settings and for statistics of the search.

Definition at line 26 of file rand.h.

Constructor & Destructor Documentation

◆ random_ir()

dejavu::search_strategy::random_ir::random_ir ( timed_print printer,
groups::schreier_workspace schreier,
groups::automorphism_workspace automorphism,
random_source rgenerator 
)
inline

Links this object to local workspaces.

Parameters
schreierSchreier workspace
automorphismworkspace to store automorphisms

Definition at line 174 of file rand.h.

Member Function Documentation

◆ h_almost_done()

static bool dejavu::search_strategy::random_ir::h_almost_done ( groups::compressed_schreier group)
inlinestatic

Definition at line 194 of file rand.h.

◆ random_walks()

void dejavu::search_strategy::random_ir::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 
)
inline

Performs Monte Carlo IR search.

Returns either when probabilistic or deterministic abort criterion is satisfied, or whenever the fail_limit is reached.

May use non-uniform base-alignment to fill Schreier tables faster.

Parameters
ggraph
hookhook to return automorphisms
selectorcell selector
ir_treeir tree computed so far
groupSchreier structure to sift found automorphisms into, used to calculate probabilistic abort criterion
local_stateLocal workspace used to perform random walks of IR tree
fail_limitLimits the number of random IR walks not leading to a new automorphisms

Definition at line 224 of file rand.h.

◆ random_walks_from_tree()

void dejavu::search_strategy::random_ir::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 
)
inline

Performs Monte Carlo IR search. Uses a given IR tree to initiate the search further down the tree (i.e., if BFS has been performed, we can start from the furthest BFS level).

Returns either when probabilistic or deterministic abort criterion is satisfied, or whenever the fail_limit is reached.

Parameters
ggraph
hookhook to return automorphisms
selectorcell selector
ir_treeir tree computed so far
groupSchreier structure to sift found automorphisms into, used to calculate probabilistic abort criterion
local_stateLocal workspace used to perform random walks of IR tree
fail_limitLimits the number of random IR walks not leading to a new automorphisms

Definition at line 392 of file rand.h.

◆ reset_statistics()

void dejavu::search_strategy::random_ir::reset_statistics ( )
inline

Resets all recorded statistics.

Definition at line 182 of file rand.h.

◆ specific_walk()

static void dejavu::search_strategy::random_ir::specific_walk ( sgraph g,
ir::shared_tree ir_tree,
ir::controller local_state,
std::vector< int > &  base_vertex 
)
inlinestatic

Definition at line 199 of file rand.h.

◆ use_look_close()

void dejavu::search_strategy::random_ir::use_look_close ( bool  look_close = false)
inline

Definition at line 164 of file rand.h.

Member Data Documentation

◆ h_hash_col_limit

const int dejavu::search_strategy::random_ir::h_hash_col_limit = 32

limit for how many hash collisions are allowed

Definition at line 159 of file rand.h.

◆ h_look_close

bool dejavu::search_strategy::random_ir::h_look_close = false

whether to use trace early out on first level

Definition at line 158 of file rand.h.

◆ h_randomize_up_to

int dejavu::search_strategy::random_ir::h_randomize_up_to = INT32_MAX

randomize vertex selection up to this level

Definition at line 162 of file rand.h.

◆ h_sift_random

bool dejavu::search_strategy::random_ir::h_sift_random = true

sift random elements into Schreier structure

Definition at line 160 of file rand.h.

◆ h_sift_random_lim

int dejavu::search_strategy::random_ir::h_sift_random_lim = 8

after how many paths random elements are sifted

Definition at line 161 of file rand.h.

◆ s_leaves

int dejavu::search_strategy::random_ir::s_leaves = 0

how many leaves were added

Definition at line 152 of file rand.h.

◆ s_min_split_number

int dejavu::search_strategy::random_ir::s_min_split_number = 0

Definition at line 153 of file rand.h.

◆ s_paths

int dejavu::search_strategy::random_ir::s_paths = 0

how many total paths have been computed

Definition at line 148 of file rand.h.

◆ s_paths_fail1

int dejavu::search_strategy::random_ir::s_paths_fail1 = 0

how many total paths failed on first level

Definition at line 149 of file rand.h.

◆ s_paths_failany

int dejavu::search_strategy::random_ir::s_paths_failany = 0

how many total paths have failed

Definition at line 150 of file rand.h.

◆ s_random_sift_success

int dejavu::search_strategy::random_ir::s_random_sift_success = 0

Definition at line 155 of file rand.h.

◆ s_rolling_first_level_success

double dejavu::search_strategy::random_ir::s_rolling_first_level_success = 1.0

rolling probability how many random paths succeed on the first level

Definition at line 144 of file rand.h.

◆ s_rolling_success

double dejavu::search_strategy::random_ir::s_rolling_success = 0

rolling probability how many random paths succeed

Definition at line 143 of file rand.h.

◆ s_succeed

int dejavu::search_strategy::random_ir::s_succeed = 0

how many total paths have succeeded

Definition at line 151 of file rand.h.

◆ s_trace_cost1

long dejavu::search_strategy::random_ir::s_trace_cost1 = 0

total cost incurred on first level

Definition at line 147 of file rand.h.


The documentation for this class was generated from the following file: