permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
shallow_schreier_tree_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 SHALLOWSCHREIERTREETRANSVERSAL_H_
34#define SHALLOWSCHREIERTREETRANSVERSAL_H_
35
36#include <permlib/transversal/schreier_tree_transversal.h>
37
38#include <boost/scoped_ptr.hpp>
39#include <boost/dynamic_bitset.hpp>
40
41namespace permlib {
42
44template <class PERM>
46public:
49
50 virtual void orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators);
51 virtual void orbitUpdate(unsigned long alpha, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g);
52
53 virtual void updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange);
55
59 ShallowSchreierTreeTransversal<PERM> clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const;
60
61 virtual void permute(const PERM& g, const PERM& gInv);
62protected:
64 std::list<typename PERM::ptr> m_cubeLabels;
65
67 void addNewCubeLabel(unsigned long beta, const PERM &s, const unsigned long &beta_prime);
68};
69
70//
71// ---- IMPLEMENTATION
72//
73
74template <class PERM>
76 : SchreierTreeTransversal<PERM>(n_)
77{ }
78
79template <class PERM>
80void ShallowSchreierTreeTransversal<PERM>::orbitUpdate(unsigned long beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g) {
81 this->orbit(beta, generators);
82}
83
84template <class PERM>
85void ShallowSchreierTreeTransversal<PERM>::orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators) {
86 std::vector<boost::shared_ptr<PERM> > &transversal = Transversal<PERM>::m_transversal;
87
88 if (Transversal<PERM>::size() == 0) {
89 Transversal<PERM>::m_orbit.push_back(beta);
90 boost::shared_ptr<PERM> identity(new PERM(this->m_n));
91 transversal[beta] = identity;
92 }
93
94 typename std::list<unsigned long>::const_iterator it;
95
96 PERM g(this->m_n);
97 typename std::list<typename PERM::ptr>::const_iterator genIt = generators.begin();
98 for (it = Transversal<PERM>::m_orbit.begin(); it != Transversal<PERM>::m_orbit.end(); ++it) {
99 for (genIt = generators.begin(); genIt != generators.end(); ++genIt) {
100 const unsigned long &beta_prime = *it;
101 if (!transversal[**genIt / beta_prime]) {
102 addNewCubeLabel(beta, **genIt, beta_prime);
103 }
104 }
105 }
106}
107
108template <class PERM>
109void ShallowSchreierTreeTransversal<PERM>::addNewCubeLabel(unsigned long beta, const PERM &s, const unsigned long &beta_prime) {
110 std::vector<boost::shared_ptr<PERM> > &transversal = Transversal<PERM>::m_transversal;
111 boost::shared_ptr<PERM> gPath(SchreierTreeTransversal<PERM>::at(beta_prime));
112 *gPath *= s;
113 // will be new generator, so better flush it
114 gPath->flush();
115
116 // compute orbit * gPath
117 //
118 std::list<unsigned long> tempOrbit;
119 typename std::list<unsigned long>::const_iterator orbIt = Transversal<PERM>::m_orbit.begin();
120 for (; orbIt != Transversal<PERM>::m_orbit.end(); ++orbIt) {
121 const unsigned long alpha = *gPath / *orbIt;
122 //PERMLIB_DEBUG
123 //std::cout << "g_i " << alpha << std::endl;
124 if (!transversal[alpha]) {
125 transversal[alpha] = gPath;
126 tempOrbit.push_back(alpha);
127 }
128 }
130
131 m_cubeLabels.push_back(gPath);
132
133 boost::shared_ptr<PERM> gPathInv(new PERM(*gPath));
134 gPathInv->invertInplace();
135
136 // compute inv(gPath) * ... other generators
137 //
138
139 unsigned long beta1 = *gPathInv / beta;
140 if (!transversal[beta1]) {
141 transversal[beta1] = gPathInv;
142 Transversal<PERM>::m_orbit.push_back(beta1);
143 }
144
145 boost::dynamic_bitset<> omega(this->m_n);
146 boost::dynamic_bitset<> todo(this->m_n);
147 unsigned long i;
148 omega[beta1] = 1;
149 BOOST_FOREACH(const typename PERM::ptr& l, m_cubeLabels) {
150 for (i = 0; i < this->m_n; ++i) {
151 if (!omega[i])
152 continue;
153 unsigned long alpha = *l / i;
154 todo[alpha] = 1;
155 if (!transversal[alpha]) {
156 transversal[alpha] = l;
157 Transversal<PERM>::m_orbit.push_back(alpha);
158 }
159 }
160 omega |= todo;
161 }
162
163 m_cubeLabels.push_front(gPathInv);
164}
165
166template <class PERM>
167void ShallowSchreierTreeTransversal<PERM>::updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange) {
168}
169
170template <class PERM>
171ShallowSchreierTreeTransversal<PERM> ShallowSchreierTreeTransversal<PERM>::clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const {
173 std::map<PERM*,typename PERM::ptr> labelMap;
174 BOOST_FOREACH(typename PERM::ptr& p, ret.m_cubeLabels) {
175 PERM* gen = p.get();
176 p = typename PERM::ptr(new PERM(*p));
177 labelMap.insert(std::make_pair(gen, p));
178 }
179 ret.SchreierTreeTransversal<PERM>::updateGenerators(labelMap);
180 return ret;
181}
182
183template <class PERM>
184void ShallowSchreierTreeTransversal<PERM>::permute(const PERM& g, const PERM& gInv) {
186 BOOST_FOREACH(typename PERM::ptr& p, m_cubeLabels) {
187 *p ^= gInv;
188 *p *= g;
189 p->flush();
190 }
191}
192
193}
194
195#endif // -- SHALLOWSCHREIERTREETRANSVERSAL_H_
Transversal class that stores transversal elements in a Schreier tree.
Definition: schreier_tree_transversal.h:44
Transversal class that stores elements in a shallow Schreier tree.
Definition: shallow_schreier_tree_transversal.h:45
virtual void orbit(unsigned long beta, const std::list< typename PERM::ptr > &generators)
computes transversal based on orbit of under generators
Definition: shallow_schreier_tree_transversal.h:85
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: shallow_schreier_tree_transversal.h:80
virtual void updateGenerators(const std::map< PERM *, typename PERM::ptr > &generatorChange)
updates transversal after group generators have been exchanged
Definition: shallow_schreier_tree_transversal.h:167
void addNewCubeLabel(unsigned long beta, const PERM &s, const unsigned long &beta_prime)
adds a new cube label where s maps beta_prime to a point that has no transversal element yet
Definition: shallow_schreier_tree_transversal.h:109
ShallowSchreierTreeTransversal< PERM > clone(const std::map< PERM *, typename PERM::ptr > &generatorChange) const
returns a clone of this transversal
Definition: shallow_schreier_tree_transversal.h:171
std::list< typename PERM::ptr > m_cubeLabels
ordered list of group elements that are used as cube labels
Definition: shallow_schreier_tree_transversal.h:64
ShallowSchreierTreeTransversal(unsigned int n)
constructor
Definition: shallow_schreier_tree_transversal.h:75
virtual void permute(const PERM &g, const PERM &gInv)
updates transversal after group generators have been conjugated by g
Definition: shallow_schreier_tree_transversal.h:184
Transversal base class corresponding to a base element .
Definition: transversal.h:66
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 n() const
size of the set the group is working on
Definition: transversal.h:98
std::list< unsignedlong >::const_iterator begin() const
begin iterator of basic orbit
Definition: transversal.h:86
std::list< unsignedlong >::const_iterator end() const
end iterator of basic orbit
Definition: transversal.h:88