permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/test/type_recognition.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 #ifndef TYPE_RECOGNITION_H_
00033 #define TYPE_RECOGNITION_H_
00034 
00035 #include <permlib/prime_helper.h>
00036 #include <permlib/transversal/schreier_tree_transversal.h>
00037 #include <permlib/generator/bsgs_generator.h>
00038 #include <permlib/construct/schreier_sims_construction.h>
00039 #include <permlib/transversal/orbit_set.h>
00040 #include <permlib/test/giant_test.h>
00041 #include <permlib/test/group_type.h>
00042 #include <permlib/test/primitivity_sgs_test.h>
00043 
00044 #include <iostream>
00045 
00046 
00047 namespace permlib {
00048 
00050 
00054 template<class PERM, class TRANSVERSAL = SchreierTreeTransversal<PERM> >
00055 class TypeRecognition {
00056 public:
00058         typedef boost::shared_ptr<BSGS<PERM, TRANSVERSAL> > PermutationGroupPtr;
00059         
00065         template<class InputIterator>
00066         TypeRecognition(unsigned int n, InputIterator genBegin, InputIterator genEnd);
00067         
00071         TypeRecognition(const PermutationGroupPtr& bsgs);
00072         
00074         GroupType* analyze() { return analyze(true); }
00076         PermutationGroupPtr bsgs() const { return m_bsgs; }
00077 private:
00078         const unsigned int m_n;
00079         std::list<typename PERM::ptr> m_generators;
00080         const PermutationGroupPtr m_externalBSGS;
00081         PermutationGroupPtr m_bsgs;
00082         
00086         GroupType* analyze(bool allowRecursiveCalls);
00087         
00089 
00092         GroupType* checkOrbitActions();
00093         
00095         static const unsigned int m_bsgsComputationDegreeLimit = 50;
00096 };
00097 
00098 template<class PERM, class TRANSVERSAL>
00099 template<class InputIterator>
00100 TypeRecognition<PERM,TRANSVERSAL>::TypeRecognition(unsigned int n, InputIterator genBegin, InputIterator genEnd) 
00101         : m_n(n), m_generators(genBegin, genEnd)
00102 { }
00103 
00104 template<class PERM, class TRANSVERSAL>
00105 TypeRecognition<PERM,TRANSVERSAL>::TypeRecognition(const PermutationGroupPtr& bsgs_) 
00106         : m_n(bsgs_->n), m_generators(bsgs_->S.begin(), bsgs_->S.end()), m_externalBSGS(bsgs_), m_bsgs(m_externalBSGS)
00107 { }
00108 
00109 
00110 template<class PERM, class TRANSVERSAL>
00111 GroupType* TypeRecognition<PERM,TRANSVERSAL>::analyze(bool allowRecursiveCalls) {
00112         if (m_n < m_bsgsComputationDegreeLimit && ! m_bsgs) {
00113                 SchreierSimsConstruction<PERM,TRANSVERSAL> ssc(m_n);
00114                 m_bsgs = PermutationGroupPtr(new BSGS<PERM, TRANSVERSAL>(ssc.construct(m_generators.begin(), m_generators.end())));
00115         }
00116 
00117         // error probability for randomized algorithms
00118         const double eps = 1e-3;
00119         
00120         if (m_bsgs) {
00121                 const unsigned int groupIntOrder = m_bsgs->template order<unsigned int>();
00122                 
00123                 if (groupIntOrder == 1)
00124                         return new TrivialGroupType(m_n);
00125 
00126                 if (groupIntOrder == 2)
00127                         return new SymmetricGroupType(groupIntOrder, m_n);
00128                 
00129                 //
00130                 // check for cyclic groups
00131                 //
00132                 if (PrimeHelper::isPrimeNumber(groupIntOrder, false)) {
00133                         BOOST_ASSERT( m_n % groupIntOrder == 0 );
00134                         return new CyclicGroupType(groupIntOrder, m_n);
00135                 }
00136                 
00137                 if (groupIntOrder == 4) {
00138                         // distinguish between C_4 and the Klein four group
00139                         BSGSGenerator<TRANSVERSAL> bsgsGen(m_bsgs->U);
00140                         while (bsgsGen.hasNext()) {
00141                                 PERM el = bsgsGen.next();
00142                                 if (el.order() == 4)
00143                                         return new CyclicGroupType(4, m_n);
00144                         }
00145                         return new DirectProductGroupType(new SymmetricGroupType(2,2), new SymmetricGroupType(2,2), m_n);
00146                 }
00147                 
00148                 //
00149                 // check for symmetric groups, natural action
00150                 //
00151                 unsigned int symmetricGroupCandidateDegree = 0;
00152                 
00153                 std::vector<unsigned int> transversalSizes(m_bsgs->U.size());
00154                 for (unsigned int i = 0; i < m_bsgs->U.size(); ++i) {
00155                         transversalSizes[i] = m_bsgs->U[i].size();
00156                 }
00157                 std::sort(transversalSizes.begin(), transversalSizes.end());
00158                 
00159                 // test whether group order is a factorial of some natural number
00160                 
00161                 unsigned int expectedFactor = 2;
00162                 for (std::vector<unsigned int>::const_iterator it = transversalSizes.begin(); it != transversalSizes.end(); ++it) {
00163                         if (*it == 1)
00164                                 continue;
00165                         if (*it == expectedFactor)
00166                                 ++expectedFactor;
00167                         else {
00168                                 expectedFactor = 0;
00169                                 break;
00170                         }
00171                 }
00172                 
00173                 if (expectedFactor > 0)
00174                         symmetricGroupCandidateDegree = expectedFactor - 1;
00175                 
00176                 if (symmetricGroupCandidateDegree == m_n)
00177                         return new SymmetricGroupType(symmetricGroupCandidateDegree, m_n);
00178                 
00179                 // check for wreath products of symmetric groups if group is transitive
00180                 if (m_bsgs->U[0].size() == m_n) {
00181                         std::list<typename PERM::ptr> S1;
00182                         PointwiseStabilizerPredicate<PERM> stabPred(m_bsgs->B[0]);
00183                         BOOST_FOREACH(const typename PERM::ptr& p, m_bsgs->S) {
00184                                 if (stabPred(p))
00185                                         S1.push_back(p);
00186                         }
00187                         PrimitivitySGSTest<TRANSVERSAL> primitivityTest(m_bsgs->S.begin(), m_bsgs->S.end(), m_bsgs->B[0], S1.begin(), S1.end(), m_bsgs->U[0]);
00188                         std::vector<dom_int> minimalBlock;
00189                         bool groupIsPrimitive = primitivityTest.blockOfImprimitivity(&minimalBlock); 
00190                         if ( ! groupIsPrimitive ) {
00191                                 // TODO: avoid integer overflow in order computation
00192                                 unsigned int degreeG = minimalBlock.size();
00193                                 unsigned int degreeH = m_n / degreeG;
00194                                 if (m_n % degreeG == 0) {
00195                                         boost::uint64_t wreathSize = 1;
00196                                         // group order must equal   factorial(deg G)^(deg H) * factorial(deg H)
00197                                         for (unsigned int i = 1; i <= degreeH; ++i) {
00198                                                 for (unsigned int j = 2; j <= degreeG; ++j) {
00199                                                         wreathSize *= j;
00200                                                 }
00201                                                 wreathSize *= i;
00202                                         }
00203                                         if (wreathSize == m_bsgs->order())
00204                                                 return new WreathSymmetricGroupType(degreeG, degreeH, m_n);
00205                                 }
00206                         } else {
00207                                 GiantTest<PERM> giantTest;
00208                                 GiantTestBase::GiantGroupType giant = giantTest.determineGiantType(eps, 
00209                                         m_n, m_bsgs->S.begin(), m_bsgs->S.end(), true);
00210                                 if (giant == GiantTestBase::Symmetric)
00211                                         return new SymmetricGroupType(m_n, m_n);
00212                                 else if (giant == GiantTestBase::Alternating)
00213                                         return new AlternatingGroupType(m_n, m_n);
00214                         }
00215                 }
00216                 
00217                 
00218                 if (allowRecursiveCalls) {
00219                         // check for multiple linked copies of S_k
00220                         // TODO: check for inner direct products of S_k \times S_l
00221                         GroupType* t = checkOrbitActions();
00222                         if (t) {
00223                                 return t;
00224                         }
00225                 }
00226         } // end if m_bsgs
00227         else // else if ! m_bsgs
00228         {
00229                 GiantTest<PERM> giantTest;
00230                 GiantTestBase::GiantGroupType giant = giantTest.determineGiantType(eps, 
00231                         m_n, m_generators.begin(), m_generators.end());
00232                 if (giant == GiantTestBase::Symmetric)
00233                         return new SymmetricGroupType(m_n, m_n);
00234                 else if (giant == GiantTestBase::Alternating)
00235                         return new AlternatingGroupType(m_n, m_n);
00236                 
00237                 if (allowRecursiveCalls) {
00238                         GroupType* t = checkOrbitActions();
00239                         if (t)
00240                                 return t;
00241                 }
00242         }
00243         
00244         if (m_bsgs)
00245                 return new AnonymousGroupType<>(m_n, m_bsgs->order());
00246         return new AnonymousGroupType<>(m_n);
00247 }
00248 
00249 template<class PERM, class TRANSVERSAL>
00250 GroupType* TypeRecognition<PERM,TRANSVERSAL>::checkOrbitActions() {
00251         if (m_generators.empty())
00252                 return NULL;
00253         
00254         typedef typename PERM::ptr PERMptr;
00255         boost::dynamic_bitset<> worked(m_n);
00256         GroupType* candidateType = 0;
00257         
00258         for (unsigned int i = 0; i < m_n; ++i) {
00259                 if (worked[i])
00260                         continue;
00261                 worked.set(i, true);
00262                 OrbitSet<PERM, dom_int> orbit;
00263                 orbit.orbit(i, m_generators, typename Transversal<PERM>::TrivialAction());
00264                 for (typename OrbitSet<PERM, dom_int>::const_iterator it = orbit.begin(); it != orbit.end(); ++it) {
00265                         worked.set(*it, true);
00266                 }
00267                 
00268                 // restrict group to this orbit
00269                 std::list<PERMptr> orbitGenerators;
00270                 BOOST_FOREACH(const PERMptr& p, m_generators) {
00271                         orbitGenerators.push_back(PERMptr(p->project(orbit.size(), orbit.begin(), orbit.end())));
00272                 }
00273                 TypeRecognition<PERM, TRANSVERSAL> orbitTypeRecognition(orbit.size(), orbitGenerators.begin(), orbitGenerators.end());
00274                 GroupType* orbitType = orbitTypeRecognition.analyze(false);
00275                 if ( ! candidateType )
00276                         candidateType = orbitType;
00277                 else {
00278                         const bool isEqualType = candidateType->equals(orbitType);
00279                         delete orbitType;
00280                         if ( ! isEqualType ) 
00281                                 return NULL;
00282                 }
00283         }
00284         if (candidateType)
00285                 candidateType->setNonNaturalAction(m_n);
00286         return candidateType;
00287 }
00288 
00289 
00290 }
00291 
00292 #endif
00293