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 <vector>
43 #include <list>
44 
45 namespace permlib {
46 
48 
54 template<typename TRANS>
56 private:
57  typedef typename TRANS::PERMtype PERM;
58 public:
69  template<typename InputIterator>
70  PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS& U);
71 
77  bool blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const;
78 
82  bool isPrimitive() const { return blockOfImprimitivity(NULL); }
83 
84 private:
85  const TRANS& m_U;
86  const dom_int m_alpha;
87  const std::list<typename PERM::ptr> m_generators;
88  const std::list<typename PERM::ptr> m_generatorsStab;
89 };
90 
91 
92 
93 template<typename TRANS>
94 template<typename InputIterator>
95 PrimitivitySGSTest<TRANS>::PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS& U)
96  : m_U(U), m_alpha(alpha), m_generators(genBegin, genEnd), m_generatorsStab(genStabBegin, genStabEnd)
97 {}
98 
99 
100 template<typename TRANS>
101 bool PrimitivitySGSTest<TRANS>::blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const {
102  const unsigned int n = m_U.n();
103  std::vector<dom_int> AllLambdas(n);
104  std::vector<dom_int> LambdaReverse(n, n);
105  unsigned int LambdaLastIndex = 0;
106  std::list<unsigned int> LambdaBegin;
107  std::list<unsigned int> LambdaSize;
108 
109  dom_int omega;
110  for (omega = 0; omega < n; ++omega)
111  if (m_alpha != omega)
112  break;
113 
114  BOOST_ASSERT( omega < n );
115 
116  OrbitSet<PERM, dom_int> omegaOrbit;
117  omegaOrbit.orbit(omega, m_generatorsStab, typename Transversal<PERM>::TrivialAction());
118  for (typename OrbitSet<PERM, dom_int>::const_iterator oit = omegaOrbit.begin(); oit != omegaOrbit.end(); ++oit) {
119  AllLambdas[LambdaLastIndex++] = *oit;
120  LambdaReverse[*oit] = 0;
121  }
122  LambdaBegin.push_back(0);
123  LambdaSize.push_back(omegaOrbit.size());
124 
125  while (true) {
126  const dom_int lambda = AllLambdas[LambdaBegin.back()];
127  std::vector<dom_int>::const_iterator LambdaItBegin = AllLambdas.begin() + LambdaBegin.back();
128  std::vector<dom_int>::const_iterator LambdaItEnd = LambdaItBegin + LambdaSize.back();
129  bool needAnotherIteration = false;
130 
131  PERMLIB_DEBUG( std::cout << "lambda = " << lambda << std::endl; )
132 
133  for (std::vector<dom_int>::const_iterator lit = LambdaItBegin; lit != LambdaItEnd; ++lit) {
134  boost::scoped_ptr<PERM> u_lambda(m_U.at(lambda));
135  BOOST_ASSERT( u_lambda );
136 
137  const dom_int gamma = *lit;
138  const dom_int mu = *u_lambda / gamma;
139 
140  PERMLIB_DEBUG( std::cout << " u_lambda = " << *u_lambda << ", gamma = " << gamma << ", mu = " << mu << std::endl; )
141 
142  const unsigned int muIndex = LambdaReverse[mu];
143  if (mu != m_alpha && muIndex == n) {
144  PERMLIB_DEBUG( std::cout << " add orbit of mu = " << mu << " at " << LambdaBegin.size() << std::endl; )
145  OrbitSet<PERM, dom_int> muOrbit;
146  muOrbit.orbit(mu, m_generatorsStab, typename Transversal<PERM>::TrivialAction());
147  LambdaBegin.push_back(LambdaLastIndex);
148  LambdaSize.push_back(muOrbit.size());
149  for (typename OrbitSet<PERM, dom_int>::const_iterator oit = muOrbit.begin(); oit != muOrbit.end(); ++oit) {
150  AllLambdas[LambdaLastIndex++] = *oit;
151  LambdaReverse[*oit] = LambdaBegin.size() - 1;
152  }
153  needAnotherIteration = true;
154  break;
155  } else if (muIndex < LambdaBegin.size() - 1) {
156  std::list<unsigned int>::const_reverse_iterator sizeIt = LambdaSize.rbegin();
157  std::list<unsigned int>::const_reverse_iterator reprIt = LambdaBegin.rbegin();
158  unsigned int largestReprIndex = n;
159  unsigned int largestLambdaSize = 0;
160  for (dom_int i = muIndex; i < LambdaBegin.size(); ++i) {
161  if (*sizeIt > largestLambdaSize) {
162  largestLambdaSize = *sizeIt;
163  largestReprIndex = *reprIt;
164  }
165  ++sizeIt;
166  ++reprIt;
167  }
168  PERMLIB_DEBUG( std::cout << " merge sets from i = " << muIndex << " with representative " << AllLambdas[largestReprIndex] << std::endl; )
169 
170  std::swap(AllLambdas[*boost::next(LambdaBegin.begin(), muIndex)], AllLambdas[largestReprIndex]);
171  for (dom_int i = LambdaBegin.size() - 1; i > muIndex ; --i) {
172  const unsigned int oldSize = LambdaSize.back();
173  LambdaSize.pop_back();
174  LambdaBegin.pop_back();
175  LambdaSize.back() += oldSize;
176  }
177  for (unsigned int i = 0; i < n; ++i)
178  if (LambdaReverse[i] > muIndex && LambdaReverse[i] < n)
179  LambdaReverse[i] = muIndex;
180 
181  PERMLIB_DEBUG( std::cout << " now there are " << LambdaBegin.size() << " sets left" << std::endl; )
182  needAnotherIteration = true;
183  break;
184  }
185  }
186 
187  BOOST_ASSERT( LambdaBegin.size() == LambdaSize.size() );
188 
189  if (!needAnotherIteration)
190  break;
191  }
192 
193  if (minimalBlock) {
194  minimalBlock->clear();
195  minimalBlock->resize(LambdaSize.back() + 1);
196  minimalBlock->at(0) = m_alpha;
197  for (unsigned int i = 1; i < minimalBlock->size(); ++i)
198  minimalBlock->at(i) = AllLambdas[LambdaBegin.back() + i - 1];
199  }
200 
201  return LambdaSize.back() == m_U.size() - 1;
202 }
203 
204 }
205 
206 #endif
action of a PERM on unsigned long element
Definition: transversal.h:112
const_iterator begin() const
begin-iterator to orbit elements
Definition: orbit_set.h:66
PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS &U)
Definition: primitivity_sgs_test.h:95
stores an orbit in a set for fast contains() operation
Definition: orbit_set.h:42
const_iterator end() const
end-iterator to orbit elements
Definition: orbit_set.h:68
Tests a transitive group for which a strong generating set is availble for primitivity.
Definition: primitivity_sgs_test.h:55
bool blockOfImprimitivity(std::vector< dom_int > *minimalBlock) const
Definition: primitivity_sgs_test.h:101
size_t size() const
number of orbit elements
Definition: orbit_set.h:60
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
bool isPrimitive() const
Definition: primitivity_sgs_test.h:82
Definition: abstract_bsgs.h:49