permlib  0.2.9
Library for permutation computations
backtrack_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 BACKTRACKSEARCH_H_
34 #define BACKTRACKSEARCH_H_
35 
36 #include <permlib/bsgs.h>
37 #include <permlib/predicate/subgroup_predicate.h>
38 #include <permlib/predicate/pointwise_stabilizer_predicate.h>
39 #include <permlib/predicate/group_intersection_predicate.h>
40 
41 #include <permlib/search/base_search.h>
42 
43 #include <boost/scoped_ptr.hpp>
44 
45 namespace permlib {
46 namespace classic {
47 
49 template <class BSGSIN, class TRANSRET>
50 class BacktrackSearch : public BaseSearch<BSGSIN,TRANSRET> {
51 public:
52  typedef typename BaseSearch<BSGSIN,TRANSRET>::PERM PERM;
53  typedef typename BaseSearch<BSGSIN,TRANSRET>::TRANS TRANS;
54 
56 
62  BacktrackSearch(const BSGSIN& bsgs, unsigned int pruningLevelDCM, bool breakAfterChildRestriction = false, bool stopAfterFirstElement = false);
63 
65  void search(BSGS<PERM,TRANSRET> &groupK);
66 
69 protected:
70  virtual const std::vector<dom_int>& subgroupBase() const;
71 
73  void construct(SubgroupPredicate<PERM>* pred, bool addPredRefinement);
75  unsigned int search(const PERM& t, unsigned int level, unsigned int& completed, BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL);
76 private:
78 
81  const bool m_breakAfterChildRestriction;
82 };
83 
84 //
85 // IMPLEMENTATION
86 //
87 
88 
89 template <class BSGSIN, class TRANSRET>
90 BacktrackSearch<BSGSIN,TRANSRET>::BacktrackSearch(const BSGSIN& bsgs, unsigned int pruningLevelDCM, bool breakAfterChildRestriction, bool stopAfterFirstElement)
91  : BaseSearch<BSGSIN,TRANSRET>(bsgs, pruningLevelDCM, stopAfterFirstElement),
92  m_breakAfterChildRestriction(breakAfterChildRestriction)
93 { }
94 
95 template <class BSGSIN, class TRANSRET>
97  BOOST_ASSERT(this->m_pred != 0);
98 
99  this->setupEmptySubgroup(groupK);
100 
101  this->m_order = BaseSorterByReference::createOrder(this->m_bsgs.n, this->m_bsgs.B.begin(), this->m_bsgs.B.end());
102  this->m_sorter.reset(new BaseSorterByReference(this->m_order));
103 
104  unsigned int completed = this->m_bsgs.n;
105  BSGS<PERM,TRANSRET> groupL(groupK);
106  search(PERM(this->m_bsgs.n), 0, completed, groupK, groupL);
107 
108  groupK.stripRedundantBasePoints();
109 }
110 
111 template <class BSGSIN, class TRANSRET>
113  BOOST_ASSERT(this->m_pred != 0);
114 
115  this->setupEmptySubgroup(groupK);
116  this->setupEmptySubgroup(groupL);
117 
118  this->m_order = BaseSorterByReference::createOrder(this->m_bsgs.n, this->m_bsgs.B.begin(), this->m_bsgs.B.end());
119  this->m_sorter.reset(new BaseSorterByReference(this->m_order));
120 
121  unsigned int completed = this->m_bsgs.n;
122  search(PERM(this->m_bsgs.n), 0, completed, groupK, groupL);
123 
125 }
126 
127 template <class BSGSIN, class TRANSRET>
128 unsigned int BacktrackSearch<BSGSIN,TRANSRET>::search(const PERM& g, unsigned int level, unsigned int& completed, BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL) {
129  const std::vector<dom_int> &B = this->m_bsgs.B;
130  std::vector<TRANS > &U = this->m_bsgs.U;
131 
132  PERMLIB_DEBUG(std::cout << "starting with " << g << " @ " << level << std::endl;)
133  ++this->m_statNodesVisited;
134 
135  if (level == B.size() || this->checkLeaf(level)) {
136  PERMLIB_DEBUG(std::cout << "limit reached for " << g << " // " << (*this->m_pred)(g) << std::endl;)
137  return this->processLeaf(g, level, level, completed, groupK, groupL);
138  }
139 
140 
141  std::vector<unsigned long> orbit(U[level].begin(), U[level].end());
142  BOOST_FOREACH(unsigned long &alpha, orbit) {
143  alpha = g / alpha;
144  }
145  std::sort(orbit.begin(), orbit.end(), *this->m_sorter);
146  unsigned int s = orbit.size();
147 
148  std::vector<unsigned long>::const_iterator orbIt;
149  for (orbIt = orbit.begin(); orbIt != orbit.end(); ++orbIt) {
150  if (s < groupK.U[level].size()) {
151  PERMLIB_DEBUG(std::cout << "PRUNE the rest: s=" << s << " < " << groupK.U[level].size() << std::endl;)
152  this->m_statNodesPrunedCosetMinimality += s;
153  // skip the rest due to double coset minimality
154  break;
155  }
156 
157  --s;
158  unsigned long beta = g % *orbIt;
159  PERMLIB_DEBUG(std::cout << " BETA = " << beta << " <-- " << B[level] << std::endl;)
160  boost::scoped_ptr<PERM> u_beta_ptr(U[level].at(beta));
161  *u_beta_ptr *= g;
162 
163  if (!this->m_pred->childRestriction(*u_beta_ptr, level, B[level])) {
164  ++this->m_statNodesPrunedChildRestriction;
165  if (m_breakAfterChildRestriction)
166  break;
167  continue;
168  }
169  if (this->m_pruningLevelDCM && this->pruneDCM(*u_beta_ptr, level, groupK, groupL)) {
170  ++this->m_statNodesPrunedCosetMinimality2;
171  continue;
172  }
173 
174  unsigned int ret = search(*u_beta_ptr, level+1, completed, groupK, groupL);
176  return 0;
177  if (ret < level) {
178  PERMLIB_DEBUG(std::cout << "^^ MULTI BACKTRACK! leave " << level << " to " << ret << std::endl;)
179  return ret;
180  }
181  }
182  completed = std::min(completed, level);
183 
184  return level;
185 }
186 
187 template<class BSGSIN,class TRANSRET>
189  this->m_pred.reset(pred);
190 }
191 
192 template<class BSGSIN,class TRANSRET>
193 const std::vector<dom_int>& BacktrackSearch<BSGSIN,TRANSRET>::subgroupBase() const {
194  return this->m_bsgs.B;
195 }
196 
197 }
198 }
199 
200 #endif // -- BACKTRACKSEARCH_H_
virtual PERM::ptr searchCosetRepresentative()
searches for a coset representative if one exists
Definition: base_search.h:271
searching in a group with classical backtracking
Definition: backtrack_search.h:50
base class for searching in a group
Definition: base_search.h:45
void search(BSGS< PERM, TRANSRET > &groupK)
searches for a subgroup and stores it into groupK
Definition: backtrack_search.h:96
virtual const std::vector< dom_int > & subgroupBase() const
base of the sought subgroup
Definition: backtrack_search.h:193
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g. a base)
Definition: base_sorter.h:113
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
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition: bsgs.h:436
BacktrackSearch(const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool breakAfterChildRestriction=false, bool stopAfterFirstElement=false)
constructor
Definition: backtrack_search.h:90
void construct(SubgroupPredicate< PERM > *pred, bool addPredRefinement)
initializes the search
Definition: backtrack_search.h:188
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
Definition: abstract_bsgs.h:49