permlib  0.2.9
Library for permutation computations
Classes | Public Member Functions | Protected Member Functions | Protected Attributes | Friends | List of all members
permlib::Transversal< PERM > Class Template Referenceabstract

Transversal base class corresponding to a base element $\alpha$. More...

#include <transversal.h>

Inheritance diagram for permlib::Transversal< PERM >:
permlib::Orbit< PERM, unsigned long > permlib::ExplicitTransversal< PERM > permlib::SchreierTreeTransversal< PERM > permlib::ShallowSchreierTreeTransversal< PERM >

Classes

struct  TrivialAction
 action of a PERM on unsigned long element More...
 

Public Member Functions

 Transversal (unsigned int n)
 constructor More...
 
virtual ~Transversal ()
 virtual destructor
 
virtual PERM * at (unsigned long val) const =0
 returns a transversal element $u$ such that $\alpha^u$ equals val
 
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 by defintion
 
virtual bool contains (const unsigned long &val) const
 true iff there exists a transversal element mapping $\alpha$ to val
 
std::list< unsigned long >::const_iterator begin () const
 begin iterator of basic orbit
 
std::list< unsigned long >::const_iterator end () const
 end iterator of basic orbit
 
std::pair< std::list< unsigned long >::const_iterator, std::list< unsigned long >::const_iterator > pairIt () const
 pair of begin, end iterator
 
size_t size () const
 size of basic orbit / transversal
 
unsigned int n () const
 size of the set the group is working on
 
template<class InputIterator >
void sort (InputIterator Bbegin, InputIterator Bend)
 sorts orbit according to order given by list of points More...
 
bool sorted () const
 true iff orbit is sorted
 
virtual void orbit (unsigned long alpha, const std::list< typename PERM::ptr > &generators)
 computes transversal based on orbit of $\alpha$ under generators More...
 
virtual void orbitUpdate (unsigned long alpha, const std::list< typename PERM::ptr > &generators, const typename PERM::ptr &g)
 updates transversal based on orbit of $\alpha$ under generators where g is a new generator More...
 
virtual void permute (const PERM &g, const PERM &gInv)
 updates transversal after group generators have been conjugated by g More...
 
virtual void updateGenerators (const std::map< PERM *, typename PERM::ptr > &generatorChange)
 updates transversal after group generators have been exchanged More...
 
virtual const unsigned long & element () const
 returns one element of the orbit
 

Protected Member Functions

virtual void registerMove (unsigned long from, unsigned long to, const typename PERM::ptr &p)
 stores that 'p' maps 'from' onto 'to'
 
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 More...
 
- Protected Member Functions inherited from permlib::Orbit< PERM, unsigned long >
void orbit (const unsigned long &beta, const std::list< typename PERM::ptr > &generators, Action a, std::list< unsigned long > &orbitList)
 computes orbit of beta under generators More...
 
void orbitUpdate (const unsigned long &beta, const std::list< typename PERM::ptr > &generators, const typename PERM::ptr &g, Action a, std::list< unsigned long > &orbitList)
 updates an existing orbit of beta after one element has been added More...
 

Protected Attributes

unsigned int m_n
 size of the set the group is working on
 
std::vector< boost::shared_ptr< PERM > > m_transversal
 transversal elements
 
std::list< unsigned long > m_orbit
 orbit elements
 
bool m_sorted
 true if orbit is sorted (according to a previous sort(InputIterator, InputIterator) call
 

Friends

std::ostream & operator<< (std::ostream &out, const Transversal< PERM > &p)
 to stream
 

Additional Inherited Members

- Public Types inherited from permlib::Orbit< PERM, unsigned long >
typedef PERM PERMtype
 type of permutation used for this orbit
 

Detailed Description

template<class PERM>
class permlib::Transversal< PERM >

Transversal base class corresponding to a base element $\alpha$.

Constructor & Destructor Documentation

◆ Transversal()

template<class PERM >
permlib::Transversal< PERM >::Transversal ( unsigned int  n)

constructor

Parameters
nsize of the set the group is working on

Member Function Documentation

◆ foundOrbitElement()

template<class PERM >
bool permlib::Transversal< PERM >::foundOrbitElement ( const unsigned long &  alpha,
const unsigned long &  alpha_p,
const typename PERM::ptr &  p 
)
protectedvirtual

callback when the orbit algorithm constructs an element alpha_p from alpha and p

Returns
true iff alpha_p is a new element that has not been seen before

Implements permlib::Orbit< PERM, unsigned long >.

◆ orbit()

template<class PERM >
void permlib::Transversal< PERM >::orbit ( unsigned long  alpha,
const std::list< typename PERM::ptr > &  generators 
)
virtual

computes transversal based on orbit of $\alpha$ under generators

Parameters
alpha$\alpha$
generatorsgroup generators for the orbit

Reimplemented in permlib::ShallowSchreierTreeTransversal< PERM >.

◆ orbitUpdate()

template<class PERM >
void permlib::Transversal< PERM >::orbitUpdate ( unsigned long  alpha,
const std::list< typename PERM::ptr > &  generators,
const typename PERM::ptr &  g 
)
virtual

updates transversal based on orbit of $\alpha$ under generators where g is a new generator

Parameters
alpha$\alpha$
generatorsgroup generators for the orbit
gnew generator that the transversal is updated for

Reimplemented in permlib::ShallowSchreierTreeTransversal< PERM >.

◆ permute()

template<class PERM >
void permlib::Transversal< PERM >::permute ( const PERM &  g,
const PERM &  gInv 
)
virtual

updates transversal after group generators have been conjugated by g

Parameters
gpermutation to conjugate
gInvinverse of g for performance reasons

Reimplemented in permlib::ShallowSchreierTreeTransversal< PERM >, and permlib::ExplicitTransversal< PERM >.

◆ sort()

template<class PERM >
template<class InputIterator >
void permlib::Transversal< PERM >::sort ( InputIterator  Bbegin,
InputIterator  Bend 
)

sorts orbit according to order given by list of points

Parameters
Bbeginbegin iterator of point list (unsigned long) inducing an order
Bendend iterator of point list (unsigned long) inducing an order

◆ updateGenerators()

template<class PERM>
virtual void permlib::Transversal< PERM >::updateGenerators ( const std::map< PERM *, typename PERM::ptr > &  generatorChange)
inlinevirtual

updates transversal after group generators have been exchanged

Parameters
generatorChangemap of old generators to new generators

Reimplemented in permlib::ShallowSchreierTreeTransversal< PERM >, and permlib::SchreierTreeTransversal< PERM >.


The documentation for this class was generated from the following file: