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_
52template<
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;
89template<
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);
105template <
class TRANS>
108 sizes.reserve(m_bsgs->U.size());
109 BOOST_FOREACH(
const TRANS &Ui, m_bsgs->U) {
110 sizes.push_back(Ui.size());
114template <
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);
142template <
class TRANS>
144 return this->orbits(boost::counting_iterator<dom_int>(0), boost::counting_iterator<dom_int>(m_bsgs->n));
147template <
class TRANS>
149 return this->orbits(s.begin(), s.end());
152template <
class TRANS>
153template<
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()));
179template <
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 );
231template <
class TRANS>
236template <
class TRANS>
238 BOOST_ASSERT( m_bsgs );
243 if (m_bsgs->B.size() <= 10 )
A high level interface implementing a group represented by a BSGS data structure.
Definition abstract_bsgs.h:53
std::list< typename TRANS::PERMtype::ptr > generators() const
strong generating set of this permutation group
Definition abstract_bsgs.h:232
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 AbstractGroupType type() const
implementation type of this abstract class
Definition abstract_bsgs.h:68
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
AbstractBSGS(const boost::shared_ptr< PermutationGroup > &bsgs_, bool computeSupport=true)
constructor
Definition abstract_bsgs.h:90
virtual OrbitList * orbits() const
computes all orbits
Definition abstract_bsgs.h:143
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
BSGS< typename TRANS::PERMtype, TRANS > PermutationGroup
typedef for the BSGS type associated with this group
Definition abstract_bsgs.h:56
virtual AbstractPermutationGroup * setStabilizer(const std::vector< dom_int > &s) const
computes the stabilizer of a set
Definition abstract_bsgs.h:115
A high level interface for a permutation group.
Definition abstract_permutation_group.h:54
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
base change by conjugation and, if necessary, transpositions
Definition conjugating_base_change.h:52
algorithm to find the lexicographically minimal set in an orbit
Definition orbit_lex_min_search.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
stores an orbit in a sorted list
Definition orbit_list.h:42
implementation of a randomized base transposition algorithm
Definition random_base_transpose.h:50
void search(BSGS< PERM, TRANSRET > &groupK)
searches for a subgroup and stores it into groupK
Definition backtrack_search.h:96
subgroup search for a set stabilizer based on classical backtracking
Definition set_stabilizer_search.h:44
void construct(InputIterator begin, InputIterator end)
initializes search
Definition set_stabilizer_search.h:71
This class never imposes a restriction on any set.
Definition abstract_bsgs_helpers.h:60
This class implements both canBeIgnored() and set()
Definition abstract_bsgs_helpers.h:102
This class implements canBeIgnored() but has a trivial set()
Definition abstract_bsgs_helpers.h:83
dom_int n
degree of group
Definition bsgs_core.h:61
Represents a base and strong generating set (BSGS)
Definition redundant_base_point_insertion_strategy.h:39
void conjugate(const PERM &g)
conjugate group with a permutation
Definition bsgs.h:324