permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/construct/base_construction.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 BASECONSTRUCTION_H
00034 #define BASECONSTRUCTION_H
00035 
00036 #include <map>
00037 #include <algorithm>
00038 
00039 #include <permlib/predicate/pointwise_stabilizer_predicate.h>
00040 #include <permlib/predicate/identity_predicate.h>
00041 
00042 namespace permlib {
00043 
00045 template <class PERM, class TRANS>
00046 class BaseConstruction {
00047 public:
00049 
00052         explicit BaseConstruction(dom_int n);
00053 protected:
00055         dom_int m_n;
00056         
00058 
00066         template <class ForwardIterator, class InputIterator>
00067         void setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, BSGS<PERM, TRANS> &bsgs, std::vector<std::list<typename PERM::ptr> > &S) const;
00068         
00070         void mergeGenerators(std::vector<std::list<typename PERM::ptr> >& S, BSGS<PERM,TRANS>& ret) const;
00071         
00073         static const unsigned long *empty;
00074 };
00075 
00076 //
00077 //     ----       IMPLEMENTATION
00078 //
00079 
00080 template <class PERM, class TRANS>
00081 const unsigned long *BaseConstruction<PERM, TRANS>::empty = static_cast<unsigned long*>(0);
00082 
00083 
00084 template <class PERM, class TRANS>
00085 BaseConstruction<PERM,TRANS>::BaseConstruction(dom_int n) 
00086         : m_n(n) 
00087 { }
00088 
00089 template <class PERM, class TRANS>
00090 template <class ForwardIterator, class InputIterator>
00091 void BaseConstruction<PERM,TRANS>::setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, BSGS<PERM, TRANS> &bsgs, std::vector<std::list<typename PERM::ptr> > &S) const
00092 {
00093         std::vector<dom_int> &B = bsgs.B;
00094         std::vector<TRANS> &U = bsgs.U;
00095         
00096         std::list<typename PERM::ptr> nonIdentityGenerators;
00097         std::remove_copy_if(generatorsBegin, generatorsEnd, std::back_inserter(nonIdentityGenerators), IdentityPredicate<PERM>());
00098 
00099         B.insert(B.begin(), prescribedBaseBegin, prescribedBaseEnd);
00100         // extend base so that no group element fixes all base elements
00101         dom_int beta = m_n + 1;
00102         PointwiseStabilizerPredicate<PERM> stab_k(B.begin(), B.end());
00103         BOOST_FOREACH(const typename PERM::ptr &gen, nonIdentityGenerators) {
00104                 if (stab_k(gen)) {
00105                         if (bsgs.chooseBaseElement(*gen, beta)) {
00106                                 B.push_back(beta);
00107                                 stab_k = PointwiseStabilizerPredicate<PERM>(B.begin(), B.end());
00108                         }
00109                 }
00110         }
00111         
00112         if (B.empty()) {
00113                 B.push_back(0);
00114                 U.push_back(TRANS(m_n));
00115                 // the trivial group has an empty generator list
00116                 std::list<typename PERM::ptr> S_0;
00117                 S.push_back(S_0);
00118                 U[0].orbit(B[0], S_0);
00119                 return;
00120         }
00121         S.reserve(B.size());
00122         
00123         // pre-compute transversals and fundamental orbits for the current base
00124         unsigned int i = 0;
00125         std::vector<dom_int>::iterator Bit;
00126         for (Bit = B.begin(); Bit != B.end(); ++Bit) {
00127                 std::list<typename PERM::ptr> S_i;
00128                 std::copy_if(nonIdentityGenerators.begin(), nonIdentityGenerators.end(),
00129                                 std::back_inserter(S_i), PointwiseStabilizerPredicate<PERM>(B.begin(), Bit));
00130 
00131                 U.push_back(TRANS(m_n));
00132                 S.push_back(S_i);
00133 
00134                 bsgs.orbit(i, S_i);
00135 
00136                 ++i;
00137         }
00138 }
00139 
00140 template <class PERM, class TRANS>
00141 void BaseConstruction<PERM,TRANS>::mergeGenerators(std::vector<std::list<typename PERM::ptr> >& S, BSGS<PERM,TRANS>& ret) const {
00142         std::map<PERM*,typename PERM::ptr> generatorMap;
00143         // merge all generators into one list
00144         BOOST_FOREACH(std::list<typename PERM::ptr> &S_j, S) {
00145                 BOOST_FOREACH(typename PERM::ptr &gen, S_j) {
00146                         bool found = false;
00147                         BOOST_FOREACH(const typename PERM::ptr& genS, ret.S) {
00148                                 if (*genS == *gen) {
00149                                         found = true;
00150                                         generatorMap.insert(std::make_pair(gen.get(), genS));
00151                                         break;
00152                                 }
00153                         }
00154                         if (!found) {
00155                                 ret.S.push_back(gen);
00156                                 generatorMap.insert(std::make_pair(gen.get(), gen));
00157                         }
00158                 }
00159         }
00160 
00161         BOOST_FOREACH(TRANS& U_i, ret.U) {
00162                 U_i.updateGenerators(generatorMap);
00163         }
00164 }
00165 
00166 }
00167 
00168 #endif // -- BASECONSTRUCTION_H