36#include <permlib/sorter/base_sorter.h>
37#include <permlib/transversal/orbit.h>
43#include <boost/foreach.hpp>
44#include <boost/shared_ptr.hpp>
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);
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);
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);
192 typename PERM::ptr identity(
new PERM(
m_n));
214template <
class InputIterator>
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;
228 BOOST_FOREACH(
unsigned long& alpha, this->
m_orbit) {
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g....
Definition base_sorter.h:76
abstract base class for orbit computation
Definition orbit.h:44
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
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
Transversal base class corresponding to a base element .
Definition transversal.h:66
virtual bool contains(const unsigned long &val) const
true iff there exists a transversal element mapping to val
Definition transversal.h:203
size_t size() const
size of basic orbit / transversal
Definition transversal.h:95
Transversal(unsigned int n)
constructor
Definition transversal.h:173
virtual void permute(const PERM &g, const PERM &gInv)
updates transversal after group generators have been conjugated by g
Definition transversal.h:221
unsigned int m_n
size of the set the group is working on
Definition transversal.h:151
bool sorted() const
true iff orbit is sorted
Definition transversal.h:109
bool m_sorted
true if orbit is sorted (according to a previous sort(InputIterator, InputIterator) call
Definition transversal.h:160
std::vector< boost::shared_ptr< PERM > > m_transversal
transversal elements
Definition transversal.h:154
virtual PERM * at(unsigned long val) const =0
returns a transversal element such that equals val
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
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
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
virtual ~Transversal()
virtual destructor
Definition transversal.h:74
unsigned int n() const
size of the set the group is working on
Definition transversal.h:98
void sort(InputIterator Bbegin, InputIterator Bend)
sorts orbit according to order given by list of points
Definition transversal.h:215
virtual const unsigned long & element() const
returns one element of the orbit
Definition transversal.h:235
std::list< unsigned long > m_orbit
orbit elements
Definition transversal.h:157
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
std::list< unsignedlong >::const_iterator begin() const
begin iterator of basic orbit
Definition transversal.h:86
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
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< unsignedlong >::const_iterator end() const
end iterator of basic orbit
Definition transversal.h:88
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 ...
action of a PERM on unsigned long element
Definition transversal.h:112
unsigned long operator()(const PERM &p, unsigned long v) const
action
Definition transversal.h:114