CoCoALib-0.9905 date: 23 May 2007


TmpIsTree.H

Go to the documentation of this file.
00001 #ifndef CoCoA_IsTree_H
00002 #define CoCoA_IsTree_H
00003 
00004 //   Copyright (c)  2006  Massimo Caboara
00005 
00006 //   This file is part of the source of CoCoALib, the CoCoA Library.
00007 
00008 //   CoCoALib is free software; you can redistribute it and/or modify
00009 //   it under the terms of the GNU General Public License (version 2)
00010 //   as published by the Free Software Foundation.  A copy of the full
00011 //   licence may be found in the file COPYING in this directory.
00012 
00013 //   CoCoALib is distributed in the hope that it will be useful,
00014 //   but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 //   GNU General Public License for more details.
00017 
00018 //   You should have received a copy of the GNU General Public License
00019 //   along with CoCoA; if not, write to the Free Software
00020 //   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00021 
00022 
00023 #include "CoCoA/TmpGTypes.H"
00024 #include "CoCoA/io.H"
00025 #include "CoCoA/time.H"
00026 
00027 #include <vector>
00028 //using std::vector;
00029 #include <list>
00030 //using std::list;
00031 #include <bitset>
00032 //using std::bitset;
00033 #include <utility>
00034 //using std::pair;
00035 
00036 
00037 namespace CoCoA
00038 {
00039 
00040   class PolyRing; // forward declaration -- defined in PolyRing.H
00041   class RingElem; // forward declaration -- defined in ring.H
00042 
00043   class facet; // fwd decl
00044 
00045   const unsigned int WordLen = 64; // for 64bit machines
00046   typedef std::bitset<WordLen> BitsetWordLen;
00047 
00048 
00049 // WARNING TODO: facets are supposed to have all the same len.
00050 // Add a static field and some check.
00051 // a facet is a sqfr power product with A LOT of indeterminates.
00052 // It is implemented here as a vector std::bitset<32> because the
00053 // operation on bitsets are sooo efficient. the operations are the
00054 // obvious ones.
00055   class facet
00056   {
00057   public:
00058     facet(const std::vector<long>&);
00059     facet(const facet&);
00060     facet(){};
00061     ~facet(){};
00062 
00063     unsigned int size()const{return myFacet.size();};
00064     inline std::list<unsigned int> myVertices()const;
00065     inline bool myAmIEmpty()const;
00066     inline bool myAmINotEmpty()const;
00067     inline friend bool AreDirectlyConnected(const facet&,const facet&);
00068     inline friend bool contains(const facet&,const facet&);
00069     inline friend bool IsFLesser(const facet&,const facet&,const facet&);
00070     inline friend facet FacetIntersection(const facet&, const facet&);
00071 
00072     inline facet& operator=(const facet&);
00073     inline void operator-=(const facet&);
00074     inline friend facet operator-(const facet&, const facet&);
00075     inline void operator+=(const facet&);
00076     inline friend facet operator+(const facet&, const facet&);
00077     inline void operator&=(const facet&);
00078     inline bool operator==(const facet& the_facet)const{return myFacet==the_facet.myFacet;};
00079     inline bool operator!=(const facet& the_facet)const{return myFacet!=the_facet.myFacet;};
00080 
00081 
00082     friend std::ostream& operator<<(std::ostream&, const facet&);
00083     inline bool lesser(const facet&)const;
00084     inline friend bool lesser(const facet&, const facet&);
00085 
00086     // expensive functions, we are dealing with bitsets
00087     inline bool myIsEntryThere(const unsigned int j)const;
00088     inline void mySetEntryThere(const unsigned int j,bool value);
00089     //inline unsigned int size()const;
00090 
00091     friend std::list<facet> PolyList2FacetList(const PolyRing&,const PolyList&);
00092     friend PolyList FacetList2PolyList(const PolyRing&,const std::list<facet>&);
00093     friend RingElem Facet2RingElem(const PolyRing&,const facet&);
00094 
00095   private:
00096     std::vector<BitsetWordLen> myFacet;
00097 
00098   }; // end class facet
00099 
00100 
00101 
00102   inline bool lesser(const bool&, const bool&);
00103 
00104 
00105 // Function Object: gives order for set<facet>
00106   class LexicographicOrderFacet
00107   {
00108   public:
00109     bool operator()(const facet& f1, const facet& f2)const
00110       {
00111         return lesser(f1,f2);
00112       }
00113   }; // end class LexicographicOrderFacet, really a Function Object
00114 
00115 
00116 
00117 // Add the PolyRing (at least Monomial) to the FacetComplex class.
00118 // This helps the I/O. Or, change the I/O in such a way to get the
00119 // PR from the PL, special case list []
00120 // functions: PolyList2FacetList, FacetComplex(const PolyRing&, const PolyList&);
00121 // a FacetComplex is, more or less, a set of facets with lex ordering.
00122 
00123   typedef std::list<facet>::const_iterator FacetComplexConstIter;
00124   typedef std::list<facet>::iterator FacetComplexIter;
00125   typedef std::vector<std::pair<FacetComplexConstIter,std::vector<FacetComplexConstIter> > >::const_iterator conn_block_const_itr;
00126   typedef std::vector<std::pair<FacetComplexConstIter,std::vector<FacetComplexConstIter> > >::iterator ConnBlockIter;
00127 
00128 
00129   class FacetComplex
00130   {
00131   public:
00132     friend class ConnectionBlock;
00133 
00134     FacetComplex(const PolyRing&, const PolyList&);
00135     FacetComplex(const FacetComplex& theFacetComplex){myElems=theFacetComplex.myElems;};
00136     FacetComplex(){};
00137     FacetComplex(const std::list<facet>&);
00138     ~FacetComplex(){};
00139     unsigned int myNumIndets()const;
00140     unsigned int myGetIndex(const facet&)const;
00141     friend std::ostream& operator<<(std::ostream&, const FacetComplex&);
00142     FacetComplex& operator=(const FacetComplex&);
00143     void myInsert(const facet& f){myElems.push_back(f);};
00144     void myErase(const facet& f){myElems.remove(f);};
00145     unsigned int mySize()const{return myElems.size();};
00146     bool myAmIEmpty()const{return myElems.empty();};
00147     std::list<facet> myFacetComplex2FacetList()const;
00148     FacetComplex mySetDifference(const facet&)const;
00149     FacetComplex delta(const facet&,const facet&,const facet&)const;// the delta operation in the extended abstract
00150     FacetComplex delta_new(const facet&,const facet&,const facet&)const;// the delta operation in the paper
00151 
00152     bool AreConnected(const facet&,const facet&)const;// old algorithm
00153     bool AreConnected_new(const facet&,const facet&)const;// new O(nl) algorithm
00154     bool IsTripleCondition(const facet&,const facet&,const facet&)const;// triple condition
00155     std::list<facet> myIsTreeNoOpt();
00156     std::list<facet> myIsTreeOpt();
00157     std::list<facet> myIsTreeCBNoOpt();
00158     std::list<facet> myIsTreeCBOpt();
00159     void myClear(){myElems.clear();};
00160 
00161   private:
00162     // they are just used in delta_new(...)
00163     void myMakeXj(std::list<unsigned int>&,const unsigned int j)const;
00164     void myMakeG(std::vector<unsigned int>&,const std::vector<unsigned int>& P,
00165                  const std::list<unsigned int>& xj)const;
00166     std::list<facet> myElems;
00167   };// end class FacetComplex
00168 
00169 
00170 
00171 // Graph sparse description of the direct connectedeness of the facets of a FacetComplex
00172 // A connection block is a std::vector of <itr,std::vector<itr>>, where the itrs are really ptrs to some facet in the FacetComplex
00173 // the meaning: if p is in the vector associated to q, p and q are directly connected
00174   class ConnectionBlock
00175   {
00176   public:
00177     friend class FacetComplex;
00178     ConnectionBlock(const FacetComplex&);
00179     ConnectionBlock(){};
00180     friend std::ostream& operator<<(std::ostream&, const ConnectionBlock&);
00181     ConnBlockIter erase(ConnBlockIter&);
00182   private:
00183     std::vector<std::pair<FacetComplexConstIter,std::vector<FacetComplexConstIter> > > my_array;
00184   };// end class ConnectionBlock
00185 
00186 
00187 ///////////// inline facet functions ///////////////////////////////////////////
00188 
00189   // Returns the list of the indexes of the vertices in the facet
00190   std::list<unsigned int> facet::myVertices()const
00191   {         
00192     std::list<unsigned int> l;    
00193     for (unsigned int i=0;i!=size()*WordLen;i++)
00194       if (myFacet[i/WordLen][i%WordLen])
00195         l.push_back(i);     
00196     return l;       
00197   }//facet::myVertices()      
00198 
00199 
00200   bool lesser(const bool& b1, const bool& b2)
00201   {
00202     if (!b1&&b2) return true;
00203     return false;
00204   }//lesser
00205 
00206 
00207   bool facet::lesser(const facet& f2) const
00208   {
00209     for (std::vector<BitsetWordLen>::const_iterator it1=myFacet.begin(),it2=f2.myFacet.begin();
00210          it1!=myFacet.end();it1++,it2++)
00211     {
00212       for (unsigned int i=0;i!=WordLen;i++)
00213       {
00214   if ((*it1)[i]!=(*it2)[i])
00215     if ((*it1)[i])
00216       return false;
00217     else
00218       return true;
00219       }//for
00220     }//for
00221     return false;
00222   }//facet::lesser
00223 
00224 
00225   bool lesser(const facet& f1, const facet& f2)
00226   {
00227     return f1.lesser(f2);
00228   }
00229 
00230   // No bits in the facet are set to 1
00231   bool facet::myAmIEmpty()const
00232   {
00233     for (std::vector<BitsetWordLen>::const_iterator it=myFacet.begin();
00234          it!=myFacet.end();it++)
00235     {
00236       if (it->any()) return false;
00237     }
00238     return true;
00239   }//facet::myAmIEmpty()
00240 
00241   // At least a bit in the facet is set to 1
00242   bool facet::myAmINotEmpty()const
00243   {
00244     for (std::vector<BitsetWordLen>::const_iterator it=myFacet.begin();
00245          it!=myFacet.end();it++)
00246     {
00247       if (it->any()) return true;
00248     }
00249     return false;
00250   }//facet::AmINotEmpty()
00251 
00252 
00253 // FacetIntersection(f1,f2)!=emptyset
00254   bool AreDirectlyConnected(const facet& f1,const facet& f2)
00255   {
00256     BitsetWordLen tmp;
00257     for (std::vector<BitsetWordLen>::const_iterator it1=f1.myFacet.begin(),it2=f2.myFacet.begin();
00258        it2!=f2.myFacet.end();it1++,it2++)
00259     {
00260       tmp=*it1;tmp&=*it2;
00261       if (tmp.any())
00262       {
00263         return true;
00264       }
00265     }
00266     return false;
00267   } //AreDirectlyConnected
00268 
00269 
00270   // f1 contains f2
00271   bool contains(const facet& f1,const facet& f2)
00272   {
00273     BitsetWordLen tmp;
00274     for (std::vector<BitsetWordLen>::const_iterator it1=f1.myFacet.begin(),it2=f2.myFacet.begin();
00275          it2!=f2.myFacet.end();it1++,it2++)
00276     {
00277       tmp =(*it2);
00278       tmp&=~(*it1);
00279       if (tmp.any())
00280         return false;
00281     }
00282     return true;
00283   }//contains
00284 
00285 
00286   // The IsFLesser operation from the paper
00287   bool IsFLesser(const facet& f,const facet& g1,const facet& g2)
00288   {
00289     facet F1(FacetIntersection(f,g1));
00290     facet F2(FacetIntersection(f,g2));
00291     return contains(F1,F2);
00292   }//IsFLesser
00293 
00294 
00295 
00296    // f1=f2
00297   facet& facet::operator=(const facet& the_facet)
00298   {
00299     myFacet=the_facet.myFacet;
00300     return *this;
00301   }
00302 
00303 
00304   // No duplications *this=*this mySetDifference the_facet
00305   void facet::operator-=(const facet& the_facet)
00306   {
00307     std::vector<BitsetWordLen>::iterator it1=myFacet.begin();
00308     for (std::vector<BitsetWordLen>::const_iterator it2=the_facet.myFacet.begin();
00309          it2!=the_facet.myFacet.end();it2++,it1++)
00310     {
00311       *it1&= ~(*it2); // v1 And Not v2
00312     }
00313   }//facet::operator-=
00314 
00315   // returns f1 mySetDifference f2. Duplicates
00316   facet operator-(const facet& v1, const facet& v2)
00317   {
00318     facet v(v1);
00319     v-=v2;
00320     return v;
00321   }
00322 
00323   // No duplications - *this=*this union the_facet
00324   void facet::operator+=(const facet& the_facet)
00325   {
00326     std::vector<BitsetWordLen>::iterator it1=myFacet.begin();
00327     for (std::vector<BitsetWordLen>::const_iterator it2=the_facet.myFacet.begin();
00328          it2!=the_facet.myFacet.end();it2++,it1++)
00329     {
00330       *it1|= *it2; // v1 Or v2
00331     }
00332   }//facet::operator+=
00333 
00334   // returns f1 union f2. Duplicates
00335   facet operator+(const facet& v1, const facet& v2)
00336   {
00337     facet v(v1);
00338     v+=v2;
00339     return v;
00340   }
00341 
00342 
00343 // No duplications
00344   void facet::operator&=(const facet& the_facet)
00345   {
00346     std::vector<BitsetWordLen>::iterator it1=myFacet.begin();
00347     for (std::vector<BitsetWordLen>::const_iterator it2=the_facet.myFacet.begin();
00348          it2!=the_facet.myFacet.end();it2++,it1++)
00349     {
00350       *it1 &= *it2; // v1 And v2
00351     }
00352   }//facet::operator&=
00353 
00354   // returns f1 And f2. Duplicates
00355   facet FacetIntersection(const facet& v1, const facet& v2)
00356   {
00357 //std::cout<<"begin FacetIntersection"<<std::endl;
00358     facet v(v1);
00359     v&=v2;
00360 //std::cout<<"end FacetIntersection"<<std::endl;
00361     return v;
00362   }//FacetIntersection
00363 
00364 
00365   // inspects entry j in myFacet
00366   // Expensive
00367   bool facet::myIsEntryThere(const unsigned int j)const
00368   {
00369     return myFacet[j/WordLen][j%WordLen];
00370   }//facet::myIsEntryThere
00371 
00372   // sets entry j in myFacet to value
00373   // Expensive
00374   void facet::mySetEntryThere(const unsigned int j,bool value)
00375   {
00376     myFacet[j/WordLen][j%WordLen]=value;
00377   }//facet::mySetEntryThere
00378 
00379 
00380 }// end namespace cocoa#endif
00381 
00382 
00383 // RCS header/log on the next few lines
00384 // $Header: /Volumes/Home/cocoa/cvs-repository/CoCoALib-0.99/include/CoCoA/TmpIsTree.H,v 1.2 2007/03/27 15:27:05 bigatti Exp $
00385 // $Log: TmpIsTree.H,v $
00386 // Revision 1.2  2007/03/27 15:27:05  bigatti
00387 // -- minor update for TmpIsTree + test
00388 //
00389 // Revision 1.1.1.1  2007/03/09 15:16:11  abbott
00390 // Imported files
00391 //
00392 // Revision 1.7  2007/03/07 22:24:03  bigatti
00393 // -- reintroduced TmpGTypes.H (waiting for a better solution)
00394 //
00395 // Revision 1.6  2007/03/07 17:39:24  bigatti
00396 // -- fix for PolyList and VectorList
00397 //
00398 // Revision 1.5  2007/03/07 14:59:02  cocoa
00399 // -- renamed complex --> FacetComplex
00400 //
00401 // Revision 1.4  2006/11/24 17:35:22  cocoa
00402 // -- reorganized includes of header files
00403 //
00404 // Revision 1.3  2006/10/06 14:04:15  cocoa
00405 // Corrected position of #ifndef in header files.
00406 // Separated CoCoA_ASSERT into assert.H from config.H;
00407 // many minor consequential changes (have to #include assert.H).
00408 // A little tidying of #include directives (esp. in Max's code).
00409 //
00410 // Revision 1.2  2006/08/07 21:23:25  cocoa
00411 // Removed almost all publicly visible references to SmallExponent_t;
00412 // changed to long in all PPMonoid functions and SparsePolyRing functions.
00413 // DivMask remains to sorted out.
00414 //
00415 // Revision 1.1.1.1  2006/05/30 11:39:37  cocoa
00416 // Imported files
00417 //
00418 // Revision 1.1  2006/05/16 09:03:11  cocoa
00419 // -- first import
00420 //
00421 
00422 #endif

Generated on Wed May 23 13:43:36 2007 for CoCoALib by  doxygen 1.4.6