33 #ifndef BASECONSTRUCTION_H 34 #define BASECONSTRUCTION_H 39 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 40 #include <permlib/predicate/identity_predicate.h> 45 template <
class PERM,
class TRANS>
66 template <
class ForwardIterator,
class InputIterator>
67 void setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd,
BSGS<PERM, TRANS> &bsgs, std::vector<std::list<typename PERM::ptr> > &S)
const;
73 static const unsigned long *
empty;
80 template <
class PERM,
class TRANS>
84 template <
class PERM,
class TRANS>
89 template <
class PERM,
class TRANS>
90 template <
class ForwardIterator,
class InputIterator>
93 std::vector<dom_int> &B = bsgs.
B;
94 std::vector<TRANS> &U = bsgs.
U;
96 std::list<typename PERM::ptr> nonIdentityGenerators;
97 std::remove_copy_if(generatorsBegin, generatorsEnd, std::back_inserter(nonIdentityGenerators),
IdentityPredicate<PERM>());
99 B.insert(B.begin(), prescribedBaseBegin, prescribedBaseEnd);
101 dom_int beta = m_n + 1;
103 BOOST_FOREACH(
const typename PERM::ptr &gen, nonIdentityGenerators) {
114 U.push_back(TRANS(m_n));
116 std::list<typename PERM::ptr> S_0;
118 U[0].orbit(B[0], S_0);
125 std::vector<dom_int>::iterator Bit;
126 for (Bit = B.begin(); Bit != B.end(); ++Bit) {
127 std::list<typename PERM::ptr> S_i;
128 std::copy_if(nonIdentityGenerators.begin(), nonIdentityGenerators.end(),
131 U.push_back(TRANS(m_n));
140 template <
class PERM,
class TRANS>
142 std::map<PERM*,typename PERM::ptr> generatorMap;
144 BOOST_FOREACH(std::list<typename PERM::ptr> &S_j, S) {
145 BOOST_FOREACH(
typename PERM::ptr &gen, S_j) {
147 BOOST_FOREACH(
const typename PERM::ptr& genS, ret.
S) {
150 generatorMap.insert(std::make_pair(gen.get(), genS));
155 ret.
S.push_back(gen);
156 generatorMap.insert(std::make_pair(gen.get(), gen));
161 BOOST_FOREACH(TRANS& U_i, ret.
U) {
162 U_i.updateGenerators(generatorMap);
168 #endif // -- BASECONSTRUCTION_H BaseConstruction(dom_int n)
constructor
Definition: base_construction.h:85
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition: bsgs.h:289
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: pointwise_stabilizer_predicate.h:42
void mergeGenerators(std::vector< std::list< typename PERM::ptr > > &S, BSGS< PERM, TRANS > &ret) const
merges all strong generators in S into a single strong generating set ret.S
Definition: base_construction.h:141
dom_int m_n
cardinality of the set the group is acting on
Definition: base_construction.h:55
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
base class for BSGS construction algorithms
Definition: base_construction.h:46
static const unsigned long * empty
auxilliary element marking an empty iterator
Definition: base_construction.h:73
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: identity_predicate.h:42
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
void orbit(unsigned int j, const PERMlist &generators)
re-computes the j-th fundamental orbit with the given orbit generators
Definition: bsgs.h:300
void setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, BSGS< PERM, TRANS > &bsgs, std::vector< std::list< typename PERM::ptr > > &S) const
initializes BSGS object
Definition: base_construction.h:91
PERMlist S
strong generating set
Definition: bsgs_core.h:57
Definition: abstract_bsgs.h:49