permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/search/classic/backtrack_search.h
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_