permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/test/primitivity_sgs_test.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 PRIMITIVITY_SGS_TEST_H_
00034 #define PRIMITIVITY_SGS_TEST_H_
00035 
00036 #include <permlib/transversal/orbit_set.h>
00037 #include <permlib/transversal/transversal.h>
00038 
00039 #include <boost/foreach.hpp>
00040 #include <boost/scoped_ptr.hpp>
00041 #include <boost/utility.hpp>
00042 #include <vector>
00043 #include <list>
00044 
00045 namespace permlib {
00046 
00048 
00054 template<typename TRANS>
00055 class PrimitivitySGSTest {
00056 private:
00057         typedef typename TRANS::PERMtype PERM;
00058 public:
00069         template<typename InputIterator>
00070         PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS& U);
00071         
00077         bool blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const;
00078         
00082         bool isPrimitive() const { return blockOfImprimitivity(NULL); }
00083         
00084 private:
00085         const TRANS& m_U;
00086         const dom_int m_alpha;
00087         const std::list<typename PERM::ptr> m_generators;
00088         const std::list<typename PERM::ptr> m_generatorsStab;
00089 };
00090 
00091 
00092 
00093 template<typename TRANS>
00094 template<typename InputIterator>
00095 PrimitivitySGSTest<TRANS>::PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS& U)
00096         : m_U(U), m_alpha(alpha), m_generators(genBegin, genEnd), m_generatorsStab(genStabBegin, genStabEnd)
00097 {}
00098 
00099 
00100 template<typename TRANS>
00101 bool PrimitivitySGSTest<TRANS>::blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const {
00102         const unsigned int n = m_U.n();
00103         std::vector<dom_int> AllLambdas(n);
00104         std::vector<dom_int> LambdaReverse(n, n);
00105         unsigned int LambdaLastIndex = 0;
00106         std::list<unsigned int> LambdaBegin;
00107         std::list<unsigned int> LambdaSize;
00108         
00109         dom_int omega;
00110         for (omega = 0; omega < n; ++omega)
00111                 if (m_alpha != omega) 
00112                         break;
00113         
00114         BOOST_ASSERT( omega < n );
00115         
00116         OrbitSet<PERM, dom_int> omegaOrbit;
00117         omegaOrbit.orbit(omega, m_generatorsStab, typename Transversal<PERM>::TrivialAction());
00118         for (typename OrbitSet<PERM, dom_int>::const_iterator oit = omegaOrbit.begin(); oit != omegaOrbit.end(); ++oit) {
00119                 AllLambdas[LambdaLastIndex++] = *oit;
00120                 LambdaReverse[*oit] = 0;
00121         }
00122         LambdaBegin.push_back(0);
00123         LambdaSize.push_back(omegaOrbit.size());
00124         
00125         while (true) {
00126                 const dom_int lambda = AllLambdas[LambdaBegin.back()];
00127                 std::vector<dom_int>::const_iterator LambdaItBegin = AllLambdas.begin() + LambdaBegin.back();
00128                 std::vector<dom_int>::const_iterator LambdaItEnd = LambdaItBegin + LambdaSize.back();
00129                 bool needAnotherIteration = false;
00130                 
00131                 PERMLIB_DEBUG( std::cout << "lambda = " << lambda << std::endl; )
00132                 
00133                 for (std::vector<dom_int>::const_iterator lit = LambdaItBegin; lit != LambdaItEnd; ++lit) {
00134                         boost::scoped_ptr<PERM> u_lambda(m_U.at(lambda));
00135                         BOOST_ASSERT( u_lambda );
00136                         
00137                         const dom_int gamma = *lit;
00138                         const dom_int mu = *u_lambda / gamma;
00139                         
00140                         PERMLIB_DEBUG( std::cout << " u_lambda = " << *u_lambda << ", gamma = " << gamma << ", mu = " << mu << std::endl; )
00141                         
00142                         const unsigned int muIndex = LambdaReverse[mu];
00143                         if (mu != m_alpha && muIndex == n) {
00144                                 PERMLIB_DEBUG( std::cout << " add orbit of mu = " << mu << " at " << LambdaBegin.size() << std::endl; )
00145                                 OrbitSet<PERM, dom_int> muOrbit;
00146                                 muOrbit.orbit(mu, m_generatorsStab, typename Transversal<PERM>::TrivialAction());
00147                                 LambdaBegin.push_back(LambdaLastIndex);
00148                                 LambdaSize.push_back(muOrbit.size());
00149                                 for (typename OrbitSet<PERM, dom_int>::const_iterator oit = muOrbit.begin(); oit != muOrbit.end(); ++oit) {
00150                                         AllLambdas[LambdaLastIndex++] = *oit;
00151                                         LambdaReverse[*oit] = LambdaBegin.size() - 1;
00152                                 }
00153                                 needAnotherIteration = true;
00154                                 break;
00155                         } else if (muIndex < LambdaBegin.size() - 1) {
00156                                 std::list<unsigned int>::const_reverse_iterator sizeIt = LambdaSize.rbegin();
00157                                 std::list<unsigned int>::const_reverse_iterator reprIt = LambdaBegin.rbegin();
00158                                 unsigned int largestReprIndex = n;
00159                                 unsigned int largestLambdaSize = 0;
00160                                 for (dom_int i = muIndex; i < LambdaBegin.size(); ++i) {
00161                                         if (*sizeIt > largestLambdaSize) {
00162                                                 largestLambdaSize = *sizeIt;
00163                                                 largestReprIndex = *reprIt;
00164                                         }
00165                                         ++sizeIt;
00166                                         ++reprIt;
00167                                 }
00168                                 PERMLIB_DEBUG( std::cout << " merge sets from i = " << muIndex << " with representative " << AllLambdas[largestReprIndex] << std::endl; )
00169                                 
00170                                 std::swap(AllLambdas[*boost::next(LambdaBegin.begin(), muIndex)], AllLambdas[largestReprIndex]);
00171                                 for (dom_int i = LambdaBegin.size() - 1; i > muIndex ; --i) {
00172                                         const unsigned int oldSize = LambdaSize.back();
00173                                         LambdaSize.pop_back();
00174                                         LambdaBegin.pop_back();
00175                                         LambdaSize.back() += oldSize;
00176                                 }
00177                                 for (unsigned int i = 0; i < n; ++i)
00178                                         if (LambdaReverse[i] > muIndex && LambdaReverse[i] < n)
00179                                                 LambdaReverse[i] = muIndex;
00180                                 
00181                                 PERMLIB_DEBUG( std::cout << " now there are " << LambdaBegin.size() << " sets left" << std::endl; )
00182                                 needAnotherIteration = true;
00183                                 break;
00184                         }
00185                 }
00186                 
00187                 BOOST_ASSERT( LambdaBegin.size() == LambdaSize.size() );
00188                 
00189                 if (!needAnotherIteration)
00190                         break;
00191         }
00192         
00193         if (minimalBlock) {
00194                 minimalBlock->clear();
00195                 minimalBlock->resize(LambdaSize.back() + 1);
00196                 minimalBlock->at(0) = m_alpha;
00197                 for (unsigned int i = 1; i < minimalBlock->size(); ++i)
00198                         minimalBlock->at(i) = AllLambdas[LambdaBegin.back() + i - 1];
00199         }
00200         
00201         return LambdaSize.back() == m_U.size() - 1;
00202 }
00203 
00204 }
00205 
00206 #endif