permlib  0.2.9
Library for permutation computations
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 
40 namespace permlib {
41 
43 template<class PERM,class PDOMAIN>
44 class Orbit {
45 public:
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;
56 protected:
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 
87 template <class PERM,class PDOMAIN>
88 template<class Action>
89 inline 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 
110 template <class PERM,class PDOMAIN>
111 template<class Action>
112 inline 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_
virtual const PDOMAIN & element() const =0
returns one element of the orbit
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
abstract base class for orbit computation
Definition: orbit.h:44
PERM PERMtype
type of permutation used for this orbit
Definition: orbit.h:55
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
virtual bool contains(const PDOMAIN &val) const =0
true iff there exists a transversal element mapping to val
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
Definition: abstract_bsgs.h:49