permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
orbit.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 ORBIT_H_
34#define ORBIT_H_
35
36#include <list>
37
38#include <boost/foreach.hpp>
39
40namespace permlib {
41
43template<class PERM,class PDOMAIN>
44class Orbit {
45public:
46 virtual ~Orbit() {}
47
49 virtual bool contains(const PDOMAIN& val) const = 0;
50
52 virtual const PDOMAIN& element() const = 0;
53
55 typedef PERM PERMtype;
56protected:
58
64 template<class Action>
65 void orbit(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, Action a, std::list<PDOMAIN>& orbitList);
66
68
77 template<class Action>
78 void orbitUpdate(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g, Action a, std::list<PDOMAIN>& orbitList);
79
81
84 virtual bool foundOrbitElement(const PDOMAIN& alpha, const PDOMAIN& alpha_p, const typename PERM::ptr& p) = 0;
85};
86
87template <class PERM,class PDOMAIN>
88template<class Action>
89inline void Orbit<PERM,PDOMAIN>::orbit(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, Action a, std::list<PDOMAIN>& orbitList) {
90 if (orbitList.empty()) {
91 orbitList.push_back(beta);
92 foundOrbitElement(beta, beta, typename PERM::ptr());
93 }
94 BOOST_ASSERT( orbitList.size() >= 1 );
95
96 PERMLIB_DEBUG(std::cout << "orbit of " << beta << std::endl;)
97 typename std::list<PDOMAIN>::const_iterator it;
98 for (it = orbitList.begin(); it != orbitList.end(); ++it) {
99 const PDOMAIN &alpha = *it;
100 BOOST_FOREACH(const typename PERM::ptr& p, generators) {
101 //std::cout << " " << orbitList.size() << std::endl;
102 PDOMAIN alpha_p = a(*p, alpha);
103 if (alpha_p != alpha && foundOrbitElement(alpha, alpha_p, p))
104 orbitList.push_back(alpha_p);
105 }
106 }
107 //std::cout << "orb size " << orbitList.size() << std::endl;
108}
109
110template <class PERM,class PDOMAIN>
111template<class Action>
112inline void Orbit<PERM,PDOMAIN>::orbitUpdate(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g, Action a, std::list<PDOMAIN>& orbitList) {
113 if (orbitList.empty()) {
114 orbitList.push_back(beta);
115 foundOrbitElement(beta, beta, typename PERM::ptr());
116 }
117 BOOST_ASSERT( orbitList.size() >= 1 );
118
119 PERMLIB_DEBUG(std::cout << "orbiUpdate of " << beta << " and " << *g << std::endl;)
120 const unsigned int oldSize = orbitList.size();
121 // first, compute only ORBIT^g
122 typename std::list<PDOMAIN>::const_iterator it;
123 for (it = orbitList.begin(); it != orbitList.end(); ++it) {
124 const PDOMAIN &alpha = *it;
125 PDOMAIN alpha_g = a(*g, alpha);
126 if (alpha_g != alpha && foundOrbitElement(alpha, alpha_g, g))
127 orbitList.push_back(alpha_g);
128 }
129
130 if (oldSize == orbitList.size())
131 return;
132
133 orbit(beta, generators, a, orbitList);
134}
135
136}
137
138#endif // -- ORBIT_H_
abstract base class for orbit computation
Definition orbit.h:44
PERM PERMtype
type of permutation used for this orbit
Definition orbit.h:55
void orbit(const PDOMAIN &beta, const std::list< typename PERM::ptr > &generators, Action a, std::list< PDOMAIN > &orbitList)
computes orbit of beta under generators
Definition orbit.h:89
void orbitUpdate(const PDOMAIN &beta, const std::list< typename PERM::ptr > &generators, const typename PERM::ptr &g, Action a, std::list< PDOMAIN > &orbitList)
updates an existing orbit of beta after one element has been added
Definition orbit.h:112
virtual const PDOMAIN & element() const =0
returns one element of the orbit
virtual bool contains(const PDOMAIN &val) const =0
true iff there exists a transversal element mapping to val
virtual bool foundOrbitElement(const PDOMAIN &alpha, const PDOMAIN &alpha_p, const typename PERM::ptr &p)=0
callback when the orbit algorithm constructs an element alpha_p from alpha and p