33 #ifndef BACKTRACKSEARCH_H_ 34 #define BACKTRACKSEARCH_H_ 36 #include <permlib/bsgs.h> 37 #include <permlib/predicate/subgroup_predicate.h> 38 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 39 #include <permlib/predicate/group_intersection_predicate.h> 41 #include <permlib/search/base_search.h> 43 #include <boost/scoped_ptr.hpp> 49 template <
class BSGSIN,
class TRANSRET>
52 typedef typename BaseSearch<BSGSIN,TRANSRET>::PERM PERM;
53 typedef typename BaseSearch<BSGSIN,TRANSRET>::TRANS TRANS;
62 BacktrackSearch(
const BSGSIN& bsgs,
unsigned int pruningLevelDCM,
bool breakAfterChildRestriction =
false,
bool stopAfterFirstElement =
false);
70 virtual const std::vector<dom_int>&
subgroupBase()
const;
81 const bool m_breakAfterChildRestriction;
89 template <
class BSGSIN,
class TRANSRET>
91 :
BaseSearch<BSGSIN,TRANSRET>(bsgs, pruningLevelDCM, stopAfterFirstElement),
92 m_breakAfterChildRestriction(breakAfterChildRestriction)
95 template <
class BSGSIN,
class TRANSRET>
97 BOOST_ASSERT(this->
m_pred != 0);
104 unsigned int completed = this->
m_bsgs.n;
106 search(PERM(this->
m_bsgs.n), 0, completed, groupK, groupL);
111 template <
class BSGSIN,
class TRANSRET>
113 BOOST_ASSERT(this->
m_pred != 0);
121 unsigned int completed = this->
m_bsgs.n;
122 search(PERM(this->
m_bsgs.n), 0, completed, groupK, groupL);
127 template <
class BSGSIN,
class TRANSRET>
129 const std::vector<dom_int> &B = this->
m_bsgs.B;
130 std::vector<TRANS > &U = this->
m_bsgs.U;
132 PERMLIB_DEBUG(std::cout <<
"starting with " << g <<
" @ " << level << std::endl;)
135 if (level == B.size() || this->
checkLeaf(level)) {
136 PERMLIB_DEBUG(std::cout <<
"limit reached for " << g <<
" // " << (*this->
m_pred)(g) << std::endl;)
137 return this->
processLeaf(g, level, level, completed, groupK, groupL);
141 std::vector<unsigned long> orbit(U[level].begin(), U[level].end());
142 BOOST_FOREACH(
unsigned long &alpha, orbit) {
145 std::sort(orbit.begin(), orbit.end(), *this->
m_sorter);
146 unsigned int s = orbit.size();
148 std::vector<unsigned long>::const_iterator orbIt;
149 for (orbIt = orbit.begin(); orbIt != orbit.end(); ++orbIt) {
150 if (s < groupK.
U[level].size()) {
151 PERMLIB_DEBUG(std::cout <<
"PRUNE the rest: s=" << s <<
" < " << groupK.
U[level].size() << std::endl;)
158 unsigned long beta = g % *orbIt;
159 PERMLIB_DEBUG(std::cout <<
" BETA = " << beta <<
" <-- " << B[level] << std::endl;)
160 boost::scoped_ptr<PERM> u_beta_ptr(U[level].at(beta));
163 if (!this->
m_pred->childRestriction(*u_beta_ptr, level, B[level])) {
165 if (m_breakAfterChildRestriction)
174 unsigned int ret =
search(*u_beta_ptr, level+1, completed, groupK, groupL);
178 PERMLIB_DEBUG(std::cout <<
"^^ MULTI BACKTRACK! leave " << level <<
" to " << ret << std::endl;)
182 completed = std::min(completed, level);
187 template<
class BSGSIN,
class TRANSRET>
192 template<
class BSGSIN,
class TRANSRET>
200 #endif // -- BACKTRACKSEARCH_H_ boost::scoped_ptr< SubgroupPredicate< PERM > > m_pred
predicate that matches sought elements
Definition: base_search.h:95
virtual PERM::ptr searchCosetRepresentative()
searches for a coset representative if one exists
Definition: base_search.h:271
unsigned long m_statNodesVisited
nodes visited during backtrack search
Definition: base_search.h:81
bool checkLeaf(unsigned int level)
true iff level is a leaf level
Definition: base_search.h:222
searching in a group with classical backtracking
Definition: backtrack_search.h:50
BSGSIN m_bsgs
main BSGS to search in
Definition: base_search.h:91
base class for searching in a group
Definition: base_search.h:45
void search(BSGS< PERM, TRANSRET > &groupK)
searches for a subgroup and stores it into groupK
Definition: backtrack_search.h:96
virtual const std::vector< dom_int > & subgroupBase() const
base of the sought subgroup
Definition: backtrack_search.h:193
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g. a base)
Definition: base_sorter.h:113
const unsigned int m_pruningLevelDCM
leves i with 0 <= i < m_pruningLevelDCM are prunged by advanced double coset minimality ...
Definition: base_search.h:106
static std::vector< unsigned long > createOrder(unsigned int size, InputIterator begin, InputIterator end)
constructs an ordering array with the same parameters as BaseSorter for use with BaseSorterByReferenc...
Definition: base_sorter.h:121
bool pruneDCM(const PERM &t, unsigned int backtrackLevel, BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL)
try to prune with advanced double coset minimality
Definition: base_search.h:188
unsigned long m_statNodesPrunedChildRestriction
number of nodes where a child constraint pruning was in effect
Definition: base_search.h:87
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition: bsgs.h:436
boost::scoped_ptr< BaseSorterByReference > m_sorter
a sorter with respect to m_order
Definition: base_search.h:100
BacktrackSearch(const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool breakAfterChildRestriction=false, bool stopAfterFirstElement=false)
constructor
Definition: backtrack_search.h:90
unsigned long m_statNodesPrunedCosetMinimality
number of nodes where (simple) double coset minimality pruning was in effect
Definition: base_search.h:83
unsigned int processLeaf(const PERM &t, unsigned int level, unsigned int backtrackLevel, unsigned int completed, BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL)
processes a leaf and adds corresponding element to the generator set of K
Definition: base_search.h:227
void construct(SubgroupPredicate< PERM > *pred, bool addPredRefinement)
initializes the search
Definition: backtrack_search.h:188
abstract base class for subgroup (and coset) predicates
Definition: subgroup_predicate.h:45
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
void setupEmptySubgroup(BSGS< PERM, TRANSRET > &group) const
sets up a BSGS structure for an empty group with base subgroupBase()
Definition: base_search.h:263
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
std::vector< unsigned long > m_order
base point order
Definition: base_search.h:98
unsigned long m_statNodesPrunedCosetMinimality2
number of nodes where advanced double coset minimality pruning with base change was in effect ...
Definition: base_search.h:85
Definition: abstract_bsgs.h:49