36 #include <permlib/predicate/subgroup_predicate.h> 38 #include <permlib/search/base_search.h> 40 #include <permlib/search/partition/partition.h> 41 #include <permlib/search/partition/refinement_family.h> 42 #include <permlib/search/partition/backtrack_refinement.h> 44 #include <permlib/change/conjugating_base_change.h> 45 #include <permlib/change/random_base_transpose.h> 47 #include <permlib/sorter/base_sorter.h> 55 template<
class BSGSIN,
class TRANSRET>
58 typedef typename BaseSearch<BSGSIN,TRANSRET>::PERM PERM;
59 typedef typename BaseSearch<BSGSIN,TRANSRET>::TRANS TRANS;
67 RBase(
const BSGSIN& bsgs,
unsigned int pruningLevelDCM,
bool stopAfterFirstElement =
false);
69 typedef typename Refinement<PERM>::RefinementPtr RefinementPtr;
70 typedef typename RefinementFamily<PERM>::PartitionPtr PartitionPtr;
71 typedef typename std::list<std::pair<PartitionPtr,RefinementPtr> >::const_iterator PartitionIt;
94 virtual const std::vector<dom_int>&
subgroupBase()
const;
97 std::vector<dom_int> m_subgroupBase;
99 std::list<std::pair<PartitionPtr,RefinementPtr> > partitions;
102 unsigned int search(PartitionIt pIt,
Partition &pi,
const PERM& t,
const PERM* t2,
unsigned int level,
unsigned int backtrackLevel,
unsigned int& completed,
BSGS<PERM,TRANSRET> &groupK,
BSGS<PERM,TRANSRET> &groupL);
105 bool updateMappingPermutation(
const BSGSIN& bsgs,
const Partition& sigma,
const Partition& pi2, PERM& t2)
const;
108 template<
class BSGSIN,
class TRANSRET>
110 :
BaseSearch<BSGSIN,TRANSRET>(bsgs, pruningLevelDCM, stopAfterFirstElement),
114 template<
class BSGSIN,
class TRANSRET>
117 typedef typename boost::shared_ptr<RefinementFamily<PERM> > RefinementFamilyPtr;
118 std::list<RefinementFamilyPtr> refinements;
120 if (!this->
m_bsgs.isSymmetricGroup()) {
122 refinements.push_back(gr);
125 if (predRefinement) {
126 RefinementFamilyPtr predR( predRefinement );
127 refinements.push_back(predR);
130 PERMLIB_DEBUG(print_iterable(this->
m_bsgs.B.begin(), this->
m_bsgs.B.end(), 1,
"orig BSGS");)
133 while (pi.cells() < this->
m_bsgs.n) {
134 PERMLIB_DEBUG(std::cout << std::endl <<
"PI0 = " << pi << std::endl;)
138 unsigned int foo = 0;
139 BOOST_FOREACH(RefinementFamilyPtr ref, refinements) {
140 const unsigned int oldFixPointsSize = pi.fixPointsSize();
141 std::pair<PartitionPtr,RefinementPtr> newRef = ref->apply(pi);
143 partitions.push_back(newRef);
144 if (oldFixPointsSize < pi.fixPointsSize()) {
154 PERMLIB_DEBUG(std::cout << std::endl <<
"PI1 = " << pi << std::endl;)
156 if (pi.cells() < this->
m_bsgs.n) {
157 unsigned int alpha = -1;
160 if (pi.fixPointsSize() < this->
m_bsgs.B.size())
161 alpha = this->
m_bsgs.B[pi.fixPointsSize()];
162 if (alpha >= this->
m_bsgs.n) {
163 for (
unsigned int i = 0; i < this->
m_bsgs.n; ++i) {
164 if (std::find(pi.fixPointsBegin(), pi.fixPointsEnd(), i) == pi.fixPointsEnd()) {
170 BOOST_ASSERT( alpha < this->
m_bsgs.n );
171 PERMLIB_DEBUG(std::cout <<
"choose alpha = " << alpha << std::endl;)
176 PERMLIB_DEBUG(std::cout <<
"BACKTRACK " << (ref->
alpha()+1) <<
" in " << pi <<
" --> " << *newPi << std::endl;)
177 partitions.push_back(std::make_pair(newPi, br));
182 m_subgroupBase.push_back(ref->
alpha());
188 for (
typename std::list<std::pair<PartitionPtr,RefinementPtr> >::iterator pIt = partitions.begin(); pIt != partitions.end(); ++pIt) {
189 (*pIt).second->sort(*this->
m_sorter, 0);
190 PERMLIB_DEBUG(std::cout <<
"SIGMA = " << *(*pIt).first << std::endl;)
193 PERMLIB_DEBUG(print_iterable(this->
m_order.begin(), this->
m_order.end(), 0,
"ORDER");)
196 template<class BSGSIN,class TRANSRET>
202 PERMLIB_DEBUG(print_iterable(this->
m_bsgs.B.begin(), this->
m_bsgs.B.end(), 1,
"change base");)
206 template<
class BSGSIN,
class TRANSRET>
208 BOOST_ASSERT( this->
m_pred != 0 );
212 unsigned int completed = partitions.size();
214 PERM identH(this->
m_bsgs.n);
215 search(partitions.begin(), m_partition2, PERM(this->
m_bsgs.n), &identH, 0, 0, completed, groupK, groupL);
218 template<
class BSGSIN,
class TRANSRET>
220 BOOST_ASSERT( this->
m_pred != 0 );
228 unsigned int completed = partitions.size();
230 PERM identH(this->
m_bsgs.n);
231 search(partitions.begin(), m_partition2, PERM(this->
m_bsgs.n), &identH, 0, 0, completed, groupK, groupL);
238 template<
class BSGSIN,
class TRANSRET>
239 unsigned int RBase<BSGSIN,TRANSRET>::search(PartitionIt pIt,
Partition &pi,
const PERM& t,
const PERM* t2,
unsigned int level,
unsigned int backtrackLevel,
unsigned int& completed,
BSGS<PERM,TRANSRET> &groupK,
BSGS<PERM,TRANSRET> &groupL) {
242 if (pIt == partitions.end() || this->
checkLeaf(level)) {
243 PERMLIB_DEBUG(std::cout <<
"LEAF: " << pi <<
" with t = " << t << std::endl;)
244 return this->
processLeaf(t, level, backtrackLevel, completed, groupK, groupL);
247 const Partition& sigma = *((*pIt).first);
248 const RefinementPtr& ref = (*pIt).second;
251 unsigned int s = ref->alternatives();
252 const bool isBacktrack = ref->type() == Backtrack;
253 const bool isGroup = ref->type() == Group;
254 const PERM* tForRefinement = &t;
264 typedef typename Refinement<PERM>::RefinementPtrIterator RefIt;
265 for (RefIt rIt = ref->backtrackBegin(); rIt != ref->backtrackEnd(); ++rIt) {
266 if (isBacktrack && s < groupK.
U[backtrackLevel].size()) {
267 PERMLIB_DEBUG(std::cout <<
"PRUNE the rest: s=" << s <<
" < " << groupK.
U[backtrackLevel].size() << std::endl;)
273 RefinementPtr ref2 = *rIt;
276 PERMLIB_DEBUG(std::cout <<
" refinement from " << pi << std::endl;)
277 const unsigned int strictRefinement = ref2->apply2(pi, *tForRefinement);
278 PERMLIB_DEBUG(std::cout <<
" to " << pi <<
" with " << strictRefinement << std::endl;)
279 PERMLIB_DEBUG(
for(
unsigned int jj=0; jj<level; ++jj) std::cout <<
" ";)
280 PERMLIB_DEBUG(std::cout <<
"NODE " << sigma <<
" ~~~> " << pi << std::endl;)
287 if (!strictRefinement) {
288 PERMLIB_DEBUG(std::cout <<
"no strict refinement " << sigma <<
" -- " << pi << std::endl;)
293 PERMLIB_DEBUG(std::cout <<
"cell number mismatch " << sigma <<
" -- " << pi << std::endl;)
294 ref2->undo(pi, strictRefinement);
299 PERMLIB_DEBUG(std::cout <<
"fix point number mismatch " << sigma <<
" -- " << pi << std::endl;)
300 ref2->undo(pi, strictRefinement);
307 if (!updateMappingPermutation(this->
m_bsgs, sigma, pi, tG)) {
308 PERMLIB_DEBUG(std::cout <<
"no t found " << sigma <<
" -- " << pi <<
"; tG = " << tG << std::endl;)
309 ref2->undo(pi, strictRefinement);
315 if (!updateMappingPermutation(*this->
m_bsgs2, sigma, pi, *tH)) {
316 PERMLIB_DEBUG(std::cout <<
"no t found " << sigma <<
" -- " << pi <<
"; tH = " << tH << std::endl;)
317 ref2->undo(pi, strictRefinement);
324 if (this->
pruneDCM(tG, backtrackLevel, groupK, groupL)) {
326 ref2->undo(pi, strictRefinement);
330 unsigned int ret =
search(pIt, pi, tG, tH ? tH : t2, level+1, isBacktrack ? (backtrackLevel + 1) : backtrackLevel, completed, groupK, groupL);
332 PERMLIB_DEBUG(std::cout <<
"retract " << strictRefinement <<
" from " << pi <<
" to ";)
333 ref2->undo(pi, strictRefinement);
334 PERMLIB_DEBUG(std::cout << pi << std::endl;)
341 completed = std::min(completed, level);
345 template<
class BSGSIN,
class TRANSRET>
347 typedef std::vector<unsigned int>::const_iterator FixIt;
348 std::vector<dom_int>::const_iterator bIt;
353 PERMLIB_DEBUG(print_iterable(bsgs.B.begin(), bsgs.B.end(), 1,
"B ");)
354 PERMLIB_DEBUG(print_iterable(fixSigmaIt, fixSigmaEndIt, 1,
"Sigma");)
355 for (bIt = bsgs.B.begin(); bIt != bsgs.B.end(); ++bIt, ++i) {
356 PERMLIB_DEBUG(std::cout <<
" base: " << (*bIt)+1 << std::endl;)
357 while (fixSigmaIt != fixSigmaEndIt && *fixSigmaIt != *bIt) {
358 PERMLIB_DEBUG(std::cout <<
" skipping " << (*fixSigmaIt)+1 <<
" for " << (*bIt)+1 << std::endl;)
362 if (fixSigmaIt == fixSigmaEndIt) {
363 PERMLIB_DEBUG(std::cout <<
" no more fix point found for " << (*bIt)+1 << std::endl;)
366 const unsigned int alpha = *fixSigmaIt;
367 const unsigned int beta = *fixPiIt;
368 if (t2 / alpha != beta) {
369 boost::scoped_ptr<PERM> u_beta(bsgs.U[i].at(t2 % beta));
385 template<
class BSGSIN,
class TRANSRET>
387 return m_subgroupBase;
393 #endif // -- RBASE_H_ bool initializeAndApply(Partition &pi)
applies (left-)refinement to partition and initializes refinement for future use in R-base ...
Definition: refinement.h:136
void setupEmptySubgroup(BSGS< PERM, TRANSRET > &group) const
sets up a BSGS structure for an empty group with base subgroupBase()
Definition: base_search.h:263
boost::scoped_ptr< SubgroupPredicate< PERM > > m_pred
predicate that matches sought elements
Definition: base_search.h:95
virtual PERM::ptr searchCosetRepresentative()
searches for a coset representative if one exists
Definition: base_search.h:271
BSGSIN * m_bsgs2
second BSGS of a group the sough elements have to member of
Definition: base_search.h:93
unsigned long cells() const
number of cells in this partition
Definition: partition.h:157
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
virtual const std::vector< dom_int > & subgroupBase() const
base of the sought subgroup
Definition: r_base.h:386
BSGSIN m_bsgs
main BSGS to search in
Definition: base_search.h:91
base class for searching in a group
Definition: base_search.h:45
virtual void sort(const BaseSorterByReference &, const Partition *)
sorts siblings in the search tree
Definition: refinement.h:100
partition
Definition: partition.h:48
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g. a base)
Definition: base_sorter.h:113
-refinements for group membership
Definition: refinement_family.h:67
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
vector_t::const_iterator fixPointsEnd() const
iterator to the end of fix points
Definition: partition.h:167
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
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
const BSGSCore< PERM, TRANS > & bsgs() const
bsgs which membership for is required
Definition: group_refinement.h:251
RBase(const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement=false)
constructor
Definition: r_base.h:109
R-base for partition backtracking.
Definition: r_base.h:56
boost::scoped_ptr< BaseSorterByReference > m_sorter
a sorter with respect to m_order
Definition: base_search.h:100
unsigned long m_statNodesPrunedCosetMinimality
number of nodes where (simple) double coset minimality pruning was in effect
Definition: base_search.h:83
void construct(SubgroupPredicate< PERM > *pred, RefinementFamily< PERM > *predRefinement)
constructs an R-base for given predicate and refinement family
Definition: r_base.h:115
Partition m_partition
partition to base the backtrack tree on
Definition: r_base.h:80
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
backtrack refinement
Definition: backtrack_refinement.h:45
vector_t::const_iterator fixPointsBegin() const
iterator to the begin of fix points
Definition: partition.h:164
virtual unsigned int processNewFixPoints(const Partition &pi, unsigned int level)
callback when a new fix point appears during R-base construction
Definition: r_base.h:197
concrete -refinements for group membership
Definition: group_refinement.h:44
void search(BSGS< PERM, TRANSRET > &groupK)
perform search and store result in groupK
Definition: r_base.h:207
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
represents a class of -refinements for a given problem
Definition: refinement_family.h:49
std::vector< unsigned long > m_order
base point order
Definition: base_search.h:98
unsigned int fixPointsSize() const
number of fix points in this partition
Definition: partition.h:161
unsigned long alpha() const
alpha point chosen for backtracking
Definition: backtrack_refinement.h:110
unsigned long m_statNodesPrunedCosetMinimality2
number of nodes where advanced double coset minimality pruning with base change was in effect ...
Definition: base_search.h:85
Definition: abstract_bsgs.h:49