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);
99 this->setupEmptySubgroup(groupK);
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);
115 this->setupEmptySubgroup(groupK);
116 this->setupEmptySubgroup(groupL);
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;)
133 ++this->m_statNodesVisited;
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;)
152 this->m_statNodesPrunedCosetMinimality += s;
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])) {
164 ++this->m_statNodesPrunedChildRestriction;
165 if (m_breakAfterChildRestriction)
169 if (this->m_pruningLevelDCM && this->pruneDCM(*u_beta_ptr, level, groupK, groupL)) {
170 ++this->m_statNodesPrunedCosetMinimality2;
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>
189 this->m_pred.reset(pred);
192 template<
class BSGSIN,
class TRANSRET>
194 return this->m_bsgs.B;
200 #endif // -- BACKTRACKSEARCH_H_ virtual PERM::ptr searchCosetRepresentative()
searches for a coset representative if one exists
Definition: base_search.h:271
searching in a group with classical backtracking
Definition: backtrack_search.h:50
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
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
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition: bsgs.h:436
BacktrackSearch(const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool breakAfterChildRestriction=false, bool stopAfterFirstElement=false)
constructor
Definition: backtrack_search.h:90
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
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
Definition: abstract_bsgs.h:49