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_ vector_t::const_iterator fixPointsEnd() const
iterator to the end of fix points
Definition: partition.h:167
virtual unsigned int apply(Partition &pi) const
applies (left-)refinement to pi which is the original partition this refinement was initialized to ...
Definition: group_refinement.h:75
base class for a -refinement which is used in an R-base and bound to an initial partition ...
Definition: refinement.h:53
partition
Definition: partition.h:48
core data of a base and strong generating set (BSGS)
Definition: bsgs_core.h:42
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: pointwise_stabilizer_predicate.h:42
unsigned long cells() const
number of cells in this partition
Definition: partition.h:157
bool intersect(ForwardIterator begin, ForwardIterator end, unsigned int j)
intersects the j-th cell of this partition with a given set
Definition: partition.h:186
unsigned int fixPointsSize() const
number of fix points in this partition
Definition: partition.h:161
virtual unsigned int apply2(Partition &pi, const PERM &t) const
applies (right-)refinement to pi which is the image of the original partition this refinement was ini...
Definition: group_refinement.h:80
GroupRefinement(const BSGSCore< PERM, TRANS > &bsgs)
constructor
Definition: group_refinement.h:69
const BSGSCore< PERM, TRANS > & bsgs() const
bsgs which membership for is required
Definition: group_refinement.h:251
concrete -refinements for group membership
Definition: group_refinement.h:44
virtual bool init(Partition &pi)
initializes refinement
Definition: group_refinement.h:136
vector_t::const_iterator fixPointsBegin() const
iterator to the begin of fix points
Definition: partition.h:164
Definition: abstract_bsgs.h:49
unsigned long cellSize(unsigned int c) const
size of the c-th cell
Definition: partition.h:170