33 #ifndef BASETRANSPOSE_H_ 34 #define BASETRANSPOSE_H_ 36 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 37 #include <permlib/generator/generator.h> 39 #include <boost/scoped_ptr.hpp> 40 #include <boost/iterator/indirect_iterator.hpp> 48 template<
class PERM,
class TRANS>
68 typedef std::list<typename PERM::ptr> PERMlist;
84 template<
class PERM,
class TRANS>
86 : m_statScheierGeneratorsConsidered(0), m_statNewGenerators(0)
89 template<
class PERM,
class TRANS>
91 std::vector<dom_int> &B = bsgs.
B;
92 std::vector<TRANS> &U = bsgs.
U;
101 std::swap(B[i], B[i+1]);
106 unsigned int targetTransversalSize = U[i+1].size() * U[i].size();
110 U_i.orbit(B[i], S_i);
111 targetTransversalSize /= U_i.size();
113 m_statScheierGeneratorsConsidered = 0;
114 m_statNewGenerators = 0;
115 TRANS U_i1(U[i+1].n());
116 U_i1.orbit(B[i+1], S_i1);
117 boost::scoped_ptr<Generator<PERM> > generator(setupGenerator(bsgs, i, S_i, U_i));
118 BOOST_ASSERT(generator != 0);
120 while (U_i1.size() < targetTransversalSize) {
121 bool newGeneratorFound =
false;
122 while (generator->hasNext()) {
123 PERM g = generator->next();
124 ++m_statScheierGeneratorsConsidered;
125 boost::indirect_iterator<typename PERMlist::iterator> sBegin(S_i1.begin()), sEnd(S_i1.end());
126 if (!U_i1.contains(g / B[i+1]) && std::find(sBegin, sEnd, g) == sEnd) {
128 boost::shared_ptr<PERM> gen(
new PERM(g));
129 S_i1.push_front(gen);
130 ++m_statNewGenerators;
131 U_i1.orbitUpdate(B[i+1], S_i1, gen);
132 newGeneratorFound =
true;
136 if (!newGeneratorFound)
140 BOOST_ASSERT(U_i1.size() >= targetTransversalSize);
142 bsgs.
S.insert(bsgs.
S.end(), S_i1.begin(), boost::next(S_i1.begin(), m_statNewGenerators));
149 #endif // -- BASETRANSPOSE_H_ virtual Generator< PERM > * setupGenerator(BSGS< PERM, TRANS > &bsgs, unsigned int i, const PERMlist &S_i, const TRANS &U_i) const =0
initializes the specific Schreier Generator that is used for the BaseTranpose implementation ...
BaseTranspose()
constructor
Definition: base_transpose.h:85
unsigned int m_statScheierGeneratorsConsidered
number of Schreier generators that have been considered during the last transpose call ...
Definition: base_transpose.h:64
void transpose(BSGS< PERM, TRANS > &bsgs, unsigned int i) const
performs a base transposition on bsgs between bsgs.B[i] and bsgs.B[i+1]
Definition: base_transpose.h:90
interface for group element generators
Definition: generator.h:40
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: pointwise_stabilizer_predicate.h:42
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
unsigned int m_statNewGenerators
number of new strong generators that have been added during the last transpose call ...
Definition: base_transpose.h:66
abstract base class for base transposition
Definition: base_transpose.h:49
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
virtual ~BaseTranspose()
virtual destructor
Definition: base_transpose.h:54
PERMlist S
strong generating set
Definition: bsgs_core.h:57
Definition: abstract_bsgs.h:49