permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
46namespace permlib {
47
48template <class PERM>
49class Transversal;
50
51template <class PERM>
52std::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
65template <class PERM>
66class Transversal : public Orbit<PERM,unsigned long> {
67public:
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
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);
149protected:
151 unsigned int m_n;
152
154 std::vector<boost::shared_ptr<PERM> > m_transversal;
155
157 std::list<unsigned long> m_orbit;
158
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
172template <class PERM>
174 : m_n(n_), m_transversal(n_), m_sorted(false)
175{ }
176
177template <class PERM>
178void 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
182template <class PERM>
183void 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
187template <class PERM>
188bool 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
202template <class PERM>
203bool Transversal<PERM>::contains(const unsigned long& val) const {
204 return m_transversal[val] != 0;
205}
206
207template <class PERM>
208void Transversal<PERM>::registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p) {
209 m_sorted = false;
210}
211
212
213template <class PERM>
214template <class InputIterator>
215void Transversal<PERM>::sort(InputIterator Bbegin, InputIterator Bend) {
216 this->m_orbit.sort(BaseSorter(m_n, Bbegin, Bend));
217 m_sorted = true;
218}
219
220template <class PERM>
221void 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
234template <class PERM>
235inline const unsigned long& Transversal<PERM>::element() const {
236 return m_orbit.front();
237}
238
239}
240
241#endif // -- TRANSVERSAL_H_
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