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>
49template <
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);
81 const bool m_breakAfterChildRestriction;
89template <
class BSGSIN,
class TRANSRET>
91 :
BaseSearch<BSGSIN,TRANSRET>(bsgs, pruningLevelDCM, stopAfterFirstElement),
92 m_breakAfterChildRestriction(breakAfterChildRestriction)
95template <
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);
111template <
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);
127template <
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);
187template<
class BSGSIN,
class TRANSRET>
192template<
class BSGSIN,
class TRANSRET>
unsigned long m_statNodesVisited
nodes visited during backtrack search
Definition base_search.h:81
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
unsigned long m_statNodesPrunedCosetMinimality
number of nodes where (simple) double coset minimality pruning was in effect
Definition base_search.h:83
boost::scoped_ptr< SubgroupPredicate< PERM > > m_pred
predicate that matches sought elements
Definition base_search.h:95
void setupEmptySubgroup(BSGS< PERM, TRANSRET > &group) const
sets up a BSGS structure for an empty group with base subgroupBase()
Definition base_search.h:263
PERM::ptr m_lastElement
last element found with desired property; only used if m_stopAfterFirstElement is true
Definition base_search.h:129
const unsigned int m_pruningLevelDCM
leves i with 0 <= i < m_pruningLevelDCM are prunged by advanced double coset minimality
Definition base_search.h:106
virtual PERM::ptr searchCosetRepresentative()
searches for a coset representative if one exists
Definition base_search.h:271
BaseSearch(const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement)
constructor
Definition base_search.h:143
boost::scoped_ptr< BaseSorterByReference > m_sorter
a sorter with respect to m_order
Definition base_search.h:100
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
const bool m_stopAfterFirstElement
true iff the search can be stopped after the first element found with the desired property
Definition base_search.h:127
unsigned long m_statNodesPrunedChildRestriction
number of nodes where a child constraint pruning was in effect
Definition base_search.h:87
unsigned long m_statNodesPrunedCosetMinimality2
number of nodes where advanced double coset minimality pruning with base change was in effect
Definition base_search.h:85
std::vector< unsigned long > m_order
base point order
Definition base_search.h:98
BSGSIN m_bsgs
main BSGS to search in
Definition base_search.h:91
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g....
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
abstract base class for subgroup (and coset) predicates
Definition subgroup_predicate.h:45
virtual const std::vector< dom_int > & subgroupBase() const
base of the sought subgroup
Definition backtrack_search.h:193
void search(BSGS< PERM, TRANSRET > &groupK)
searches for a subgroup and stores it into groupK
Definition backtrack_search.h:96
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
virtual BaseSearch< BSGSIN, TRANSRET >::PERM::ptr searchCosetRepresentative(BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL)
unsigned int search(const PERM &t, unsigned int level, unsigned int &completed, BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL)
recursive backtrack search
Definition backtrack_search.h:128
std::vector< TRANS > U
transversals along the stabilizer chain
Definition bsgs_core.h:59
Represents a base and strong generating set (BSGS)
Definition bsgs.h:89
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition bsgs.h:437