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_