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_