33 #ifndef TRANSVERSAL_H_ 34 #define TRANSVERSAL_H_ 36 #include <permlib/sorter/base_sorter.h> 37 #include <permlib/transversal/orbit.h> 43 #include <boost/foreach.hpp> 44 #include <boost/shared_ptr.hpp> 52 std::ostream &operator<< (std::ostream &out, const Transversal<PERM> &t) {
54 BOOST_FOREACH (boost::shared_ptr<PERM> p, t.m_transversal) {
77 virtual PERM*
at(
unsigned long val)
const = 0;
83 virtual bool contains(
const unsigned long& val)
const;
86 std::list<unsigned long>::const_iterator
begin()
const {
return this->
m_orbit.begin(); };
88 std::list<unsigned long>::const_iterator
end()
const {
return this->
m_orbit.end(); };
90 std::pair<std::list<unsigned long>::const_iterator,std::list<unsigned long>::const_iterator>
pairIt()
const {
91 return std::make_pair(
begin(),
end());
98 inline unsigned int n()
const {
return m_n; }
105 template <
class InputIterator>
106 void sort(InputIterator Bbegin, InputIterator Bend);
114 unsigned long operator()(
const PERM &p,
unsigned long v)
const {
124 virtual void orbit(
unsigned long alpha,
const std::list<typename PERM::ptr> &generators);
131 virtual void orbitUpdate(
unsigned long alpha,
const std::list<typename PERM::ptr> &generators,
const typename PERM::ptr &g);
138 virtual void permute(
const PERM& g,
const PERM& gInv);
143 virtual void updateGenerators(
const std::map<PERM*,typename PERM::ptr>& generatorChange) {}
145 virtual const unsigned long&
element()
const;
148 friend std::ostream &operator<< <> (std::ostream &out,
const Transversal<PERM> &p);
163 virtual void registerMove(
unsigned long from,
unsigned long to,
const typename PERM::ptr &p);
165 virtual bool foundOrbitElement(
const unsigned long& alpha,
const unsigned long& alpha_p,
const typename PERM::ptr& p);
172 template <
class PERM>
174 : m_n(n_), m_transversal(n_), m_sorted(false)
177 template <
class PERM>
182 template <
class PERM>
187 template <
class PERM>
189 BOOST_ASSERT( alpha_p < m_transversal.size() );
190 if (!m_transversal[alpha_p]) {
192 typename PERM::ptr identity(
new PERM(m_n));
193 registerMove(alpha, alpha_p, identity);
195 registerMove(alpha, alpha_p, p);
202 template <
class PERM>
204 return m_transversal[val] != 0;
207 template <
class PERM>
213 template <
class PERM>
214 template <
class InputIterator>
216 this->m_orbit.sort(
BaseSorter(m_n, Bbegin, Bend));
220 template <
class PERM>
222 std::vector<boost::shared_ptr<PERM> > temp(m_n);
223 for (
unsigned long i=0; i<m_n; ++i) {
224 const unsigned long j = g / i;
225 temp[j] = m_transversal[i];
227 std::copy(temp.begin(), temp.end(), m_transversal.begin());
228 BOOST_FOREACH(
unsigned long& alpha, this->m_orbit) {
234 template <
class PERM>
236 return m_orbit.front();
241 #endif // -- TRANSVERSAL_H_ unsigned int m_n
size of the set the group is working on
Definition: transversal.h:151
virtual bool foundOrbitElement(const unsigned long &alpha, const unsigned long &alpha_p, const typename PERM::ptr &p)
callback when the orbit algorithm constructs an element alpha_p from alpha and p
Definition: transversal.h:188
virtual bool contains(const unsigned long &val) const
true iff there exists a transversal element mapping to val
Definition: transversal.h:203
std::list< unsigned long >::const_iterator end() const
end iterator of basic orbit
Definition: transversal.h:88
action of a PERM on unsigned long element
Definition: transversal.h:112
virtual PERM * at(unsigned long val) const =0
returns a transversal element such that equals val
void orbit(const PDOMAIN &beta, const std::list< typename PERM::ptr > &generators, Action a, std::list< PDOMAIN > &orbitList)
computes orbit of beta under generators
Definition: orbit.h:89
Transversal base class corresponding to a base element .
Definition: transversal.h:49
virtual const unsigned long & element() const
returns one element of the orbit
Definition: transversal.h:235
virtual void orbitUpdate(unsigned long alpha, const std::list< typename PERM::ptr > &generators, const typename PERM::ptr &g)
updates transversal based on orbit of under generators where g is a new generator ...
Definition: transversal.h:183
abstract base class for orbit computation
Definition: orbit.h:44
bool m_sorted
true if orbit is sorted (according to a previous sort(InputIterator, InputIterator) call ...
Definition: transversal.h:160
void sort(InputIterator Bbegin, InputIterator Bend)
sorts orbit according to order given by list of points
Definition: transversal.h:215
Transversal(unsigned int n)
constructor
Definition: transversal.h:173
virtual void orbit(unsigned long alpha, const std::list< typename PERM::ptr > &generators)
computes transversal based on orbit of under generators
Definition: transversal.h:178
std::list< unsigned long >::const_iterator begin() const
begin iterator of basic orbit
Definition: transversal.h:86
virtual ~Transversal()
virtual destructor
Definition: transversal.h:74
std::pair< std::list< unsigned long >::const_iterator, std::list< unsigned long >::const_iterator > pairIt() const
pair of begin, end iterator
Definition: transversal.h:90
bool sorted() const
true iff orbit is sorted
Definition: transversal.h:109
unsigned int n() const
size of the set the group is working on
Definition: transversal.h:98
virtual void permute(const PERM &g, const PERM &gInv)
updates transversal after group generators have been conjugated by g
Definition: transversal.h:221
size_t size() const
size of basic orbit / transversal
Definition: transversal.h:95
virtual bool trivialByDefinition(const PERM &x, unsigned long to) const =0
true if Schreier generator constructed from x and the transversal element related to "to" is trivial ...
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g. a base)
Definition: base_sorter.h:76
unsigned long operator()(const PERM &p, unsigned long v) const
action
Definition: transversal.h:114
void orbitUpdate(const PDOMAIN &beta, const std::list< typename PERM::ptr > &generators, const typename PERM::ptr &g, Action a, std::list< PDOMAIN > &orbitList)
updates an existing orbit of beta after one element has been added
Definition: orbit.h:112
virtual void updateGenerators(const std::map< PERM *, typename PERM::ptr > &generatorChange)
updates transversal after group generators have been exchanged
Definition: transversal.h:143
std::list< unsigned long > m_orbit
orbit elements
Definition: transversal.h:157
std::vector< boost::shared_ptr< PERM > > m_transversal
transversal elements
Definition: transversal.h:154
Definition: abstract_bsgs.h:49
virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p)
stores that 'p' maps 'from' onto 'to'
Definition: transversal.h:208