permlib  0.2.9
Library for permutation computations
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 
41 namespace permlib {
42 
44 template<class BSGSIN, class TRANSRET>
45 class BaseSearch {
46 public:
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 
89 protected:
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;
130 private:
131  static PERMlistType ms_emptyList;
132 };
133 
134 //
135 // IMPLEMENTATION
136 //
137 
138 template<class BSGSIN,class TRANSRET>
139 typename BaseSearch<BSGSIN,TRANSRET>::PERMlistType BaseSearch<BSGSIN,TRANSRET>::ms_emptyList;
140 
141 
142 template<class BSGSIN,class TRANSRET>
143 BaseSearch<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 
155 template<class BSGSIN,class TRANSRET>
156 bool 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 
187 template<class BSGSIN,class TRANSRET>
188 bool 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 
221 template<class BSGSIN,class TRANSRET>
222 bool BaseSearch<BSGSIN,TRANSRET>::checkLeaf(unsigned int level) {
223  return m_limitInitialized && level >= m_limitLevel;
224 }
225 
226 template<class BSGSIN,class TRANSRET>
227 unsigned 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 
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);
268 }
269 
270 template<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_
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