permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
base_search.h
1// ---------------------------------------------------------------------------
2//
3// This file is part of PermLib.
4//
5// Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6// All rights reserved.
7//
8// Redistribution and use in source and binary forms, with or without
9// modification, are permitted provided that the following conditions
10// are met:
11// 1. Redistributions of source code must retain the above copyright
12// notice, this list of conditions and the following disclaimer.
13// 2. Redistributions in binary form must reproduce the above copyright
14// notice, this list of conditions and the following disclaimer in the
15// documentation and/or other materials provided with the distribution.
16// 3. The name of the author may not be used to endorse or promote products
17// derived from this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29//
30// ---------------------------------------------------------------------------
31
32
33#ifndef BASE_SEARCH_H_
34#define BASE_SEARCH_H_
35
36#include <permlib/change/conjugating_base_change.h>
37#include <permlib/change/random_base_transpose.h>
38
39#include <boost/dynamic_bitset.hpp>
40
41namespace permlib {
42
44template<class BSGSIN, class TRANSRET>
46public:
47 typedef typename BSGSIN::PERMtype PERM;
48 typedef typename BSGSIN::TRANStype TRANS;
49 typedef std::list<typename PERM::ptr> PERMlistType;
50
52
57 BaseSearch(const BSGSIN& bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement);
58
60 virtual ~BaseSearch(){}
61
63
66 bool minOrbit(unsigned long alpha, BSGS<PERM,TRANSRET> &groupK, unsigned int i, unsigned long beta_i) const;
67
69 virtual typename PERM::ptr searchCosetRepresentative();
70
72
78 virtual typename PERM::ptr searchCosetRepresentative(BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL) = 0;
79
81 unsigned long m_statNodesVisited;
88
89protected:
91 BSGSIN m_bsgs;
93 BSGSIN* m_bsgs2;
95 boost::scoped_ptr<SubgroupPredicate<PERM> > m_pred;
96
98 std::vector<unsigned long> m_order;
100 boost::scoped_ptr<BaseSorterByReference> m_sorter;
101
104
106 const unsigned int m_pruningLevelDCM;
110 unsigned int m_limitBase;
112 unsigned int m_limitLevel;
113
115 bool pruneDCM(const PERM& t, unsigned int backtrackLevel, BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL);
117 bool checkLeaf(unsigned int level);
119 unsigned int processLeaf(const PERM& t, unsigned int level, unsigned int backtrackLevel, unsigned int completed, BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL);
121 virtual const std::vector<dom_int>& subgroupBase() const = 0;
122
124 void setupEmptySubgroup(BSGS<PERM,TRANSRET>& group) const;
125
129 typename PERM::ptr m_lastElement;
130private:
131 static PERMlistType ms_emptyList;
132};
133
134//
135// IMPLEMENTATION
136//
137
138template<class BSGSIN,class TRANSRET>
139typename BaseSearch<BSGSIN,TRANSRET>::PERMlistType BaseSearch<BSGSIN,TRANSRET>::ms_emptyList;
140
141
142template<class BSGSIN,class TRANSRET>
143BaseSearch<BSGSIN,TRANSRET>::BaseSearch(const BSGSIN& bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement)
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),
150 m_lastElement()
151{
152}
153
154
155template<class BSGSIN,class TRANSRET>
156bool BaseSearch<BSGSIN,TRANSRET>::minOrbit(unsigned long alpha, BSGS<PERM,TRANSRET> &groupK, unsigned int i, unsigned long beta_i) const {
157 PERMlistType S_i;
158 std::copy_if(groupK.S.begin(), groupK.S.end(), std::back_inserter(S_i), PointwiseStabilizerPredicate<PERM>(groupK.B.begin(), groupK.B.begin() + i));
159 if (S_i.empty()) {
160 if (alpha == beta_i)
161 return true;
162 return (*m_sorter)(beta_i, alpha);
163 }
164
165 //TODO: avoid multiple allocation?
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;)
179 return false;
180 }
181 }
182 }
183 }
184 return true;
185}
186
187template<class BSGSIN,class TRANSRET>
188bool BaseSearch<BSGSIN,TRANSRET>::pruneDCM(const PERM& t, unsigned int backtrackLevel, BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL) {
189 // change base only for the lower nodes in the tree
190 if (backtrackLevel < m_pruningLevelDCM) {
191 //TODO: avoid multiple allocation?
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];
195 //print_iterable(newBaseImage.begin(), newBaseImage.begin() + (backtrackLevel+1), 1, "new base image");
197 cbc.change(groupL, newBaseImage.begin(), newBaseImage.begin() + (backtrackLevel+1), false);
198 //print_iterable(groupL.B.begin(), groupL.B.end(), 1, "new base");
199 }
200
201 const unsigned long alpha = groupK.B[backtrackLevel];
202
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;)
207
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;)
212 return true;
213 }
214 }
215 if (t / groupK.B[i] != groupL.B[i])
216 return false;
217 }
218 return false;
219}
220
221template<class BSGSIN,class TRANSRET>
223 return m_limitInitialized && level >= m_limitLevel;
224}
225
226template<class BSGSIN,class TRANSRET>
227unsigned int BaseSearch<BSGSIN,TRANSRET>::processLeaf(const PERM& t, unsigned int level, unsigned int backtrackLevel, unsigned int completed, BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL) {
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;
231
232 if ( ! (*m_pred)(t) )
233 return level;
234
235 if (m_stopAfterFirstElement) {
236 m_lastElement = typename PERM::ptr(new PERM(t));
237 return 0;
238 }
239 const bool isIdentity = t.isIdentity();
240 if (m_limitInitialized && level == m_limitLevel && isIdentity) {
241 PointwiseStabilizerPredicate<PERM> stabPred(m_bsgs.B.begin(), m_bsgs.B.begin() + m_limitBase);
242 BOOST_FOREACH(const PERMptr &s, m_bsgs.S) {
243 if (stabPred(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));
248 groupK.insertGenerator(sK, true);
249 groupL.insertGenerator(sL, true);
250 }
251 }
252 } else if (!isIdentity) {
253 PERMptr genK(new PERM(t));
254 PERMptr genL(new PERM(t));
255 groupK.insertGenerator(genK, true);
256 groupL.insertGenerator(genL, true);
257 PERMLIB_DEBUG(std::cout << "-- accepted" << std::endl;)
258 }
259 return completed;
260}
261
262template<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);
268}
269
270template<class BSGSIN,class TRANSRET>
272 BSGS<PERM,TRANSRET> groupK(this->m_bsgs.n);
273 BSGS<PERM,TRANSRET> groupL(this->m_bsgs.n);
274
275 setupEmptySubgroup(groupK);
276 setupEmptySubgroup(groupL);
277
278 return this->searchCosetRepresentative(groupK, groupL);
279}
280
281}
282
283#endif // -- BASE_SEARCH_H_
base class for searching in a group
Definition: base_search.h:45
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
unsigned int m_limitLevel
maximal backtrack level
Definition: base_search.h:112
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
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
a sorter with respect to m_order
Definition: base_search.h:100
bool m_limitInitialized
true iff other m_limit variables have been initialized
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
true iff the search can be stopped after the first element found with the desired property
Definition: base_search.h:127
ConjugatingBaseChange< PERM, TRANS, RandomBaseTranspose< PERM, TRANS > > m_baseChange
base change algorithm
Definition: base_search.h:103
unsigned long m_statNodesPrunedChildRestriction
number of nodes where a child constraint pruning was in effect
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
second BSGS of a group the sough elements have to member of
Definition: base_search.h:93
unsigned int m_limitBase
number of base points that correspond to maximal backtrack level m_limitLevel
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
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
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