permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/transversal/shallow_schreier_tree_transversal.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 SHALLOWSCHREIERTREETRANSVERSAL_H_
00034 #define SHALLOWSCHREIERTREETRANSVERSAL_H_
00035 
00036 #include <permlib/transversal/schreier_tree_transversal.h>
00037 
00038 #include <boost/scoped_ptr.hpp>
00039 #include <boost/dynamic_bitset.hpp>
00040 
00041 namespace permlib {
00042 
00044 template <class PERM>
00045 class ShallowSchreierTreeTransversal : public SchreierTreeTransversal<PERM> {
00046 public:
00048     ShallowSchreierTreeTransversal(unsigned int n);
00049 
00050     virtual void orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators);
00051         virtual void orbitUpdate(unsigned long alpha, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g);
00052         
00053         virtual void updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange);
00055 
00059         ShallowSchreierTreeTransversal<PERM> clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const;
00060         
00061         virtual void permute(const PERM& g, const PERM& gInv);
00062 protected:
00064         std::list<typename PERM::ptr> m_cubeLabels;
00065 
00067         void addNewCubeLabel(unsigned long beta, const PERM &s, const unsigned long &beta_prime);
00068 };
00069 
00070 //
00071 //     ----       IMPLEMENTATION
00072 //
00073 
00074 template <class PERM>
00075 ShallowSchreierTreeTransversal<PERM>::ShallowSchreierTreeTransversal(unsigned int n_)
00076         : SchreierTreeTransversal<PERM>(n_)
00077 { }
00078 
00079 template <class PERM>
00080 void ShallowSchreierTreeTransversal<PERM>::orbitUpdate(unsigned long beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g) {
00081         this->orbit(beta, generators);
00082 }
00083 
00084 template <class PERM>
00085 void ShallowSchreierTreeTransversal<PERM>::orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators) {
00086         std::vector<boost::shared_ptr<PERM> > &transversal = Transversal<PERM>::m_transversal;
00087     
00088         if (Transversal<PERM>::size() == 0) {
00089                 Transversal<PERM>::m_orbit.push_back(beta);
00090                 boost::shared_ptr<PERM> identity(new PERM(this->m_n));
00091                         transversal[beta] = identity;
00092         }
00093         
00094         typename std::list<unsigned long>::const_iterator it;
00095 
00096         PERM g(this->m_n);
00097         typename std::list<typename PERM::ptr>::const_iterator genIt = generators.begin();
00098         for (it = Transversal<PERM>::m_orbit.begin(); it != Transversal<PERM>::m_orbit.end(); ++it) {
00099                 for (genIt = generators.begin(); genIt != generators.end(); ++genIt) {
00100                         const unsigned long &beta_prime = *it;
00101                         if (!transversal[**genIt / beta_prime]) {
00102                                 addNewCubeLabel(beta, **genIt, beta_prime);
00103                         }
00104                 }
00105         }
00106 }
00107 
00108 template <class PERM>
00109 void ShallowSchreierTreeTransversal<PERM>::addNewCubeLabel(unsigned long beta, const PERM &s, const unsigned long &beta_prime) {
00110         std::vector<boost::shared_ptr<PERM> > &transversal = Transversal<PERM>::m_transversal;
00111         boost::shared_ptr<PERM> gPath(SchreierTreeTransversal<PERM>::at(beta_prime));
00112         *gPath *= s;
00113         // will be new generator, so better flush it
00114         gPath->flush();
00115         
00116         // compute orbit * gPath
00117         //
00118         std::list<unsigned long> tempOrbit;
00119         typename std::list<unsigned long>::const_iterator orbIt = Transversal<PERM>::m_orbit.begin();
00120         for (; orbIt != Transversal<PERM>::m_orbit.end(); ++orbIt) {
00121                 const unsigned long alpha = *gPath / *orbIt;
00122                 //PERMLIB_DEBUG
00123                 //std::cout << "g_i " << alpha << std::endl;
00124                 if (!transversal[alpha]) {
00125                         transversal[alpha] = gPath;
00126                         tempOrbit.push_back(alpha);
00127                 }
00128         }
00129         Transversal<PERM>::m_orbit.splice(Transversal<PERM>::m_orbit.end(), tempOrbit);
00130 
00131         m_cubeLabels.push_back(gPath);
00132         
00133         boost::shared_ptr<PERM> gPathInv(new PERM(*gPath));
00134         gPathInv->invertInplace();
00135         
00136         // compute inv(gPath) * ... other generators
00137         //
00138 
00139         unsigned long beta1 = *gPathInv / beta;
00140         if (!transversal[beta1]) {
00141                 transversal[beta1] = gPathInv;
00142                 Transversal<PERM>::m_orbit.push_back(beta1);
00143         }
00144         
00145         boost::dynamic_bitset<> omega(this->m_n);
00146         boost::dynamic_bitset<> todo(this->m_n);
00147         unsigned long i;
00148         omega[beta1] = 1;
00149         BOOST_FOREACH(const typename PERM::ptr& l, m_cubeLabels) {
00150                 for (i = 0; i < this->m_n; ++i) {
00151                         if (!omega[i])
00152                                 continue;
00153                         unsigned long alpha = *l / i;
00154                         todo[alpha] = 1;
00155                         if (!transversal[alpha]) {
00156                                 transversal[alpha] = l;
00157                                 Transversal<PERM>::m_orbit.push_back(alpha);
00158                         }
00159                 }
00160                 omega |= todo;
00161         }
00162         
00163         m_cubeLabels.push_front(gPathInv);
00164 }
00165 
00166 template <class PERM>
00167 void ShallowSchreierTreeTransversal<PERM>::updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange) {
00168 }
00169 
00170 template <class PERM>
00171 ShallowSchreierTreeTransversal<PERM> ShallowSchreierTreeTransversal<PERM>::clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const {
00172         ShallowSchreierTreeTransversal<PERM> ret(*this);
00173         std::map<PERM*,typename PERM::ptr> labelMap;
00174         BOOST_FOREACH(typename PERM::ptr& p, ret.m_cubeLabels) {
00175                 PERM* gen = p.get();
00176                 p = typename PERM::ptr(new PERM(*p));
00177                 labelMap.insert(std::make_pair(gen, p));
00178         }
00179         ret.SchreierTreeTransversal<PERM>::updateGenerators(labelMap);
00180         return ret;
00181 }
00182 
00183 template <class PERM>
00184 void ShallowSchreierTreeTransversal<PERM>::permute(const PERM& g, const PERM& gInv) {
00185         Transversal<PERM>::permute(g, gInv);
00186         BOOST_FOREACH(typename PERM::ptr& p, m_cubeLabels) {
00187                 *p ^= gInv;
00188                 *p *= g;
00189                 p->flush();
00190         }
00191 }
00192 
00193 }
00194 
00195 #endif // -- SHALLOWSCHREIERTREETRANSVERSAL_H_