33 #ifndef BASE_SEARCH_H_ 34 #define BASE_SEARCH_H_ 36 #include <permlib/change/conjugating_base_change.h> 37 #include <permlib/change/random_base_transpose.h> 39 #include <boost/dynamic_bitset.hpp> 44 template<
class BSGSIN,
class TRANSRET>
47 typedef typename BSGSIN::PERMtype PERM;
48 typedef typename BSGSIN::TRANStype TRANS;
49 typedef std::list<typename PERM::ptr> PERMlistType;
57 BaseSearch(
const BSGSIN& bsgs,
unsigned int pruningLevelDCM,
bool stopAfterFirstElement);
95 boost::scoped_ptr<SubgroupPredicate<PERM> >
m_pred;
121 virtual const std::vector<dom_int>&
subgroupBase()
const = 0;
131 static PERMlistType ms_emptyList;
138 template<
class BSGSIN,
class TRANSRET>
142 template<
class BSGSIN,
class TRANSRET>
144 : m_statNodesVisited(0), m_statNodesPrunedCosetMinimality(0), m_statNodesPrunedCosetMinimality2(0),
145 m_statNodesPrunedChildRestriction(0),
146 m_bsgs(bsgs), m_bsgs2(0), m_pred(0), m_baseChange(m_bsgs),
147 m_pruningLevelDCM(pruningLevelDCM),
148 m_limitInitialized(false), m_limitBase(0), m_limitLevel(0),
149 m_stopAfterFirstElement(stopAfterFirstElement),
155 template<
class BSGSIN,
class TRANSRET>
162 return (*m_sorter)(beta_i, alpha);
166 boost::dynamic_bitset<> orbitCharacteristic(m_bsgs.n);
167 orbitCharacteristic.set(alpha, 1);
168 std::list<unsigned long> orbit;
169 orbit.push_back(alpha);
170 for (std::list<unsigned long>::const_iterator it = orbit.begin(); it != orbit.end(); ++it) {
171 unsigned long beta = *it;
172 BOOST_FOREACH(
const typename PERM::ptr& p, S_i) {
173 unsigned long beta_p = *p / beta;
174 if (!orbitCharacteristic[beta_p]) {
175 orbitCharacteristic.set(beta_p, 1);
176 orbit.push_back(beta_p);
177 if ((*m_sorter)(beta_p, beta_i)) {
178 PERMLIB_DEBUG(std::cout <<
"DCM2 beta_p = " << beta_p+1 <<
" , beta_i = " << beta_i+1 << std::endl;)
187 template<
class BSGSIN,
class TRANSRET>
190 if (backtrackLevel < m_pruningLevelDCM) {
192 std::vector<unsigned long> newBaseImage(subgroupBase().begin(), subgroupBase().end());
193 for (
unsigned int j=0; j<=backtrackLevel; ++j)
194 newBaseImage[j] = t / newBaseImage[j];
197 cbc.
change(groupL, newBaseImage.begin(), newBaseImage.begin() + (backtrackLevel+1),
false);
201 const unsigned long alpha = groupK.
B[backtrackLevel];
203 for (
unsigned int i = 0; i <= backtrackLevel; ++i) {
204 if (i == backtrackLevel || groupK.
U[i].contains(alpha)) {
205 PERMLIB_DEBUG(std::cout <<
"DCM2 found " << (alpha+1) <<
" in U_" << i <<
" btLevel " << backtrackLevel << std::endl;)
206 PERMLIB_DEBUG(std::cout <<
" t = " << t << std::endl;)
208 if (!minOrbit(t / alpha, groupL, i, t / groupK.
B[i])) {
209 PERMLIB_DEBUG(std::cout <<
"DCM2 : " << ((t / groupK.
B[i]) + 1) <<
" // " << ((t / alpha) + 1) << std::endl;)
210 PERMLIB_DEBUG(std::cout <<
" K = " << groupK << std::endl;)
211 PERMLIB_DEBUG(std::cout <<
" L = " << groupL << std::endl;)
215 if (t / groupK.
B[i] != groupL.
B[i])
221 template<
class BSGSIN,
class TRANSRET>
223 return m_limitInitialized && level >= m_limitLevel;
226 template<
class BSGSIN,
class TRANSRET>
228 PERMLIB_DEBUG(std::cout <<
"XXX level " << level <<
" bLevel " << backtrackLevel << std::endl;)
229 PERMLIB_DEBUG(std::cout <<
"XXX limitLevel " << m_limitLevel <<
" limitBase " << m_limitBase << std::endl;)
230 typedef typename PERM::ptr PERMptr;
232 if ( ! (*m_pred)(t) )
235 if (m_stopAfterFirstElement) {
236 m_lastElement =
typename PERM::ptr(
new PERM(t));
239 const bool isIdentity = t.isIdentity();
240 if (m_limitInitialized && level == m_limitLevel && isIdentity) {
242 BOOST_FOREACH(
const PERMptr &s, m_bsgs.S) {
244 PERMLIB_DEBUG(std::cout << *s <<
" extended gen\n";)
245 BOOST_ASSERT((*m_pred)(*s));
246 PERMptr sK(
new PERM(*s));
247 PERMptr sL(
new PERM(*s));
252 }
else if (!isIdentity) {
253 PERMptr genK(
new PERM(t));
254 PERMptr genL(
new PERM(t));
257 PERMLIB_DEBUG(std::cout <<
"-- accepted" << std::endl;)
262 template<
class BSGSIN,
class TRANSRET>
264 group.
B = subgroupBase();
265 group.
U.resize(subgroupBase().size(), TRANSRET(this->m_bsgs.n));
266 for (
unsigned int i=0; i<subgroupBase().size(); ++i)
267 group.
orbit(i, ms_emptyList);
270 template<
class BSGSIN,
class TRANSRET>
275 setupEmptySubgroup(groupK);
276 setupEmptySubgroup(groupL);
278 return this->searchCosetRepresentative(groupK, groupL);
283 #endif // -- BASE_SEARCH_H_ boost::scoped_ptr< SubgroupPredicate< PERM > > m_pred
predicate that matches sought elements
Definition: base_search.h:95
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
virtual PERM::ptr searchCosetRepresentative()
searches for a coset representative if one exists
Definition: base_search.h:271
base change by conjugation and, if necessary, transpositions
Definition: conjugating_base_change.h:52
BSGSIN * m_bsgs2
second BSGS of a group the sough elements have to member of
Definition: base_search.h:93
bool minOrbit(unsigned long alpha, BSGS< PERM, TRANSRET > &groupK, unsigned int i, unsigned long beta_i) const
finds minimal elements in an orbit
Definition: base_search.h:156
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
BSGSIN m_bsgs
main BSGS to search in
Definition: base_search.h:91
virtual ~BaseSearch()
destructor
Definition: base_search.h:60
bool m_limitInitialized
true iff other m_limit variables have been initialized
Definition: base_search.h:108
base class for searching in a group
Definition: base_search.h:45
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: pointwise_stabilizer_predicate.h:42
ConjugatingBaseChange< PERM, TRANS, RandomBaseTranspose< PERM, TRANS > > m_baseChange
base change algorithm
Definition: base_search.h:103
const unsigned int m_pruningLevelDCM
leves i with 0 <= i < m_pruningLevelDCM are prunged by advanced double coset minimality ...
Definition: base_search.h:106
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
boost::scoped_ptr< BaseSorterByReference > m_sorter
a sorter with respect to m_order
Definition: base_search.h:100
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
unsigned int change(BSGS< PERM, TRANS > &bsgs, InputIterator baseBegin, InputIterator baseEnd, bool skipRedundant=false) const
changes base of bsgs so that it starts with the sequence given by baseBegin to baseEnd ...
Definition: conjugating_base_change.h:73
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
virtual const std::vector< dom_int > & subgroupBase() const =0
base of the sought subgroup
PERM::ptr m_lastElement
last element found with desired property; only used if m_stopAfterFirstElement is true ...
Definition: base_search.h:129
unsigned int m_limitLevel
maximal backtrack level
Definition: base_search.h:112
BaseSearch(const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement)
constructor
Definition: base_search.h:143
int insertGenerator(const typename PERM::ptr &g, bool updateOrbit)
adds a new group generator
Definition: bsgs.h:347
unsigned int m_limitBase
number of base points that correspond to maximal backtrack level m_limitLevel
Definition: base_search.h:110
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
void orbit(unsigned int j, const PERMlist &generators)
re-computes the j-th fundamental orbit with the given orbit generators
Definition: bsgs.h:300
unsigned long m_statNodesPrunedCosetMinimality2
number of nodes where advanced double coset minimality pruning with base change was in effect ...
Definition: base_search.h:85
PERMlist S
strong generating set
Definition: bsgs_core.h:57
Definition: abstract_bsgs.h:49