permlib
0.2.6
Library for permutation computations
|
00001 // --------------------------------------------------------------------------- 00002 // 00003 // This file is part of PermLib. 00004 // 00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de> 00006 // All rights reserved. 00007 // 00008 // Redistribution and use in source and binary forms, with or without 00009 // modification, are permitted provided that the following conditions 00010 // are met: 00011 // 1. Redistributions of source code must retain the above copyright 00012 // notice, this list of conditions and the following disclaimer. 00013 // 2. Redistributions in binary form must reproduce the above copyright 00014 // notice, this list of conditions and the following disclaimer in the 00015 // documentation and/or other materials provided with the distribution. 00016 // 3. The name of the author may not be used to endorse or promote products 00017 // derived from this software without specific prior written permission. 00018 // 00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 // 00030 // --------------------------------------------------------------------------- 00031 00032 00033 #ifndef BACKTRACKSEARCH_H_ 00034 #define BACKTRACKSEARCH_H_ 00035 00036 #include <permlib/bsgs.h> 00037 #include <permlib/predicate/subgroup_predicate.h> 00038 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 00039 #include <permlib/predicate/group_intersection_predicate.h> 00040 00041 #include <permlib/search/base_search.h> 00042 00043 #include <boost/scoped_ptr.hpp> 00044 00045 namespace permlib { 00046 namespace classic { 00047 00049 template <class BSGSIN, class TRANSRET> 00050 class BacktrackSearch : public BaseSearch<BSGSIN,TRANSRET> { 00051 public: 00052 typedef typename BaseSearch<BSGSIN,TRANSRET>::PERM PERM; 00053 typedef typename BaseSearch<BSGSIN,TRANSRET>::TRANS TRANS; 00054 00056 00062 BacktrackSearch(const BSGSIN& bsgs, unsigned int pruningLevelDCM, bool breakAfterChildRestriction = false, bool stopAfterFirstElement = false); 00063 00065 void search(BSGS<PERM,TRANSRET> &groupK); 00066 00067 using BaseSearch<BSGSIN,TRANSRET>::searchCosetRepresentative; 00068 virtual typename BaseSearch<BSGSIN,TRANSRET>::PERM::ptr searchCosetRepresentative(BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL); 00069 protected: 00070 virtual const std::vector<dom_int>& subgroupBase() const; 00071 00073 void construct(SubgroupPredicate<PERM>* pred, bool addPredRefinement); 00075 unsigned int search(const PERM& t, unsigned int level, unsigned int& completed, BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL); 00076 private: 00078 00081 const bool m_breakAfterChildRestriction; 00082 }; 00083 00084 // 00085 // IMPLEMENTATION 00086 // 00087 00088 00089 template <class BSGSIN, class TRANSRET> 00090 BacktrackSearch<BSGSIN,TRANSRET>::BacktrackSearch(const BSGSIN& bsgs, unsigned int pruningLevelDCM, bool breakAfterChildRestriction, bool stopAfterFirstElement) 00091 : BaseSearch<BSGSIN,TRANSRET>(bsgs, pruningLevelDCM, stopAfterFirstElement), 00092 m_breakAfterChildRestriction(breakAfterChildRestriction) 00093 { } 00094 00095 template <class BSGSIN, class TRANSRET> 00096 void BacktrackSearch<BSGSIN,TRANSRET>::search(BSGS<PERM,TRANSRET> &groupK) { 00097 BOOST_ASSERT(this->m_pred != 0); 00098 00099 this->setupEmptySubgroup(groupK); 00100 00101 this->m_order = BaseSorterByReference::createOrder(this->m_bsgs.n, this->m_bsgs.B.begin(), this->m_bsgs.B.end()); 00102 this->m_sorter.reset(new BaseSorterByReference(this->m_order)); 00103 00104 unsigned int completed = this->m_bsgs.n; 00105 BSGS<PERM,TRANSRET> groupL(groupK); 00106 search(PERM(this->m_bsgs.n), 0, completed, groupK, groupL); 00107 00108 groupK.stripRedundantBasePoints(); 00109 } 00110 00111 template <class BSGSIN, class TRANSRET> 00112 typename BaseSearch<BSGSIN,TRANSRET>::PERM::ptr BacktrackSearch<BSGSIN,TRANSRET>::searchCosetRepresentative(BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL) { 00113 BOOST_ASSERT(this->m_pred != 0); 00114 00115 this->setupEmptySubgroup(groupK); 00116 this->setupEmptySubgroup(groupL); 00117 00118 this->m_order = BaseSorterByReference::createOrder(this->m_bsgs.n, this->m_bsgs.B.begin(), this->m_bsgs.B.end()); 00119 this->m_sorter.reset(new BaseSorterByReference(this->m_order)); 00120 00121 unsigned int completed = this->m_bsgs.n; 00122 search(PERM(this->m_bsgs.n), 0, completed, groupK, groupL); 00123 00124 return BaseSearch<BSGSIN,TRANSRET>::m_lastElement; 00125 } 00126 00127 template <class BSGSIN, class TRANSRET> 00128 unsigned int BacktrackSearch<BSGSIN,TRANSRET>::search(const PERM& g, unsigned int level, unsigned int& completed, BSGS<PERM,TRANSRET> &groupK, BSGS<PERM,TRANSRET> &groupL) { 00129 const std::vector<dom_int> &B = this->m_bsgs.B; 00130 std::vector<TRANS > &U = this->m_bsgs.U; 00131 00132 PERMLIB_DEBUG(std::cout << "starting with " << g << " @ " << level << std::endl;) 00133 ++this->m_statNodesVisited; 00134 00135 if (level == B.size() || this->checkLeaf(level)) { 00136 PERMLIB_DEBUG(std::cout << "limit reached for " << g << " // " << (*this->m_pred)(g) << std::endl;) 00137 return this->processLeaf(g, level, level, completed, groupK, groupL); 00138 } 00139 00140 00141 std::vector<unsigned long> orbit(U[level].begin(), U[level].end()); 00142 BOOST_FOREACH(unsigned long &alpha, orbit) { 00143 alpha = g / alpha; 00144 } 00145 std::sort(orbit.begin(), orbit.end(), *this->m_sorter); 00146 unsigned int s = orbit.size(); 00147 00148 std::vector<unsigned long>::const_iterator orbIt; 00149 for (orbIt = orbit.begin(); orbIt != orbit.end(); ++orbIt) { 00150 if (s < groupK.U[level].size()) { 00151 PERMLIB_DEBUG(std::cout << "PRUNE the rest: s=" << s << " < " << groupK.U[level].size() << std::endl;) 00152 this->m_statNodesPrunedCosetMinimality += s; 00153 // skip the rest due to double coset minimality 00154 break; 00155 } 00156 00157 --s; 00158 unsigned long beta = g % *orbIt; 00159 PERMLIB_DEBUG(std::cout << " BETA = " << beta << " <-- " << B[level] << std::endl;) 00160 boost::scoped_ptr<PERM> u_beta_ptr(U[level].at(beta)); 00161 *u_beta_ptr *= g; 00162 00163 if (!this->m_pred->childRestriction(*u_beta_ptr, level, B[level])) { 00164 ++this->m_statNodesPrunedChildRestriction; 00165 if (m_breakAfterChildRestriction) 00166 break; 00167 continue; 00168 } 00169 if (this->m_pruningLevelDCM && this->pruneDCM(*u_beta_ptr, level, groupK, groupL)) { 00170 ++this->m_statNodesPrunedCosetMinimality2; 00171 continue; 00172 } 00173 00174 unsigned int ret = search(*u_beta_ptr, level+1, completed, groupK, groupL); 00175 if (BaseSearch<BSGSIN,TRANSRET>::m_stopAfterFirstElement && ret == 0) 00176 return 0; 00177 if (ret < level) { 00178 PERMLIB_DEBUG(std::cout << "^^ MULTI BACKTRACK! leave " << level << " to " << ret << std::endl;) 00179 return ret; 00180 } 00181 } 00182 completed = std::min(completed, level); 00183 00184 return level; 00185 } 00186 00187 template<class BSGSIN,class TRANSRET> 00188 void BacktrackSearch<BSGSIN,TRANSRET>::construct(SubgroupPredicate<PERM>* pred, bool addPredRefinement) { 00189 this->m_pred.reset(pred); 00190 } 00191 00192 template<class BSGSIN,class TRANSRET> 00193 const std::vector<dom_int>& BacktrackSearch<BSGSIN,TRANSRET>::subgroupBase() const { 00194 return this->m_bsgs.B; 00195 } 00196 00197 } 00198 } 00199 00200 #endif // -- BACKTRACKSEARCH_H_