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
38namespace permlib {
39
40namespace exports { struct BSGSSchreierExport; struct BSGSSchreierImport; }
41
43template <class PERM>
45public:
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;
63protected:
64 virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p);
65
68};
69
70//
71// ---- IMPLEMENTATION
72//
73
74template <class PERM>
76 : Transversal<PERM>(n_), m_statMaxDepth(0)
77{ }
78
79template <class PERM>
80bool SchreierTreeTransversal<PERM>::trivialByDefinition(const PERM& x, unsigned long to) const {
81 return *Transversal<PERM>::m_transversal[to] == x;
82}
83
84template <class PERM>
85void SchreierTreeTransversal<PERM>::registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p) {
88}
89
90
91template <class PERM>
92PERM* 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
119template <class PERM>
120void 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
139template <class PERM>
140SchreierTreeTransversal<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 class that stores transversal elements in a Schreier tree.
Definition: schreier_tree_transversal.h:44
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
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 void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p)
stores that 'p' maps 'from' onto 'to'
Definition: schreier_tree_transversal.h:85
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 PERM * at(unsigned long val) const
returns a transversal element such that equals val
Definition: schreier_tree_transversal.h:92
unsigned int m_statMaxDepth
maximal depth of tree structure representing the transversal
Definition: schreier_tree_transversal.h:62
Transversal base class corresponding to a base element .
Definition: transversal.h:66
unsigned int n() const
size of the set the group is working on
Definition: transversal.h:98
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
export of a BSGS based on SchreierTreeTransversal
Definition: bsgs_schreier_export.h:99
import of a BSGS based on SchreierTreeTransversal
Definition: bsgs_schreier_export.h:146