permlib  0.2.9
Library for permutation computations
transversal.h
1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 // 1. Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // 3. The name of the author may not be used to endorse or promote products
17 // derived from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // ---------------------------------------------------------------------------
31 
32 
33 #ifndef TRANSVERSAL_H_
34 #define TRANSVERSAL_H_
35 
36 #include <permlib/sorter/base_sorter.h>
37 #include <permlib/transversal/orbit.h>
38 
39 #include <map>
40 #include <list>
41 #include <vector>
42 
43 #include <boost/foreach.hpp>
44 #include <boost/shared_ptr.hpp>
45 
46 namespace permlib {
47 
48 template <class PERM>
50 
51 template <class PERM>
52 std::ostream &operator<< (std::ostream &out, const Transversal<PERM> &t) {
53  out << "{";
54  BOOST_FOREACH (boost::shared_ptr<PERM> p, t.m_transversal) {
55  if (p)
56  out << *p << ", ";
57  else
58  out << "O, ";
59  }
60  out << "}";
61  return out;
62 }
63 
65 template <class PERM>
66 class Transversal : public Orbit<PERM,unsigned long> {
67 public:
69 
72  Transversal(unsigned int n);
74  virtual ~Transversal() {}
75 
77  virtual PERM* at(unsigned long val) const = 0;
78 
80  virtual bool trivialByDefinition(const PERM& x, unsigned long to) const = 0;
81 
83  virtual bool contains(const unsigned long& val) const;
84 
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());
92  }
93 
95  size_t size() const { return this->m_orbit.size(); }
96 
98  inline unsigned int n() const { return m_n; }
99 
101 
105  template <class InputIterator>
106  void sort(InputIterator Bbegin, InputIterator Bend);
107 
109  inline bool sorted() const { return m_sorted; }
110 
112  struct TrivialAction {
114  unsigned long operator()(const PERM &p, unsigned long v) const {
115  return p / v;
116  }
117  };
118 
120 
124  virtual void orbit(unsigned long alpha, const std::list<typename PERM::ptr> &generators);
126 
131  virtual void orbitUpdate(unsigned long alpha, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g);
132 
134 
138  virtual void permute(const PERM& g, const PERM& gInv);
140 
143  virtual void updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange) {}
144 
145  virtual const unsigned long& element() const;
146 
148  friend std::ostream &operator<< <> (std::ostream &out, const Transversal<PERM> &p);
149 protected:
151  unsigned int m_n;
152 
154  std::vector<boost::shared_ptr<PERM> > m_transversal;
155 
157  std::list<unsigned long> m_orbit;
158 
160  bool m_sorted;
161 
163  virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p);
164 
165  virtual bool foundOrbitElement(const unsigned long& alpha, const unsigned long& alpha_p, const typename PERM::ptr& p);
166 };
167 
168 //
169 // ---- IMPLEMENTATION
170 //
171 
172 template <class PERM>
174  : m_n(n_), m_transversal(n_), m_sorted(false)
175 { }
176 
177 template <class PERM>
178 void Transversal<PERM>::orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators) {
179  Orbit<PERM,unsigned long>::orbit(beta, generators, TrivialAction(), m_orbit);
180 }
181 
182 template <class PERM>
183 void Transversal<PERM>::orbitUpdate(unsigned long beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g) {
184  Orbit<PERM,unsigned long>::orbitUpdate(beta, generators, g, TrivialAction(), m_orbit);
185 }
186 
187 template <class PERM>
188 bool Transversal<PERM>::foundOrbitElement(const unsigned long& alpha, const unsigned long& alpha_p, const typename PERM::ptr& p) {
189  BOOST_ASSERT( alpha_p < m_transversal.size() );
190  if (!m_transversal[alpha_p]) {
191  if (!p) {
192  typename PERM::ptr identity(new PERM(m_n));
193  registerMove(alpha, alpha_p, identity);
194  } else {
195  registerMove(alpha, alpha_p, p);
196  }
197  return true;
198  }
199  return false;
200 }
201 
202 template <class PERM>
203 bool Transversal<PERM>::contains(const unsigned long& val) const {
204  return m_transversal[val] != 0;
205 }
206 
207 template <class PERM>
208 void Transversal<PERM>::registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p) {
209  m_sorted = false;
210 }
211 
212 
213 template <class PERM>
214 template <class InputIterator>
215 void Transversal<PERM>::sort(InputIterator Bbegin, InputIterator Bend) {
216  this->m_orbit.sort(BaseSorter(m_n, Bbegin, Bend));
217  m_sorted = true;
218 }
219 
220 template <class PERM>
221 void Transversal<PERM>::permute(const PERM& g, const PERM& gInv) {
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];
226  }
227  std::copy(temp.begin(), temp.end(), m_transversal.begin());
228  BOOST_FOREACH(unsigned long& alpha, this->m_orbit) {
229  alpha = g / alpha;
230  }
231  m_sorted = false;
232 }
233 
234 template <class PERM>
235 inline const unsigned long& Transversal<PERM>::element() const {
236  return m_orbit.front();
237 }
238 
239 }
240 
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 &#39;p&#39; maps &#39;from&#39; onto &#39;to&#39;
Definition: transversal.h:208