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
45namespace permlib {
46namespace classic {
47
49template <class BSGSIN, class TRANSRET>
50class BacktrackSearch : public BaseSearch<BSGSIN,TRANSRET> {
51public:
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
67 using BaseSearch<BSGSIN,TRANSRET>::searchCosetRepresentative;
69protected:
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);
76private:
78
81 const bool m_breakAfterChildRestriction;
82};
83
84//
85// IMPLEMENTATION
86//
87
88
89template <class BSGSIN, class TRANSRET>
90BacktrackSearch<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
95template <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
109}
110
111template <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
127template <class BSGSIN, class TRANSRET>
128unsigned 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
187template<class BSGSIN,class TRANSRET>
189 this->m_pred.reset(pred);
190}
191
192template<class BSGSIN,class TRANSRET>
193const std::vector<dom_int>& BacktrackSearch<BSGSIN,TRANSRET>::subgroupBase() const {
194 return this->m_bsgs.B;
195}
196
197}
198}
199
200#endif // -- BACKTRACKSEARCH_H_
base class for searching in a group
Definition: base_search.h:45
virtual PERM::ptr searchCosetRepresentative()
searches for a coset representative if one exists
Definition: base_search.h:271
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g....
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
abstract base class for subgroup (and coset) predicates
Definition: subgroup_predicate.h:45
searching in a group with classical backtracking
Definition: backtrack_search.h:50
virtual const std::vector< dom_int > & subgroupBase() const
base of the sought subgroup
Definition: backtrack_search.h:193
void search(BSGS< PERM, TRANSRET > &groupK)
searches for a subgroup and stores it into groupK
Definition: backtrack_search.h:96
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
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:89
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition: bsgs.h:437