32 #include <boost/shared_ptr.hpp>
33 #include <boost/scoped_ptr.hpp>
34 #include <boost/iterator/counting_iterator.hpp>
38 #include <permlib/abstract_permutation_group.h>
39 #include <permlib/abstract_bsgs_helpers.h>
41 #include <permlib/change/random_base_transpose.h>
42 #include <permlib/change/conjugating_base_change.h>
43 #include <permlib/search/classic/set_stabilizer_search.h>
44 #include <permlib/search/orbit_lex_min_search.h>
46 #ifndef ABSTRACT_BSGS_H_
47 #define ABSTRACT_BSGS_H_
52 template<
typename TRANS>
62 AbstractBSGS(
const boost::shared_ptr<PermutationGroup>& bsgs_,
bool computeSupport =
true);
67 virtual bool isLexMinSet(
const std::vector<dom_int>& setIndices,
const std::vector<dom_int>& rankIndices)
const;
68 virtual AbstractGroupType
type()
const {
return AGT_BSGS; }
71 std::list<typename TRANS::PERMtype::ptr>
generators()
const;
74 const boost::shared_ptr<PermutationGroup>
bsgs()
const {
return m_bsgs; }
78 template<
typename Iterator>
84 const boost::shared_ptr<PermutationGroup> m_bsgs;
85 boost::shared_ptr<std::set<dom_int> > m_support;
89 template<
typename TRANS>
93 if ( ! computeSupport )
96 m_support.reset(
new std::set<dom_int>() );
97 BOOST_FOREACH(
const typename TRANS::PERMtype::ptr& p, m_bsgs->S) {
98 for (dom_int i = 0; i < m_bsgs->n; ++i) {
100 m_support->insert(i);
105 template <
class TRANS>
108 sizes.reserve(m_bsgs->U.size());
109 BOOST_FOREACH(
const TRANS &Ui, m_bsgs->U) {
110 sizes.push_back(Ui.size());
114 template <
class TRANS>
119 boost::scoped_ptr<helpers::BaseSupportRestriction> supRestriction( supportRestriction(s) );
120 if ( supRestriction->canBeIgnored() )
122 const std::vector<dom_int>* setToStabilize = supRestriction->set();
123 BOOST_ASSERT( setToStabilize );
125 typedef typename TRANS::PERMtype PERM;
130 baseChange.change(copy, setToStabilize->begin(), setToStabilize->end());
134 backtrackSearch.
construct(setToStabilize->begin(), setToStabilize->end());
138 backtrackSearch.
search(*stabilizer);
142 template <
class TRANS>
144 return this->orbits(boost::counting_iterator<dom_int>(0), boost::counting_iterator<dom_int>(m_bsgs->n));
147 template <
class TRANS>
149 return this->orbits(s.begin(), s.end());
152 template <
class TRANS>
153 template<
typename Iterator>
157 for (Iterator it = begin; it != end; ++it) {
158 const dom_int& alpha = *it;
159 bool knownElement =
false;
160 BOOST_FOREACH(
const std::set<dom_int>& orb, *retList) {
161 if (orb.find(alpha) != orb.end()) {
170 typedef typename TRANS::PERMtype PERM;
171 OrbitSet<PERM,dom_int> orbit;
172 orbit.orbit(alpha, m_bsgs->S,
typename Transversal<PERM>::TrivialAction());
173 retList->push_back(std::set<dom_int>(orbit.begin(), orbit.end()));
179 template <
class TRANS>
181 if (setIndices.empty())
184 boost::scoped_ptr<helpers::BaseSupportRestriction> supRestriction( supportRestriction(setIndices) );
185 if ( supRestriction->canBeIgnored() )
187 const std::vector<dom_int>* setToLexMin = supRestriction->set();
188 BOOST_ASSERT( setToLexMin );
190 typedef typename TRANS::PERMtype PERM;
191 const unsigned int n = m_bsgs->n;
194 typename PERM::perm conjugatingPerm(n);
199 for (std::vector<dom_int>::const_iterator it = rankIndices.begin(); it != rankIndices.end(); ++it)
201 conjugatingPerm[*it] = i;
212 conjugatingPerm[v] = i;
216 PERM c(conjugatingPerm);
220 dset rankedTestSet(n);
221 for (std::vector<dom_int>::const_iterator it = setToLexMin->begin(); it != setToLexMin->end(); ++it)
223 rankedTestSet[c / *it] = 1;
227 const bool t = ( orbLexMin.
lexMin(rankedTestSet) == rankedTestSet );
231 template <
class TRANS>
236 template <
class TRANS>
238 BOOST_ASSERT( m_bsgs );
243 if (m_bsgs->B.size() <= 10 )