permlib  0.2.9
Library for permutation computations
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 
39 namespace permlib {
40 namespace partition {
41 
43 template<class PERM,class TRANS>
44 class GroupRefinement : public Refinement<PERM> {
45 public:
47  explicit GroupRefinement(const BSGSCore<PERM,TRANS>& bsgs);
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;
56 private:
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 
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)
71 {
72 }
73 
74 template<class PERM,class TRANS>
76  return apply2(pi, 0);
77 }
78 
79 template<class PERM,class TRANS>
80 unsigned int GroupRefinement<PERM,TRANS>::apply2(Partition& pi, const PERM& t) const {
81  return apply2(pi, &t);
82 }
83 
84 template<class PERM,class TRANS>
85 unsigned 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 
135 template<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  }
224  Refinement<PERM>::m_cellPairs.push_back(c);
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 
250 template<class PERM,class TRANS>
252  return m_bsgs;
253 }
254 
255 }
256 }
257 
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