36#include <permlib/change/conjugating_base_change.h>
37#include <permlib/change/random_base_transpose.h>
39#include <boost/dynamic_bitset.hpp>
44template<
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;
131 static PERMlistType ms_emptyList;
138template<
class BSGSIN,
class TRANSRET>
139typename BaseSearch<BSGSIN,TRANSRET>::PERMlistType BaseSearch<BSGSIN,TRANSRET>::ms_emptyList;
142template<
class BSGSIN,
class TRANSRET>
155template<
class BSGSIN,
class TRANSRET>
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);
178 PERMLIB_DEBUG(std::cout <<
"DCM2 beta_p = " << beta_p+1 <<
" , beta_i = " << beta_i+1 << std::endl;)
187template<
class BSGSIN,
class TRANSRET>
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])
221template<
class BSGSIN,
class TRANSRET>
226template<
class BSGSIN,
class TRANSRET>
228 PERMLIB_DEBUG(std::cout <<
"XXX level " << level <<
" bLevel " << backtrackLevel << std::endl;)
230 typedef typename PERM::ptr PERMptr;
239 const bool isIdentity = t.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;)
262template<
class BSGSIN,
class TRANSRET>
267 group.
orbit(i, ms_emptyList);
270template<
class BSGSIN,
class TRANSRET>
unsigned long m_statNodesVisited
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
Definition base_search.h:83
boost::scoped_ptr< SubgroupPredicate< PERM > > m_pred
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
Definition base_search.h:129
unsigned int m_limitLevel
Definition base_search.h:112
const unsigned int m_pruningLevelDCM
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
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
boost::scoped_ptr< BaseSorterByReference > m_sorter
Definition base_search.h:100
bool m_limitInitialized
Definition base_search.h:108
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
Definition base_search.h:127
ConjugatingBaseChange< PERM, TRANS, RandomBaseTranspose< PERM, TRANS > > m_baseChange
Definition base_search.h:103
unsigned long m_statNodesPrunedChildRestriction
Definition base_search.h:87
virtual ~BaseSearch()
destructor
Definition base_search.h:60
virtual const std::vector< dom_int > & subgroupBase() const =0
base of the sought subgroup
BSGSIN * m_bsgs2
Definition base_search.h:93
unsigned int m_limitBase
Definition base_search.h:110
bool checkLeaf(unsigned int level)
true iff level is a leaf level
Definition base_search.h:222
virtual PERM::ptr searchCosetRepresentative(BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL)=0
searches for a coset representative if one exists
unsigned long m_statNodesPrunedCosetMinimality2
Definition base_search.h:85
std::vector< unsigned long > m_order
Definition base_search.h:98
BSGSIN m_bsgs
Definition base_search.h:91
base change by conjugation and, if necessary, transpositions
Definition conjugating_base_change.h:52
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
predicate matching a permutation if it stabilizes a given list of points pointwise
Definition pointwise_stabilizer_predicate.h:42
OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
copies elements of (begin to end) to destBegin if they match the given predicate
Definition common.h:49
std::vector< TRANS > U
transversals along the stabilizer chain
Definition bsgs_core.h:59
std::vector< dom_int > B
base
Definition bsgs_core.h:55
PERMlist S
strong generating set
Definition bsgs_core.h:57
Represents a base and strong generating set (BSGS)
Definition bsgs.h:89
int insertGenerator(const typename PERM::ptr &g, bool updateOrbit)
adds a new group generator
Definition bsgs.h:348
void orbit(unsigned int j, const PERMlist &generators)
re-computes the j-th fundamental orbit with the given orbit generators
Definition bsgs.h:301