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

enum dejavu::search_strategy::dfs_ir::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:

• dfs.h