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

schreier	Schreier workspace
automorphism	workspace 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

g	graph
hook	hook to return automorphisms
selector	cell selector
ir_tree	ir tree computed so far
group	Schreier structure to sift found automorphisms into, used to calculate probabilistic abort criterion
local_state	Local workspace used to perform random walks of IR tree
fail_limit	Limits 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

g	graph
hook	hook to return automorphisms
selector	cell selector
ir_tree	ir tree computed so far
group	Schreier structure to sift found automorphisms into, used to calculate probabilistic abort criterion
local_state	Local workspace used to perform random walks of IR tree
fail_limit	Limits 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:

rand.h

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ random_ir()

Member Function Documentation

◆ h_almost_done()

◆ random_walks()

◆ random_walks_from_tree()

◆ reset_statistics()

◆ specific_walk()

◆ use_look_close()

Member Data Documentation

◆ h_hash_col_limit

◆ h_look_close

◆ h_randomize_up_to

◆ h_sift_random

◆ h_sift_random_lim

◆ s_leaves

◆ s_min_split_number

◆ s_paths

◆ s_paths_fail1

◆ s_paths_failany

◆ s_random_sift_success

◆ s_rolling_first_level_success

◆ s_rolling_success

◆ s_succeed

◆ s_trace_cost1