33 #ifndef PRIMITIVITY_SGS_TEST_H_ 34 #define PRIMITIVITY_SGS_TEST_H_ 36 #include <permlib/transversal/orbit_set.h> 37 #include <permlib/transversal/transversal.h> 39 #include <boost/foreach.hpp> 40 #include <boost/scoped_ptr.hpp> 41 #include <boost/utility.hpp> 54 template<
typename TRANS>
57 typedef typename TRANS::PERMtype PERM;
69 template<
typename InputIterator>
70 PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd,
const TRANS& 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;
93 template<
typename TRANS>
94 template<
typename InputIterator>
96 : m_U(U), m_alpha(alpha), m_generators(genBegin, genEnd), m_generatorsStab(genStabBegin, genStabEnd)
100 template<
typename TRANS>
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;
110 for (omega = 0; omega < n; ++omega)
111 if (m_alpha != omega)
114 BOOST_ASSERT( omega < n );
118 for (
typename OrbitSet<PERM, dom_int>::const_iterator oit = omegaOrbit.
begin(); oit != omegaOrbit.
end(); ++oit) {
119 AllLambdas[LambdaLastIndex++] = *oit;
120 LambdaReverse[*oit] = 0;
122 LambdaBegin.push_back(0);
123 LambdaSize.push_back(omegaOrbit.
size());
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;
131 PERMLIB_DEBUG( std::cout <<
"lambda = " << lambda << std::endl; )
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 );
137 const dom_int gamma = *lit;
138 const dom_int mu = *u_lambda / gamma;
140 PERMLIB_DEBUG( std::cout <<
" u_lambda = " << *u_lambda <<
", gamma = " << gamma <<
", mu = " << mu << std::endl; )
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; )
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;
153 needAnotherIteration =
true;
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;
168 PERMLIB_DEBUG( std::cout <<
" merge sets from i = " << muIndex <<
" with representative " << AllLambdas[largestReprIndex] << std::endl; )
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;
177 for (
unsigned int i = 0; i < n; ++i)
178 if (LambdaReverse[i] > muIndex && LambdaReverse[i] < n)
179 LambdaReverse[i] = muIndex;
181 PERMLIB_DEBUG( std::cout <<
" now there are " << LambdaBegin.size() <<
" sets left" << std::endl; )
182 needAnotherIteration =
true;
187 BOOST_ASSERT( LambdaBegin.size() == LambdaSize.size() );
189 if (!needAnotherIteration)
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];
201 return LambdaSize.back() == m_U.size() - 1;
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