permlib  0.2.9
Library for permutation computations
explicit_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 EXPLICITTRANSVERSAL_H_
34 #define EXPLICITTRANSVERSAL_H_
35 
36 #include <permlib/transversal/transversal.h>
37 
38 namespace permlib {
39 
41 template <class PERM>
42 class ExplicitTransversal : public Transversal<PERM> {
43 public:
45  ExplicitTransversal(unsigned int n);
46 
47  virtual PERM* at(unsigned long val) const;
48  virtual bool trivialByDefinition(const PERM& x, unsigned long to) const;
49 
50  virtual void permute(const PERM& g, const PERM& gInv);
51 
53 
56  ExplicitTransversal<PERM> clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const;
57 
59  static const unsigned int m_statMaxDepth;
60 protected:
61  virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p);
62 };
63 
64 //
65 // ---- IMPLEMENTATION
66 //
67 
68 template <class PERM>
69 const unsigned int ExplicitTransversal<PERM>::m_statMaxDepth = 1;
70 
71 template <class PERM>
73  : Transversal<PERM>(n_)
74 { }
75 
76 template <class PERM>
77 bool ExplicitTransversal<PERM>::trivialByDefinition(const PERM& x, unsigned long to) const {
78  // we cannot infer this information from the transversal
79  return false;
80 }
81 
82 template <class PERM>
83 PERM* ExplicitTransversal<PERM>::at(unsigned long val) const {
85  return 0;
86  return new PERM(*(Transversal<PERM>::m_transversal[val]));
87 }
88 
89 template <class PERM>
90 void ExplicitTransversal<PERM>::registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p) {
92 
93  std::vector<boost::shared_ptr<PERM> > &transversal = Transversal<PERM>::m_transversal;
94 
95  if (!transversal[from])
96  transversal[to] = boost::shared_ptr<PERM>(new PERM(*p));
97  else {
98  transversal[to] = boost::shared_ptr<PERM>(new PERM(*transversal[from]));
99  (*transversal[to]) *= *p;
100  }
101 }
102 
103 template <class PERM>
104 void ExplicitTransversal<PERM>::permute(const PERM& g, const PERM& gInv) {
106  BOOST_FOREACH(typename PERM::ptr& p, Transversal<PERM>::m_transversal) {
107  if (p) {
108  *p ^= gInv;
109  *p *= g;
110  }
111  }
112 }
113 
114 template <class PERM>
115 ExplicitTransversal<PERM> ExplicitTransversal<PERM>::clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const {
116  ExplicitTransversal<PERM> ret(*this);
117  BOOST_FOREACH(typename PERM::ptr& p, ret.m_transversal) {
118  if (!p)
119  continue;
120  p = boost::shared_ptr<PERM>(new PERM(*p));
121  }
122  return ret;
123 }
124 
125 }
126 
127 #endif // -- EXPLICITTRANSVERSAL_H_
Transversal base class corresponding to a base element .
Definition: transversal.h:49
ExplicitTransversal< PERM > clone(const std::map< PERM *, typename PERM::ptr > &generatorChange) const
returns a clone of this transversal
Definition: explicit_transversal.h:115
Transversal class that stores all transversal elements explicitly.
Definition: explicit_transversal.h:42
virtual void permute(const PERM &g, const PERM &gInv)
updates transversal after group generators have been conjugated by g
Definition: explicit_transversal.h:104
ExplicitTransversal(unsigned int n)
constructor
Definition: explicit_transversal.h:72
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: explicit_transversal.h:90
virtual PERM * at(unsigned long val) const
returns a transversal element such that equals val
Definition: explicit_transversal.h:83
unsigned int n() const
size of the set the group is working on
Definition: transversal.h:98
virtual bool trivialByDefinition(const PERM &x, unsigned long to) const
true if Schreier generator constructed from x and the transversal element related to "to" is trivial ...
Definition: explicit_transversal.h:77
virtual void permute(const PERM &g, const PERM &gInv)
updates transversal after group generators have been conjugated by g
Definition: transversal.h:221
static const unsigned int m_statMaxDepth
maximal depth of "tree" structure representing the transversal; identical to 1 for explicit transvers...
Definition: explicit_transversal.h:59
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