permlib  0.2.9
Library for permutation computations
primitivity_sgs_test.h
1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 // 1. Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // 3. The name of the author may not be used to endorse or promote products
17 // derived from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // ---------------------------------------------------------------------------
31 
32 
33 #ifndef PRIMITIVITY_SGS_TEST_H_
34 #define PRIMITIVITY_SGS_TEST_H_
35 
36 #include <permlib/transversal/orbit_set.h>
37 #include <permlib/transversal/transversal.h>
38 
39 #include <boost/foreach.hpp>
40 #include <boost/scoped_ptr.hpp>
41 #include <boost/utility.hpp>
42 #include <boost/next_prior.hpp>
43 #include <vector>
44 #include <list>
45 
46 namespace permlib {
47 
49 
55 template<typename TRANS>
57 private:
58  typedef typename TRANS::PERMtype PERM;
59 public:
70  template<typename InputIterator>
71  PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS& U);
72 
78  bool blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const;
79 
83  bool isPrimitive() const { return blockOfImprimitivity(NULL); }
84 
85 private:
86  const TRANS& m_U;
87  const dom_int m_alpha;
88  const std::list<typename PERM::ptr> m_generators;
89  const std::list<typename PERM::ptr> m_generatorsStab;
90 };
91 
92 
93 
94 template<typename TRANS>
95 template<typename InputIterator>
96 PrimitivitySGSTest<TRANS>::PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS& U)
97  : m_U(U), m_alpha(alpha), m_generators(genBegin, genEnd), m_generatorsStab(genStabBegin, genStabEnd)
98 {}
99 
100 
101 template<typename TRANS>
102 bool PrimitivitySGSTest<TRANS>::blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const {
103  const unsigned int n = m_U.n();
104  std::vector<dom_int> AllLambdas(n);
105  std::vector<dom_int> LambdaReverse(n, n);
106  unsigned int LambdaLastIndex = 0;
107  std::list<unsigned int> LambdaBegin;
108  std::list<unsigned int> LambdaSize;
109 
110  dom_int omega;
111  for (omega = 0; omega < n; ++omega)
112  if (m_alpha != omega)
113  break;
114 
115  BOOST_ASSERT( omega < n );
116 
117  OrbitSet<PERM, dom_int> omegaOrbit;
118  omegaOrbit.orbit(omega, m_generatorsStab, typename Transversal<PERM>::TrivialAction());
119  for (typename OrbitSet<PERM, dom_int>::const_iterator oit = omegaOrbit.begin(); oit != omegaOrbit.end(); ++oit) {
120  AllLambdas[LambdaLastIndex++] = *oit;
121  LambdaReverse[*oit] = 0;
122  }
123  LambdaBegin.push_back(0);
124  LambdaSize.push_back(omegaOrbit.size());
125 
126  while (true) {
127  const dom_int lambda = AllLambdas[LambdaBegin.back()];
128  std::vector<dom_int>::const_iterator LambdaItBegin = AllLambdas.begin() + LambdaBegin.back();
129  std::vector<dom_int>::const_iterator LambdaItEnd = LambdaItBegin + LambdaSize.back();
130  bool needAnotherIteration = false;
131 
132  PERMLIB_DEBUG( std::cout << "lambda = " << lambda << std::endl; )
133 
134  for (std::vector<dom_int>::const_iterator lit = LambdaItBegin; lit != LambdaItEnd; ++lit) {
135  boost::scoped_ptr<PERM> u_lambda(m_U.at(lambda));
136  BOOST_ASSERT( u_lambda );
137 
138  const dom_int gamma = *lit;
139  const dom_int mu = *u_lambda / gamma;
140 
141  PERMLIB_DEBUG( std::cout << " u_lambda = " << *u_lambda << ", gamma = " << gamma << ", mu = " << mu << std::endl; )
142 
143  const unsigned int muIndex = LambdaReverse[mu];
144  if (mu != m_alpha && muIndex == n) {
145  PERMLIB_DEBUG( std::cout << " add orbit of mu = " << mu << " at " << LambdaBegin.size() << std::endl; )
146  OrbitSet<PERM, dom_int> muOrbit;
147  muOrbit.orbit(mu, m_generatorsStab, typename Transversal<PERM>::TrivialAction());
148  LambdaBegin.push_back(LambdaLastIndex);
149  LambdaSize.push_back(muOrbit.size());
150  for (typename OrbitSet<PERM, dom_int>::const_iterator oit = muOrbit.begin(); oit != muOrbit.end(); ++oit) {
151  AllLambdas[LambdaLastIndex++] = *oit;
152  LambdaReverse[*oit] = LambdaBegin.size() - 1;
153  }
154  needAnotherIteration = true;
155  break;
156  } else if (muIndex < LambdaBegin.size() - 1) {
157  std::list<unsigned int>::const_reverse_iterator sizeIt = LambdaSize.rbegin();
158  std::list<unsigned int>::const_reverse_iterator reprIt = LambdaBegin.rbegin();
159  unsigned int largestReprIndex = n;
160  unsigned int largestLambdaSize = 0;
161  for (dom_int i = muIndex; i < LambdaBegin.size(); ++i) {
162  if (*sizeIt > largestLambdaSize) {
163  largestLambdaSize = *sizeIt;
164  largestReprIndex = *reprIt;
165  }
166  ++sizeIt;
167  ++reprIt;
168  }
169  PERMLIB_DEBUG( std::cout << " merge sets from i = " << muIndex << " with representative " << AllLambdas[largestReprIndex] << std::endl; )
170 
171  std::swap(AllLambdas[*boost::next(LambdaBegin.begin(), muIndex)], AllLambdas[largestReprIndex]);
172  for (dom_int i = LambdaBegin.size() - 1; i > muIndex ; --i) {
173  const unsigned int oldSize = LambdaSize.back();
174  LambdaSize.pop_back();
175  LambdaBegin.pop_back();
176  LambdaSize.back() += oldSize;
177  }
178  for (unsigned int i = 0; i < n; ++i)
179  if (LambdaReverse[i] > muIndex && LambdaReverse[i] < n)
180  LambdaReverse[i] = muIndex;
181 
182  PERMLIB_DEBUG( std::cout << " now there are " << LambdaBegin.size() << " sets left" << std::endl; )
183  needAnotherIteration = true;
184  break;
185  }
186  }
187 
188  BOOST_ASSERT( LambdaBegin.size() == LambdaSize.size() );
189 
190  if (!needAnotherIteration)
191  break;
192  }
193 
194  if (minimalBlock) {
195  minimalBlock->clear();
196  minimalBlock->resize(LambdaSize.back() + 1);
197  minimalBlock->at(0) = m_alpha;
198  for (unsigned int i = 1; i < minimalBlock->size(); ++i)
199  minimalBlock->at(i) = AllLambdas[LambdaBegin.back() + i - 1];
200  }
201 
202  return LambdaSize.back() == m_U.size() - 1;
203 }
204 
205 }
206 
207 #endif
permlib::OrbitSet::orbit
void orbit(const PDOMAIN &beta, const std::list< typename PERM::ptr > &generators, Action a)
computes orbit of beta under generators
Definition: orbit_set.h:92
permlib::OrbitSet::end
const_iterator end() const
end-iterator to orbit elements
Definition: orbit_set.h:68
permlib::OrbitSet
stores an orbit in a set for fast contains() operation
Definition: orbit_set.h:42
permlib::PrimitivitySGSTest
Tests a transitive group for which a strong generating set is availble for primitivity.
Definition: primitivity_sgs_test.h:56
permlib::PrimitivitySGSTest::blockOfImprimitivity
bool blockOfImprimitivity(std::vector< dom_int > *minimalBlock) const
Definition: primitivity_sgs_test.h:102
permlib::PrimitivitySGSTest::isPrimitive
bool isPrimitive() const
Definition: primitivity_sgs_test.h:83
permlib::OrbitSet::size
size_t size() const
number of orbit elements
Definition: orbit_set.h:60
permlib::OrbitSet::begin
const_iterator begin() const
begin-iterator to orbit elements
Definition: orbit_set.h:66
permlib::PrimitivitySGSTest::PrimitivitySGSTest
PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS &U)
Definition: primitivity_sgs_test.h:96
permlib::Transversal::TrivialAction
action of a PERM on unsigned long element
Definition: transversal.h:112