permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
38namespace permlib {
39
41template <class PERM>
42class ExplicitTransversal : public Transversal<PERM> {
43public:
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;
60protected:
61 virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p);
62};
63
64//
65// ---- IMPLEMENTATION
66//
67
68template <class PERM>
70
71template <class PERM>
73 : Transversal<PERM>(n_)
74{ }
75
76template <class PERM>
77bool ExplicitTransversal<PERM>::trivialByDefinition(const PERM& x, unsigned long to) const {
78 // we cannot infer this information from the transversal
79 return false;
80}
81
82template <class PERM>
83PERM* ExplicitTransversal<PERM>::at(unsigned long val) const {
85 return 0;
86 return new PERM(*(Transversal<PERM>::m_transversal[val]));
87}
88
89template <class PERM>
90void 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
103template <class PERM>
104void 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
114template <class PERM>
115ExplicitTransversal<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 class that stores all transversal elements explicitly.
Definition: explicit_transversal.h:42
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
virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p)
stores that 'p' maps 'from' onto 'to'
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
ExplicitTransversal(unsigned int n)
constructor
Definition: explicit_transversal.h:72
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< PERM > clone(const std::map< PERM *, typename PERM::ptr > &generatorChange) const
returns a clone of this transversal
Definition: explicit_transversal.h:115
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
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
std::vector< boost::shared_ptr< PERM > > m_transversal
transversal elements
Definition: transversal.h:154
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