permlib  0.2.9
Library for permutation computations
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 SCHREIERTRANSVERSAL_H_
34 #define SCHREIERTRANSVERSAL_H_
35 
36 #include <permlib/transversal/transversal.h>
37 
38 namespace permlib {
39 
40 namespace exports { struct BSGSSchreierExport; struct BSGSSchreierImport; }
41 
43 template <class PERM>
44 class SchreierTreeTransversal : public Transversal<PERM> {
45 public:
47  SchreierTreeTransversal(unsigned int n);
48 
49  virtual bool trivialByDefinition(const PERM& x, unsigned long to) const;
50  virtual PERM* at(unsigned long val) const;
51 
52  virtual void updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange);
53 
55 
59  SchreierTreeTransversal<PERM> clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const;
60 
62  mutable unsigned int m_statMaxDepth;
63 protected:
64  virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p);
65 
68 };
69 
70 //
71 // ---- IMPLEMENTATION
72 //
73 
74 template <class PERM>
76  : Transversal<PERM>(n_), m_statMaxDepth(0)
77 { }
78 
79 template <class PERM>
80 bool SchreierTreeTransversal<PERM>::trivialByDefinition(const PERM& x, unsigned long to) const {
81  return *Transversal<PERM>::m_transversal[to] == x;
82 }
83 
84 template <class PERM>
85 void SchreierTreeTransversal<PERM>::registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p) {
88 }
89 
90 
91 template <class PERM>
92 PERM* SchreierTreeTransversal<PERM>::at(unsigned long val) const {
93  const std::vector<boost::shared_ptr<PERM> > &transversal = Transversal<PERM>::m_transversal;
94 
95  if (transversal[val] == 0) {
96  return 0;
97  }
98 
99  unsigned int depth = 1;
100  PERM *res = new PERM(*transversal[val]);
101  const PERM* inv = 0;
102  //std::cout << "Schreier " << *res << std::endl;
103  unsigned long pred = *res % val;
104  //TODO: reserve space for PermutationWord-res beforehand (we know how long the m_word vector will be)
105  while (pred != val) {
106  inv = transversal[pred].get();
107  BOOST_ASSERT(inv);
108  PERMLIB_DEBUG(std::cout << "Schreier2 " << inv << " / " << val << " , " << pred << std::endl;)
109  *res ^= *inv;
110  val = pred;
111  pred = *inv % pred;
112  ++depth;
113  }
114  m_statMaxDepth = std::max(m_statMaxDepth, depth);
115  //std::cout << "Schreier3 " << *res << std::endl;
116  return res;
117 }
118 
119 template <class PERM>
120 void SchreierTreeTransversal<PERM>::updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange) {
121  unsigned int missedCount = 0;
122  BOOST_FOREACH(typename PERM::ptr& p, this->m_transversal) {
123  if (!p)
124  continue;
125  //std::cout << "require " << p.get() << std::endl;
126  typename std::map<PERM*,typename PERM::ptr>::const_iterator pIt = generatorChange.find(p.get());
127  //BOOST_ASSERT( pIt != generatorChange.end() );
128  if (pIt != generatorChange.end()) {
129  p = (*pIt).second;
130  } else {
131  ++missedCount;
132  //std::cout << "missed " << p.get() << " = " << *p << std::endl;
133  }
134  }
135  // we always miss the identity -- and not anything else
136  BOOST_ASSERT( missedCount == 1 );
137 }
138 
139 template <class PERM>
140 SchreierTreeTransversal<PERM> SchreierTreeTransversal<PERM>::clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const {
142  ret.updateGenerators(generatorChange);
143  return ret;
144 }
145 
146 }
147 
148 #endif // -- SCHREIERTRANSVERSAL_H_
Transversal base class corresponding to a base element .
Definition: transversal.h:49
SchreierTreeTransversal< PERM > clone(const std::map< PERM *, typename PERM::ptr > &generatorChange) const
returns a clone of this transversal
Definition: schreier_tree_transversal.h:140
virtual PERM * at(unsigned long val) const
returns a transversal element such that equals val
Definition: schreier_tree_transversal.h:92
import of a BSGS based on SchreierTreeTransversal
Definition: bsgs_schreier_export.h:146
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: schreier_tree_transversal.h:85
Transversal class that stores transversal elements in a Schreier tree.
Definition: schreier_tree_transversal.h:44
export of a BSGS based on SchreierTreeTransversal
Definition: bsgs_schreier_export.h:99
SchreierTreeTransversal(unsigned int n)
constructor
Definition: schreier_tree_transversal.h:75
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: 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: schreier_tree_transversal.h:120
unsigned int n() const
size of the set the group is working on
Definition: transversal.h:98
unsigned int m_statMaxDepth
maximal depth of tree structure representing the transversal
Definition: schreier_tree_transversal.h:62
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