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

Depth-first search without backtracking. More...

#include <dfs.h>

+ Collaboration diagram for dejavu::search_strategy::dfs_ir:

Public Types

enum  termination_reason { r_none , r_fail , r_cost }
 

Public Member Functions

 dfs_ir (timed_print &printer, groups::automorphism_workspace &automorphism)
 
int paired_recurse_to_equal_leaf (sgraph *g, ir::controller &state_left, ir::controller &state_right, bool recurse=false)
 
int do_paired_dfs (dejavu_hook *hook, sgraph *g, ir::controller &state_left, ir::controller &state_right, std::vector< std::pair< int, int > > &computed_orbits, bool prune=true)
 
int do_simple_dfs (dejavu_hook *hook, sgraph *g, ir::controller &state_right, std::vector< std::pair< int, int > > &computed_orbits, bool prune=true)
 

Public Attributes

termination_reason s_termination = r_none
 
double h_recent_cost_snapshot_limit = 0.25
 
big_number s_grp_sz
 
groups::orbit orbs
 

Detailed Description

Depth-first search without backtracking.

Depth-first IR search which does not backtrack. Can parallelize along the base. Due to the search not back-tracking, this module can not deal with difficult parts of combinatorial graphs.

Definition at line 60 of file dfs.h.

Member Enumeration Documentation

◆ termination_reason

Enumerator
r_none 
r_fail 
r_cost 

Definition at line 66 of file dfs.h.

Constructor & Destructor Documentation

◆ dfs_ir()

dejavu::search_strategy::dfs_ir::dfs_ir ( timed_print printer,
groups::automorphism_workspace automorphism 
)
inlineexplicit

Definition at line 75 of file dfs.h.

Member Function Documentation

◆ do_paired_dfs()

int dejavu::search_strategy::dfs_ir::do_paired_dfs ( dejavu_hook hook,
sgraph g,
ir::controller state_left,
ir::controller state_right,
std::vector< std::pair< int, int > > &  computed_orbits,
bool  prune = true 
)
inline

Definition at line 146 of file dfs.h.

◆ do_simple_dfs()

int dejavu::search_strategy::dfs_ir::do_simple_dfs ( dejavu_hook hook,
sgraph g,
ir::controller state_right,
std::vector< std::pair< int, int > > &  computed_orbits,
bool  prune = true 
)
inline

Definition at line 325 of file dfs.h.

◆ paired_recurse_to_equal_leaf()

int dejavu::search_strategy::dfs_ir::paired_recurse_to_equal_leaf ( sgraph g,
ir::controller state_left,
ir::controller state_right,
bool  recurse = false 
)
inline

Definition at line 78 of file dfs.h.

Member Data Documentation

◆ h_recent_cost_snapshot_limit

double dejavu::search_strategy::dfs_ir::h_recent_cost_snapshot_limit = 0.25

A float in the range [0-1]. Limits continuation of DFS search to whethercomputing recent elements only cost this fraction of the cost of an entire root-to-leaf walk.

Definition at line 70 of file dfs.h.

◆ orbs

groups::orbit dejavu::search_strategy::dfs_ir::orbs

Definition at line 144 of file dfs.h.

◆ s_grp_sz

big_number dejavu::search_strategy::dfs_ir::s_grp_sz

group size

Definition at line 73 of file dfs.h.

◆ s_termination

termination_reason dejavu::search_strategy::dfs_ir::s_termination = r_none

Why did we stop performing DFS? Cost too high, or did we have to backtrack?

Definition at line 67 of file dfs.h.


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