33 #ifndef SHALLOWSCHREIERTREETRANSVERSAL_H_ 34 #define SHALLOWSCHREIERTREETRANSVERSAL_H_ 36 #include <permlib/transversal/schreier_tree_transversal.h> 38 #include <boost/scoped_ptr.hpp> 39 #include <boost/dynamic_bitset.hpp> 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);
53 virtual void updateGenerators(
const std::map<PERM*,typename PERM::ptr>& generatorChange);
61 virtual void permute(
const PERM& g,
const PERM& gInv);
67 void addNewCubeLabel(
unsigned long beta,
const PERM &s,
const unsigned long &beta_prime);
81 this->orbit(beta, generators);
90 boost::shared_ptr<PERM> identity(
new PERM(this->m_n));
91 transversal[beta] = identity;
94 typename std::list<unsigned long>::const_iterator it;
97 typename std::list<typename PERM::ptr>::const_iterator genIt = generators.begin();
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);
108 template <
class PERM>
118 std::list<unsigned long> tempOrbit;
121 const unsigned long alpha = *gPath / *orbIt;
124 if (!transversal[alpha]) {
125 transversal[alpha] = gPath;
126 tempOrbit.push_back(alpha);
131 m_cubeLabels.push_back(gPath);
133 boost::shared_ptr<PERM> gPathInv(
new PERM(*gPath));
134 gPathInv->invertInplace();
139 unsigned long beta1 = *gPathInv / beta;
140 if (!transversal[beta1]) {
141 transversal[beta1] = gPathInv;
145 boost::dynamic_bitset<> omega(this->m_n);
146 boost::dynamic_bitset<> todo(this->m_n);
149 BOOST_FOREACH(
const typename PERM::ptr& l, m_cubeLabels) {
150 for (i = 0; i < this->m_n; ++i) {
153 unsigned long alpha = *l / i;
155 if (!transversal[alpha]) {
156 transversal[alpha] = l;
163 m_cubeLabels.push_front(gPathInv);
166 template <
class PERM>
170 template <
class PERM>
173 std::map<PERM*,typename PERM::ptr> labelMap;
174 BOOST_FOREACH(
typename PERM::ptr& p, ret.
m_cubeLabels) {
176 p =
typename PERM::ptr(
new PERM(*p));
177 labelMap.insert(std::make_pair(gen, p));
179 ret.SchreierTreeTransversal<PERM>::updateGenerators(labelMap);
183 template <
class PERM>
186 BOOST_FOREACH(
typename PERM::ptr& p, m_cubeLabels) {
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