38 #include <boost/foreach.hpp> 43 template<
class PERM,
class PDOMAIN>
49 virtual bool contains(
const PDOMAIN& val)
const = 0;
52 virtual const PDOMAIN&
element()
const = 0;
64 template<
class Action>
65 void orbit(
const PDOMAIN& beta,
const std::list<typename PERM::ptr> &generators, Action a, std::list<PDOMAIN>& orbitList);
77 template<
class Action>
78 void orbitUpdate(
const PDOMAIN& beta,
const std::list<typename PERM::ptr> &generators,
const typename PERM::ptr &g, Action a, std::list<PDOMAIN>& orbitList);
84 virtual bool foundOrbitElement(
const PDOMAIN& alpha,
const PDOMAIN& alpha_p,
const typename PERM::ptr& p) = 0;
87 template <
class PERM,
class PDOMAIN>
88 template<
class Action>
89 inline void Orbit<PERM,PDOMAIN>::orbit(
const PDOMAIN& beta,
const std::list<typename PERM::ptr> &generators, Action a, std::list<PDOMAIN>& orbitList) {
90 if (orbitList.empty()) {
91 orbitList.push_back(beta);
92 foundOrbitElement(beta, beta,
typename PERM::ptr());
94 BOOST_ASSERT( orbitList.size() >= 1 );
96 PERMLIB_DEBUG(std::cout <<
"orbit of " << beta << std::endl;)
97 typename std::list<PDOMAIN>::const_iterator it;
98 for (it = orbitList.begin(); it != orbitList.end(); ++it) {
99 const PDOMAIN &alpha = *it;
100 BOOST_FOREACH(
const typename PERM::ptr& p, generators) {
102 PDOMAIN alpha_p = a(*p, alpha);
103 if (alpha_p != alpha && foundOrbitElement(alpha, alpha_p, p))
104 orbitList.push_back(alpha_p);
110 template <
class PERM,
class PDOMAIN>
111 template<
class Action>
112 inline void Orbit<PERM,PDOMAIN>::orbitUpdate(
const PDOMAIN& beta,
const std::list<typename PERM::ptr> &generators,
const typename PERM::ptr &g, Action a, std::list<PDOMAIN>& orbitList) {
113 if (orbitList.empty()) {
114 orbitList.push_back(beta);
115 foundOrbitElement(beta, beta,
typename PERM::ptr());
117 BOOST_ASSERT( orbitList.size() >= 1 );
119 PERMLIB_DEBUG(std::cout <<
"orbiUpdate of " << beta <<
" and " << *g << std::endl;)
120 const unsigned int oldSize = orbitList.size();
122 typename std::list<PDOMAIN>::const_iterator it;
123 for (it = orbitList.begin(); it != orbitList.end(); ++it) {
124 const PDOMAIN &alpha = *it;
125 PDOMAIN alpha_g = a(*g, alpha);
126 if (alpha_g != alpha && foundOrbitElement(alpha, alpha_g, g))
127 orbitList.push_back(alpha_g);
130 if (oldSize == orbitList.size())
133 orbit(beta, generators, a, orbitList);
138 #endif // -- ORBIT_H_ virtual const PDOMAIN & element() const =0
returns one element of the orbit
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
abstract base class for orbit computation
Definition: orbit.h:44
PERM PERMtype
type of permutation used for this orbit
Definition: orbit.h:55
virtual bool foundOrbitElement(const PDOMAIN &alpha, const PDOMAIN &alpha_p, const typename PERM::ptr &p)=0
callback when the orbit algorithm constructs an element alpha_p from alpha and p
virtual bool contains(const PDOMAIN &val) const =0
true iff there exists a transversal element mapping to val
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
Definition: abstract_bsgs.h:49