permlib  0.2.9
Library for permutation computations
shallow_schreier_tree_transversal.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 SHALLOWSCHREIERTREETRANSVERSAL_H_
34 #define SHALLOWSCHREIERTREETRANSVERSAL_H_
35 
36 #include <permlib/transversal/schreier_tree_transversal.h>
37 
38 #include <boost/scoped_ptr.hpp>
39 #include <boost/dynamic_bitset.hpp>
40 
41 namespace permlib {
42 
44 template <class PERM>
46 public:
48  ShallowSchreierTreeTransversal(unsigned int n);
49 
50  virtual void orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators);
51  virtual void orbitUpdate(unsigned long alpha, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g);
52 
53  virtual void updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange);
55 
59  ShallowSchreierTreeTransversal<PERM> clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const;
60 
61  virtual void permute(const PERM& g, const PERM& gInv);
62 protected:
64  std::list<typename PERM::ptr> m_cubeLabels;
65 
67  void addNewCubeLabel(unsigned long beta, const PERM &s, const unsigned long &beta_prime);
68 };
69 
70 //
71 // ---- IMPLEMENTATION
72 //
73 
74 template <class PERM>
76  : SchreierTreeTransversal<PERM>(n_)
77 { }
78 
79 template <class PERM>
80 void ShallowSchreierTreeTransversal<PERM>::orbitUpdate(unsigned long beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g) {
81  this->orbit(beta, generators);
82 }
83 
84 template <class PERM>
85 void ShallowSchreierTreeTransversal<PERM>::orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators) {
86  std::vector<boost::shared_ptr<PERM> > &transversal = Transversal<PERM>::m_transversal;
87 
88  if (Transversal<PERM>::size() == 0) {
89  Transversal<PERM>::m_orbit.push_back(beta);
90  boost::shared_ptr<PERM> identity(new PERM(this->m_n));
91  transversal[beta] = identity;
92  }
93 
94  typename std::list<unsigned long>::const_iterator it;
95 
96  PERM g(this->m_n);
97  typename std::list<typename PERM::ptr>::const_iterator genIt = generators.begin();
98  for (it = Transversal<PERM>::m_orbit.begin(); it != Transversal<PERM>::m_orbit.end(); ++it) {
99  for (genIt = generators.begin(); genIt != generators.end(); ++genIt) {
100  const unsigned long &beta_prime = *it;
101  if (!transversal[**genIt / beta_prime]) {
102  addNewCubeLabel(beta, **genIt, beta_prime);
103  }
104  }
105  }
106 }
107 
108 template <class PERM>
109 void ShallowSchreierTreeTransversal<PERM>::addNewCubeLabel(unsigned long beta, const PERM &s, const unsigned long &beta_prime) {
110  std::vector<boost::shared_ptr<PERM> > &transversal = Transversal<PERM>::m_transversal;
111  boost::shared_ptr<PERM> gPath(SchreierTreeTransversal<PERM>::at(beta_prime));
112  *gPath *= s;
113  // will be new generator, so better flush it
114  gPath->flush();
115 
116  // compute orbit * gPath
117  //
118  std::list<unsigned long> tempOrbit;
119  typename std::list<unsigned long>::const_iterator orbIt = Transversal<PERM>::m_orbit.begin();
120  for (; orbIt != Transversal<PERM>::m_orbit.end(); ++orbIt) {
121  const unsigned long alpha = *gPath / *orbIt;
122  //PERMLIB_DEBUG
123  //std::cout << "g_i " << alpha << std::endl;
124  if (!transversal[alpha]) {
125  transversal[alpha] = gPath;
126  tempOrbit.push_back(alpha);
127  }
128  }
130 
131  m_cubeLabels.push_back(gPath);
132 
133  boost::shared_ptr<PERM> gPathInv(new PERM(*gPath));
134  gPathInv->invertInplace();
135 
136  // compute inv(gPath) * ... other generators
137  //
138 
139  unsigned long beta1 = *gPathInv / beta;
140  if (!transversal[beta1]) {
141  transversal[beta1] = gPathInv;
142  Transversal<PERM>::m_orbit.push_back(beta1);
143  }
144 
145  boost::dynamic_bitset<> omega(this->m_n);
146  boost::dynamic_bitset<> todo(this->m_n);
147  unsigned long i;
148  omega[beta1] = 1;
149  BOOST_FOREACH(const typename PERM::ptr& l, m_cubeLabels) {
150  for (i = 0; i < this->m_n; ++i) {
151  if (!omega[i])
152  continue;
153  unsigned long alpha = *l / i;
154  todo[alpha] = 1;
155  if (!transversal[alpha]) {
156  transversal[alpha] = l;
157  Transversal<PERM>::m_orbit.push_back(alpha);
158  }
159  }
160  omega |= todo;
161  }
162 
163  m_cubeLabels.push_front(gPathInv);
164 }
165 
166 template <class PERM>
167 void ShallowSchreierTreeTransversal<PERM>::updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange) {
168 }
169 
170 template <class PERM>
171 ShallowSchreierTreeTransversal<PERM> ShallowSchreierTreeTransversal<PERM>::clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const {
173  std::map<PERM*,typename PERM::ptr> labelMap;
174  BOOST_FOREACH(typename PERM::ptr& p, ret.m_cubeLabels) {
175  PERM* gen = p.get();
176  p = typename PERM::ptr(new PERM(*p));
177  labelMap.insert(std::make_pair(gen, p));
178  }
179  ret.SchreierTreeTransversal<PERM>::updateGenerators(labelMap);
180  return ret;
181 }
182 
183 template <class PERM>
184 void ShallowSchreierTreeTransversal<PERM>::permute(const PERM& g, const PERM& gInv) {
186  BOOST_FOREACH(typename PERM::ptr& p, m_cubeLabels) {
187  *p ^= gInv;
188  *p *= g;
189  p->flush();
190  }
191 }
192 
193 }
194 
195 #endif // -- SHALLOWSCHREIERTREETRANSVERSAL_H_
ShallowSchreierTreeTransversal< PERM > clone(const std::map< PERM *, typename PERM::ptr > &generatorChange) const
returns a clone of this transversal
Definition: shallow_schreier_tree_transversal.h:171
std::list< unsigned long >::const_iterator end() const
end iterator of basic orbit
Definition: transversal.h:88
virtual void orbitUpdate(unsigned long alpha, const std::list< typename PERM::ptr > &generators, const typename PERM::ptr &g)
updates transversal based on orbit of under generators where g is a new generator ...
Definition: shallow_schreier_tree_transversal.h:80
Transversal base class corresponding to a base element .
Definition: transversal.h:49
std::list< typename PERM::ptr > m_cubeLabels
ordered list of group elements that are used as cube labels
Definition: shallow_schreier_tree_transversal.h:64
virtual void permute(const PERM &g, const PERM &gInv)
updates transversal after group generators have been conjugated by g
Definition: shallow_schreier_tree_transversal.h:184
Transversal class that stores elements in a shallow Schreier tree.
Definition: shallow_schreier_tree_transversal.h:45
ShallowSchreierTreeTransversal(unsigned int n)
constructor
Definition: shallow_schreier_tree_transversal.h:75
virtual void orbit(unsigned long beta, const std::list< typename PERM::ptr > &generators)
computes transversal based on orbit of under generators
Definition: shallow_schreier_tree_transversal.h:85
std::list< unsigned long >::const_iterator begin() const
begin iterator of basic orbit
Definition: transversal.h:86
Transversal class that stores transversal elements in a Schreier tree.
Definition: schreier_tree_transversal.h:44
virtual void updateGenerators(const std::map< PERM *, typename PERM::ptr > &generatorChange)
updates transversal after group generators have been exchanged
Definition: shallow_schreier_tree_transversal.h:167
void addNewCubeLabel(unsigned long beta, const PERM &s, const unsigned long &beta_prime)
adds a new cube label where s maps beta_prime to a point that has no transversal element yet ...
Definition: shallow_schreier_tree_transversal.h:109
unsigned int n() const
size of the set the group is working on
Definition: transversal.h:98
virtual void permute(const PERM &g, const PERM &gInv)
updates transversal after group generators have been conjugated by g
Definition: transversal.h:221
Definition: abstract_bsgs.h:49