permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/transversal/orbit.h
00001 // ---------------------------------------------------------------------------
00002 //
00003 //  This file is part of PermLib.
00004 //
00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
00006 // All rights reserved.
00007 // 
00008 // Redistribution and use in source and binary forms, with or without
00009 // modification, are permitted provided that the following conditions
00010 // are met:
00011 // 1. Redistributions of source code must retain the above copyright
00012 //    notice, this list of conditions and the following disclaimer.
00013 // 2. Redistributions in binary form must reproduce the above copyright
00014 //    notice, this list of conditions and the following disclaimer in the
00015 //    documentation and/or other materials provided with the distribution.
00016 // 3. The name of the author may not be used to endorse or promote products
00017 //    derived from this software without specific prior written permission.
00018 // 
00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029 //
00030 // ---------------------------------------------------------------------------
00031 
00032 
00033 #ifndef ORBIT_H_
00034 #define ORBIT_H_
00035 
00036 #include <list>
00037 
00038 #include <boost/foreach.hpp>
00039 
00040 namespace permlib {
00041 
00043 template<class PERM,class PDOMAIN>
00044 class Orbit {
00045 public:
00046         virtual ~Orbit() {}
00047         
00049         virtual bool contains(const PDOMAIN& val) const = 0;
00050 
00052         virtual const PDOMAIN& element() const = 0;
00053         
00055         typedef PERM PERMtype;
00056 protected:
00058 
00064         template<class Action>
00065         void orbit(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, Action a, std::list<PDOMAIN>& orbitList);
00066         
00068 
00077         template<class Action>
00078         void orbitUpdate(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g, Action a, std::list<PDOMAIN>& orbitList);
00079         
00081 
00084         virtual bool foundOrbitElement(const PDOMAIN& alpha, const PDOMAIN& alpha_p, const typename PERM::ptr& p) = 0;
00085 };
00086 
00087 template <class PERM,class PDOMAIN>
00088 template<class Action>
00089 inline void Orbit<PERM,PDOMAIN>::orbit(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, Action a, std::list<PDOMAIN>& orbitList) {
00090         if (orbitList.empty()) {
00091                 orbitList.push_back(beta);
00092                 foundOrbitElement(beta, beta, typename PERM::ptr());
00093         }
00094         BOOST_ASSERT( orbitList.size() >= 1 );
00095         
00096         PERMLIB_DEBUG(std::cout << "orbit of " << beta << std::endl;)
00097         typename std::list<PDOMAIN>::const_iterator it;
00098         for (it = orbitList.begin(); it != orbitList.end(); ++it) {
00099                 const PDOMAIN &alpha = *it;
00100                 BOOST_FOREACH(const typename PERM::ptr& p, generators) {
00101                         //std::cout << "         " << orbitList.size() << std::endl;
00102                         PDOMAIN alpha_p = a(*p, alpha);
00103                         if (alpha_p != alpha && foundOrbitElement(alpha, alpha_p, p))
00104                                 orbitList.push_back(alpha_p);
00105                 }
00106         }
00107         //std::cout << "orb size " << orbitList.size() << std::endl;
00108 }
00109 
00110 template <class PERM,class PDOMAIN>
00111 template<class Action>
00112 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) {
00113         if (orbitList.empty()) {
00114                 orbitList.push_back(beta);
00115                 foundOrbitElement(beta, beta, typename PERM::ptr());
00116         }
00117         BOOST_ASSERT( orbitList.size() >= 1 );
00118         
00119         PERMLIB_DEBUG(std::cout << "orbiUpdate of " << beta << " and " << *g << std::endl;)
00120         const unsigned int oldSize = orbitList.size();
00121         // first, compute only ORBIT^g
00122         typename std::list<PDOMAIN>::const_iterator it;
00123         for (it = orbitList.begin(); it != orbitList.end(); ++it) {
00124                 const PDOMAIN &alpha = *it;
00125                 PDOMAIN alpha_g = a(*g, alpha);
00126                 if (alpha_g != alpha && foundOrbitElement(alpha, alpha_g, g))
00127                         orbitList.push_back(alpha_g);
00128         }
00129         
00130         if (oldSize == orbitList.size())
00131                 return;
00132         
00133         orbit(beta, generators, a, orbitList);
00134 }
00135 
00136 }
00137 
00138 #endif // -- ORBIT_H_