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>
42#include <boost/next_prior.hpp>
55template<
typename TRANS>
58 typedef typename TRANS::PERMtype PERM;
70 template<
typename InputIterator>
71 PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd,
const TRANS& 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;
94template<
typename TRANS>
95template<
typename InputIterator>
97 : m_U(U), m_alpha(alpha), m_generators(genBegin, genEnd), m_generatorsStab(genStabBegin, genStabEnd)
101template<
typename TRANS>
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;
111 for (omega = 0; omega < n; ++omega)
112 if (m_alpha != omega)
115 BOOST_ASSERT( omega < n );
119 for (
typename OrbitSet<PERM, dom_int>::const_iterator oit = omegaOrbit.
begin(); oit != omegaOrbit.
end(); ++oit) {
120 AllLambdas[LambdaLastIndex++] = *oit;
121 LambdaReverse[*oit] = 0;
123 LambdaBegin.push_back(0);
124 LambdaSize.push_back(omegaOrbit.
size());
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;
132 PERMLIB_DEBUG( std::cout <<
"lambda = " << lambda << std::endl; )
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 );
138 const dom_int gamma = *lit;
139 const dom_int mu = *u_lambda / gamma;
141 PERMLIB_DEBUG( std::cout <<
" u_lambda = " << *u_lambda <<
", gamma = " << gamma <<
", mu = " << mu << std::endl; )
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; )
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;
154 needAnotherIteration =
true;
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;
169 PERMLIB_DEBUG( std::cout <<
" merge sets from i = " << muIndex <<
" with representative " << AllLambdas[largestReprIndex] << std::endl; )
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;
178 for (
unsigned int i = 0; i < n; ++i)
179 if (LambdaReverse[i] > muIndex && LambdaReverse[i] < n)
180 LambdaReverse[i] = muIndex;
182 PERMLIB_DEBUG( std::cout <<
" now there are " << LambdaBegin.size() <<
" sets left" << std::endl; )
183 needAnotherIteration =
true;
188 BOOST_ASSERT( LambdaBegin.size() == LambdaSize.size() );
190 if (!needAnotherIteration)
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];
202 return LambdaSize.back() == m_U.size() - 1;
stores an orbit in a set for fast contains() operation
Definition orbit_set.h:42
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
const_iterator end() const
end-iterator to orbit elements
Definition orbit_set.h:68
const_iterator begin() const
begin-iterator to orbit elements
Definition orbit_set.h:66
Tests a transitive group for which a strong generating set is availble for primitivity.
Definition primitivity_sgs_test.h:56
bool blockOfImprimitivity(std::vector< dom_int > *minimalBlock) const
Definition primitivity_sgs_test.h:102
PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS &U)
Definition primitivity_sgs_test.h:96
bool isPrimitive() const
Definition primitivity_sgs_test.h:83
action of a PERM on unsigned long element
Definition transversal.h:112