permlib  0.2.9
Library for permutation computations
group_type.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 #ifndef GROUP_TYPE_H_
33 #define GROUP_TYPE_H_
34 
35 #include <cstring>
36 
37 namespace permlib {
38 
40 class GroupType {
41 public:
43  enum Type {
44  None,
45  Trivial,
46  Named,
47  Anonymous,
48  WreathSymmetric,
49  DirectProduct
50  };
51 
53  void writeToStream(std::ostream& o) const {
54  if (!m_naturalAction)
55  o << "ISO( ";
56  this->writeTypeToStream(o);
57  if (!m_naturalAction)
58  o << " , " << m_realDegree << " )";
59  }
60 
62  unsigned int realDegree() const { return m_realDegree; }
64 
67  bool isNaturalAction() const { return m_naturalAction; }
69  Type type() const { return m_type; }
70 
72  bool equals(const GroupType* type_) const {
73  if (this->m_type != type_->m_type)
74  return false;
75  if (this->m_realDegree != type_->m_realDegree)
76  return false;
77  if (this->m_naturalAction != type_->m_naturalAction)
78  return false;
79  return this->equalsType(type_);
80  }
81 
83  void setNonNaturalAction(unsigned int realDegree_) {
84  m_realDegree = realDegree_;
85  m_naturalAction = false;
86  }
87 
89  virtual ~GroupType() { }
90 protected:
94  unsigned int m_realDegree;
97 
99  GroupType(Type type_, unsigned int realDegree_, bool naturalAction)
100  : m_type(type_), m_realDegree(realDegree_), m_naturalAction(naturalAction) { }
101 
103 
107  virtual bool equalsType(const GroupType* type_) const { return false; }
109  virtual void writeTypeToStream(std::ostream& o) const = 0;
110 };
111 
112 
114 class TrivialGroupType : public GroupType {
115 public:
119  TrivialGroupType(unsigned int realDegree_) : GroupType(Trivial, realDegree_, true) { }
120 
121  virtual void writeTypeToStream(std::ostream& o) const {
122  o << "Trivial(" << m_realDegree << ")";
123  }
124 protected:
125  virtual bool equalsType(const GroupType* type_) const { return true; }
126 };
127 
128 
130 template<class IntegerType = boost::uint64_t>
132 public:
137  AnonymousGroupType(unsigned int realDegree_, IntegerType order_ = 0)
138  : GroupType(Anonymous, realDegree_, true), m_order(order_) { }
139 
140  virtual void writeTypeToStream(std::ostream& o) const {
141  if (m_order)
142  o << "anonymous(" << m_realDegree << ", " << m_order << ")";
143  else
144  o << "anonymous(" << m_realDegree << ")";
145  }
146 protected:
147  IntegerType m_order;
148 
149  virtual bool equalsType(const GroupType* type_) const {
150  // we can never know if two anonymous groups are equal without digging deeper
151  return false;
152  }
153 };
154 
155 
157 class NamedGroupType : public GroupType {
158 public:
159  virtual void writeTypeToStream(std::ostream& o) const {
160  o << m_name << "_" << m_typeDegree;
161  }
162 
164  const char* name() const { return m_name; }
166  unsigned int typeDegree() const { return m_typeDegree; }
167 protected:
168  const char* m_name;
169  unsigned int m_typeDegree;
170 
176  NamedGroupType(const char* name_, unsigned int typeDegree_, unsigned int realDegree_)
177  : GroupType(Named, realDegree_, typeDegree_ == realDegree_), m_name(name_), m_typeDegree(typeDegree_) { }
178 
179  virtual bool equalsType(const GroupType* type_) const {
180  const NamedGroupType* namedType = dynamic_cast<const NamedGroupType*>(type_);
181  return namedType->m_typeDegree == this->m_typeDegree && std::strcmp(namedType->m_name, this->m_name) == 0;
182  }
183 };
184 
185 
188 public:
193  SymmetricGroupType(unsigned int typeDegree_, unsigned int realDegree_)
194  : NamedGroupType("S", typeDegree_, realDegree_) { }
195 };
196 
197 
200 public:
205  AlternatingGroupType(unsigned int typeDegree_, unsigned int realDegree_)
206  : NamedGroupType("A", typeDegree_, realDegree_) { }
207 };
208 
209 
212 public:
217  CyclicGroupType(unsigned int typeDegree_, unsigned int realDegree_)
218  : NamedGroupType("C", typeDegree_, realDegree_) { }
219 };
220 
221 
223 
227 public:
228  WreathSymmetricGroupType(unsigned int degreeG_, unsigned int degreeH_, unsigned int realDegree_)
229  : GroupType(WreathSymmetric, realDegree_, realDegree_ == degreeG_ * degreeH_), m_degreeG(degreeG_), m_degreeH(degreeH_) { }
230 
231  virtual void writeTypeToStream(std::ostream& o) const {
232  o << "S_" << m_degreeG << " wr S_" << m_degreeH;
233  }
234 
235  unsigned int degreeG() const { return m_degreeG; }
236  unsigned int degreeH() const { return m_degreeH; }
237 protected:
238  unsigned int m_degreeG;
239  unsigned int m_degreeH;
240 
241  virtual bool equalsType(const GroupType* type_) const {
242  const WreathSymmetricGroupType* wreathType = dynamic_cast<const WreathSymmetricGroupType*>(type_);
243  return wreathType->m_degreeG == m_degreeG && wreathType->m_degreeH == m_degreeH;
244  }
245 };
246 
249 public:
255  DirectProductGroupType(const GroupType* type1, const GroupType* type2, unsigned int realDegree_)
256  : GroupType(DirectProduct, realDegree_, realDegree_ == type1->realDegree() + type2->realDegree()), m_components(2)
257  {
258  m_components[0] = GroupTypePtr(type1);
259  m_components[1] = GroupTypePtr(type2);
260  }
261 
262  virtual void writeTypeToStream(std::ostream& o) const {
263  for (unsigned int i = 0; i < m_components.size(); ++i) {
264  if (i > 0)
265  o << " x ";
266  m_components[i]->writeToStream(o);
267  }
268  }
269 
270 protected:
271  typedef boost::shared_ptr<const GroupType> GroupTypePtr;
272  std::vector<GroupTypePtr> m_components;
273 
274  virtual bool equalsType(const GroupType* type_) const {
275  const DirectProductGroupType* directType = dynamic_cast<const DirectProductGroupType*>(type_);
276  if (m_components.size() != directType->m_components.size())
277  return false;
278  std::vector<GroupTypePtr>::const_iterator itMe = m_components.begin();
279  std::vector<GroupTypePtr>::const_iterator itOther = directType->m_components.begin();
280  while (itMe != m_components.end()) {
281  if ( ! (*itMe)->equals((*itOther).get()) )
282  return false;
283  ++itMe;
284  ++itOther;
285  }
286  return true;
287  }
288 };
289 
290 }
291 
292 #endif
virtual void writeTypeToStream(std::ostream &o) const =0
writes type specific string to output stream
Type m_type
group type
Definition: group_type.h:92
Group type for alternating groups.
Definition: group_type.h:199
Group type for cyclic groups.
Definition: group_type.h:211
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:159
Group type for a direct product of two groups.
Definition: group_type.h:248
AlternatingGroupType(unsigned int typeDegree_, unsigned int realDegree_)
Definition: group_type.h:205
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:121
GroupType(Type type_, unsigned int realDegree_, bool naturalAction)
protected constructor
Definition: group_type.h:99
abstract base class for named groups (such as cyclic and symmetric groups)
Definition: group_type.h:157
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:140
bool isNaturalAction() const
returns true iff action is natural
Definition: group_type.h:67
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:262
virtual ~GroupType()
destructor
Definition: group_type.h:89
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:125
Group type for symmetric groups.
Definition: group_type.h:187
const char * name() const
the name of the group
Definition: group_type.h:164
bool equals(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:72
bool m_naturalAction
stores whether action is natural
Definition: group_type.h:96
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:179
SymmetricGroupType(unsigned int typeDegree_, unsigned int realDegree_)
Definition: group_type.h:193
Group type for a permutation group whose type could not be determined.
Definition: group_type.h:131
Group type for a trivial permutation group.
Definition: group_type.h:114
virtual void writeTypeToStream(std::ostream &o) const
writes type specific string to output stream
Definition: group_type.h:231
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:149
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:274
unsigned int m_realDegree
degree of the permutation group
Definition: group_type.h:94
AnonymousGroupType(unsigned int realDegree_, IntegerType order_=0)
Definition: group_type.h:137
void setNonNaturalAction(unsigned int realDegree_)
stores the information that this group acts non-naturally on realDegree many elements ...
Definition: group_type.h:83
Group type for a wreath product of symmetric groups.
Definition: group_type.h:226
DirectProductGroupType(const GroupType *type1, const GroupType *type2, unsigned int realDegree_)
Definition: group_type.h:255
NamedGroupType(const char *name_, unsigned int typeDegree_, unsigned int realDegree_)
Definition: group_type.h:176
void writeToStream(std::ostream &o) const
writes a human readable identifier to the given output stream
Definition: group_type.h:53
abstract base class for permutation group types
Definition: group_type.h:40
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:241
TrivialGroupType(unsigned int realDegree_)
Definition: group_type.h:119
Type
types for which an implementation of GroupType exists
Definition: group_type.h:43
CyclicGroupType(unsigned int typeDegree_, unsigned int realDegree_)
Definition: group_type.h:217
virtual bool equalsType(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:107
Type type() const
the type of this the group
Definition: group_type.h:69
unsigned int typeDegree() const
the degree of the named group to which the real action is isomorphic to
Definition: group_type.h:166
unsigned int realDegree() const
the degree of the group as permutation group
Definition: group_type.h:62
Definition: abstract_bsgs.h:49