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 )
BSGS< typename TRANS::PERMtype, TRANS > PermutationGroup
typedef for the BSGS type associated with this group
Definition: abstract_bsgs.h:56
dom_int n
degree of group
Definition: bsgs_core.h:61
virtual void transversalSizes(std::vector< unsigned long > &sizes) const
fills a list with sizes of transversals along a stabilizer chain
Definition: abstract_bsgs.h:106
implementation of a randomized base transposition algorithm
Definition: random_base_transpose.h:50
base change by conjugation and, if necessary, transpositions
Definition: conjugating_base_change.h:52
dset lexMin(const dset &element, const BSGSIN *stabilizer=NULL)
searches the lexicographically minimal element of an orbit
Definition: orbit_lex_min_search.h:124
This class never imposes a restriction on any set.
Definition: abstract_bsgs_helpers.h:60
void search(BSGS< PERM, TRANSRET > &groupK)
searches for a subgroup and stores it into groupK
Definition: backtrack_search.h:96
virtual OrbitList * orbits() const
computes all orbits
Definition: abstract_bsgs.h:143
This class implements canBeIgnored() but has a trivial set()
Definition: abstract_bsgs_helpers.h:83
A high level interface implementing a group represented by a BSGS data structure. ...
Definition: abstract_bsgs.h:53
void conjugate(const PERM &g)
conjugate group with a permutation
Definition: bsgs.h:323
This class implements both canBeIgnored() and set()
Definition: abstract_bsgs_helpers.h:102
subgroup search for a set stabilizer based on classical backtracking
Definition: set_stabilizer_search.h:44
const boost::shared_ptr< PermutationGroup > bsgs() const
BSGS data structure for this permutation group.
Definition: abstract_bsgs.h:74
virtual bool isLexMinSet(const std::vector< dom_int > &setIndices, const std::vector< dom_int > &rankIndices) const
checks whether a set is lexicographically minimal with respect to a given ordering of indices ...
Definition: abstract_bsgs.h:180
virtual AbstractPermutationGroup * setStabilizer(const std::vector< dom_int > &s) const
computes the stabilizer of a set
Definition: abstract_bsgs.h:115
std::list< std::set< dom_int > > OrbitList
typedef for a list of orbits, each of which is a set
Definition: abstract_permutation_group.h:74
virtual AbstractGroupType type() const
implementation type of this abstract class
Definition: abstract_bsgs.h:68
AbstractBSGS(const boost::shared_ptr< PermutationGroup > &bsgs_, bool computeSupport=true)
constructor
Definition: abstract_bsgs.h:90
algorithm to find the lexicographically minimal set in an orbit
Definition: orbit_lex_min_search.h:52
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
helpers::BaseSupportRestriction * supportRestriction(const std::vector< dom_int > &s) const
returns a strategy to decide whether the action of this group is trivial on /s/
Definition: abstract_bsgs.h:237
stores an orbit in a sorted list
Definition: orbit_list.h:42
A high level interface for a permutation group.
Definition: abstract_permutation_group.h:54
void construct(InputIterator begin, InputIterator end)
initializes search
Definition: set_stabilizer_search.h:71
std::list< typename TRANS::PERMtype::ptr > generators() const
strong generating set of this permutation group
Definition: abstract_bsgs.h:232
Definition: abstract_bsgs.h:49