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 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_