permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
group_refinement.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 GROUPREFINEMENT_H_
34#define GROUPREFINEMENT_H_
35
36#include <permlib/predicate/pointwise_stabilizer_predicate.h>
37#include <permlib/search/partition/refinement.h>
38
39namespace permlib {
40namespace partition {
41
43template<class PERM,class TRANS>
44class GroupRefinement : public Refinement<PERM> {
45public:
48
49 virtual unsigned int apply(Partition& pi) const;
50 virtual unsigned int apply2(Partition& pi, const PERM& t) const;
51
52 virtual bool init(Partition& pi);
53
55 const BSGSCore<PERM,TRANS>& bsgs() const;
56private:
57 const BSGSCore<PERM,TRANS>& m_bsgs;
58
59 std::vector<unsigned int> thetaOrbit;
60 std::vector<int> thetaBorder;
61 //WARNING: not thread-safe
63 mutable Partition::vector_t m_myTheta;
64
65 unsigned int apply2(Partition& pi, const PERM* t) const;
66};
67
68template<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)
71{
72}
73
74template<class PERM,class TRANS>
76 return apply2(pi, 0);
77}
78
79template<class PERM,class TRANS>
80unsigned int GroupRefinement<PERM,TRANS>::apply2(Partition& pi, const PERM& t) const {
81 return apply2(pi, &t);
82}
83
84template<class PERM,class TRANS>
85unsigned int GroupRefinement<PERM,TRANS>::apply2(Partition& pi, const PERM* t) const {
86 BOOST_ASSERT( this->initialized() );
87
88 Partition::vector_t& myTheta = m_myTheta;
89
90 Partition::vector_t::iterator thetaIt;
91 Partition::vector_t::iterator thetaBeginIt, thetaEndIt;
92 Partition::vector_t::const_iterator thetaOrbitIt;
93 std::list<int>::const_iterator cellPairIt = Refinement<PERM>::m_cellPairs.begin();
94 unsigned int ret = false;
95 while (cellPairIt != Refinement<PERM>::m_cellPairs.end()) {
96 const int thetaC = *cellPairIt;
97 ++cellPairIt;
98 if (*cellPairIt < 0) {
99 ++cellPairIt;
100 continue;
101 }
102
103 int borderLo = 0;
104 if (thetaC > 0)
105 borderLo = thetaBorder[thetaC-1];
106 thetaBeginIt = myTheta.begin() + borderLo;
107 thetaEndIt = myTheta.begin() + thetaBorder[thetaC];
108
109 if (t) {
110 for (thetaIt = thetaBeginIt, thetaOrbitIt = thetaOrbit.begin() + borderLo;
111 thetaIt != thetaEndIt && thetaOrbitIt != thetaOrbit.begin() + thetaBorder[thetaC];
112 ++thetaIt, ++thetaOrbitIt)
113 {
114 *thetaIt = *t / *thetaOrbitIt;
115 }
116 std::sort(thetaBeginIt, thetaEndIt);
117 }
118
119 for (int c = *cellPairIt; c >= 0; c = *(++cellPairIt)) {
120 if (t) {
121 PERMLIB_DEBUG(std::cout << "apply theta " << thetaC << "," << c << " t = " << *t << " to " << pi << std::endl;)
122 } else {
123 PERMLIB_DEBUG(std::cout << "apply theta " << thetaC << "," << c << " t = 0 to " << pi << std::endl;)
124 }
125 //print_iterable(thetaBeginIt, thetaEndIt, 1, "theta apply");
126 if (pi.intersect(thetaBeginIt, thetaEndIt, c))
127 ++ret;
128 }
129 ++cellPairIt;
130 }
131
132 return ret;
133}
134
135template<class PERM,class TRANS>
137 unsigned int fixSize = pi.fixPointsSize();
138 if (fixSize > 0) {
139 boost::dynamic_bitset<> orbitCharacterstic(m_bsgs.n);
140
141 std::vector<dom_int>::const_iterator Bit;
142 Partition::vector_t::const_iterator fixIt = pi.fixPointsBegin();
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;)
147 ++fixIt;
148 }
149 if (fixIt == fixEndIt)
150 break;
151 ++fixIt;
152 }
153 //PointwiseStabilizerPredicate<PERM> fixStab(m_bsgs.B.begin(), m_bsgs.B.begin() + std::min(fixSize, static_cast<unsigned int>(m_bsgs.B.size())));
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");
157 print_iterable(pi.fixPointsBegin(), pi.fixPointsEnd(), 1, " fix");
158#endif
159 PointwiseStabilizerPredicate<PERM> fixStab(m_bsgs.B.begin(), Bit);
160 std::list<PERM> S_fix;
161 BOOST_FOREACH(const typename PERM::ptr& p, m_bsgs.S) {
162 if (fixStab(p)) {
163 //std::cout << "$ " << *p << " fixes " << std::min(fixSize, static_cast<unsigned long>(m_bsgs.B.size())) << " points" << std::endl;
164 S_fix.push_back(*p);
165 }
166 }
167
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])
173 continue;
174 orbitCharacterstic.flip(alpha);
175 std::vector<unsigned int>::iterator thetaOrbitBeginIt = thetaIt;
176 *thetaIt = alpha;
177 ++thetaIt;
178 ++thetaIndex;
179 std::vector<unsigned int>::iterator thetaOrbitEndIt = thetaIt;
180
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]) {
187 *thetaIt = beta_p;
188 ++thetaIt;
189 ++thetaOrbitEndIt;
190 ++thetaIndex;
191 orbitCharacterstic.flip(beta_p);
192 }
193 }
194 }
195 *thetaBorderIt = thetaIndex;
196 ++thetaBorderIt;
197 }
198
199 thetaIt = thetaOrbit.begin();
200 std::vector<unsigned int>::iterator thetaItEnd;
201 thetaBorderIt = thetaBorder.begin();
202 unsigned int thetaC = 0;
203 int oldBorder = 0;
204 while (thetaBorderIt != thetaBorder.end() && *thetaBorderIt >= 0) {
205 thetaItEnd = thetaOrbit.begin() + *thetaBorderIt;
206 std::sort(thetaIt, thetaItEnd);
207
208 if (*thetaBorderIt - oldBorder != 1 || std::find(pi.fixPointsBegin(), pi.fixPointsEnd(), *thetaIt) == pi.fixPointsEnd()) {
209 bool hasTheta = false;
210 const unsigned int oldCellNumber = pi.cells();
211 for (unsigned int c = 0; c < oldCellNumber; ++c) {
212 if (pi.cellSize(c) == 1)
213 continue;
214
215 //std::cout << " theta pi = " << pi << std::endl;
216 //print_iterable(thetaIt, thetaItEnd, 1, "theta prep");
217 if (pi.intersect(thetaIt, thetaItEnd, c)) {
218 PERMLIB_DEBUG(std::cout << "prepare theta " << thetaC << "," << c << std::endl;)
219 //print_iterable(thetaIt, thetaItEnd, 1, "theta prep");
220 if (!hasTheta) {
221 Refinement<PERM>::m_cellPairs.push_back(thetaC);
222 hasTheta = true;
223 }
225 //std::cout << (thetaIt - thetaOrbit.begin()) << " - " << (thetaItEnd - thetaOrbit.begin()) << std::endl;
226 }
227 //std::cout << "pii = " << pi << std::endl;
228 }
229
230 if (hasTheta)
231 Refinement<PERM>::m_cellPairs.push_back(-1);
232 }
233
234 oldBorder = *thetaBorderIt;
235 thetaIt = thetaItEnd;
236 ++thetaC;
237 ++thetaBorderIt;
238 }
239 //print_iterable(Refinement<PERM>::m_cellPairs.begin(), Refinement<PERM>::m_cellPairs.end(), 0, "cell pairs");
240 if (!Refinement<PERM>::m_cellPairs.empty()) {
241 typename Refinement<PERM>::RefinementPtr ref(new GroupRefinement<PERM,TRANS>(*this));
243 return true;
244 }
245 }
246
247 return false;
248}
249
250template<class PERM,class TRANS>
252 return m_bsgs;
253}
254
255}
256}
257
258#endif // -- GROUPREFINEMENT_H_
predicate matching a permutation if it stabilizes a given list of points pointwise
Definition pointwise_stabilizer_predicate.h:42
concrete -refinements for group membership
Definition group_refinement.h:44
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
const BSGSCore< PERM, TRANS > & bsgs() const
bsgs which membership for is required
Definition group_refinement.h:251
GroupRefinement(const BSGSCore< PERM, TRANS > &bsgs)
constructor
Definition group_refinement.h:69
virtual bool init(Partition &pi)
initializes refinement
Definition group_refinement.h:136
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
partition
Definition partition.h:48
unsigned long cellSize(unsigned int c) const
size of the c-th cell
Definition partition.h:170
unsigned long cells() const
number of cells in this partition
Definition partition.h:157
vector_t::const_iterator fixPointsBegin() const
iterator to the begin of fix points
Definition partition.h:164
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
vector_t::const_iterator fixPointsEnd() const
iterator to the end of fix points
Definition partition.h:167
base class for a -refinement which is used in an R-base and bound to an initial partition
Definition refinement.h:53
core data of a base and strong generating set (BSGS)
Definition bsgs_core.h:42