33 #ifndef GROUPREFINEMENT_H_
34 #define GROUPREFINEMENT_H_
36 #include <permlib/predicate/pointwise_stabilizer_predicate.h>
37 #include <permlib/search/partition/refinement.h>
43 template<
class PERM,
class TRANS>
59 std::vector<unsigned int> thetaOrbit;
60 std::vector<int> thetaBorder;
63 mutable Partition::vector_t m_myTheta;
68 template<
class PERM,
class TRANS>
70 :
Refinement<PERM>(bsgs_.n, Group), m_bsgs(bsgs_), thetaOrbit(m_bsgs.n), thetaBorder(m_bsgs.n, -1), m_myTheta(m_bsgs.n)
74 template<
class PERM,
class TRANS>
79 template<
class PERM,
class TRANS>
81 return apply2(pi, &t);
84 template<
class PERM,
class TRANS>
86 BOOST_ASSERT( this->initialized() );
88 Partition::vector_t& myTheta = m_myTheta;
90 Partition::vector_t::iterator thetaIt;
91 Partition::vector_t::iterator thetaBeginIt, thetaEndIt;
92 Partition::vector_t::const_iterator thetaOrbitIt;
94 unsigned int ret =
false;
96 const int thetaC = *cellPairIt;
98 if (*cellPairIt < 0) {
105 borderLo = thetaBorder[thetaC-1];
106 thetaBeginIt = myTheta.begin() + borderLo;
107 thetaEndIt = myTheta.begin() + thetaBorder[thetaC];
110 for (thetaIt = thetaBeginIt, thetaOrbitIt = thetaOrbit.begin() + borderLo;
111 thetaIt != thetaEndIt && thetaOrbitIt != thetaOrbit.begin() + thetaBorder[thetaC];
112 ++thetaIt, ++thetaOrbitIt)
114 *thetaIt = *t / *thetaOrbitIt;
116 std::sort(thetaBeginIt, thetaEndIt);
119 for (
int c = *cellPairIt; c >= 0; c = *(++cellPairIt)) {
121 PERMLIB_DEBUG(std::cout <<
"apply theta " << thetaC <<
"," << c <<
" t = " << *t <<
" to " << pi << std::endl;)
123 PERMLIB_DEBUG(std::cout <<
"apply theta " << thetaC <<
"," << c <<
" t = 0 to " << pi << std::endl;)
126 if (pi.
intersect(thetaBeginIt, thetaEndIt, c))
135 template<
class PERM,
class TRANS>
139 boost::dynamic_bitset<> orbitCharacterstic(m_bsgs.n);
141 std::vector<dom_int>::const_iterator Bit;
143 Partition::vector_t::const_iterator fixEndIt = pi.
fixPointsEnd();
144 for (Bit = m_bsgs.B.begin(); Bit != m_bsgs.B.end(); ++Bit) {
145 while (fixIt != fixEndIt && *fixIt != *Bit) {
146 PERMLIB_DEBUG(std::cout <<
"skip " << (*fixIt + 1) <<
" for " << (*Bit + 1) << std::endl;)
149 if (fixIt == fixEndIt)
154 #ifdef PERMLIB_DEBUG_OUTPUT
155 print_iterable(m_bsgs.B.begin(), m_bsgs.B.end(), 1,
" BSGS ");
156 print_iterable(m_bsgs.B.begin(), Bit, 1,
"to fix");
160 std::list<PERM> S_fix;
161 BOOST_FOREACH(
const typename PERM::ptr& p, m_bsgs.S) {
168 unsigned int thetaIndex = 0;
169 std::vector<int>::iterator thetaBorderIt = thetaBorder.begin();
170 std::vector<unsigned int>::iterator thetaIt = thetaOrbit.begin();
171 for (
unsigned long alpha = 0; alpha < m_bsgs.n; ++alpha) {
172 if (orbitCharacterstic[alpha])
174 orbitCharacterstic.flip(alpha);
175 std::vector<unsigned int>::iterator thetaOrbitBeginIt = thetaIt;
179 std::vector<unsigned int>::iterator thetaOrbitEndIt = thetaIt;
181 std::vector<unsigned int>::iterator it;
182 for (it = thetaOrbitBeginIt; it != thetaOrbitEndIt; ++it) {
183 unsigned int beta = *it;
184 BOOST_FOREACH(
const PERM &p, S_fix) {
185 unsigned int beta_p = p / beta;
186 if (!orbitCharacterstic[beta_p]) {
191 orbitCharacterstic.flip(beta_p);
195 *thetaBorderIt = thetaIndex;
199 thetaIt = thetaOrbit.begin();
200 std::vector<unsigned int>::iterator thetaItEnd;
201 thetaBorderIt = thetaBorder.begin();
202 unsigned int thetaC = 0;
204 while (thetaBorderIt != thetaBorder.end() && *thetaBorderIt >= 0) {
205 thetaItEnd = thetaOrbit.begin() + *thetaBorderIt;
206 std::sort(thetaIt, thetaItEnd);
209 bool hasTheta =
false;
210 const unsigned int oldCellNumber = pi.
cells();
211 for (
unsigned int c = 0; c < oldCellNumber; ++c) {
217 if (pi.
intersect(thetaIt, thetaItEnd, c)) {
218 PERMLIB_DEBUG(std::cout <<
"prepare theta " << thetaC <<
"," << c << std::endl;)
234 oldBorder = *thetaBorderIt;
235 thetaIt = thetaItEnd;
250 template<
class PERM,
class TRANS>
258 #endif // -- GROUPREFINEMENT_H_