permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
46namespace permlib {
47
49
55template<typename TRANS>
57private:
58 typedef typename TRANS::PERMtype PERM;
59public:
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
85private:
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
94template<typename TRANS>
95template<typename InputIterator>
96PrimitivitySGSTest<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
101template<typename TRANS>
102bool 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; )
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
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
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