Changeset 1d9469 in git for kernel/gfan.cc


Ignore:
Timestamp:
Oct 1, 2009, 9:57:24 AM (15 years ago)
Author:
Martin Monerjan
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
418bd6de476ff6f8e0ea70a0de50d16f54b890d3
Parents:
ac6e45db1f490e638b067d932fc2c4100bc9526c
Message:
Definition of class gcone into gfan.h


git-svn-id: file:///usr/local/Singular/svn/trunk@12146 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed
  • kernel/gfan.cc

    rac6e45 r1d9469  
    22Compute the Groebner fan of an ideal
    33$Author: monerjan $
    4 $Date: 2009-10-01 07:15:49 $
    5 $Header: /exports/cvsroot-2/cvsroot/kernel/gfan.cc,v 1.92 2009-10-01 07:15:49 monerjan Exp $
    6 $Id: gfan.cc,v 1.92 2009-10-01 07:15:49 monerjan Exp $
     4$Date: 2009-10-01 07:57:24 $
     5$Header: /exports/cvsroot-2/cvsroot/kernel/gfan.cc,v 1.93 2009-10-01 07:57:24 monerjan Exp $
     6$Id: gfan.cc,v 1.93 2009-10-01 07:57:24 monerjan Exp $
    77*/
    88
     
    290290* @see facet
    291291*/
    292 /*class gcone
    293 finally this should become s.th. like gconelib.{h,cc} to provide an API
     292
     293
     294/** \brief Default constructor.
     295 *
     296 * Initialises this->next=NULL and this->facetPtr=NULL
     297 */
     298gcone::gcone()
     299{
     300        this->next=NULL;
     301        this->facetPtr=NULL;    //maybe this->facetPtr = new facet();                   
     302        this->baseRing=currRing;
     303        this->counter++;
     304        this->UCN=this->counter;                       
     305        this->numFacets=0;
     306        this->ivIntPt=NULL;
     307}
     308               
     309/** \brief Constructor with ring and ideal
     310 *
     311 * This constructor takes the root ring and the root ideal as parameters and stores
     312 * them in the private members gcone::rootRing and gcone::inputIdeal
     313 * Since knowledge of the root ring is only needed when using reverse search,
     314 * this constructor is not needed when using the "second" method
    294315*/
    295 class gcone
    296 {
    297         private:               
    298                 ring rootRing;          //good to know this -> generic walk
    299                 ideal inputIdeal;       //the original
    300                 ring baseRing;          //the basering of the cone             
    301                 /* TODO in order to save memory use pointers to rootRing and inputIdeal instead */
    302                 intvec *ivIntPt;        //an interior point of the cone
    303                 int UCN;                //unique number of the cone
    304                 static int counter;
    305                
    306         public:
    307                 /** \brief Pointer to the first facet */
    308                 facet *facetPtr;        //Will hold the adress of the first facet; set by gcone::getConeNormals
    309                
    310                 /** # of variables in the ring */
    311                 int numVars;            //#of variables in the ring
    312                
    313                 /** # of facets of the cone
    314                 * This value is set by gcone::getConeNormals
    315                 */
    316                 int numFacets;          //#of facets of the cone
    317                
    318                 /**
    319                 * At least as a workaround we store the irredundant facets of a matrix here.
    320                 * Otherwise, since we throw away non-flippable facets, facets2Matrix will not
    321                 * yield all the necessary information
    322                 */
    323                 dd_MatrixPtr ddFacets;  //Matrix to store irredundant facets of the cone
    324                
    325                 /** Contains the Groebner basis of the cone. Is set by gcone::getGB(ideal I)*/
    326                 ideal gcBasis;          //GB of the cone, set by gcone::getGB();
    327                 gcone *next;            //Pointer to *previous* cone in search tree     
    328                
    329                 /** \brief Default constructor.
    330                 *
    331                 * Initialises this->next=NULL and this->facetPtr=NULL
    332                 */
    333                 gcone()
    334                 {
    335                         this->next=NULL;
    336                         this->facetPtr=NULL;    //maybe this->facetPtr = new facet();                   
    337                         this->baseRing=currRing;
    338                         this->counter++;
    339                         this->UCN=this->counter;                       
    340                         this->numFacets=0;
    341                         this->ivIntPt=NULL;
    342                 }
    343                
    344                 /** \brief Constructor with ring and ideal
    345                 *
    346                 * This constructor takes the root ring and the root ideal as parameters and stores
    347                 * them in the private members gcone::rootRing and gcone::inputIdeal
    348                 * Since knowledge of the root ring is only needed when using reverse search,
    349                 * this constructor is not needed when using the "second" method
    350                 */
    351                 gcone(ring r, ideal I)
    352                 {
    353                         this->next=NULL;
    354                         this->facetPtr=NULL;                   
    355                         this->rootRing=r;
    356                         this->inputIdeal=I;
    357                         this->baseRing=currRing;
    358                         this->counter++;
    359                         this->UCN=this->counter;                       
    360                         this->numFacets=0;
    361                         this->ivIntPt=NULL;
    362                 }
    363                
    364                 /** \brief Copy constructor
    365                 *
    366                 * Copies a cone, sets this->gcBasis to the flipped GB
    367                 * Call this only after a successful call to gcone::flip which sets facet::flipGB
    368                 */             
    369                 gcone(const gcone& gc, const facet &f)
    370                 {
    371                         this->next=NULL;
    372                         this->numVars=gc.numVars;                                               
    373                         this->counter++;
    374                         this->UCN=this->counter;                       
    375                         this->facetPtr=NULL;
    376                         this->gcBasis=idCopy(f.flipGB);
    377                         this->inputIdeal=idCopy(this->gcBasis);
    378                         this->baseRing=rCopy(f.flipRing);
    379                         this->numFacets=0;
    380                         this->ivIntPt=NULL;
     316gcone::gcone(ring r, ideal I)
     317{
     318        this->next=NULL;
     319        this->facetPtr=NULL;                   
     320        this->rootRing=r;
     321        this->inputIdeal=I;
     322        this->baseRing=currRing;
     323        this->counter++;
     324        this->UCN=this->counter;                       
     325        this->numFacets=0;
     326        this->ivIntPt=NULL;
     327}
     328               
     329/** \brief Copy constructor
     330 *
     331 * Copies a cone, sets this->gcBasis to the flipped GB
     332 * Call this only after a successful call to gcone::flip which sets facet::flipGB
     333*/             
     334gcone::gcone(const gcone& gc, const facet &f)
     335{
     336        this->next=NULL;
     337        this->numVars=gc.numVars;                                               
     338        this->counter++;
     339        this->UCN=this->counter;                       
     340        this->facetPtr=NULL;
     341        this->gcBasis=idCopy(f.flipGB);
     342        this->inputIdeal=idCopy(this->gcBasis);
     343        this->baseRing=rCopy(f.flipRing);
     344        this->numFacets=0;
     345        this->ivIntPt=NULL;
    381346                        //rComplete(this->baseRing);
    382347                        //rChangeCurrRing(this->baseRing);
     348}
     349               
     350/** \brief Default destructor
     351*/
     352gcone::~gcone()
     353{
     354                        //NOTE SAVE THE FACET STRUCTURE!!!
     355}                       
     356               
     357/** \brief Set the interior point of a cone */
     358void gcone::setIntPoint(intvec *iv)
     359{
     360        this->ivIntPt=ivCopy(iv);
     361}
     362               
     363/** \brief Return the interior point */
     364intvec *gcone::getIntPoint()
     365{
     366        return this->ivIntPt;
     367}
     368               
     369/** \brief Print the interior point */
     370void gcone::showIntPoint()
     371{
     372        ivIntPt->show();
     373}
     374               
     375/** \brief Print facets
     376 * This is mainly for debugging purposes. Usually called from within gdb
     377 */
     378void gcone::showFacets(short codim)
     379{
     380        facet *f;
     381        switch(codim)
     382        {
     383                case 1:
     384                        f = this->facetPtr;
     385                        break;
     386                case 2:
     387                        f = this->facetPtr->codim2Ptr;
     388                        break;
     389        }                       
     390                       
     391        intvec *iv;                     
     392        while(f!=NULL)
     393        {
     394                iv = f->getFacetNormal();
     395                cout << "(";
     396                iv->show(1,0);                         
     397                if(f->isFlippable==FALSE)
     398                        cout << ")* ";
     399                else
     400                        cout << ") ";
     401                f=f->next;
     402        }
     403        cout << endl;
     404}
     405               
     406/** For debugging purposes only */
     407void gcone::showSLA(facet &f)
     408{
     409        facet *fAct;
     410        fAct = &f;
     411        facet *codim2Act;
     412        codim2Act = fAct->codim2Ptr;
     413        intvec *fNormal;// = new intvec(this->numVars);
     414        intvec *f2Normal;
     415        cout << endl;
     416        while(fAct!=NULL)
     417        {
     418                fNormal=fAct->getFacetNormal();
     419                cout << "(";
     420                fNormal->show(1,0);
     421                if(fAct->isFlippable==TRUE)
     422                        cout << ") ";
     423                else
     424                        cout << ")* ";
     425                codim2Act = fAct->codim2Ptr;
     426                cout << " Codim2: ";
     427                while(codim2Act!=NULL)
     428                {
     429                        f2Normal = codim2Act->getFacetNormal();
     430                        cout << "(";
     431                        f2Normal->show(1,0);
     432                        cout << ") ";
     433                        codim2Act = codim2Act->next;
    383434                }
    384                
    385                 /** \brief Default destructor
    386                 */
    387                 ~gcone()
    388                 {
    389                         //NOTE SAVE THE FACET STRUCTURE!!!
    390                 }                       
    391                
    392                 /** \brief Set the interior point of a cone */
    393                 void setIntPoint(intvec *iv)
    394                 {
    395                         this->ivIntPt=ivCopy(iv);
    396                 }
    397                
    398                 /** \brief Return the interior point */
    399                 intvec *getIntPoint()
    400                 {
    401                         return this->ivIntPt;
    402                 }
    403                
    404                 /** \brief Print the interior point */
    405                 void showIntPoint()
    406                 {
    407                         ivIntPt->show();
    408                 }
    409                
    410                 /** \brief Print facets
    411                 * This is mainly for debugging purposes. Usually called from within gdb
    412                 */
    413                 void showFacets(short codim=1)
    414                 {
    415                         facet *f;
    416                         switch(codim)
    417                         {
    418                                 case 1:
    419                                         f = this->facetPtr;
    420                                         break;
    421                                 case 2:
    422                                         f = this->facetPtr->codim2Ptr;
    423                                         break;
    424                         }                       
    425                        
    426                         intvec *iv;                     
    427                         while(f!=NULL)
    428                         {
    429                                 iv = f->getFacetNormal();
    430                                 cout << "(";
    431                                 iv->show(1,0);                         
    432                                 if(f->isFlippable==FALSE)
    433                                         cout << ")* ";
    434                                 else
    435                                         cout << ") ";
    436                                 f=f->next;
    437                         }
    438                         cout << endl;
    439                 }
    440                
    441                 /** For debugging purposes only */
    442                 void showSLA(facet &f)
    443                 {
    444                         facet *fAct;
    445                         fAct = &f;
    446                         facet *codim2Act;
    447                         codim2Act = fAct->codim2Ptr;
    448                         intvec *fNormal;// = new intvec(this->numVars);
    449                         intvec *f2Normal;
    450                         cout << endl;
    451                         while(fAct!=NULL)
    452                         {
    453                                 fNormal=fAct->getFacetNormal();
    454                                 cout << "(";
    455                                 fNormal->show(1,0);
    456                                 if(fAct->isFlippable==TRUE)
    457                                         cout << ") ";
    458                                 else
    459                                         cout << ")* ";
    460                                 codim2Act = fAct->codim2Ptr;
    461                                 cout << " Codim2: ";
    462                                 while(codim2Act!=NULL)
    463                                 {
    464                                         f2Normal = codim2Act->getFacetNormal();
    465                                         cout << "(";
    466                                         f2Normal->show(1,0);
    467                                         cout << ") ";
    468                                         codim2Act = codim2Act->next;
    469                                 }
    470                                 cout << "UCN = " << fAct->getUCN() << endl;                             
    471                                 fAct = fAct->next;
    472                         }
    473                 }
    474                
    475                 void idDebugPrint(ideal const &I)
    476                 {
    477                         int numElts=IDELEMS(I);
    478                         cout << "Ideal with " << numElts << " generators" << endl;
    479                         cout << "Leading terms: ";
    480                         for (int ii=0;ii<numElts;ii++)
    481                         {
    482                                 pWrite0(pHead(I->m[ii]));
    483                                 cout << ",";
    484                         }
    485                         cout << endl;
    486                 }
    487                
    488                 /** \brief Set gcone::numFacets */
    489                 void setNumFacets()
    490                 {
    491                 }
    492                
    493                 /** \brief Get gcone::numFacets */
    494                 int getNumFacets()
    495                 {
    496                         return this->numFacets;
    497                 }
    498                
    499                 int getUCN()
    500                 {
    501                         if(this!=NULL)
    502                                 return this->UCN;
    503                         else
    504                                 return -1;
    505                 }
    506                
    507                 /** \brief Compute the normals of the cone
    508                 *
    509                 * This method computes a representation of the cone in terms of facet normals. It takes an ideal
    510                 * as its input. Redundancies are automatically removed using cddlib's dd_MatrixCanonicalize.
    511                 * Other methods for redundancy checkings might be implemented later. See Anders' diss p.44.
    512                 * Note that in order to use cddlib a 0-th column has to be added to the matrix since cddlib expects
    513                 * each row to represent an inequality of type const+x1+...+xn <= 0. While computing the normals we come across
    514                 * the set \f$ \partial\mathcal{G} \f$ which we might store for later use. C.f p71 of journal
    515                 * As a result of this procedure the pointer facetPtr points to the first facet of the cone.
    516                 *
    517                 * Optionally, if the parameter bool compIntPoint is set to TRUE the method will also compute
    518                 * an interior point of the cone.
    519                 */
    520                 void getConeNormals(ideal const &I, bool compIntPoint=FALSE)
    521                 {
    522 #ifdef gfan_DEBUG
    523                         std::cout << "*** Computing Inequalities... ***" << std::endl;
     435                cout << "UCN = " << fAct->getUCN() << endl;                             
     436                fAct = fAct->next;
     437        }
     438}
     439               
     440void gcone::idDebugPrint(ideal const &I)
     441{
     442        int numElts=IDELEMS(I);
     443        cout << "Ideal with " << numElts << " generators" << endl;
     444        cout << "Leading terms: ";
     445        for (int ii=0;ii<numElts;ii++)
     446        {
     447                pWrite0(pHead(I->m[ii]));
     448                cout << ",";
     449        }
     450        cout << endl;
     451}
     452               
     453/** \brief Set gcone::numFacets */
     454void gcone::setNumFacets()
     455{
     456}
     457               
     458/** \brief Get gcone::numFacets */
     459int gcone::getNumFacets()
     460{
     461        return this->numFacets;
     462}
     463               
     464int gcone::getUCN()
     465{
     466        if(this!=NULL)
     467                return this->UCN;
     468        else
     469                return -1;
     470}
     471/** \brief Compute the normals of the cone
     472 *
     473 * This method computes a representation of the cone in terms of facet normals. It takes an ideal
     474 * as its input. Redundancies are automatically removed using cddlib's dd_MatrixCanonicalize.
     475 * Other methods for redundancy checkings might be implemented later. See Anders' diss p.44.
     476 * Note that in order to use cddlib a 0-th column has to be added to the matrix since cddlib expects
     477 * each row to represent an inequality of type const+x1+...+xn <= 0. While computing the normals we come across
     478 * the set \f$ \partial\mathcal{G} \f$ which we might store for later use. C.f p71 of journal
     479 * As a result of this procedure the pointer facetPtr points to the first facet of the cone.
     480 *
     481 * Optionally, if the parameter bool compIntPoint is set to TRUE the method will also compute
     482 * an interior point of the cone.
     483                 */
     484void gcone::getConeNormals(ideal const &I, bool compIntPoint)
     485{
     486#ifdef gfan_DEBUG
     487        std::cout << "*** Computing Inequalities... ***" << std::endl;
    524488#endif         
    525489                        //All variables go here - except ineq matrix and *v, see below
    526                         int lengthGB=IDELEMS(I);        // # of polys in the groebner basis
    527                         int pCompCount;                 // # of terms in a poly
    528                         poly aktpoly;
    529                         int numvar = pVariables;        // # of variables in a polynomial (or ring?)
    530                         int leadexp[numvar];            // dirty hack of exp.vects
    531                         int aktexp[numvar];
    532                         int cols,rows;                  // will contain the dimensions of the ineq matrix - deprecated by
    533                         dd_rowrange ddrows;
    534                         dd_colrange ddcols;
    535                         dd_rowset ddredrows;            // # of redundant rows in ddineq
    536                         dd_rowset ddlinset;             // the opposite
    537                         dd_rowindex ddnewpos;             // all to make dd_Canonicalize happy
    538                         dd_NumberType ddnumb=dd_Integer; //Number type
    539                         dd_ErrorType dderr=dd_NoError;  //
     490        int lengthGB=IDELEMS(I);        // # of polys in the groebner basis
     491        int pCompCount;                 // # of terms in a poly
     492        poly aktpoly;
     493        int numvar = pVariables;        // # of variables in a polynomial (or ring?)
     494        int leadexp[numvar];            // dirty hack of exp.vects
     495        int aktexp[numvar];
     496        int cols,rows;                  // will contain the dimensions of the ineq matrix - deprecated by
     497        dd_rowrange ddrows;
     498        dd_colrange ddcols;
     499        dd_rowset ddredrows;            // # of redundant rows in ddineq
     500        dd_rowset ddlinset;             // the opposite
     501        dd_rowindex ddnewpos;             // all to make dd_Canonicalize happy
     502        dd_NumberType ddnumb=dd_Integer; //Number type
     503        dd_ErrorType dderr=dd_NoError;  //
    540504                        // End of var declaration
    541505#ifdef gfan_DEBUG
     
    543507//                      cout << "The current ring has " << numvar << " variables" << endl;
    544508#endif
    545                         cols = numvar;
     509        cols = numvar;
    546510               
    547511                        //Compute the # inequalities i.e. rows of the matrix
    548                         rows=0; //Initialization
    549                         for (int ii=0;ii<IDELEMS(I);ii++)
    550                         {
    551                                 aktpoly=(poly)I->m[ii];
    552                                 rows=rows+pLength(aktpoly)-1;
    553                         }
     512        rows=0; //Initialization
     513        for (int ii=0;ii<IDELEMS(I);ii++)
     514        {
     515                aktpoly=(poly)I->m[ii];
     516                rows=rows+pLength(aktpoly)-1;
     517        }
    554518#ifdef gfan_DEBUG
    555519//                      cout << "rows=" << rows << endl;
    556520//                      cout << "Will create a " << rows << " x " << cols << " matrix to store inequalities" << endl;
    557521#endif
    558                         dd_rowrange aktmatrixrow=0;     // needed to store the diffs of the expvects in the rows of ddineq
    559                         dd_set_global_constants();
    560                         ddrows=rows;
    561                         ddcols=cols;
    562                         dd_MatrixPtr ddineq;            //Matrix to store the inequalities                     
    563                         ddineq=dd_CreateMatrix(ddrows,ddcols+1); //The first col has to be 0 since cddlib checks for additive consts there
     522        dd_rowrange aktmatrixrow=0;     // needed to store the diffs of the expvects in the rows of ddineq
     523        dd_set_global_constants();
     524        ddrows=rows;
     525        ddcols=cols;
     526        dd_MatrixPtr ddineq;            //Matrix to store the inequalities                     
     527        ddineq=dd_CreateMatrix(ddrows,ddcols+1); //The first col has to be 0 since cddlib checks for additive consts there
    564528               
    565529                        // We loop through each g\in GB and compute the resulting inequalities
    566                         for (int i=0; i<IDELEMS(I); i++)
    567                         {
    568                                 aktpoly=(poly)I->m[i];          //get aktpoly as i-th component of I
    569                                 pCompCount=pLength(aktpoly);    //How many terms does aktpoly consist of?
     530        for (int i=0; i<IDELEMS(I); i++)
     531        {
     532                aktpoly=(poly)I->m[i];          //get aktpoly as i-th component of I
     533                pCompCount=pLength(aktpoly);    //How many terms does aktpoly consist of?
    570534#ifdef gfan_DEBUG
    571535//                              cout << "Poly No. " << i << " has " << pCompCount << " components" << endl;
    572536#endif
    573537               
    574                                 int *v=(int *)omAlloc((numvar+1)*sizeof(int));
    575                                 pGetExpV(aktpoly,v);    //find the exp.vect in v[1],...,v[n], use pNext(p)
     538                int *v=(int *)omAlloc((numvar+1)*sizeof(int));
     539                pGetExpV(aktpoly,v);    //find the exp.vect in v[1],...,v[n], use pNext(p)
    576540                               
    577541                                //Store leadexp for aktpoly
    578                                 for (int kk=0;kk<numvar;kk++)
    579                                 {
    580                                         leadexp[kk]=v[kk+1];
     542                for (int kk=0;kk<numvar;kk++)
     543                {
     544                        leadexp[kk]=v[kk+1];
    581545                                        //Since we need to know the difference of leadexp with the other expvects we do nothing here
    582546                                        //but compute the diff below
    583                                 }
     547                }
    584548               
    585549                               
    586                                 while (pNext(aktpoly)!=NULL) //move to next term until NULL
    587                                 {
    588                                         aktpoly=pNext(aktpoly);
    589                                         pSetm(aktpoly);         //doesn't seem to help anything
    590                                         pGetExpV(aktpoly,v);
    591                                         for (int kk=0;kk<numvar;kk++)
    592                                         {
    593                                                 aktexp[kk]=v[kk+1];
     550                while (pNext(aktpoly)!=NULL) //move to next term until NULL
     551                {
     552                        aktpoly=pNext(aktpoly);
     553                        pSetm(aktpoly);         //doesn't seem to help anything
     554                        pGetExpV(aktpoly,v);
     555                        for (int kk=0;kk<numvar;kk++)
     556                        {
     557                                aktexp[kk]=v[kk+1];
    594558                                                //ineq[aktmatrixrow][kk]=leadexp[kk]-aktexp[kk];        //dito
    595                                                 dd_set_si(ddineq->matrix[(dd_rowrange)aktmatrixrow][kk+1],leadexp[kk]-aktexp[kk]); //because of the 1st col being const 0
    596                                         }
    597                                         aktmatrixrow=aktmatrixrow+1;
    598                                 }//while
    599                
    600                         } //for
     559                                dd_set_si(ddineq->matrix[(dd_rowrange)aktmatrixrow][kk+1],leadexp[kk]-aktexp[kk]); //because of the 1st col being const 0
     560                        }
     561                        aktmatrixrow=aktmatrixrow+1;
     562                }//while
     563               
     564        } //for
    601565               
    602566                        //Maybe add another row to contain the constraints of the standard simplex?
     
    609573                        // The inequalities are now stored in ddineq
    610574                        // Next we check for superflous rows
    611                         ddredrows = dd_RedundantRows(ddineq, &dderr);
    612                         if (dderr!=dd_NoError)                  // did an error occur?
    613                         {
    614                                 dd_WriteErrorMessages(stderr,dderr);    //if so tell us
    615                         }
    616 #ifdef gfan_DEBUG
    617                         else
    618                         {
     575        ddredrows = dd_RedundantRows(ddineq, &dderr);
     576        if (dderr!=dd_NoError)                  // did an error occur?
     577        {
     578                dd_WriteErrorMessages(stderr,dderr);    //if so tell us
     579        }
     580#ifdef gfan_DEBUG
     581        else
     582        {
    619583//                              cout << "Redundant rows: ";
    620584//                              set_fwrite(stdout, ddredrows);          //otherwise print the redundant rows
    621                         }//if dd_Error
     585        }//if dd_Error
    622586#endif
    623587                        //Remove reduntant rows here!
    624                         dd_MatrixCanonicalize(&ddineq, &ddlinset, &ddredrows, &ddnewpos, &dderr);
    625                         ddrows = ddineq->rowsize;       //Size of the matrix with redundancies removed
    626                         ddcols = ddineq->colsize;
     588        dd_MatrixCanonicalize(&ddineq, &ddlinset, &ddredrows, &ddnewpos, &dderr);
     589        ddrows = ddineq->rowsize;       //Size of the matrix with redundancies removed
     590        ddcols = ddineq->colsize;
    627591                       
    628592                        //ddCreateMatrix(ddrows,ddcols+1);
    629                         ddFacets = dd_CopyMatrix(ddineq);
     593        ddFacets = dd_CopyMatrix(ddineq);
    630594#ifdef gfan_DEBUG
    631595//                      cout << "Having removed redundancies, the normals now read:" << endl;
     
    635599#endif
    636600                       
    637                         /*Write the normals into class facet*/
     601        /*Write the normals into class facet*/
    638602#ifdef gfan_DEBUG
    639603//                      cout << "Creating list of normals" << endl;
    640604#endif
    641                         /*The pointer *fRoot should be the return value of this function*/
     605        /*The pointer *fRoot should be the return value of this function*/
    642606                        //facet *fRoot = new facet();   //instantiate new facet
    643607                        //fRoot->setUCN(this->getUCN());
    644608                        //this->facetPtr = fRoot;               //set variable facetPtr of class gcone to first facet
    645                         facet *fAct;                    //pointer to active facet
     609        facet *fAct;                    //pointer to active facet
    646610                        //fAct = fRoot;                 //Seems to do the trick. fRoot and fAct have to point to the same adress!
    647611                        //std::cout << "fRoot = " << fRoot << ", fAct = " << fAct << endl;
    648                         int numNonFlip=0;
    649                         for (int kk = 0; kk<ddrows; kk++)
    650                         {
    651                                 intvec *load = new intvec(this->numVars);       //intvec to store a single facet normal that will then be stored via setFacetNormal
    652                                 for (int jj = 1; jj <ddcols; jj++)
    653                                 {
    654                                         double foo;
    655                                         foo = mpq_get_d(ddineq->matrix[kk][jj]);
     612        int numNonFlip=0;
     613        for (int kk = 0; kk<ddrows; kk++)
     614        {
     615                intvec *load = new intvec(this->numVars);       //intvec to store a single facet normal that will then be stored via setFacetNormal
     616                for (int jj = 1; jj <ddcols; jj++)
     617                {
     618                        double foo;
     619                        foo = mpq_get_d(ddineq->matrix[kk][jj]);
    656620#ifdef gfan_DEBUG
    657621//                                      std::cout << "fAct is " << foo << " at " << fAct << std::endl;
    658622#endif
    659                                         (*load)[jj-1] = (int)foo;               //store typecasted entry at pos jj-1 of load           
    660                                 }//for (int jj = 1; jj <ddcols; jj++)
     623                        (*load)[jj-1] = (int)foo;               //store typecasted entry at pos jj-1 of load           
     624                }//for (int jj = 1; jj <ddcols; jj++)
    661625                               
    662                                 /*Quick'n'dirty hack for flippability*/
    663                                 bool isFlip=FALSE;
     626                /*Quick'n'dirty hack for flippability*/
     627                bool isFlip=FALSE;
    664628                                                               
    665                                 for (int jj = 0; jj<load->length(); jj++)
    666                                 {
    667                                         intvec *ivCanonical = new intvec(load->length());
    668                                         (*ivCanonical)[jj]=1;
     629                for (int jj = 0; jj<load->length(); jj++)
     630                {
     631                        intvec *ivCanonical = new intvec(load->length());
     632                        (*ivCanonical)[jj]=1;
    669633//                                      cout << "dotProd=" << dotProduct(*load,*ivCanonical) << endl;
    670                                         if (dotProduct(*load,*ivCanonical)<0)   
     634                        if (dotProduct(*load,*ivCanonical)<0)   
    671635                                        //if (ivMult(load,ivCanonical)<0)
    672                                         {
    673                                                 isFlip=TRUE;
    674                                                 break;  //URGHS
    675                                         }
    676                                 }       
    677                                 if (isFlip==FALSE)
    678                                 {
    679                                         this->numFacets++;
    680                                         numNonFlip++;
    681                                         if(this->numFacets==1)
    682                                         {
    683                                                 facet *fRoot = new facet();
    684                                                 this->facetPtr = fRoot;
    685                                                 fAct = fRoot;
     636                        {
     637                                isFlip=TRUE;
     638                                break;  //URGHS
     639                        }
     640                }       
     641                if (isFlip==FALSE)
     642                {
     643                        this->numFacets++;
     644                        numNonFlip++;
     645                        if(this->numFacets==1)
     646                        {
     647                                facet *fRoot = new facet();
     648                                this->facetPtr = fRoot;
     649                                fAct = fRoot;
    686650                                               
    687                                         }
    688                                         else
    689                                         {
    690                                                 fAct->next = new facet();
    691                                                 fAct = fAct->next;
    692                                         }
    693                                         fAct->isFlippable=FALSE;
    694                                         fAct->setFacetNormal(load);
    695                                         fAct->setUCN(this->getUCN());
    696 #ifdef gfan_DEBUG
    697                                         cout << "Marking facet (";
    698                                         load->show(1,0);
    699                                         cout << ") as non flippable" << endl;                           
    700 #endif
    701                                 }
    702                                 else
    703                                 {       /*Now load should be full and we can call setFacetNormal*/                                     
    704                                         this->numFacets++;
    705                                         if(this->numFacets==1)
    706                                         {
    707                                                 facet *fRoot = new facet();
    708                                                 this->facetPtr = fRoot;
    709                                                 fAct = fRoot;
    710                                         }
    711                                         else
    712                                         {
    713                                                 fAct->next = new facet();
    714                                                 fAct = fAct->next;
    715                                         }
    716                                         fAct->isFlippable=TRUE;
    717                                         fAct->setFacetNormal(load);
    718                                         fAct->setUCN(this->getUCN());                                   
    719                                 }//if (isFlippable==FALSE)
     651                        }
     652                        else
     653                        {
     654                                fAct->next = new facet();
     655                                fAct = fAct->next;
     656                        }
     657                        fAct->isFlippable=FALSE;
     658                        fAct->setFacetNormal(load);
     659                        fAct->setUCN(this->getUCN());
     660#ifdef gfan_DEBUG
     661                        cout << "Marking facet (";
     662                        load->show(1,0);
     663                        cout << ") as non flippable" << endl;                           
     664#endif
     665                }
     666                else
     667                {       /*Now load should be full and we can call setFacetNormal*/                                     
     668                        this->numFacets++;
     669                        if(this->numFacets==1)
     670                        {
     671                                facet *fRoot = new facet();
     672                                this->facetPtr = fRoot;
     673                                fAct = fRoot;
     674                        }
     675                        else
     676                        {
     677                                fAct->next = new facet();
     678                                fAct = fAct->next;
     679                        }
     680                        fAct->isFlippable=TRUE;
     681                        fAct->setFacetNormal(load);
     682                        fAct->setUCN(this->getUCN());                                   
     683                }//if (isFlippable==FALSE)
    720684                                //delete load;                         
    721                         }//for (int kk = 0; kk<ddrows; kk++)
     685        }//for (int kk = 0; kk<ddrows; kk++)
    722686                       
    723687                        //In cases like I=<x-1,y-1> there are only non-flippable facets...
    724                         if(numNonFlip==this->numFacets)
    725                         {                                       
    726                                 cerr << "Only non-flippable facets. Terminating..." << endl;
    727                         }
     688        if(numNonFlip==this->numFacets)
     689        {                                       
     690                cerr << "Only non-flippable facets. Terminating..." << endl;
     691        }
    728692                       
    729693                        /*
    730                         Now we should have a linked list containing the facet normals of those facets that are
    731                         -irredundant
    732                         -flipable
    733                         Adressing is done via *facetPtr
     694        Now we should have a linked list containing the facet normals of those facets that are
     695        -irredundant
     696        -flipable
     697        Adressing is done via *facetPtr
    734698                        */
    735699                       
    736                         if (compIntPoint==TRUE)
    737                         {
    738                                 intvec *iv = new intvec(this->numVars);
    739                                 dd_MatrixPtr posRestr=dd_CreateMatrix(this->numVars,this->numVars+1);
    740                                 int jj=1;
    741                                 for (int ii=0;ii<=this->numVars;ii++)
    742                                 {
    743                                         dd_set_si(posRestr->matrix[ii][jj],1);
    744                                         jj++;                                                   
    745                                 }
    746                                 dd_MatrixAppendTo(&ddineq,posRestr);
    747                                 interiorPoint(ddineq, *iv);     //NOTE ddineq contains non-flippable facets
    748                                 this->setIntPoint(iv);  //stores the interior point in gcone::ivIntPt
     700        if (compIntPoint==TRUE)
     701        {
     702                intvec *iv = new intvec(this->numVars);
     703                dd_MatrixPtr posRestr=dd_CreateMatrix(this->numVars,this->numVars+1);
     704                int jj=1;
     705                for (int ii=0;ii<=this->numVars;ii++)
     706                {
     707                        dd_set_si(posRestr->matrix[ii][jj],1);
     708                        jj++;                                                   
     709                }
     710                dd_MatrixAppendTo(&ddineq,posRestr);
     711                interiorPoint(ddineq, *iv);     //NOTE ddineq contains non-flippable facets
     712                this->setIntPoint(iv);  //stores the interior point in gcone::ivIntPt
    749713                                //delete iv;
    750                         }
     714        }
    751715                       
    752716                        //Compute the number of facets
     
    764728                        //dd_free_global_constants();
    765729
    766                 }//method getConeNormals(ideal I)       
    767                
    768                 /** \brief Compute the (codim-2)-facets of a given cone
    769                 * This method is used during noRevS
    770                 * Additionally we check whether the codim2-facet normal is strictly positive. Otherwise
    771                 * the facet is marked as non-flippable.
    772                 */
    773                 void getCodim2Normals(gcone const &gc)
    774                 {
     730}//method getConeNormals(ideal I)       
     731               
     732/** \brief Compute the (codim-2)-facets of a given cone
     733 * This method is used during noRevS
     734 * Additionally we check whether the codim2-facet normal is strictly positive. Otherwise
     735 * the facet is marked as non-flippable.
     736 */
     737void gcone::getCodim2Normals(gcone const &gc)
     738{
    775739                        //this->facetPtr->codim2Ptr = new facet(2);     //instantiate a (codim-2)-facet
    776                         facet *fAct;
    777                         fAct = this->facetPtr;         
    778                         facet *codim2Act;
     740        facet *fAct;
     741        fAct = this->facetPtr;         
     742        facet *codim2Act;
    779743                        //codim2Act = this->facetPtr->codim2Ptr;
    780744                       
    781                         dd_set_global_constants();
    782                        
    783                         dd_MatrixPtr ddineq,P,ddakt;
    784                         dd_rowset impl_linset, redset;
    785                         dd_ErrorType err;
    786                         dd_rowindex newpos;             
     745        dd_set_global_constants();
     746                       
     747        dd_MatrixPtr ddineq,P,ddakt;
     748        dd_rowset impl_linset, redset;
     749        dd_ErrorType err;
     750        dd_rowindex newpos;             
    787751
    788752                        //ddineq = facets2Matrix(gc);   //get a matrix representation of the cone
    789                         ddineq = dd_CopyMatrix(gc.ddFacets);
     753        ddineq = dd_CopyMatrix(gc.ddFacets);
    790754                               
    791                         /*Now set appropriate linearity*/
    792                         dd_PolyhedraPtr ddpolyh;
    793                         for (int ii=0; ii<this->numFacets; ii++)                       
    794                         {                               
    795                                 ddakt = dd_CopyMatrix(ddineq);
    796                                 ddakt->representation=dd_Inequality;
    797                                 set_addelem(ddakt->linset,ii+1);                               
    798                                 dd_MatrixCanonicalize(&ddakt, &impl_linset, &redset, &newpos, &err);                   
     755        /*Now set appropriate linearity*/
     756        dd_PolyhedraPtr ddpolyh;
     757        for (int ii=0; ii<this->numFacets; ii++)                       
     758        {                               
     759                ddakt = dd_CopyMatrix(ddineq);
     760                ddakt->representation=dd_Inequality;
     761                set_addelem(ddakt->linset,ii+1);                               
     762                dd_MatrixCanonicalize(&ddakt, &impl_linset, &redset, &newpos, &err);                   
    799763                                       
    800764#ifdef gfan_DEBUG
     
    802766//                              dd_WriteMatrix(stdout,ddakt);
    803767#endif
    804                                 ddpolyh=dd_DDMatrix2Poly(ddakt, &err);
    805                                 P=dd_CopyGenerators(ddpolyh);                           
     768                ddpolyh=dd_DDMatrix2Poly(ddakt, &err);
     769                P=dd_CopyGenerators(ddpolyh);                           
    806770#ifdef gfan_DEBUG
    807771//                              cout << "Codim2 facet:" << endl;
     
    810774#endif
    811775                                       
    812                                 /* We loop through each row of P
    813                                 * normalize it by making all entries integer ones
    814                                 * and add the resulting vector to the int matrix facet::codim2Facets
    815                                 */
    816                                 for (int jj=1;jj<=P->rowsize;jj++)
    817                                 {                                       
    818                                         fAct->numCodim2Facets++;
    819                                         if(fAct->numCodim2Facets==1)                                   
    820                                         {                                               
    821                                                 fAct->codim2Ptr = new facet(2);                                         
    822                                                 codim2Act = fAct->codim2Ptr;
    823                                         }
    824                                         else
    825                                         {
    826                                                 codim2Act->next = new facet(2);
    827                                                 codim2Act = codim2Act->next;
    828                                         }
    829                                         intvec *n = new intvec(this->numVars);
    830                                         makeInt(P,jj,*n);
    831                                         codim2Act->setFacetNormal(n);
    832                                         delete n;                                       
    833                                 }               
    834                                 /*We check whether the facet spanned by the codim-2 facets
    835                                 * intersects with the positive orthant. Otherwise we define this
    836                                 * facet to be non-flippable
    837                                 */
    838                                 intvec *iv_intPoint = new intvec(this->numVars);
    839                                 dd_MatrixPtr shiftMatrix;
    840                                 dd_MatrixPtr intPointMatrix;
    841                                 shiftMatrix = dd_CreateMatrix(this->numVars,this->numVars+1);
    842                                 for(int kk=0;kk<this->numVars;kk++)
    843                                 {
    844                                         dd_set_si(shiftMatrix->matrix[kk][0],1);
    845                                         dd_set_si(shiftMatrix->matrix[kk][kk+1],1);
    846                                 }
    847                                 intPointMatrix=dd_MatrixAppend(ddakt,shiftMatrix);
     776                /* We loop through each row of P
     777                * normalize it by making all entries integer ones
     778                * and add the resulting vector to the int matrix facet::codim2Facets
     779                */
     780                for (int jj=1;jj<=P->rowsize;jj++)
     781                {                                       
     782                        fAct->numCodim2Facets++;
     783                        if(fAct->numCodim2Facets==1)                                   
     784                        {                                               
     785                                fAct->codim2Ptr = new facet(2);                                         
     786                                codim2Act = fAct->codim2Ptr;
     787                        }
     788                        else
     789                        {
     790                                codim2Act->next = new facet(2);
     791                                codim2Act = codim2Act->next;
     792                        }
     793                        intvec *n = new intvec(this->numVars);
     794                        makeInt(P,jj,*n);
     795                        codim2Act->setFacetNormal(n);
     796                        delete n;                                       
     797                }               
     798                /*We check whether the facet spanned by the codim-2 facets
     799                * intersects with the positive orthant. Otherwise we define this
     800                * facet to be non-flippable
     801                */
     802                intvec *iv_intPoint = new intvec(this->numVars);
     803                dd_MatrixPtr shiftMatrix;
     804                dd_MatrixPtr intPointMatrix;
     805                shiftMatrix = dd_CreateMatrix(this->numVars,this->numVars+1);
     806                for(int kk=0;kk<this->numVars;kk++)
     807                {
     808                        dd_set_si(shiftMatrix->matrix[kk][0],1);
     809                        dd_set_si(shiftMatrix->matrix[kk][kk+1],1);
     810                }
     811                intPointMatrix=dd_MatrixAppend(ddakt,shiftMatrix);
    848812                                //dd_WriteMatrix(stdout,intPointMatrix);
    849                                 interiorPoint(intPointMatrix,*iv_intPoint);
    850                                 for(int ll=0;ll<this->numVars;ll++)
    851                                 {
    852                                         if( (*iv_intPoint)[ll] < 0 )
    853                                         {
    854                                                 fAct->isFlippable=FALSE;
    855                                                 break;
    856                                         }
    857                                 }
    858                                 /*End of check*/                                       
    859                                 fAct = fAct->next;     
    860                                 dd_FreeMatrix(ddakt);
    861                                 dd_FreePolyhedra(ddpolyh);
    862                                 delete iv_intPoint;
    863                         }//while
     813                interiorPoint(intPointMatrix,*iv_intPoint);
     814                for(int ll=0;ll<this->numVars;ll++)
     815                {
     816                        if( (*iv_intPoint)[ll] < 0 )
     817                        {
     818                                fAct->isFlippable=FALSE;
     819                                break;
     820                        }
    864821                }
    865                
    866                 /** \brief Compute the Groebner Basis on the other side of a shared facet
    867                 *
    868                 * Implements algorithm 4.3.2 from Anders' thesis.
    869                 * As shown there it is not necessary to compute an interior point. The knowledge of the facet normal
    870                 * suffices. A term \f$ x^\gamma \f$ of \f$ g \f$ is in \f$  in_\omega(g) \f$ iff \f$ \gamma - leadexp(g)\f$
    871                 * is parallel to \f$ leadexp(g) \f$
    872                 * Parallelity is checked using basic linear algebra. See gcone::isParallel.
    873                 * Other possibilities include computing the rank of the matrix consisting of the vectors in question and
    874                 * computing an interior point of the facet and taking all terms having the same weight with respect
    875                 * to this interior point.
    876                 *\param ideal, facet
    877                 * Input: a marked,reduced Groebner basis and a facet
    878                 */
    879                 void flip(ideal gb, facet *f)           //Compute "the other side"
    880                 {                       
    881                         intvec *fNormal = new intvec(this->numVars);    //facet normal, check for parallelity                   
    882                         fNormal = f->getFacetNormal();  //read this->fNormal;
     822                /*End of check*/                                       
     823                fAct = fAct->next;     
     824                dd_FreeMatrix(ddakt);
     825                dd_FreePolyhedra(ddpolyh);
     826                delete iv_intPoint;
     827        }//while
     828}
     829               
     830/** \brief Compute the Groebner Basis on the other side of a shared facet
     831 *
     832 * Implements algorithm 4.3.2 from Anders' thesis.
     833 * As shown there it is not necessary to compute an interior point. The knowledge of the facet normal
     834 * suffices. A term \f$ x^\gamma \f$ of \f$ g \f$ is in \f$  in_\omega(g) \f$ iff \f$ \gamma - leadexp(g)\f$
     835 * is parallel to \f$ leadexp(g) \f$
     836 * Parallelity is checked using basic linear algebra. See gcone::isParallel.
     837 * Other possibilities include computing the rank of the matrix consisting of the vectors in question and
     838 * computing an interior point of the facet and taking all terms having the same weight with respect
     839 * to this interior point.
     840 *\param ideal, facet
     841 * Input: a marked,reduced Groebner basis and a facet
     842 */
     843void gcone::flip(ideal gb, facet *f)            //Compute "the other side"
     844{                       
     845        intvec *fNormal = new intvec(this->numVars);    //facet normal, check for parallelity                   
     846        fNormal = f->getFacetNormal();  //read this->fNormal;
    883847#ifdef gfan_DEBUG
    884848                        //std::cout << "===" << std::endl;
    885                         std::cout << "running gcone::flip" << std::endl;
    886                         std::cout << "flipping UCN " << this->getUCN() << endl;
     849        std::cout << "running gcone::flip" << std::endl;
     850        std::cout << "flipping UCN " << this->getUCN() << endl;
    887851//                      for(int ii=0;ii<IDELEMS(gb);ii++)       //not very handy with large examples
    888852//                      {
    889853//                              pWrite((poly)gb->m[ii]);
    890854//                      }
    891                         cout << "over facet (";
    892                         fNormal->show(1,0);
    893                         cout << ") with UCN " << f->getUCN();
    894                         std::cout << std::endl;
     855        cout << "over facet (";
     856        fNormal->show(1,0);
     857        cout << ") with UCN " << f->getUCN();
     858        std::cout << std::endl;
    895859#endif                         
    896                         /*1st step: Compute the initial ideal*/
    897                         poly initialFormElement[IDELEMS(gb)];   //array of #polys in GB to store initial form
    898                         ideal initialForm=idInit(IDELEMS(gb),this->gcBasis->rank);
    899                         poly aktpoly;
    900                         intvec *check = new intvec(this->numVars);      //array to store the difference of LE and v
    901                        
    902                         for (int ii=0;ii<IDELEMS(gb);ii++)
    903                         {
    904                                 aktpoly = (poly)gb->m[ii];                                                             
    905                                 int *v=(int *)omAlloc((this->numVars+1)*sizeof(int));
    906                                 int *leadExpV=(int *)omAlloc((this->numVars+1)*sizeof(int));
    907                                 pGetExpV(aktpoly,leadExpV);     //find the leading exponent in leadExpV[1],...,leadExpV[n], use pNext(p)
    908                                 initialFormElement[ii]=pHead(aktpoly);
     860        /*1st step: Compute the initial ideal*/
     861        poly initialFormElement[IDELEMS(gb)];   //array of #polys in GB to store initial form
     862        ideal initialForm=idInit(IDELEMS(gb),this->gcBasis->rank);
     863        poly aktpoly;
     864        intvec *check = new intvec(this->numVars);      //array to store the difference of LE and v
     865                       
     866        for (int ii=0;ii<IDELEMS(gb);ii++)
     867        {
     868                aktpoly = (poly)gb->m[ii];                                                             
     869                int *v=(int *)omAlloc((this->numVars+1)*sizeof(int));
     870                int *leadExpV=(int *)omAlloc((this->numVars+1)*sizeof(int));
     871                pGetExpV(aktpoly,leadExpV);     //find the leading exponent in leadExpV[1],...,leadExpV[n], use pNext(p)
     872                initialFormElement[ii]=pHead(aktpoly);
    909873                               
    910                                 while(pNext(aktpoly)!=NULL)     /*loop trough terms and check for parallelity*/
    911                                 {
    912                                         aktpoly=pNext(aktpoly); //next term
    913                                         pSetm(aktpoly);
    914                                         pGetExpV(aktpoly,v);           
    915                                         /* Convert (int)v into (intvec)check */                 
    916                                         for (int jj=0;jj<this->numVars;jj++)
    917                                         {
     874                while(pNext(aktpoly)!=NULL)     /*loop trough terms and check for parallelity*/
     875                {
     876                        aktpoly=pNext(aktpoly); //next term
     877                        pSetm(aktpoly);
     878                        pGetExpV(aktpoly,v);           
     879                        /* Convert (int)v into (intvec)check */                 
     880                        for (int jj=0;jj<this->numVars;jj++)
     881                        {
    918882                                                //cout << "v["<<jj+1<<"]="<<v[jj+1]<<endl;
    919883                                                //cout << "leadExpV["<<jj+1<<"]="<<leadExpV[jj+1]<<endl;
    920                                                 (*check)[jj]=v[jj+1]-leadExpV[jj+1];
    921                                         }
     884                                (*check)[jj]=v[jj+1]-leadExpV[jj+1];
     885                        }
    922886#ifdef gfan_DEBUG
    923887//                                      cout << "check=";                       
     
    926890#endif
    927891                                        //TODO why not *check, *fNormal????
    928                                         if (isParallel(*check,*fNormal)) //pass *check when
    929                                         {
     892                        if (isParallel(*check,*fNormal)) //pass *check when
     893                        {
    930894//                                              cout << "Parallel vector found, adding to initialFormElement" << endl;                 
    931                                                 initialFormElement[ii] = pAdd(pCopy(initialFormElement[ii]),(poly)pHead(aktpoly));
    932                                         }                                               
    933                                 }//while
     895                                initialFormElement[ii] = pAdd(pCopy(initialFormElement[ii]),(poly)pHead(aktpoly));
     896                        }                                               
     897                }//while
    934898#ifdef gfan_DEBUG
    935899//                              cout << "Initial Form=";                               
     
    937901//                              cout << "---" << endl;
    938902#endif
    939                                 /*Now initialFormElement must be added to (ideal)initialForm */
    940                                 initialForm->m[ii]=initialFormElement[ii];
    941                         }//for                 
     903                /*Now initialFormElement must be added to (ideal)initialForm */
     904                initialForm->m[ii]=initialFormElement[ii];
     905        }//for                 
    942906#ifdef gfan_DEBUG
    943907/*                      cout << "Initial ideal is: " << endl;
    944                         idShow(initialForm);
    945                         //f->printFlipGB();*/
     908        idShow(initialForm);
     909        //f->printFlipGB();*/
    946910//                      cout << "===" << endl;
    947911#endif
    948912                        //delete check;
    949913                       
    950                         /*2nd step: lift initial ideal to a GB of the neighbouring cone using minus alpha as weight*/
     914        /*2nd step: lift initial ideal to a GB of the neighbouring cone using minus alpha as weight*/
    951915                        /*Substep 2.1
    952                         compute $G_{-\alpha}(in_v(I))
    953                         see journal p. 66
    954                         NOTE Check for different rings. Prolly it will not always be necessary to add a weight, if the
    955                         srcRing already has a weighted ordering
     916        compute $G_{-\alpha}(in_v(I))
     917        see journal p. 66
     918        NOTE Check for different rings. Prolly it will not always be necessary to add a weight, if the
     919        srcRing already has a weighted ordering
    956920                        */
    957                         ring srcRing=currRing;
    958                         ring tmpRing;
    959                        
    960                         if( (srcRing->order[0]!=ringorder_a))
    961                         {
    962                                 tmpRing=rCopyAndAddWeight(srcRing,ivNeg(fNormal));
    963                         }
    964                         else
    965                         {
    966                                 tmpRing=rCopy0(srcRing);
    967                                 int length=fNormal->length();
    968                                 int *A=(int *)omAlloc0(length*sizeof(int));
    969                                 for(int jj=0;jj<length;jj++)
    970                                 {
    971                                         A[jj]=-(*fNormal)[jj];
    972                                 }
    973                                 omFree(tmpRing->wvhdl[0]);
    974                                 tmpRing->wvhdl[0]=(int*)A;
    975                                 tmpRing->block1[0]=length;
    976                                 rComplete(tmpRing);     
    977                         }
    978                         rChangeCurrRing(tmpRing);
     921        ring srcRing=currRing;
     922        ring tmpRing;
     923                       
     924        if( (srcRing->order[0]!=ringorder_a))
     925        {
     926                tmpRing=rCopyAndAddWeight(srcRing,ivNeg(fNormal));
     927        }
     928        else
     929        {
     930                tmpRing=rCopy0(srcRing);
     931                int length=fNormal->length();
     932                int *A=(int *)omAlloc0(length*sizeof(int));
     933                for(int jj=0;jj<length;jj++)
     934                {
     935                        A[jj]=-(*fNormal)[jj];
     936                }
     937                omFree(tmpRing->wvhdl[0]);
     938                tmpRing->wvhdl[0]=(int*)A;
     939                tmpRing->block1[0]=length;
     940                rComplete(tmpRing);     
     941        }
     942        rChangeCurrRing(tmpRing);
    979943                       
    980944                        //rWrite(currRing); cout << endl;
    981945                       
    982                         ideal ina;                     
    983                         ina=idrCopyR(initialForm,srcRing);                     
     946        ideal ina;                     
     947        ina=idrCopyR(initialForm,srcRing);                     
    984948#ifdef gfan_DEBUG
    985949//                      cout << "ina=";
    986950//                      idShow(ina); cout << endl;
    987951#endif
    988                         ideal H;
     952        ideal H;
    989953                        //H=kStd(ina,NULL,isHomog,NULL);        //we know it is homogeneous
    990                         H=kStd(ina,NULL,testHomog,NULL);
    991                         idSkipZeroes(H);
     954        H=kStd(ina,NULL,testHomog,NULL);
     955        idSkipZeroes(H);
    992956#ifdef gfan_DEBUG
    993957//                      cout << "H="; idShow(H); cout << endl;
    994958#endif
    995959                        /*Substep 2.2
    996                         do the lifting and mark according to H
     960        do the lifting and mark according to H
    997961                        */
    998                         rChangeCurrRing(srcRing);
    999                         ideal srcRing_H;
    1000                         ideal srcRing_HH;                       
    1001                         srcRing_H=idrCopyR(H,tmpRing);
     962        rChangeCurrRing(srcRing);
     963        ideal srcRing_H;
     964        ideal srcRing_HH;                       
     965        srcRing_H=idrCopyR(H,tmpRing);
    1002966#ifdef gfan_DEBUG
    1003967//                      cout << "srcRing_H = ";
    1004968//                      idShow(srcRing_H); cout << endl;
    1005969#endif
    1006                         srcRing_HH=ffG(srcRing_H,this->gcBasis);               
     970        srcRing_HH=ffG(srcRing_H,this->gcBasis);               
    1007971#ifdef gfan_DEBUG
    1008972//                      cout << "srcRing_HH = ";
     
    1010974#endif
    1011975                        /*Substep 2.2.1
    1012                         Mark according to G_-\alpha
    1013                         Here we have a minimal basis srcRing_HH. In order to turn this basis into a reduced basis
    1014                         we have to compute an interior point of C(srcRing_HH). For this we need to know the cone
    1015                         represented by srcRing_HH MARKED ACCORDING TO G_{-\alpha}
    1016                         Thus we check whether the leading monomials of srcRing_HH and srcRing_H coincide. If not we
    1017                         compute the difference accordingly
     976        Mark according to G_-\alpha
     977        Here we have a minimal basis srcRing_HH. In order to turn this basis into a reduced basis
     978        we have to compute an interior point of C(srcRing_HH). For this we need to know the cone
     979        represented by srcRing_HH MARKED ACCORDING TO G_{-\alpha}
     980        Thus we check whether the leading monomials of srcRing_HH and srcRing_H coincide. If not we
     981        compute the difference accordingly
    1018982                        */
    1019                         dd_set_global_constants();
    1020                         bool markingsAreCorrect=FALSE;
    1021                         dd_MatrixPtr intPointMatrix;
    1022                         int iPMatrixRows=0;
    1023                         dd_rowrange aktrow=0;                   
    1024                         for (int ii=0;ii<IDELEMS(srcRing_HH);ii++)
    1025                         {
    1026                                 poly aktpoly=(poly)srcRing_HH->m[ii];
    1027                                 iPMatrixRows = iPMatrixRows+pLength(aktpoly)-1;
    1028                         }
     983        dd_set_global_constants();
     984        bool markingsAreCorrect=FALSE;
     985        dd_MatrixPtr intPointMatrix;
     986        int iPMatrixRows=0;
     987        dd_rowrange aktrow=0;                   
     988        for (int ii=0;ii<IDELEMS(srcRing_HH);ii++)
     989        {
     990                poly aktpoly=(poly)srcRing_HH->m[ii];
     991                iPMatrixRows = iPMatrixRows+pLength(aktpoly)-1;
     992        }
    1029993                        /* additionally one row for the standard-simplex and another for a row that becomes 0 during
    1030                         construction of the differences
     994        construction of the differences
    1031995                        */
    1032                         intPointMatrix = dd_CreateMatrix(iPMatrixRows+10,this->numVars+1); //iPMatrixRows+10;
    1033                         intPointMatrix->numbtype=dd_Integer;    //NOTE: DO NOT REMOVE OR CHANGE TO dd_Rational
    1034                        
    1035                         for (int ii=0;ii<IDELEMS(srcRing_HH);ii++)
    1036                         {
    1037                                 markingsAreCorrect=FALSE;       //crucial to initialise here
    1038                                 poly aktpoly=srcRing_HH->m[ii];
    1039                                 /*Comparison of leading monomials is done via exponent vectors*/
    1040                                 for (int jj=0;jj<IDELEMS(H);jj++)
     996        intPointMatrix = dd_CreateMatrix(iPMatrixRows+10,this->numVars+1); //iPMatrixRows+10;
     997        intPointMatrix->numbtype=dd_Integer;    //NOTE: DO NOT REMOVE OR CHANGE TO dd_Rational
     998                       
     999        for (int ii=0;ii<IDELEMS(srcRing_HH);ii++)
     1000        {
     1001                markingsAreCorrect=FALSE;       //crucial to initialise here
     1002                poly aktpoly=srcRing_HH->m[ii];
     1003                /*Comparison of leading monomials is done via exponent vectors*/
     1004                for (int jj=0;jj<IDELEMS(H);jj++)
     1005                {
     1006                        int *src_ExpV = (int *)omAlloc((this->numVars+1)*sizeof(int));
     1007                        int *dst_ExpV = (int *)omAlloc((this->numVars+1)*sizeof(int));
     1008                        pGetExpV(aktpoly,src_ExpV);
     1009                        rChangeCurrRing(tmpRing);       //this ring change is crucial!
     1010                        pGetExpV(pCopy(H->m[ii]),dst_ExpV);
     1011                        rChangeCurrRing(srcRing);
     1012                        bool expVAreEqual=TRUE;
     1013                        for (int kk=1;kk<=this->numVars;kk++)
     1014                        {
     1015#ifdef gfan_DEBUG
     1016                                                //cout << src_ExpV[kk] << "," << dst_ExpV[kk] << endl;
     1017#endif
     1018                                if (src_ExpV[kk]!=dst_ExpV[kk])
    10411019                                {
    1042                                         int *src_ExpV = (int *)omAlloc((this->numVars+1)*sizeof(int));
    1043                                         int *dst_ExpV = (int *)omAlloc((this->numVars+1)*sizeof(int));
    1044                                         pGetExpV(aktpoly,src_ExpV);
    1045                                         rChangeCurrRing(tmpRing);       //this ring change is crucial!
    1046                                         pGetExpV(pCopy(H->m[ii]),dst_ExpV);
    1047                                         rChangeCurrRing(srcRing);
    1048                                         bool expVAreEqual=TRUE;
    1049                                         for (int kk=1;kk<=this->numVars;kk++)
    1050                                         {
    1051 #ifdef gfan_DEBUG
    1052                                                 //cout << src_ExpV[kk] << "," << dst_ExpV[kk] << endl;
    1053 #endif
    1054                                                 if (src_ExpV[kk]!=dst_ExpV[kk])
    1055                                                 {
    1056                                                         expVAreEqual=FALSE;
    1057                                                 }
    1058                                         }                                       
     1020                                        expVAreEqual=FALSE;
     1021                                }
     1022                        }                                       
    10591023                                        //if (*src_ExpV == *dst_ExpV)
    1060                                         if (expVAreEqual==TRUE)
    1061                                         {
    1062                                                 markingsAreCorrect=TRUE; //everything is fine
     1024                        if (expVAreEqual==TRUE)
     1025                        {
     1026                                markingsAreCorrect=TRUE; //everything is fine
    10631027#ifdef gfan_DEBUG
    10641028//                                              cout << "correct markings" << endl;
    10651029#endif
    1066                                         }//if (pHead(aktpoly)==pHead(H->m[jj])
    1067                                         delete src_ExpV;
    1068                                         delete dst_ExpV;
    1069                                 }//for (int jj=0;jj<IDELEMS(H);jj++)
     1030                        }//if (pHead(aktpoly)==pHead(H->m[jj])
     1031                        delete src_ExpV;
     1032                        delete dst_ExpV;
     1033                }//for (int jj=0;jj<IDELEMS(H);jj++)
    10701034                               
    1071                                 int *v=(int *)omAlloc((this->numVars+1)*sizeof(int));
    1072                                 int *leadExpV=(int *)omAlloc((this->numVars+1)*sizeof(int));
    1073                                 if (markingsAreCorrect==TRUE)
    1074                                 {
    1075                                         pGetExpV(aktpoly,leadExpV);
    1076                                 }
    1077                                 else
    1078                                 {
    1079                                         rChangeCurrRing(tmpRing);
    1080                                         pGetExpV(pHead(H->m[ii]),leadExpV); //We use H->m[ii] as leading monomial
    1081                                         rChangeCurrRing(srcRing);
    1082                                 }
    1083                                 /*compute differences of the expvects*/                         
    1084                                 while (pNext(aktpoly)!=NULL)
    1085                                 {
     1035                int *v=(int *)omAlloc((this->numVars+1)*sizeof(int));
     1036                int *leadExpV=(int *)omAlloc((this->numVars+1)*sizeof(int));
     1037                if (markingsAreCorrect==TRUE)
     1038                {
     1039                        pGetExpV(aktpoly,leadExpV);
     1040                }
     1041                else
     1042                {
     1043                        rChangeCurrRing(tmpRing);
     1044                        pGetExpV(pHead(H->m[ii]),leadExpV); //We use H->m[ii] as leading monomial
     1045                        rChangeCurrRing(srcRing);
     1046                }
     1047                /*compute differences of the expvects*/                         
     1048                while (pNext(aktpoly)!=NULL)
     1049                {
    10861050                                        /*The following if-else-block makes sure the first term (i.e. the wrongly marked term)
    1087                                         is not omitted when computing the differences*/
    1088                                         if(markingsAreCorrect==TRUE)
    1089                                         {
    1090                                                 aktpoly=pNext(aktpoly);
    1091                                                 pGetExpV(aktpoly,v);
    1092                                         }
    1093                                         else
    1094                                         {
    1095                                                 pGetExpV(pHead(aktpoly),v);
    1096                                                 markingsAreCorrect=TRUE;
    1097                                         }
    1098 
    1099                                         for (int jj=0;jj<this->numVars;jj++)
    1100                                         {                               
    1101                                                 /*Store into ddMatrix*/                                                         
    1102                                                 dd_set_si(intPointMatrix->matrix[aktrow][jj+1],leadExpV[jj+1]-v[jj+1]);
    1103                                         }
    1104                                         aktrow +=1;
    1105                                 }
    1106                                 delete v;
    1107                                 delete leadExpV;
    1108                         }//for (int ii=0;ii<IDELEMS(srcRing_HH);ii++)
    1109                         /*Now we add the constraint for the standard simplex*/
    1110                         /*NOTE:Might actually work without the standard simplex*/
    1111                         dd_set_si(intPointMatrix->matrix[aktrow][0],-1);
    1112                         for (int jj=1;jj<=this->numVars;jj++)
    1113                         {
    1114                                 dd_set_si(intPointMatrix->matrix[aktrow][jj],1);
    1115                         }
     1051                        is not omitted when computing the differences*/
     1052                        if(markingsAreCorrect==TRUE)
     1053                        {
     1054                                aktpoly=pNext(aktpoly);
     1055                                pGetExpV(aktpoly,v);
     1056                        }
     1057                        else
     1058                        {
     1059                                pGetExpV(pHead(aktpoly),v);
     1060                                markingsAreCorrect=TRUE;
     1061                        }
     1062
     1063                        for (int jj=0;jj<this->numVars;jj++)
     1064                        {                               
     1065                                /*Store into ddMatrix*/                                                         
     1066                                dd_set_si(intPointMatrix->matrix[aktrow][jj+1],leadExpV[jj+1]-v[jj+1]);
     1067                        }
     1068                        aktrow +=1;
     1069                }
     1070                delete v;
     1071                delete leadExpV;
     1072        }//for (int ii=0;ii<IDELEMS(srcRing_HH);ii++)
     1073        /*Now we add the constraint for the standard simplex*/
     1074        /*NOTE:Might actually work without the standard simplex*/
     1075        dd_set_si(intPointMatrix->matrix[aktrow][0],-1);
     1076        for (int jj=1;jj<=this->numVars;jj++)
     1077        {
     1078                dd_set_si(intPointMatrix->matrix[aktrow][jj],1);
     1079        }
    11161080                        //Let's make sure we compute interior points from the positive orthant
    1117                         dd_MatrixPtr posRestr=dd_CreateMatrix(this->numVars,this->numVars+1);
    1118                         int jj=1;
    1119                         for (int ii=0;ii<this->numVars;ii++)
    1120                         {
    1121                                 dd_set_si(posRestr->matrix[ii][jj],1);
    1122                                 jj++;                                                   
    1123                         }
    1124                         dd_MatrixAppendTo(&intPointMatrix,posRestr);
    1125                         dd_FreeMatrix(posRestr);
     1081        dd_MatrixPtr posRestr=dd_CreateMatrix(this->numVars,this->numVars+1);
     1082        int jj=1;
     1083        for (int ii=0;ii<this->numVars;ii++)
     1084        {
     1085                dd_set_si(posRestr->matrix[ii][jj],1);
     1086                jj++;                                                   
     1087        }
     1088        dd_MatrixAppendTo(&intPointMatrix,posRestr);
     1089        dd_FreeMatrix(posRestr);
    11261090#ifdef gfan_DEBUG
    11271091//                      dd_WriteMatrix(stdout,intPointMatrix);
    11281092#endif
    1129                         intvec *iv_weight = new intvec(this->numVars);
    1130                         interiorPoint(intPointMatrix, *iv_weight);      //iv_weight now contains the interior point
    1131                         dd_FreeMatrix(intPointMatrix);
    1132                         dd_free_global_constants();
     1093        intvec *iv_weight = new intvec(this->numVars);
     1094        interiorPoint(intPointMatrix, *iv_weight);      //iv_weight now contains the interior point
     1095        dd_FreeMatrix(intPointMatrix);
     1096        dd_free_global_constants();
    11331097                       
    11341098                        /*Step 3
    1135                         turn the minimal basis into a reduced one
     1099        turn the minimal basis into a reduced one
    11361100                        */
    11371101                        //ring dstRing=rCopyAndAddWeight(tmpRing,iv_weight);   
     
    11421106                        //cout << "PLING" << endl;
    11431107                        /*ring dstRing=rCopy0(srcRing);
    1144                         for (int ii=0;ii<this->numVars;ii++)
    1145                         {                               
    1146                                 dstRing->wvhdl[0][ii]=(*iv_weight)[ii];                         
    1147                         }*/
    1148                         ring dstRing=rCopy0(tmpRing);
    1149                         int length=iv_weight->length();
    1150                         int *A=(int *)omAlloc0(length*sizeof(int));
    1151                         for(int jj=0;jj<length;jj++)
    1152                         {
    1153                                 A[jj]=(*iv_weight)[jj];
    1154                         }
    1155                         dstRing->wvhdl[0]=(int*)A;
    1156                         rComplete(dstRing);                                     
    1157                         rChangeCurrRing(dstRing);
     1108        for (int ii=0;ii<this->numVars;ii++)
     1109        {                               
     1110        dstRing->wvhdl[0][ii]=(*iv_weight)[ii];                         
     1111}*/
     1112        ring dstRing=rCopy0(tmpRing);
     1113        int length=iv_weight->length();
     1114        int *A=(int *)omAlloc0(length*sizeof(int));
     1115        for(int jj=0;jj<length;jj++)
     1116        {
     1117                A[jj]=(*iv_weight)[jj];
     1118        }
     1119        dstRing->wvhdl[0]=(int*)A;
     1120        rComplete(dstRing);                                     
     1121        rChangeCurrRing(dstRing);
    11581122                        //rDelete(tmpRing);
    1159                         delete iv_weight;
     1123        delete iv_weight;
    11601124//#ifdef gfan_DEBUG
    1161                         rWrite(dstRing); cout << endl;
     1125        rWrite(dstRing); cout << endl;
    11621126//#endif
    1163                         ideal dstRing_I;                       
    1164                         dstRing_I=idrCopyR(srcRing_HH,srcRing);
     1127        ideal dstRing_I;                       
     1128        dstRing_I=idrCopyR(srcRing_HH,srcRing);
    11651129                        //dstRing_I=idrCopyR(inputIdeal,srcRing);
    11661130                        //validOpts<1>=TRUE;
     
    11681132                        //idShow(dstRing_I);
    11691133#endif                 
    1170                         BITSET save=test;
    1171                         test|=Sy_bit(OPT_REDSB);
    1172                         test|=Sy_bit(OPT_REDTAIL);
    1173 #ifdef gfan_DEBUG
    1174                         test|=Sy_bit(6);        //OPT_DEBUG
    1175 #endif
    1176                         ideal tmpI;
     1134        BITSET save=test;
     1135        test|=Sy_bit(OPT_REDSB);
     1136        test|=Sy_bit(OPT_REDTAIL);
     1137#ifdef gfan_DEBUG
     1138        test|=Sy_bit(6);        //OPT_DEBUG
     1139#endif
     1140        ideal tmpI;
    11771141                        //NOTE Any of the two variants of tmpI={idrCopy(),dstRing_I} does the trick
    11781142                        //tmpI = idrCopyR(this->inputIdeal,this->baseRing);
    1179                         tmpI = dstRing_I;
    1180                         dstRing_I=kStd(tmpI,NULL,testHomog,NULL);
    1181                         idNorm(dstRing_I);                     
     1143        tmpI = dstRing_I;
     1144        dstRing_I=kStd(tmpI,NULL,testHomog,NULL);
     1145        idNorm(dstRing_I);                     
    11821146                        //kInterRed(dstRing_I);
    1183                         idSkipZeroes(dstRing_I);
    1184                         test=save;
    1185                         /*End of step 3 - reduction*/
    1186                        
    1187                         f->setFlipGB(dstRing_I);//store the flipped GB
    1188                         f->flipRing=rCopy(dstRing);     //store the ring on the other side
     1147        idSkipZeroes(dstRing_I);
     1148        test=save;
     1149        /*End of step 3 - reduction*/
     1150                       
     1151        f->setFlipGB(dstRing_I);//store the flipped GB
     1152        f->flipRing=rCopy(dstRing);     //store the ring on the other side
    11891153//#ifdef gfan_DEBUG
    1190                         cout << "Flipped GB is UCN " << counter+1 << ":" << endl;
     1154        cout << "Flipped GB is UCN " << counter+1 << ":" << endl;
    11911155                        //f->printFlipGB();
    1192                         this->idDebugPrint(dstRing_I);
    1193                         cout << endl;
     1156        this->idDebugPrint(dstRing_I);
     1157        cout << endl;
    11941158//#endif                       
    1195                         rChangeCurrRing(srcRing);       //return to the ring we started the computation of flipGB in
     1159        rChangeCurrRing(srcRing);       //return to the ring we started the computation of flipGB in
    11961160//                      rDelete(dstRing);
    1197                 }//void flip(ideal gb, facet *f)
     1161}//void flip(ideal gb, facet *f)
    11981162                               
    1199                 /** \brief Compute the remainder of a polynomial by a given ideal
    1200                 *
    1201                 * Compute \f$ f^{\mathcal{G}} \f$
    1202                 * Algorithm is taken from Cox, Little, O'Shea, IVA 2nd Ed. p 62
    1203                 * However, since we are only interested in the remainder, there is no need to
    1204                 * compute the factors \f$ a_i \f$
    1205                 */
     1163/** \brief Compute the remainder of a polynomial by a given ideal
     1164 *
     1165 * Compute \f$ f^{\mathcal{G}} \f$
     1166 * Algorithm is taken from Cox, Little, O'Shea, IVA 2nd Ed. p 62
     1167 * However, since we are only interested in the remainder, there is no need to
     1168 * compute the factors \f$ a_i \f$
     1169 */
    12061170                //NOTE: Should be replaced by kNF or kNF2
    1207                 poly restOfDiv(poly const &f, ideal const &I)
    1208                 {
     1171poly gcone::restOfDiv(poly const &f, ideal const &I)
     1172{
    12091173//                      cout << "Entering restOfDiv" << endl;
    1210                         poly p=f;
     1174        poly p=f;
    12111175                        //pWrite(p);                   
    1212                         poly r=NULL;    //The zero polynomial
    1213                         int ii;
    1214                         bool divOccured;
    1215                        
    1216                         while (p!=NULL)
    1217                         {
    1218                                 ii=1;
    1219                                 divOccured=FALSE;
     1176        poly r=NULL;    //The zero polynomial
     1177        int ii;
     1178        bool divOccured;
     1179                       
     1180        while (p!=NULL)
     1181        {
     1182                ii=1;
     1183                divOccured=FALSE;
    12201184                               
    1221                                 while( (ii<=IDELEMS(I) && (divOccured==FALSE) ))
    1222                                 {                                       
    1223                                         if (pDivisibleBy(I->m[ii-1],p)) //does LM(I->m[ii]) divide LM(p) ?
    1224                                         {                                               
    1225                                                 poly step1,step2,step3;
     1185                while( (ii<=IDELEMS(I) && (divOccured==FALSE) ))
     1186                {                                       
     1187                        if (pDivisibleBy(I->m[ii-1],p)) //does LM(I->m[ii]) divide LM(p) ?
     1188                        {                                               
     1189                                poly step1,step2,step3;
    12261190                                                //cout << "dividing "; pWrite(pHead(p));cout << "by ";pWrite(pHead(I->m[ii-1])); cout << endl;
    1227                                                 step1 = pDivideM(pHead(p),pHead(I->m[ii-1]));
     1191                                step1 = pDivideM(pHead(p),pHead(I->m[ii-1]));
    12281192                                                //cout << "LT(p)/LT(f_i)="; pWrite(step1); cout << endl;                               
    1229                                                 step2 = ppMult_qq(step1, I->m[ii-1]);                                           
    1230                                                 step3 = pSub(pCopy(p), step2);
     1193                                step2 = ppMult_qq(step1, I->m[ii-1]);                                           
     1194                                step3 = pSub(pCopy(p), step2);
    12311195                                                //p=pSub(p,pMult( pDivide(pHead(p),pHead(I->m[ii])), I->m[ii]));                       
    12321196                                                //pSetm(p);
    1233                                                 pSort(step3); //must be here, otherwise strange behaviour with many +o+o+o+o+ terms
    1234                                                 p=step3;
     1197                                pSort(step3); //must be here, otherwise strange behaviour with many +o+o+o+o+ terms
     1198                                p=step3;
    12351199                                                //pWrite(p);                                           
    1236                                                 divOccured=TRUE;
    1237                                         }
    1238                                         else
    1239                                         {
    1240                                                 ii += 1;
    1241                                         }//if (pLmDivisibleBy(I->m[ii],p,currRing))
    1242                                 }//while( (ii<IDELEMS(I) && (divOccured==FALSE) ))
    1243                                 if (divOccured==FALSE)
    1244                                 {
     1200                                divOccured=TRUE;
     1201                        }
     1202                        else
     1203                        {
     1204                                ii += 1;
     1205                        }//if (pLmDivisibleBy(I->m[ii],p,currRing))
     1206                }//while( (ii<IDELEMS(I) && (divOccured==FALSE) ))
     1207                if (divOccured==FALSE)
     1208                {
    12451209                                        //cout << "TICK 5" << endl;
    1246                                         r=pAdd(pCopy(r),pHead(p));
    1247                                         pSetm(r);
    1248                                         pSort(r);
     1210                        r=pAdd(pCopy(r),pHead(p));
     1211                        pSetm(r);
     1212                        pSort(r);
    12491213                                        //cout << "r="; pWrite(r); cout << endl;
    12501214                                       
    1251                                         if (pLength(p)!=1)
    1252                                         {
    1253                                                 p=pSub(pCopy(p),pHead(p));      //Here it may occur that p=0 instead of p=NULL
    1254                                         }
    1255                                         else
    1256                                         {
    1257                                                 p=NULL; //Hack to correct this situation                                               
    1258                                         }                                       
     1215                        if (pLength(p)!=1)
     1216                        {
     1217                                p=pSub(pCopy(p),pHead(p));      //Here it may occur that p=0 instead of p=NULL
     1218                        }
     1219                        else
     1220                        {
     1221                                p=NULL; //Hack to correct this situation                                               
     1222                        }                                       
    12591223                                        //cout << "p="; pWrite(p);
    1260                                 }//if (divOccured==FALSE)
    1261                         }//while (p!=0)
    1262                         return r;
    1263                 }//poly restOfDiv(poly const &f, ideal const &I)
    1264                
    1265                 /** \brief Compute \f$ f-f^{\mathcal{G}} \f$
    1266                 */
    1267                 //NOTE: use kNF or kNF2 instead of restOfDivision
    1268                 ideal ffG(ideal const &H, ideal const &G)
    1269                 {
     1224                }//if (divOccured==FALSE)
     1225        }//while (p!=0)
     1226        return r;
     1227}//poly restOfDiv(poly const &f, ideal const &I)
     1228               
     1229/** \brief Compute \f$ f-f^{\mathcal{G}} \f$
     1230        */
     1231//NOTE: use kNF or kNF2 instead of restOfDivision
     1232ideal gcone::ffG(ideal const &H, ideal const &G)
     1233{
    12701234//                      cout << "Entering ffG" << endl;
    1271                         int size=IDELEMS(H);
    1272                         ideal res=idInit(size,1);
    1273                         poly temp1, temp2, temp3;       //polys to temporarily store values for pSub
    1274                         for (int ii=0;ii<size;ii++)
    1275                         {
    1276                                 res->m[ii]=restOfDiv(H->m[ii],G);
     1235        int size=IDELEMS(H);
     1236        ideal res=idInit(size,1);
     1237        poly temp1, temp2, temp3;       //polys to temporarily store values for pSub
     1238        for (int ii=0;ii<size;ii++)
     1239        {
     1240                res->m[ii]=restOfDiv(H->m[ii],G);
    12771241                                //res->m[ii]=kNF(G, NULL,H->m[ii]);
    1278                                 temp1=H->m[ii];
    1279                                 temp2=res->m[ii];                               
    1280                                 temp3=pSub(temp1, temp2);
    1281                                 res->m[ii]=temp3;
     1242                temp1=H->m[ii];
     1243                temp2=res->m[ii];                               
     1244                temp3=pSub(temp1, temp2);
     1245                res->m[ii]=temp3;
    12821246                                //res->m[ii]=pSub(temp1,temp2); //buggy
    12831247                                //pSort(res->m[ii]);
    12841248                                //pSetm(res->m[ii]);
    12851249                                //cout << "res->m["<<ii<<"]=";pWrite(res->m[ii]);                                               
    1286                         }                       
    1287                         return res;
    1288                 }
    1289                
    1290                 /** \brief Compute a Groebner Basis
    1291                 *
    1292                 * Computes the Groebner basis and stores the result in gcone::gcBasis
    1293                 *\param ideal
    1294                 *\return void
    1295                 */
    1296                 void getGB(ideal const &inputIdeal)             
    1297                 {
    1298                         BITSET save=test;
    1299                         test|=Sy_bit(OPT_REDSB);
    1300                         test|=Sy_bit(OPT_REDTAIL);
    1301                         ideal gb;
    1302                         gb=kStd(inputIdeal,NULL,testHomog,NULL);
    1303                         idSkipZeroes(gb);
    1304                         this->gcBasis=gb;       //write the GB into gcBasis
    1305                         test=save;
    1306                 }//void getGB
    1307                
    1308                 /** \brief The Generic Groebner Walk due to FJLT
    1309                 * Needed for computing the search facet
    1310                 */
    1311                 ideal GenGrbWlk(ideal, ideal)
    1312                 {
    1313                 }//GGW
    1314                
    1315                 /** \brief Compute the negative of a given intvec
    1316                 */             
    1317                 intvec *ivNeg(const intvec *iv)
    1318                 {
    1319                         intvec *res = new intvec(iv->length());
    1320                         res=ivCopy(iv);
    1321                         *res *= (int)-1;                                               
    1322                         return res;
    1323                 }
    1324 
    1325 
    1326                 /** \brief Compute the dot product of two intvecs
    1327                 *
    1328                 */
    1329                 int dotProduct(intvec const &iva, intvec const &ivb)                           
    1330                 {                       
    1331                         int res=0;
    1332                         for (int i=0;i<this->numVars;i++)
    1333                         {
    1334                                 res = res+(iva[i]*ivb[i]);
    1335                         }
    1336                         return res;
    1337                 }//int dotProduct
    1338 
    1339                 /** \brief Check whether two intvecs are parallel
    1340                 *
    1341                 * \f$ \alpha\parallel\beta\Leftrightarrow\langle\alpha,\beta\rangle^2=\langle\alpha,\alpha\rangle\langle\beta,\beta\rangle \f$
    1342                 */
    1343                 bool isParallel(intvec const &a, intvec const &b)
    1344                 {                       
    1345                         int lhs,rhs;
    1346                         bool res;
    1347                         lhs=dotProduct(a,b)*dotProduct(a,b);
    1348                         rhs=dotProduct(a,a)*dotProduct(b,b);
     1250        }                       
     1251        return res;
     1252}
     1253               
     1254/** \brief Compute a Groebner Basis
     1255 *
     1256 * Computes the Groebner basis and stores the result in gcone::gcBasis
     1257 *\param ideal
     1258 *\return void
     1259 */
     1260void gcone::getGB(ideal const &inputIdeal)             
     1261{
     1262        BITSET save=test;
     1263        test|=Sy_bit(OPT_REDSB);
     1264        test|=Sy_bit(OPT_REDTAIL);
     1265        ideal gb;
     1266        gb=kStd(inputIdeal,NULL,testHomog,NULL);
     1267        idSkipZeroes(gb);
     1268        this->gcBasis=gb;       //write the GB into gcBasis
     1269        test=save;
     1270}//void getGB
     1271               
     1272/** \brief Compute the negative of a given intvec
     1273        */             
     1274intvec *gcone::ivNeg(const intvec *iv)
     1275{
     1276        intvec *res = new intvec(iv->length());
     1277        res=ivCopy(iv);
     1278        *res *= (int)-1;                                               
     1279        return res;
     1280}
     1281
     1282
     1283/** \brief Compute the dot product of two intvecs
     1284*
     1285*/
     1286int gcone::dotProduct(intvec const &iva, intvec const &ivb)                             
     1287{                       
     1288        int res=0;
     1289        for (int i=0;i<this->numVars;i++)
     1290        {
     1291                res = res+(iva[i]*ivb[i]);
     1292        }
     1293        return res;
     1294}//int dotProduct
     1295
     1296/** \brief Check whether two intvecs are parallel
     1297 *
     1298 * \f$ \alpha\parallel\beta\Leftrightarrow\langle\alpha,\beta\rangle^2=\langle\alpha,\alpha\rangle\langle\beta,\beta\rangle \f$
     1299 */
     1300bool gcone::isParallel(intvec const &a, intvec const &b)
     1301{                       
     1302        int lhs,rhs;
     1303        bool res;
     1304        lhs=dotProduct(a,b)*dotProduct(a,b);
     1305        rhs=dotProduct(a,a)*dotProduct(b,b);
    13491306                        //cout << "LHS="<<lhs<<", RHS="<<rhs<<endl;
    1350                         if (lhs==rhs)
    1351                         {
    1352                                 res = TRUE;
    1353                         }
    1354                         else
    1355                         {
    1356                                 res = FALSE;
    1357                         }
    1358                         return res;
    1359                 }//bool isParallel
    1360                
    1361                 /** \brief Compute an interior point of a given cone
    1362                 * Result will be written into intvec iv.
    1363                 * Any rational point is automatically converted into an integer.
    1364                 */
    1365                 void interiorPoint(dd_MatrixPtr const &M, intvec &iv) //no const &M here since we want to remove redundant rows
    1366                 {
    1367                         dd_LPPtr lp,lpInt;
    1368                         dd_ErrorType err=dd_NoError;
    1369                         dd_LPSolverType solver=dd_DualSimplex;
    1370                         dd_LPSolutionPtr lpSol=NULL;
    1371                         dd_rowset ddlinset,ddredrows;   //needed for dd_FindRelativeInterior
    1372                         dd_rowindex ddnewpos;
    1373                         dd_NumberType numb;     
     1307        if (lhs==rhs)
     1308        {
     1309                res = TRUE;
     1310        }
     1311        else
     1312        {
     1313                res = FALSE;
     1314        }
     1315        return res;
     1316}//bool isParallel
     1317               
     1318/** \brief Compute an interior point of a given cone
     1319 * Result will be written into intvec iv.
     1320 * Any rational point is automatically converted into an integer.
     1321 */
     1322void gcone::interiorPoint(dd_MatrixPtr const &M, intvec &iv) //no const &M here since we want to remove redundant rows
     1323{
     1324        dd_LPPtr lp,lpInt;
     1325        dd_ErrorType err=dd_NoError;
     1326        dd_LPSolverType solver=dd_DualSimplex;
     1327        dd_LPSolutionPtr lpSol=NULL;
     1328        dd_rowset ddlinset,ddredrows;   //needed for dd_FindRelativeInterior
     1329        dd_rowindex ddnewpos;
     1330        dd_NumberType numb;     
    13741331                        //M->representation=dd_Inequality;
    13751332                        //M->objective-dd_LPMin;  //Not sure whether this is needed
     
    13791336                                                                       
    13801337                        /*NOTE: Leave the following line commented out!
    1381                         * Otherwise it will cause interior points that are not strictly positive on some examples
    1382                         *
     1338        * Otherwise it will cause interior points that are not strictly positive on some examples
     1339        *
    13831340                        */
    13841341                        //dd_MatrixCanonicalize(&M, &ddlinset, &ddredrows, &ddnewpos, &err);
     
    13871344                        //dd_WriteMatrix(stdout,M);
    13881345                       
    1389                         lp=dd_Matrix2LP(M, &err);
    1390                         if (err!=dd_NoError){cout << "Error during dd_Matrix2LP in gcone::interiorPoint" << endl;}                     
    1391                         if (lp==NULL){cout << "LP is NULL" << endl;}
     1346        lp=dd_Matrix2LP(M, &err);
     1347        if (err!=dd_NoError){cout << "Error during dd_Matrix2LP in gcone::interiorPoint" << endl;}                     
     1348        if (lp==NULL){cout << "LP is NULL" << endl;}
    13921349#ifdef gfan_DEBUG
    13931350//                      dd_WriteLP(stdout,lp);
    13941351#endif 
    13951352                                       
    1396                         lpInt=dd_MakeLPforInteriorFinding(lp);
    1397                         if (err!=dd_NoError){cout << "Error during dd_MakeLPForInteriorFinding in gcone::interiorPoint" << endl;}
     1353        lpInt=dd_MakeLPforInteriorFinding(lp);
     1354        if (err!=dd_NoError){cout << "Error during dd_MakeLPForInteriorFinding in gcone::interiorPoint" << endl;}
    13981355#ifdef gfan_DEBUG
    13991356//                      dd_WriteLP(stdout,lpInt);
    14001357#endif                 
    14011358
    1402                         dd_FindRelativeInterior(M,&ddlinset,&ddredrows,&lpSol,&err);
    1403                         if (err!=dd_NoError)
    1404                         {
    1405                                 cout << "Error during dd_FindRelativeInterior in gcone::interiorPoint" << endl;
    1406                                 dd_WriteErrorMessages(stdout, err);
    1407                         }
     1359        dd_FindRelativeInterior(M,&ddlinset,&ddredrows,&lpSol,&err);
     1360        if (err!=dd_NoError)
     1361        {
     1362                cout << "Error during dd_FindRelativeInterior in gcone::interiorPoint" << endl;
     1363                dd_WriteErrorMessages(stdout, err);
     1364        }
    14081365                       
    14091366                        //dd_LPSolve(lpInt,solver,&err);        //This will not result in a point from the relative interior
    1410                         if (err!=dd_NoError){cout << "Error during dd_LPSolve" << endl;}
     1367        if (err!=dd_NoError){cout << "Error during dd_LPSolve" << endl;}
    14111368                                                                       
    14121369                        //lpSol=dd_CopyLPSolution(lpInt);
    1413                         if (err!=dd_NoError){cout << "Error during dd_CopyLPSolution" << endl;}                 
    1414 #ifdef gfan_DEBUG
    1415                         cout << "Interior point: ";
    1416                         for (int ii=1; ii<(lpSol->d)-1;ii++)
    1417                         {
    1418                                 dd_WriteNumber(stdout,lpSol->sol[ii]);
    1419                         }
    1420                         cout << endl;
     1370        if (err!=dd_NoError){cout << "Error during dd_CopyLPSolution" << endl;}                 
     1371#ifdef gfan_DEBUG
     1372        cout << "Interior point: ";
     1373        for (int ii=1; ii<(lpSol->d)-1;ii++)
     1374        {
     1375                dd_WriteNumber(stdout,lpSol->sol[ii]);
     1376        }
     1377        cout << endl;
    14211378#endif
    14221379                       
    14231380                        //NOTE The following strongly resembles parts of makeInt.
    14241381                        //Maybe merge sometimes
    1425                         mpz_t kgV; mpz_init(kgV);
    1426                         mpz_set_str(kgV,"1",10);
    1427                         mpz_t den; mpz_init(den);
    1428                         mpz_t tmp; mpz_init(tmp);
    1429                         mpq_get_den(tmp,lpSol->sol[1]);
    1430                         for (int ii=1;ii<(lpSol->d)-1;ii++)
    1431                         {
    1432                                 mpq_get_den(den,lpSol->sol[ii+1]);
    1433                                 mpz_lcm(kgV,tmp,den);
    1434                                 mpz_set(tmp, kgV);
    1435                         }
    1436                         mpq_t qkgV;
    1437                         mpq_init(qkgV);
    1438                         mpq_set_z(qkgV,kgV);
    1439                         for (int ii=1;ii<(lpSol->d)-1;ii++)
    1440                         {
    1441                                 mpq_t product;
    1442                                 mpq_init(product);
    1443                                 mpq_mul(product,qkgV,lpSol->sol[ii]);
    1444                                 iv[ii-1]=(int)mpz_get_d(mpq_numref(product));
    1445                                 mpq_clear(product);
    1446                         }
     1382        mpz_t kgV; mpz_init(kgV);
     1383        mpz_set_str(kgV,"1",10);
     1384        mpz_t den; mpz_init(den);
     1385        mpz_t tmp; mpz_init(tmp);
     1386        mpq_get_den(tmp,lpSol->sol[1]);
     1387        for (int ii=1;ii<(lpSol->d)-1;ii++)
     1388        {
     1389                mpq_get_den(den,lpSol->sol[ii+1]);
     1390                mpz_lcm(kgV,tmp,den);
     1391                mpz_set(tmp, kgV);
     1392        }
     1393        mpq_t qkgV;
     1394        mpq_init(qkgV);
     1395        mpq_set_z(qkgV,kgV);
     1396        for (int ii=1;ii<(lpSol->d)-1;ii++)
     1397        {
     1398                mpq_t product;
     1399                mpq_init(product);
     1400                mpq_mul(product,qkgV,lpSol->sol[ii]);
     1401                iv[ii-1]=(int)mpz_get_d(mpq_numref(product));
     1402                mpq_clear(product);
     1403        }
    14471404#ifdef gfan_DEBUG
    14481405//                      iv.show();
    14491406//                      cout << endl;
    14501407#endif
    1451                         mpq_clear(qkgV);
    1452                         mpz_clear(tmp);
    1453                         mpz_clear(den);
    1454                         mpz_clear(kgV);                 
    1455                        
    1456                         dd_FreeLPSolution(lpSol);
    1457                         dd_FreeLPData(lpInt);
    1458                         dd_FreeLPData(lp);
    1459                         set_free(ddlinset);
    1460                         set_free(ddredrows);                   
    1461                        
    1462                 }//void interiorPoint(dd_MatrixPtr const &M)
    1463                
    1464                 /** \brief Copy a ring and add a weighted ordering in first place
    1465                 *
    1466                 */
    1467                 ring rCopyAndAddWeight(ring const &r, intvec const *ivw)                               
    1468                 {
    1469                         ring res=rCopy0(r);
    1470                         int jj;
    1471                        
    1472                         omFree(res->order);
    1473                         res->order =(int *)omAlloc0(4*sizeof(int));
    1474                         omFree(res->block0);
    1475                         res->block0=(int *)omAlloc0(4*sizeof(int));
    1476                         omFree(res->block1);
    1477                         res->block1=(int *)omAlloc0(4*sizeof(int));
    1478                         omfree(res->wvhdl);
    1479                         res->wvhdl =(int **)omAlloc0(4*sizeof(int**));
    1480                        
    1481                         res->order[0]=ringorder_a;
    1482                         res->block0[0]=1;
    1483                         res->block1[0]=res->N;;
    1484                         res->order[1]=ringorder_dp;     //basically useless, since that should never be used                   
    1485                         res->block0[1]=1;
    1486                         res->block1[1]=res->N;;
    1487                         res->order[2]=ringorder_C;
    1488 
    1489                         int length=ivw->length();
    1490                         int *A=(int *)omAlloc0(length*sizeof(int));
    1491                         for (jj=0;jj<length;jj++)
    1492                         {                               
    1493                                 A[jj]=(*ivw)[jj];                               
    1494                         }                       
    1495                         res->wvhdl[0]=(int *)A;
    1496                         res->block1[0]=length;
    1497                        
    1498                         rComplete(res);
    1499                         return res;
    1500                 }//rCopyAndAdd
     1408        mpq_clear(qkgV);
     1409        mpz_clear(tmp);
     1410        mpz_clear(den);
     1411        mpz_clear(kgV);                 
     1412                       
     1413        dd_FreeLPSolution(lpSol);
     1414        dd_FreeLPData(lpInt);
     1415        dd_FreeLPData(lp);
     1416        set_free(ddlinset);
     1417        set_free(ddredrows);                   
     1418                       
     1419}//void interiorPoint(dd_MatrixPtr const &M)
     1420               
     1421/** \brief Copy a ring and add a weighted ordering in first place
     1422 *
     1423 */
     1424ring gcone::rCopyAndAddWeight(ring const &r, intvec const *ivw)                         
     1425{
     1426        ring res=rCopy0(r);
     1427        int jj;
     1428                       
     1429        omFree(res->order);
     1430        res->order =(int *)omAlloc0(4*sizeof(int));
     1431        omFree(res->block0);
     1432        res->block0=(int *)omAlloc0(4*sizeof(int));
     1433        omFree(res->block1);
     1434        res->block1=(int *)omAlloc0(4*sizeof(int));
     1435        omfree(res->wvhdl);
     1436        res->wvhdl =(int **)omAlloc0(4*sizeof(int**));
     1437                       
     1438        res->order[0]=ringorder_a;
     1439        res->block0[0]=1;
     1440        res->block1[0]=res->N;;
     1441        res->order[1]=ringorder_dp;     //basically useless, since that should never be used                   
     1442        res->block0[1]=1;
     1443        res->block1[1]=res->N;;
     1444        res->order[2]=ringorder_C;
     1445
     1446        int length=ivw->length();
     1447        int *A=(int *)omAlloc0(length*sizeof(int));
     1448        for (jj=0;jj<length;jj++)
     1449        {                               
     1450                A[jj]=(*ivw)[jj];                               
     1451        }                       
     1452        res->wvhdl[0]=(int *)A;
     1453        res->block1[0]=length;
     1454                       
     1455        rComplete(res);
     1456        return res;
     1457}//rCopyAndAdd
    15011458               
    15021459                ring rCopyAndChangeWeight(ring const &r, intvec *ivw)
    1503                 {
    1504                         ring res=rCopy0(currRing);
    1505                         rComplete(res);
    1506                         rSetWeightVec(res,(int64*)ivw);
     1460{
     1461        ring res=rCopy0(currRing);
     1462        rComplete(res);
     1463        rSetWeightVec(res,(int64*)ivw);
    15071464                        //rChangeCurrRing(rnew);
    1508                         return res;
    1509                 }
    1510                
    1511                 /** \brief Checks whether a given facet is a search facet
    1512                 * Determines whether a given facet of a cone is the search facet of a neighbouring cone
    1513                 * This is done in the following way:
    1514                 * We loop through all facets of the cone and find the "smallest" facet, i.e. the unique facet
    1515                 * that is first crossed during the generic walk.
    1516                 * We then check whether the fNormal of this facet is parallel to the fNormal of our testfacet.
    1517                 * If this is the case, then our facet is indeed a search facet and TRUE is retuned.
    1518                 */
    1519                 bool isSearchFacet(gcone &gcTmp, facet *testfacet)
    1520                 {                               
    1521                         ring actRing=currRing;
    1522                         facet *facetPtr=(facet*)gcTmp.facetPtr;                 
    1523                         facet *fMin=new facet(*facetPtr);       //Pointer to the "minimal" facet
     1465        return res;
     1466}
     1467               
     1468/** \brief Checks whether a given facet is a search facet
     1469 * Determines whether a given facet of a cone is the search facet of a neighbouring cone
     1470 * This is done in the following way:
     1471 * We loop through all facets of the cone and find the "smallest" facet, i.e. the unique facet
     1472 * that is first crossed during the generic walk.
     1473 * We then check whether the fNormal of this facet is parallel to the fNormal of our testfacet.
     1474 * If this is the case, then our facet is indeed a search facet and TRUE is retuned.
     1475*/
     1476bool gcone::isSearchFacet(gcone &gcTmp, facet *testfacet)
     1477{                               
     1478        ring actRing=currRing;
     1479        facet *facetPtr=(facet*)gcTmp.facetPtr;                 
     1480        facet *fMin=new facet(*facetPtr);       //Pointer to the "minimal" facet
    15241481                        //facet *fMin = new facet(tmpcone.facetPtr);
    15251482                        //fMin=tmpcone.facetPtr;                //Initialise to first facet of tmpcone
    1526                         facet *fAct;    //Ptr to alpha_i
    1527                         facet *fCmp;    //Ptr to alpha_j
    1528                         fAct = fMin;
    1529                         fCmp = fMin->next;                             
    1530                        
    1531                         rChangeCurrRing(this->rootRing);        //because we compare the monomials in the rootring                     
    1532                         poly p=pInit();
    1533                         poly q=pInit();
    1534                         intvec *alpha_i = new intvec(this->numVars);                   
    1535                         intvec *alpha_j = new intvec(this->numVars);
    1536                         intvec *sigma = new intvec(this->numVars);
    1537                         sigma=gcTmp.getIntPoint();
    1538                        
    1539                         int *u=(int *)omAlloc((this->numVars+1)*sizeof(int));
    1540                         int *v=(int *)omAlloc((this->numVars+1)*sizeof(int));
    1541                         u[0]=0; v[0]=0;
    1542                         int weight1,weight2;
    1543                         while(fAct->next->next!=NULL)   //NOTE this is ugly. Can it be done without fCmp?
    1544                         {
    1545                                 /* Get alpha_i and alpha_{i+1} */
    1546                                 alpha_i=fAct->getFacetNormal();
    1547                                 alpha_j=fCmp->getFacetNormal();
    1548 #ifdef gfan_DEBUG
    1549                                 alpha_i->show();
    1550                                 alpha_j->show();
    1551 #endif
    1552                                 /*Compute the dot product of sigma and alpha_{i,j}*/
    1553                                 weight1=dotProduct(sigma,alpha_i);
    1554                                 weight2=dotProduct(sigma,alpha_j);
    1555 #ifdef gfan_DEBUG
    1556                                 cout << "weight1=" << weight1 << " " << "weight2=" << weight2 << endl;
    1557 #endif
    1558                                 /*Adjust alpha_i and alpha_i+1 accordingly*/
    1559                                 for(int ii=1;ii<=this->numVars;ii++)
    1560                                 {                                       
    1561                                         u[ii]=weight1*(*alpha_i)[ii-1];
    1562                                         v[ii]=weight2*(*alpha_j)[ii-1];
    1563                                 }                               
     1483        facet *fAct;    //Ptr to alpha_i
     1484        facet *fCmp;    //Ptr to alpha_j
     1485        fAct = fMin;
     1486        fCmp = fMin->next;                             
     1487                       
     1488        rChangeCurrRing(this->rootRing);        //because we compare the monomials in the rootring                     
     1489        poly p=pInit();
     1490        poly q=pInit();
     1491        intvec *alpha_i = new intvec(this->numVars);                   
     1492        intvec *alpha_j = new intvec(this->numVars);
     1493        intvec *sigma = new intvec(this->numVars);
     1494        sigma=gcTmp.getIntPoint();
     1495                       
     1496        int *u=(int *)omAlloc((this->numVars+1)*sizeof(int));
     1497        int *v=(int *)omAlloc((this->numVars+1)*sizeof(int));
     1498        u[0]=0; v[0]=0;
     1499        int weight1,weight2;
     1500        while(fAct->next->next!=NULL)   //NOTE this is ugly. Can it be done without fCmp?
     1501        {
     1502                /* Get alpha_i and alpha_{i+1} */
     1503                alpha_i=fAct->getFacetNormal();
     1504                alpha_j=fCmp->getFacetNormal();
     1505#ifdef gfan_DEBUG
     1506                alpha_i->show();
     1507                alpha_j->show();
     1508#endif
     1509                /*Compute the dot product of sigma and alpha_{i,j}*/
     1510                weight1=dotProduct(sigma,alpha_i);
     1511                weight2=dotProduct(sigma,alpha_j);
     1512#ifdef gfan_DEBUG
     1513                cout << "weight1=" << weight1 << " " << "weight2=" << weight2 << endl;
     1514#endif
     1515                /*Adjust alpha_i and alpha_i+1 accordingly*/
     1516                for(int ii=1;ii<=this->numVars;ii++)
     1517                {                                       
     1518                        u[ii]=weight1*(*alpha_i)[ii-1];
     1519                        v[ii]=weight2*(*alpha_j)[ii-1];
     1520                }                               
    15641521                               
    1565                                 /*Now p_weight and q_weight need to be compared as exponent vectors*/
    1566                                 pSetCoeff0(p,nInit(1));
    1567                                 pSetCoeff0(q,nInit(1));
    1568                                 pSetExpV(p,u);
    1569                                 pSetm(p);                       
    1570                                 pSetExpV(q,v);
    1571                                 pSetm(q);
     1522                /*Now p_weight and q_weight need to be compared as exponent vectors*/
     1523                pSetCoeff0(p,nInit(1));
     1524                pSetCoeff0(q,nInit(1));
     1525                pSetExpV(p,u);
     1526                pSetm(p);                       
     1527                pSetExpV(q,v);
     1528                pSetm(q);
    15721529#ifdef gfan_DEBUG                               
    1573                                 pWrite(p);pWrite(q);
     1530                pWrite(p);pWrite(q);
    15741531#endif 
    15751532                                /*We want to check whether x^p < x^q
    1576                                 => want to check for return value 1 */
    1577                                 if (pLmCmp(p,q)==1)     //i.e. x^q is smaller
    1578                                 {
    1579                                         fMin=fCmp;
    1580                                         fAct=fMin;
    1581                                         fCmp=fCmp->next;
     1533                => want to check for return value 1 */
     1534                if (pLmCmp(p,q)==1)     //i.e. x^q is smaller
     1535                {
     1536                        fMin=fCmp;
     1537                        fAct=fMin;
     1538                        fCmp=fCmp->next;
     1539                }
     1540                else
     1541                {
     1542                                        //fAct=fAct->next;
     1543                        if(fCmp->next!=NULL)
     1544                        {
     1545                                fCmp=fCmp->next;
     1546                        }
     1547                        else
     1548                        {
     1549                                fAct=fAct->next;
     1550                        }
     1551                }
     1552                                //fAct=fAct->next;
     1553        }//while(fAct.facetPtr->next!=NULL)
     1554        delete alpha_i,alpha_j,sigma;
     1555                       
     1556        /*If testfacet was minimal then fMin should still point there */
     1557                       
     1558                        //if(fMin->getFacetNormal()==ivNeg(testfacet.getFacetNormal()))                 
     1559#ifdef gfan_DEBUG
     1560        cout << "Checking for parallelity" << endl <<" fMin is";
     1561        fMin->printNormal();
     1562        cout << "testfacet is ";
     1563        testfacet->printNormal();
     1564        cout << endl;
     1565#endif
     1566        if (fMin==gcTmp.facetPtr)                       
     1567                        //if(areEqual(fMin->getFacetNormal(),ivNeg(testfacet.getFacetNormal())))
     1568                        //if (isParallel(fMin->getFacetNormal(),testfacet->getFacetNormal()))
     1569        {                               
     1570                cout << "Parallel" << endl;
     1571                rChangeCurrRing(actRing);
     1572                                //delete alpha_min, test;
     1573                return TRUE;
     1574        }
     1575        else
     1576        {
     1577                cout << "Not parallel" << endl;
     1578                rChangeCurrRing(actRing);
     1579                                //delete alpha_min, test;
     1580                return FALSE;
     1581        }
     1582}//bool isSearchFacet
     1583               
     1584/** \brief Check for equality of two intvecs
     1585 */
     1586bool gcone::areEqual(intvec const &a, intvec const &b)
     1587{
     1588        bool res=TRUE;
     1589        for(int ii=0;ii<this->numVars;ii++)
     1590        {
     1591                if(a[ii]!=b[ii])
     1592                {
     1593                        res=FALSE;
     1594                        break;
     1595                }
     1596        }
     1597        return res;
     1598}
     1599               
     1600/** \brief The reverse search algorithm
     1601 */
     1602void gcone::reverseSearch(gcone *gcAct) //no const possible here since we call gcAct->flip
     1603{
     1604        facet *fAct=new facet();
     1605        fAct = gcAct->facetPtr;                 
     1606                       
     1607        while(fAct!=NULL)
     1608        {
     1609                cout << "======================"<< endl;
     1610                gcAct->flip(gcAct->gcBasis,gcAct->facetPtr);
     1611                gcone *gcTmp = new gcone(*gcAct);
     1612                                //idShow(gcTmp->gcBasis);
     1613                gcTmp->getConeNormals(gcTmp->gcBasis, TRUE);
     1614#ifdef gfan_DEBUG
     1615                facet *f = new facet();
     1616                f=gcTmp->facetPtr;
     1617                while(f!=NULL)
     1618                {
     1619                        f->printNormal();
     1620                        f=f->next;                                     
     1621                }
     1622#endif
     1623                gcTmp->showIntPoint();
     1624                /*recursive part goes gere*/
     1625                if (isSearchFacet(*gcTmp,(facet*)gcAct->facetPtr))
     1626                {
     1627                        gcAct->next=gcTmp;
     1628                        cout << "PING"<< endl;
     1629                        reverseSearch(gcTmp);
     1630                }
     1631                else
     1632                {
     1633                        delete gcTmp;
     1634                        /*NOTE remove fAct from linked list. It's no longer needed*/
     1635                }
     1636                /*recursion ends*/
     1637                fAct = fAct->next;             
     1638        }//while(fAct->next!=NULL)
     1639}//reverseSearch
     1640               
     1641/** \brief The new method of Markwig and Jensen
     1642 * Compute gcBasis and facets for the arbitrary starting cone. Store \f$(codim-1)\f$-facets as normals.
     1643 * In order to represent a facet uniquely compute also the \f$(codim-2)\f$-facets and norm by the gcd of the components.
     1644 * Keep a list of facets as a linked list containing an intvec and an integer matrix.
     1645 * Since a \f$(codim-1)\f$-facet belongs to exactly two full dimensional cones, we remove a facet from the list as
     1646 * soon as we compute this facet again. Comparison of facets is done by...
     1647 */
     1648void gcone::noRevS(gcone &gcRoot, bool usingIntPoint)
     1649{       
     1650        facet *SearchListRoot = new facet(); //The list containing ALL facets we come across
     1651        facet *SearchListAct;
     1652        SearchListAct = NULL;
     1653                        //SearchListAct = SearchListRoot;
     1654                       
     1655        gcone *gcAct;
     1656        gcAct = &gcRoot;
     1657        gcone *gcPtr;   //Pointer to end of linked list of cones
     1658        gcPtr = &gcRoot;
     1659        gcone *gcNext;  //Pointer to next cone to be visited
     1660        gcNext = &gcRoot;
     1661        gcone *gcHead;
     1662        gcHead = &gcRoot;
     1663                       
     1664        facet *fAct;
     1665        fAct = gcAct->facetPtr;                 
     1666                       
     1667        ring rAct;
     1668        rAct = currRing;
     1669                                               
     1670        int UCNcounter=gcAct->getUCN();
     1671#ifdef gfan_DEBUG
     1672        cout << "NoRevs" << endl;
     1673        cout << "Facets are:" << endl;
     1674        gcAct->showFacets();
     1675#endif                 
     1676                       
     1677        gcAct->getCodim2Normals(*gcAct);
     1678                               
     1679                        //Compute unique representation of codim-2-facets
     1680        gcAct->normalize();
     1681                       
     1682                        /*Make a copy of the facet list of first cone
     1683        Since the operations getCodim2Normals and normalize affect the facets
     1684        we must not memcpy them before these ops!
     1685                        */
     1686        intvec *fNormal;// = new intvec(this->numVars);
     1687        intvec *f2Normal;// = new intvec(this->numVars);
     1688        facet *codim2Act; codim2Act = NULL;                     
     1689        facet *sl2Root; //sl2Root = new facet(2);
     1690        facet *sl2Act;  //sl2Act = sl2Root;
     1691                       
     1692        for(int ii=0;ii<this->numFacets;ii++)
     1693        {
     1694                                //only copy flippable facets!
     1695                if(fAct->isFlippable==TRUE)
     1696                {
     1697                        fNormal = fAct->getFacetNormal();
     1698                        if( ii==0 || (ii>0 && SearchListAct==NULL) ) //1st facet may be non-flippable
     1699                        {                                               
     1700                                SearchListAct = SearchListRoot;
     1701                                                //memcpy(SearchListAct,fAct,sizeof(facet));                                     
     1702                        }
     1703                        else
     1704                        {                       
     1705                                SearchListAct->next = new facet();
     1706                                SearchListAct = SearchListAct->next;                                           
     1707                                                //memcpy(SearchListAct,fAct,sizeof(facet));                             
     1708                        }
     1709                        SearchListAct->setFacetNormal(fNormal);
     1710                        SearchListAct->setUCN(this->getUCN());
     1711                        SearchListAct->numCodim2Facets=fAct->numCodim2Facets;
     1712                        SearchListAct->isFlippable=TRUE;
     1713                                        //Copy codim2-facets                           
     1714                        codim2Act=fAct->codim2Ptr;
     1715                        SearchListAct->codim2Ptr = new facet(2);
     1716                        sl2Root = SearchListAct->codim2Ptr;
     1717                        sl2Act = sl2Root;
     1718                                        //while(codim2Act!=NULL)
     1719                        for(int jj=0;jj<fAct->numCodim2Facets;jj++)
     1720                        {
     1721                                f2Normal = codim2Act->getFacetNormal();
     1722                                if(jj==0)
     1723                                {                                               
     1724                                        sl2Act = sl2Root;
     1725                                        sl2Act->setFacetNormal(f2Normal);
    15821726                                }
    15831727                                else
    15841728                                {
    1585                                         //fAct=fAct->next;
    1586                                         if(fCmp->next!=NULL)
    1587                                         {
    1588                                                 fCmp=fCmp->next;
    1589                                         }
    1590                                         else
    1591                                         {
    1592                                                 fAct=fAct->next;
    1593                                         }
    1594                                 }
    1595                                 //fAct=fAct->next;
    1596                         }//while(fAct.facetPtr->next!=NULL)
    1597                         delete alpha_i,alpha_j,sigma;
    1598                        
    1599                         /*If testfacet was minimal then fMin should still point there */
    1600                        
    1601                         //if(fMin->getFacetNormal()==ivNeg(testfacet.getFacetNormal()))                 
    1602 #ifdef gfan_DEBUG
    1603                         cout << "Checking for parallelity" << endl <<" fMin is";
    1604                         fMin->printNormal();
    1605                         cout << "testfacet is ";
    1606                         testfacet->printNormal();
    1607                         cout << endl;
    1608 #endif
    1609                         if (fMin==gcTmp.facetPtr)                       
    1610                         //if(areEqual(fMin->getFacetNormal(),ivNeg(testfacet.getFacetNormal())))
    1611                         //if (isParallel(fMin->getFacetNormal(),testfacet->getFacetNormal()))
    1612                         {                               
    1613                                 cout << "Parallel" << endl;
    1614                                 rChangeCurrRing(actRing);
    1615                                 //delete alpha_min, test;
    1616                                 return TRUE;
    1617                         }
    1618                         else
    1619                         {
    1620                                 cout << "Not parallel" << endl;
    1621                                 rChangeCurrRing(actRing);
    1622                                 //delete alpha_min, test;
    1623                                 return FALSE;
    1624                         }
    1625                 }//bool isSearchFacet
    1626                
    1627                 /** \brief Check for equality of two intvecs
    1628                 */
    1629                 bool areEqual(intvec const &a, intvec const &b)
    1630                 {
    1631                         bool res=TRUE;
    1632                         for(int ii=0;ii<this->numVars;ii++)
    1633                         {
    1634                                 if(a[ii]!=b[ii])
    1635                                 {
    1636                                         res=FALSE;
    1637                                         break;
    1638                                 }
    1639                         }
    1640                         return res;
     1729                                        sl2Act->next = new facet(2);
     1730                                        sl2Act = sl2Act->next;
     1731                                        sl2Act->setFacetNormal(f2Normal);
     1732                                }                                       
     1733                                codim2Act = codim2Act->next;
     1734                        }
     1735                        fAct = fAct->next;
     1736                }//if(fAct->isFlippable==TRUE)
     1737                else {fAct = fAct->next;}
     1738        }//End of copying facets into SLA                               
     1739                       
     1740        SearchListAct = SearchListRoot; //Set to beginning of list
     1741        /*Make SearchList doubly linked*/
     1742        while(SearchListAct!=NULL)
     1743        {
     1744                if(SearchListAct->next!=NULL)
     1745                {
     1746                        SearchListAct->next->prev = SearchListAct;                                     
    16411747                }
    1642                
    1643                 /** \brief The reverse search algorithm
    1644                 */
    1645                 void reverseSearch(gcone *gcAct) //no const possible here since we call gcAct->flip
    1646                 {
    1647                         facet *fAct=new facet();
    1648                         fAct = gcAct->facetPtr;                 
    1649                        
    1650                         while(fAct!=NULL)
    1651                         {
    1652                                 cout << "======================"<< endl;
    1653                                 gcAct->flip(gcAct->gcBasis,gcAct->facetPtr);
    1654                                 gcone *gcTmp = new gcone(*gcAct);
    1655                                 //idShow(gcTmp->gcBasis);
    1656                                 gcTmp->getConeNormals(gcTmp->gcBasis, TRUE);
    1657 #ifdef gfan_DEBUG
    1658                                 facet *f = new facet();
    1659                                 f=gcTmp->facetPtr;
    1660                                 while(f!=NULL)
    1661                                 {
    1662                                         f->printNormal();
    1663                                         f=f->next;                                     
    1664                                 }
    1665 #endif
    1666                                 gcTmp->showIntPoint();
    1667                                 /*recursive part goes gere*/
    1668                                 if (isSearchFacet(*gcTmp,(facet*)gcAct->facetPtr))
    1669                                 {
    1670                                         gcAct->next=gcTmp;
    1671                                         cout << "PING"<< endl;
    1672                                         reverseSearch(gcTmp);
    1673                                 }
    1674                                 else
    1675                                 {
    1676                                         delete gcTmp;
    1677                                         /*NOTE remove fAct from linked list. It's no longer needed*/
    1678                                 }
    1679                                 /*recursion ends*/
    1680                                 fAct = fAct->next;             
    1681                         }//while(fAct->next!=NULL)
    1682                 }//reverseSearch
    1683                
    1684                 /** \brief The new method of Markwig and Jensen
    1685                 * Compute gcBasis and facets for the arbitrary starting cone. Store \f$(codim-1)\f$-facets as normals.
    1686                 * In order to represent a facet uniquely compute also the \f$(codim-2)\f$-facets and norm by the gcd of the components.
    1687                 * Keep a list of facets as a linked list containing an intvec and an integer matrix.
    1688                 * Since a \f$(codim-1)\f$-facet belongs to exactly two full dimensional cones, we remove a facet from the list as
    1689                 * soon as we compute this facet again. Comparison of facets is done by...
    1690                 */
    1691                 void noRevS(gcone &gcRoot, bool usingIntPoint=FALSE)
    1692                 {       
    1693                         facet *SearchListRoot = new facet(); //The list containing ALL facets we come across
    1694                         facet *SearchListAct;
    1695                         SearchListAct = NULL;
    1696                         //SearchListAct = SearchListRoot;
    1697                        
    1698                         gcone *gcAct;
    1699                         gcAct = &gcRoot;
    1700                         gcone *gcPtr;   //Pointer to end of linked list of cones
    1701                         gcPtr = &gcRoot;
    1702                         gcone *gcNext;  //Pointer to next cone to be visited
    1703                         gcNext = &gcRoot;
    1704                         gcone *gcHead;
    1705                         gcHead = &gcRoot;
    1706                        
    1707                         facet *fAct;
    1708                         fAct = gcAct->facetPtr;                 
    1709                        
    1710                         ring rAct;
    1711                         rAct = currRing;
    1712                                                
    1713                         int UCNcounter=gcAct->getUCN();
    1714 #ifdef gfan_DEBUG
    1715                         cout << "NoRevs" << endl;
    1716                         cout << "Facets are:" << endl;
    1717                         gcAct->showFacets();
    1718 #endif                 
    1719                        
    1720                         gcAct->getCodim2Normals(*gcAct);
    1721                                
    1722                         //Compute unique representation of codim-2-facets
    1723                         gcAct->normalize();
    1724                        
    1725                         /*Make a copy of the facet list of first cone
    1726                         Since the operations getCodim2Normals and normalize affect the facets
    1727                         we must not memcpy them before these ops!
    1728                         */
    1729                         intvec *fNormal;// = new intvec(this->numVars);
    1730                         intvec *f2Normal;// = new intvec(this->numVars);
    1731                         facet *codim2Act; codim2Act = NULL;                     
    1732                         facet *sl2Root; //sl2Root = new facet(2);
    1733                         facet *sl2Act;  //sl2Act = sl2Root;
    1734                        
    1735                         for(int ii=0;ii<this->numFacets;ii++)
    1736                         {
    1737                                 //only copy flippable facets!
    1738                                 if(fAct->isFlippable==TRUE)
    1739                                 {
    1740                                         fNormal = fAct->getFacetNormal();
    1741                                         if( ii==0 || (ii>0 && SearchListAct==NULL) ) //1st facet may be non-flippable
    1742                                         {                                               
    1743                                                 SearchListAct = SearchListRoot;
    1744                                                 //memcpy(SearchListAct,fAct,sizeof(facet));                                     
    1745                                         }
    1746                                         else
    1747                                         {                       
    1748                                                 SearchListAct->next = new facet();
    1749                                                 SearchListAct = SearchListAct->next;                                           
    1750                                                 //memcpy(SearchListAct,fAct,sizeof(facet));                             
    1751                                         }
    1752                                         SearchListAct->setFacetNormal(fNormal);
    1753                                         SearchListAct->setUCN(this->getUCN());
    1754                                         SearchListAct->numCodim2Facets=fAct->numCodim2Facets;
    1755                                         SearchListAct->isFlippable=TRUE;
    1756                                         //Copy codim2-facets                           
    1757                                         codim2Act=fAct->codim2Ptr;
    1758                                         SearchListAct->codim2Ptr = new facet(2);
    1759                                         sl2Root = SearchListAct->codim2Ptr;
    1760                                         sl2Act = sl2Root;
    1761                                         //while(codim2Act!=NULL)
    1762                                         for(int jj=0;jj<fAct->numCodim2Facets;jj++)
    1763                                         {
    1764                                                 f2Normal = codim2Act->getFacetNormal();
    1765                                                 if(jj==0)
    1766                                                 {                                               
    1767                                                         sl2Act = sl2Root;
    1768                                                         sl2Act->setFacetNormal(f2Normal);
    1769                                                 }
    1770                                                 else
    1771                                                 {
    1772                                                         sl2Act->next = new facet(2);
    1773                                                         sl2Act = sl2Act->next;
    1774                                                         sl2Act->setFacetNormal(f2Normal);
    1775                                                 }                                       
    1776                                                 codim2Act = codim2Act->next;
    1777                                         }
    1778                                         fAct = fAct->next;
    1779                                 }//if(fAct->isFlippable==TRUE)
    1780                                 else {fAct = fAct->next;}
    1781                         }//End of copying facets into SLA                               
    1782                        
    1783                         SearchListAct = SearchListRoot; //Set to beginning of list
    1784                         /*Make SearchList doubly linked*/
    1785                         while(SearchListAct!=NULL)
    1786                         {
    1787                                 if(SearchListAct->next!=NULL)
    1788                                 {
    1789                                         SearchListAct->next->prev = SearchListAct;                                     
    1790                                 }
    1791                                 SearchListAct = SearchListAct->next;
    1792                         }
    1793                         SearchListAct = SearchListRoot; //Set to beginning of List
    1794                        
    1795                         fAct = gcAct->facetPtr;
     1748                SearchListAct = SearchListAct->next;
     1749        }
     1750        SearchListAct = SearchListRoot; //Set to beginning of List
     1751                       
     1752        fAct = gcAct->facetPtr;
    17961753                        //NOTE Disabled until code works as expected
    17971754                        //gcAct->writeConeToFile(*gcAct);
    17981755                       
    1799                         /*End of initialisation*/
    1800                         fAct = SearchListAct;
     1756        /*End of initialisation*/
     1757        fAct = SearchListAct;
    18011758                        /*2nd step
    1802                         Choose a facet from fListPtr, flip it and forget the previous cone
    1803                         We always choose the first facet from fListPtr as facet to be flipped
     1759        Choose a facet from fListPtr, flip it and forget the previous cone
     1760        We always choose the first facet from fListPtr as facet to be flipped
    18041761                        */                     
    1805                         while((SearchListAct!=NULL))// && counter<10)
    1806                         {//NOTE See to it that the cone is only changed after ALL facets have been flipped!                             
    1807                                 fAct = SearchListAct;
     1762        while((SearchListAct!=NULL))// && counter<10)
     1763        {//NOTE See to it that the cone is only changed after ALL facets have been flipped!                             
     1764                fAct = SearchListAct;
    18081765                               
    1809                                 while(fAct!=NULL)
    1810                                 {       //Since SLA should only contain flippables there should be no need to check for that
    1811                                         gcAct->flip(gcAct->gcBasis,fAct);
    1812                                         ring rTmp=rCopy(fAct->flipRing);
    1813                                         rComplete(rTmp);
    1814                                         rChangeCurrRing(rTmp);
    1815                                         gcone *gcTmp = new gcone::gcone(*gcAct,*fAct);
    1816                                         gcTmp->getConeNormals(gcTmp->gcBasis, FALSE);                                   
    1817                                         gcTmp->getCodim2Normals(*gcTmp);                                       
    1818                                         gcTmp->normalize();
    1819 #ifdef gfan_DEBUG
    1820                                         gcTmp->showFacets(1);
     1766                while(fAct!=NULL)
     1767                {       //Since SLA should only contain flippables there should be no need to check for that
     1768                        gcAct->flip(gcAct->gcBasis,fAct);
     1769                        ring rTmp=rCopy(fAct->flipRing);
     1770                        rComplete(rTmp);
     1771                        rChangeCurrRing(rTmp);
     1772                        gcone *gcTmp = new gcone::gcone(*gcAct,*fAct);
     1773                        gcTmp->getConeNormals(gcTmp->gcBasis, FALSE);                                   
     1774                        gcTmp->getCodim2Normals(*gcTmp);                                       
     1775                        gcTmp->normalize();
     1776#ifdef gfan_DEBUG
     1777                        gcTmp->showFacets(1);
    18211778#endif
    18221779                                        //gcTmp->writeConeToFile(*gcTmp);
    1823                                         /*add facets to SLA here*/
    1824                                         SearchListRoot=gcTmp->enqueueNewFacets(*SearchListRoot);
    1825 #ifdef gfan_DEBUG
    1826                                         if(SearchListRoot!=NULL)
    1827                                                 gcTmp->showSLA(*SearchListRoot);
    1828 #endif
    1829                                         rChangeCurrRing(gcAct->baseRing);
     1780                        /*add facets to SLA here*/
     1781                        SearchListRoot=gcTmp->enqueueNewFacets(*SearchListRoot);
     1782#ifdef gfan_DEBUG
     1783                        if(SearchListRoot!=NULL)
     1784                                gcTmp->showSLA(*SearchListRoot);
     1785#endif
     1786                        rChangeCurrRing(gcAct->baseRing);
    18301787                                        //rDelete(rTmp);
    1831                                         gcPtr->next=gcTmp;
    1832                                         gcPtr=gcPtr->next;
    1833                                         if(fAct->getUCN() == fAct->next->getUCN())
    1834                                         {
    1835                                                 fAct=fAct->next;
    1836                                         }
    1837                                         else
    1838                                                 break;
    1839                                 }//while( ( (fAct->next!=NULL) && (fAct->getUCN()==fAct->next->getUCN() ) ) );
     1788                        gcPtr->next=gcTmp;
     1789                        gcPtr=gcPtr->next;
     1790                        if(fAct->getUCN() == fAct->next->getUCN())
     1791                        {
     1792                                fAct=fAct->next;
     1793                        }
     1794                        else
     1795                                break;
     1796                }//while( ( (fAct->next!=NULL) && (fAct->getUCN()==fAct->next->getUCN() ) ) );
    18401797                                //Search for cone with smallest UCN
    1841                                 gcNext = gcHead;
    1842                                 while(gcNext!=NULL)
    1843                                 {
     1798                gcNext = gcHead;
     1799                while(gcNext!=NULL)
     1800                {
    18441801                                        //if( gcNext->getUCN() == UCNcounter+1 )
    1845                                         if( gcNext->getUCN() == SearchListRoot->getUCN() )
    1846                                         {
    1847                                                 gcAct = gcNext;
    1848                                                 rAct=rCopy(gcAct->baseRing);
    1849                                                 rComplete(rAct);
    1850                                                 rChangeCurrRing(rAct);                                         
    1851                                                 break;                                         
    1852                                         }
    1853                                         gcNext = gcNext->next;
    1854                                 }
    1855                                 UCNcounter++;
     1802                        if( gcNext->getUCN() == SearchListRoot->getUCN() )
     1803                        {
     1804                                gcAct = gcNext;
     1805                                rAct=rCopy(gcAct->baseRing);
     1806                                rComplete(rAct);
     1807                                rChangeCurrRing(rAct);                                         
     1808                                break;                                         
     1809                        }
     1810                        gcNext = gcNext->next;
     1811                }
     1812                UCNcounter++;
    18561813                                //SearchListAct = SearchListAct->next;
    18571814                                //SearchListAct = fAct->next;
    1858                                 SearchListAct = SearchListRoot;
    1859                         }
    1860                         cout << endl << "Found " << counter << " cones - terminating" << endl;
     1815                SearchListAct = SearchListRoot;
     1816        }
     1817        cout << endl << "Found " << counter << " cones - terminating" << endl;
    18611818               
    18621819                        //NOTE Hm, comment in and get a crash for free...
     
    18701827                        //NOTE: gcTmp may be deleted, gcRoot from main proc should probably not!
    18711828                       
    1872                 }//void noRevS(gcone &gc)       
    1873                
    1874                
    1875                 /** \brief Make a set of rational vectors into integers
    1876                 *
    1877                 * We compute the lcm of the denominators and multiply with this to get integer values.         
    1878                 * \param dd_MatrixPtr,intvec
    1879                 */
    1880                 void makeInt(dd_MatrixPtr const &M, int const line, intvec &n)
    1881                 {                       
    1882                         mpz_t denom[this->numVars];
     1829}//void noRevS(gcone &gc)       
     1830               
     1831               
     1832/** \brief Make a set of rational vectors into integers
     1833 *
     1834 * We compute the lcm of the denominators and multiply with this to get integer values.         
     1835 * \param dd_MatrixPtr,intvec
     1836 */
     1837void gcone::makeInt(dd_MatrixPtr const &M, int const line, intvec &n)
     1838{                       
     1839        mpz_t denom[this->numVars];
     1840        for(int ii=0;ii<this->numVars;ii++)
     1841        {
     1842                mpz_init_set_str(denom[ii],"0",10);
     1843        }
     1844               
     1845        mpz_t kgV,tmp;
     1846        mpz_init(kgV);
     1847        mpz_init(tmp);
     1848                       
     1849        for (int ii=0;ii<(M->colsize)-1;ii++)
     1850        {
     1851                mpz_t z;
     1852                mpz_init(z);
     1853                mpq_get_den(z,M->matrix[line-1][ii+1]);
     1854                mpz_set( denom[ii], z);
     1855                mpz_clear(z);                           
     1856        }
     1857                                               
     1858        /*Compute lcm of the denominators*/
     1859        mpz_set(tmp,denom[0]);
     1860        for (int ii=0;ii<(M->colsize)-1;ii++)
     1861        {
     1862                mpz_lcm(kgV,tmp,denom[ii]);
     1863                mpz_set(tmp,kgV);                               
     1864        }
     1865                       
     1866        /*Multiply the nominators by kgV*/
     1867        mpq_t qkgV,res;
     1868        mpq_init(qkgV);
     1869        mpq_set_str(qkgV,"1",10);
     1870        mpq_canonicalize(qkgV);
     1871                       
     1872        mpq_init(res);
     1873        mpq_set_str(res,"1",10);
     1874        mpq_canonicalize(res);
     1875                       
     1876        mpq_set_num(qkgV,kgV);
     1877                       
     1878//                      mpq_canonicalize(qkgV);
     1879        for (int ii=0;ii<(M->colsize)-1;ii++)
     1880        {
     1881                mpq_mul(res,qkgV,M->matrix[line-1][ii+1]);
     1882                n[ii]=(int)mpz_get_d(mpq_numref(res));
     1883        }
     1884                        //mpz_clear(denom[this->numVars]);
     1885        mpz_clear(kgV);
     1886        mpq_clear(qkgV); mpq_clear(res);                       
     1887                       
     1888}
     1889/**
     1890 * For all codim-2-facets we compute the gcd of the components of the facet normal and
     1891 * divide it out. Thus we get a normalized representation of each
     1892 * (codim-2)-facet normal, i.e. a primitive vector
     1893 */
     1894void gcone::normalize()
     1895{
     1896        int ggT=1;
     1897        facet *fAct;
     1898        facet *codim2Act;
     1899        fAct = this->facetPtr;
     1900        codim2Act = fAct->codim2Ptr;
     1901        intvec *n = new intvec(this->numVars);
     1902                       
     1903                        //while(codim2Act->next!=NULL)
     1904        while(fAct!=NULL)
     1905        {
     1906                while(codim2Act!=NULL)
     1907                {                               
     1908                        n=codim2Act->getFacetNormal();
    18831909                        for(int ii=0;ii<this->numVars;ii++)
    18841910                        {
    1885                                 mpz_init_set_str(denom[ii],"0",10);
    1886                         }
    1887                
    1888                         mpz_t kgV,tmp;
    1889                         mpz_init(kgV);
    1890                         mpz_init(tmp);
    1891                        
    1892                         for (int ii=0;ii<(M->colsize)-1;ii++)
    1893                         {
    1894                                 mpz_t z;
    1895                                 mpz_init(z);
    1896                                 mpq_get_den(z,M->matrix[line-1][ii+1]);
    1897                                 mpz_set( denom[ii], z);
    1898                                 mpz_clear(z);                           
    1899                         }
    1900                                                
    1901                         /*Compute lcm of the denominators*/
    1902                         mpz_set(tmp,denom[0]);
    1903                         for (int ii=0;ii<(M->colsize)-1;ii++)
    1904                         {
    1905                                 mpz_lcm(kgV,tmp,denom[ii]);
    1906                                 mpz_set(tmp,kgV);                               
    1907                         }
    1908                        
    1909                         /*Multiply the nominators by kgV*/
    1910                         mpq_t qkgV,res;
    1911                         mpq_init(qkgV);
    1912                         mpq_set_str(qkgV,"1",10);
    1913                         mpq_canonicalize(qkgV);
    1914                        
    1915                         mpq_init(res);
    1916                         mpq_set_str(res,"1",10);
    1917                         mpq_canonicalize(res);
    1918                        
    1919                         mpq_set_num(qkgV,kgV);
    1920                        
    1921 //                      mpq_canonicalize(qkgV);
    1922                         for (int ii=0;ii<(M->colsize)-1;ii++)
    1923                         {
    1924                                 mpq_mul(res,qkgV,M->matrix[line-1][ii+1]);
    1925                                 n[ii]=(int)mpz_get_d(mpq_numref(res));
    1926                         }
    1927                         //mpz_clear(denom[this->numVars]);
    1928                         mpz_clear(kgV);
    1929                         mpq_clear(qkgV); mpq_clear(res);                       
    1930                        
     1911                                ggT = intgcd(ggT,(*n)[ii]);
     1912                        }
     1913                        for(int ii=0;ii<this->numVars;ii++)
     1914                        {
     1915                                (*n)[ii] = ((*n)[ii])/ggT;
     1916                        }
     1917                        codim2Act->setFacetNormal(n);
     1918                        codim2Act = codim2Act->next;                           
    19311919                }
    1932                 /**
    1933                  * For all codim-2-facets we compute the gcd of the components of the facet normal and
    1934                  * divide it out. Thus we get a normalized representation of each
    1935                  * (codim-2)-facet normal, i.e. a primitive vector
    1936                 */
    1937                 void normalize()
    1938                 {
    1939                         int ggT=1;
    1940                         facet *fAct;
    1941                         facet *codim2Act;
    1942                         fAct = this->facetPtr;
    1943                         codim2Act = fAct->codim2Ptr;
    1944                         intvec *n = new intvec(this->numVars);
    1945                        
    1946                         //while(codim2Act->next!=NULL)
    1947                         while(fAct!=NULL)
    1948                         {
    1949                                 while(codim2Act!=NULL)
    1950                                 {                               
    1951                                         n=codim2Act->getFacetNormal();
    1952                                         for(int ii=0;ii<this->numVars;ii++)
    1953                                         {
    1954                                                 ggT = intgcd(ggT,(*n)[ii]);
    1955                                         }
    1956                                         for(int ii=0;ii<this->numVars;ii++)
    1957                                         {
    1958                                                 (*n)[ii] = ((*n)[ii])/ggT;
    1959                                         }
    1960                                         codim2Act->setFacetNormal(n);
    1961                                         codim2Act = codim2Act->next;                           
    1962                                 }
    1963                                 fAct = fAct->next;
    1964                         }
     1920                fAct = fAct->next;
     1921        }
    19651922                               
    1966                 }
    1967                 /** \brief Enqueue new facets into the searchlist
    1968                 * The searchlist (SLA for short) is implemented as a FIFO
    1969                 * Checks are done as follows:
    1970                 * 1) Check facet fAct against all facets in SLA for parallelity. If it is not parallel to any one add it.
    1971                 * 2) If it is parallel compare the codim2 facets. If they coincide the facets are equal and we delete the
    1972                 *       facet from SLA and do not add fAct.
    1973                 * It may very well happen, that SLA=\f$ \emptyset \f$ but we do not have checked all fActs yet. In this case we
    1974                 * can be sure, that none of the facets that are still there already were in SLA once, so we just dump them into SLA.
    1975                 * Takes ptr to search list root
    1976                 * Returns a pointer to new first element of Searchlist
    1977                 */
     1923}
     1924/** \brief Enqueue new facets into the searchlist
     1925 * The searchlist (SLA for short) is implemented as a FIFO
     1926 * Checks are done as follows:
     1927 * 1) Check facet fAct against all facets in SLA for parallelity. If it is not parallel to any one add it.
     1928 * 2) If it is parallel compare the codim2 facets. If they coincide the facets are equal and we delete the
     1929 *      facet from SLA and do not add fAct.
     1930 * It may very well happen, that SLA=\f$ \emptyset \f$ but we do not have checked all fActs yet. In this case we
     1931 * can be sure, that none of the facets that are still there already were in SLA once, so we just dump them into SLA.
     1932 * Takes ptr to search list root
     1933 * Returns a pointer to new first element of Searchlist
     1934 */
    19781935                //void enqueueNewFacets(facet &f)
    1979                 facet * enqueueNewFacets(facet &f)
    1980                 {
    1981                         facet *slHead;
    1982                         slHead = &f;
    1983                         facet *slAct;   //called with f=SearchListRoot
    1984                         slAct = &f;
    1985                         facet *slEnd;   //Pointer to end of SLA
    1986                         slEnd = &f;
    1987                         facet *slEndStatic;     //marks the end before a new facet is added             
    1988                         facet *fAct;
    1989                         fAct = this->facetPtr;
    1990                         facet *codim2Act;
    1991                         codim2Act = this->facetPtr->codim2Ptr;
    1992                         facet *sl2Act;
    1993                         sl2Act = f.codim2Ptr;
    1994                         /** Pointer to a facet that will be deleted */
    1995                         facet *deleteMarker;
    1996                         deleteMarker = NULL;
    1997                        
    1998                         /** Flag to indicate a facet that should be added to SLA*/
    1999                         bool doNotAdd=FALSE;
    2000                         /** \brief  Flag to mark a facet that might be added
    2001                         * The following case may occur:
    2002                         * A facet fAct is found to be parallel but not equal to the current facet slAct from SLA.
    2003                         * This does however not mean that there does not exist a facet behind the current slAct that is actually equal
    2004                         * to fAct. In this case we set the boolean flag maybe to TRUE. If we encounter an equality lateron, it is reset to
    2005                         * FALSE and the according slAct is deleted.
    2006                         * If slAct->next==NULL AND maybe==TRUE we know, that fAct must be added
    2007                         */
    2008                         volatile bool maybe=FALSE;
    2009                         /**A facet was removed, lengthOfSearchlist-- thus we must not rely on
    2010                         * if(notParallelCtr==lengthOfSearchList) but rather
    2011                         * if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE)
    2012                         */
    2013                         volatile bool removalOccured=FALSE;
    2014                         int ctr=0;      //encountered equalities in SLA
    2015                         int notParallelCtr=0;
    2016                         int lengthOfSearchList=1;
    2017                         while(slEnd->next!=NULL)
    2018                         {
    2019                                 slEnd=slEnd->next;
    2020                                 lengthOfSearchList++;
    2021                         }
    2022                         slEndStatic = slEnd;
    2023                         /*1st step: compare facetNormals*/
    2024                         intvec *fNormal=NULL; //= new intvec(this->numVars);
    2025                         intvec *f2Normal=NULL; //= new intvec(this->numVars);
    2026                         intvec *slNormal=NULL; //= new intvec(this->numVars);
    2027                         intvec *sl2Normal=NULL; //= new intvec(this->numVars);
    2028                        
    2029                         while(fAct!=NULL)
    2030                         {                                               
    2031                                 if(fAct->isFlippable==TRUE)
    2032                                 {
    2033                                         maybe=FALSE;
    2034                                         doNotAdd=TRUE;
    2035                                         fNormal=fAct->getFacetNormal();
    2036                                         slAct = slHead;
    2037                                         notParallelCtr=0;
     1936facet * gcone::enqueueNewFacets(facet &f)
     1937{
     1938        facet *slHead;
     1939        slHead = &f;
     1940        facet *slAct;   //called with f=SearchListRoot
     1941        slAct = &f;
     1942        facet *slEnd;   //Pointer to end of SLA
     1943        slEnd = &f;
     1944        facet *slEndStatic;     //marks the end before a new facet is added             
     1945        facet *fAct;
     1946        fAct = this->facetPtr;
     1947        facet *codim2Act;
     1948        codim2Act = this->facetPtr->codim2Ptr;
     1949        facet *sl2Act;
     1950        sl2Act = f.codim2Ptr;
     1951        /** Pointer to a facet that will be deleted */
     1952        facet *deleteMarker;
     1953        deleteMarker = NULL;
     1954                       
     1955        /** Flag to indicate a facet that should be added to SLA*/
     1956        bool doNotAdd=FALSE;
     1957        /** \brief  Flag to mark a facet that might be added
     1958         * The following case may occur:
     1959         * A facet fAct is found to be parallel but not equal to the current facet slAct from SLA.
     1960         * This does however not mean that there does not exist a facet behind the current slAct that is actually equal
     1961         * to fAct. In this case we set the boolean flag maybe to TRUE. If we encounter an equality lateron, it is reset to
     1962         * FALSE and the according slAct is deleted.
     1963         * If slAct->next==NULL AND maybe==TRUE we know, that fAct must be added
     1964         */
     1965        volatile bool maybe=FALSE;
     1966        /**A facet was removed, lengthOfSearchlist-- thus we must not rely on
     1967         * if(notParallelCtr==lengthOfSearchList) but rather
     1968         * if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE)
     1969         */
     1970        volatile bool removalOccured=FALSE;
     1971        int ctr=0;      //encountered equalities in SLA
     1972        int notParallelCtr=0;
     1973        int lengthOfSearchList=1;
     1974        while(slEnd->next!=NULL)
     1975        {
     1976                slEnd=slEnd->next;
     1977                lengthOfSearchList++;
     1978        }
     1979        slEndStatic = slEnd;
     1980        /*1st step: compare facetNormals*/
     1981        intvec *fNormal=NULL; //= new intvec(this->numVars);
     1982        intvec *f2Normal=NULL; //= new intvec(this->numVars);
     1983        intvec *slNormal=NULL; //= new intvec(this->numVars);
     1984        intvec *sl2Normal=NULL; //= new intvec(this->numVars);
     1985                       
     1986        while(fAct!=NULL)
     1987        {                                               
     1988                if(fAct->isFlippable==TRUE)
     1989                {
     1990                        maybe=FALSE;
     1991                        doNotAdd=TRUE;
     1992                        fNormal=fAct->getFacetNormal();
     1993                        slAct = slHead;
     1994                        notParallelCtr=0;
    20381995//                                      delete deleteMarker;
    20391996//                                      deleteMarker=NULL;
    20401997                                        /*If slAct==NULL and fAct!=NULL
    2041                                         we just copy all remaining facets into SLA*/
     1998                        we just copy all remaining facets into SLA*/
     1999                        if(slAct==NULL)
     2000                        {
     2001                                facet *fCopy;
     2002                                fCopy = fAct;
     2003                                while(fCopy!=NULL)
     2004                                {
    20422005                                        if(slAct==NULL)
    20432006                                        {
    2044                                                 facet *fCopy;
    2045                                                 fCopy = fAct;
    2046                                                 while(fCopy!=NULL)
     2007                                                slAct = new facet();
     2008                                                slHead = slAct;                                                         
     2009                                        }
     2010                                        else
     2011                                        {
     2012                                                slAct->next = new facet();
     2013                                                slAct = slAct->next;
     2014                                        }                                                       
     2015                                        slAct->setFacetNormal(fAct->getFacetNormal());
     2016                                        slAct->setUCN(fAct->getUCN());
     2017                                        slAct->isFlippable=fAct->isFlippable;
     2018                                        facet *f2Copy;
     2019                                        f2Copy = fCopy->codim2Ptr;
     2020                                        sl2Act = slAct->codim2Ptr;
     2021                                        while(f2Copy!=NULL)
     2022                                        {
     2023                                                if(sl2Act==NULL)
    20472024                                                {
    2048                                                         if(slAct==NULL)
    2049                                                         {
    2050                                                                 slAct = new facet();
    2051                                                                 slHead = slAct;                                                         
    2052                                                         }
    2053                                                         else
    2054                                                         {
    2055                                                                 slAct->next = new facet();
    2056                                                                 slAct = slAct->next;
    2057                                                         }                                                       
    2058                                                         slAct->setFacetNormal(fAct->getFacetNormal());
    2059                                                         slAct->setUCN(fAct->getUCN());
    2060                                                         slAct->isFlippable=fAct->isFlippable;
    2061                                                         facet *f2Copy;
    2062                                                         f2Copy = fCopy->codim2Ptr;
    2063                                                         sl2Act = slAct->codim2Ptr;
    2064                                                         while(f2Copy!=NULL)
    2065                                                         {
    2066                                                                 if(sl2Act==NULL)
    2067                                                                 {
    2068                                                                         sl2Act = new facet(2);
    2069                                                                         slAct->codim2Ptr = sl2Act;                                     
    2070                                                                 }
    2071                                                                 else
    2072                                                                 {
    2073                                                                         facet *marker;
    2074                                                                         marker = sl2Act;
    2075                                                                         sl2Act->next = new facet(2);
    2076                                                                         sl2Act = sl2Act->next;
    2077                                                                         sl2Act->prev = marker;
    2078                                                                 }
    2079                                                                 sl2Act->setFacetNormal(f2Copy->getFacetNormal());
    2080                                                                 sl2Act->setUCN(f2Copy->getUCN());
    2081                                                                 f2Copy = f2Copy->next;
    2082                                                         }
    2083                                                         fCopy = fCopy->next;
     2025                                                        sl2Act = new facet(2);
     2026                                                        slAct->codim2Ptr = sl2Act;                                     
    20842027                                                }
    2085                                                 break;
     2028                                                else
     2029                                                {
     2030                                                        facet *marker;
     2031                                                        marker = sl2Act;
     2032                                                        sl2Act->next = new facet(2);
     2033                                                        sl2Act = sl2Act->next;
     2034                                                        sl2Act->prev = marker;
     2035                                                }
     2036                                                sl2Act->setFacetNormal(f2Copy->getFacetNormal());
     2037                                                sl2Act->setUCN(f2Copy->getUCN());
     2038                                                f2Copy = f2Copy->next;
    20862039                                        }
    2087                                         /*End of */
    2088                                         while(slAct!=NULL)
     2040                                        fCopy = fCopy->next;
     2041                                }
     2042                                break;
     2043                        }
     2044                        /*End of */
     2045                        while(slAct!=NULL)
    20892046                                        //while(slAct!=slEndStatic->next)
    2090                                         {
     2047                        {
    20912048//                                              if(deleteMarker!=NULL)
    20922049//                                              {
     
    20942051//                                                      deleteMarker=NULL;
    20952052//                                              }
    2096                                                 removalOccured=FALSE;
    2097                                                 slNormal = slAct->getFacetNormal();
    2098 #ifdef gfan_DEBUG
    2099                                                 cout << "Checking facet (";
    2100                                                 fNormal->show(1,1);
    2101                                                 cout << ") against (";
    2102                                                 slNormal->show(1,1);
    2103                                                 cout << ")" << endl;
    2104 #endif
    2105                                                 if(!isParallel(fNormal, slNormal))
     2053                                removalOccured=FALSE;
     2054                                slNormal = slAct->getFacetNormal();
     2055#ifdef gfan_DEBUG
     2056                                cout << "Checking facet (";
     2057                                fNormal->show(1,1);
     2058                                cout << ") against (";
     2059                                slNormal->show(1,1);
     2060                                cout << ")" << endl;
     2061#endif
     2062                                if(!isParallel(fNormal, slNormal))
     2063                                {
     2064                                        notParallelCtr++;
     2065//                                                      slAct = slAct->next;
     2066                                }
     2067                                else    //fN and slN are parallel
     2068                                {
     2069                                                        //We check whether the codim-2-facets coincide
     2070                                        codim2Act = fAct->codim2Ptr;
     2071                                        ctr=0;
     2072                                        while(codim2Act!=NULL)
     2073                                        {
     2074                                                f2Normal = codim2Act->getFacetNormal();
     2075                                                                //sl2Act = f.codim2Ptr;
     2076                                                sl2Act = slAct->codim2Ptr;
     2077                                                while(sl2Act!=NULL)
    21062078                                                {
    2107                                                         notParallelCtr++;
    2108 //                                                      slAct = slAct->next;
     2079                                                        sl2Normal = sl2Act->getFacetNormal();
     2080                                                        if(areEqual(f2Normal, sl2Normal))
     2081                                                                ctr++;
     2082                                                        sl2Act = sl2Act->next;
     2083                                                }//while(sl2Act!=NULL)
     2084                                                codim2Act = codim2Act->next;
     2085                                        }//while(codim2Act!=NULL)
     2086                                        if(ctr==fAct->numCodim2Facets)  //facets ARE equal
     2087                                        {
     2088#ifdef gfan_DEBUG
     2089                                                cout << "Removing facet (";
     2090                                                slNormal->show(1,0);
     2091                                                cout << ") from SLA:" << endl;
     2092                                                fAct->fDebugPrint();
     2093                                                slAct->fDebugPrint();
     2094#endif
     2095                                                removalOccured=TRUE;
     2096                                                slAct->isFlippable=FALSE;
     2097                                                doNotAdd=TRUE;
     2098                                                maybe=FALSE;                                                           
     2099                                                if(slAct==slHead)       //We want to delete the first element of SearchList
     2100                                                {
     2101                                                        deleteMarker = slHead;                         
     2102                                                        slHead = slAct->next;                                           
     2103                                                        if(slHead!=NULL)
     2104                                                                slHead->prev = NULL;                                   
     2105                                                                        //set a bool flag to mark slAct as to be deleted
     2106                                                }//NOTE find a way to delete without affecting slAct = slAct->next
     2107                                                else if(slAct==slEndStatic)
     2108                                                {
     2109                                                        deleteMarker = slAct;                                   
     2110                                                        if(slEndStatic->next==NULL)
     2111                                                        {                                                       
     2112                                                                slEndStatic = slEndStatic->prev;
     2113                                                                slEndStatic->next = NULL;
     2114                                                                slEnd = slEndStatic;
     2115                                                        }
     2116                                                        else    //we already added a facet after slEndStatic
     2117                                                        {
     2118                                                                slEndStatic->prev->next = slEndStatic->next;
     2119                                                                slEndStatic->next->prev = slEndStatic->prev;
     2120                                                                slEndStatic = slEndStatic->prev;
     2121                                                                                        //slEnd = slEndStatic;
     2122                                                        }
     2123                                                }                                                               
     2124                                                else
     2125                                                {
     2126                                                        deleteMarker = slAct;
     2127                                                        slAct->prev->next = slAct->next;
     2128                                                        slAct->next->prev = slAct->prev;
    21092129                                                }
    2110                                                 else    //fN and slN are parallel
    2111                                                 {
    2112                                                         //We check whether the codim-2-facets coincide
    2113                                                         codim2Act = fAct->codim2Ptr;
    2114                                                         ctr=0;
    2115                                                         while(codim2Act!=NULL)
    2116                                                         {
    2117                                                                 f2Normal = codim2Act->getFacetNormal();
    2118                                                                 //sl2Act = f.codim2Ptr;
    2119                                                                 sl2Act = slAct->codim2Ptr;
    2120                                                                 while(sl2Act!=NULL)
    2121                                                                 {
    2122                                                                         sl2Normal = sl2Act->getFacetNormal();
    2123                                                                         if(areEqual(f2Normal, sl2Normal))
    2124                                                                                         ctr++;
    2125                                                                         sl2Act = sl2Act->next;
    2126                                                                 }//while(sl2Act!=NULL)
    2127                                                                 codim2Act = codim2Act->next;
    2128                                                         }//while(codim2Act!=NULL)
    2129                                                         if(ctr==fAct->numCodim2Facets)  //facets ARE equal
    2130                                                         {
    2131 #ifdef gfan_DEBUG
    2132                                                                 cout << "Removing facet (";
    2133                                                                 slNormal->show(1,0);
    2134                                                                 cout << ") from SLA:" << endl;
    2135                                                                 fAct->fDebugPrint();
    2136                                                                 slAct->fDebugPrint();
    2137 #endif
    2138                                                                 removalOccured=TRUE;
    2139                                                                 slAct->isFlippable=FALSE;
    2140                                                                 doNotAdd=TRUE;
    2141                                                                 maybe=FALSE;                                                           
    2142                                                                 if(slAct==slHead)       //We want to delete the first element of SearchList
    2143                                                                 {
    2144                                                                         deleteMarker = slHead;                         
    2145                                                                         slHead = slAct->next;                                           
    2146                                                                         if(slHead!=NULL)
    2147                                                                                 slHead->prev = NULL;                                   
    2148                                                                         //set a bool flag to mark slAct as to be deleted
    2149                                                                 }//NOTE find a way to delete without affecting slAct = slAct->next
    2150                                                                 else if(slAct==slEndStatic)
    2151                                                                         {
    2152                                                                                 deleteMarker = slAct;                                   
    2153                                                                                 if(slEndStatic->next==NULL)
    2154                                                                                 {                                                       
    2155                                                                                         slEndStatic = slEndStatic->prev;
    2156                                                                                         slEndStatic->next = NULL;
    2157                                                                                         slEnd = slEndStatic;
    2158                                                                                 }
    2159                                                                                 else    //we already added a facet after slEndStatic
    2160                                                                                 {
    2161                                                                                         slEndStatic->prev->next = slEndStatic->next;
    2162                                                                                         slEndStatic->next->prev = slEndStatic->prev;
    2163                                                                                         slEndStatic = slEndStatic->prev;
    2164                                                                                         //slEnd = slEndStatic;
    2165                                                                                 }
    2166                                                                         }                                                               
    2167                                                                         else
    2168                                                                         {
    2169                                                                                 deleteMarker = slAct;
    2170                                                                                 slAct->prev->next = slAct->next;
    2171                                                                                 slAct->next->prev = slAct->prev;
    2172                                                                         }
    21732130                                                               
    21742131                                                                //update lengthOfSearchList                                     
    2175                                                                 lengthOfSearchList--;
     2132                                                lengthOfSearchList--;
    21762133                                                                //delete slAct;
    21772134                                                                //slAct=NULL;
     
    21802137                                                                //deleteMarker=NULL;
    21812138                                                                //fAct = fAct->next;
    2182                                                                 break;
    2183                                                         }//if(ctr==fAct->numCodim2Facets)
    2184                                                         else    //facets are parallel but NOT equal. But this does not imply that there
     2139                                                break;
     2140                                        }//if(ctr==fAct->numCodim2Facets)
     2141                                        else    //facets are parallel but NOT equal. But this does not imply that there
    21852142                                                                //is no other facet later in SLA that might be equal.
    2186                                                         {
    2187                                                                 maybe=TRUE;
     2143                                        {
     2144                                                maybe=TRUE;
    21882145//                                                                      if(slAct->next==NULL && maybe==TRUE)
    21892146//                                                                      {
     
    21942151//                                                                      else
    21952152//                                                                      slAct=slAct->next;
    2196                                                         }
     2153                                        }
    21972154                                                        //slAct = slAct->next;
    21982155                                                        //delete deleteMarker;                                                 
    2199                                                 }//if(!isParallel(fNormal, slNormal))
    2200                                                 if( (slAct->next==NULL) && (maybe==TRUE) )
    2201                                                 {
    2202                                                         doNotAdd=FALSE;
    2203                                                         break;
    2204                                                 }
    2205                                                 slAct = slAct->next;
     2156                                }//if(!isParallel(fNormal, slNormal))
     2157                                if( (slAct->next==NULL) && (maybe==TRUE) )
     2158                                {
     2159                                        doNotAdd=FALSE;
     2160                                        break;
     2161                                }
     2162                                slAct = slAct->next;
    22062163                                                /* NOTE The following lines must not be here but rather called inside the if-block above.
    2207                                                 Otherwise results get crappy. Unfortunately there are two slAct=slAct->next calls now,
    2208                                                 (not nice!) but since they are in seperate branches of the if-statement there should not
     2164                                Otherwise results get crappy. Unfortunately there are two slAct=slAct->next calls now,
     2165                                (not nice!) but since they are in seperate branches of the if-statement there should not
    22092166                                                be a way it gets called twice thus ommiting one facet:
    2210                                                 slAct = slAct->next;*/                                         
     2167                                slAct = slAct->next;*/                                         
    22112168                                                //delete deleteMarker;
    22122169                                                //deleteMarker=NULL;
    22132170                                                //if slAct was marked as to be deleted, delete it here!
    2214                                         }//while(slAct!=NULL)                                                                   
    2215                                         if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE) || (doNotAdd==FALSE) )
    2216                                         //if( (notParallelCtr==lengthOfSearchList ) || doNotAdd==FALSE )
     2171                        }//while(slAct!=NULL)                                                                   
     2172                        if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE) || (doNotAdd==FALSE) )
     2173                                        //if( (notParallelCtr==lengthOfSearchList ) || doNotAdd==FALSE )
     2174                        {
     2175#ifdef gfan_DEBUG
     2176                                cout << "Adding facet (";
     2177                                fNormal->show(1,0);
     2178                                cout << ") to SLA " << endl;
     2179#endif
     2180                                                //Add fAct to SLA
     2181                                facet *marker;
     2182                                marker = slEnd;
     2183                                facet *f2Act;
     2184                                f2Act = fAct->codim2Ptr;
     2185                                               
     2186                                slEnd->next = new facet();
     2187                                slEnd = slEnd->next;
     2188                                facet *slEndCodim2Root;
     2189                                facet *slEndCodim2Act;
     2190                                slEndCodim2Root = slEnd->codim2Ptr;
     2191                                slEndCodim2Act = slEndCodim2Root;
     2192                                                               
     2193                                slEnd->setUCN(this->getUCN());
     2194                                slEnd->isFlippable = TRUE;
     2195                                slEnd->setFacetNormal(fNormal);
     2196                                slEnd->prev = marker;
     2197                                                //Copy codim2-facets
     2198                                intvec *f2Normal;// = new intvec(this->numVars);
     2199                                while(f2Act!=NULL)
     2200                                {
     2201                                        f2Normal=f2Act->getFacetNormal();
     2202                                        if(slEndCodim2Root==NULL)
    22172203                                        {
    2218 #ifdef gfan_DEBUG
    2219                                                 cout << "Adding facet (";
    2220                                                 fNormal->show(1,0);
    2221                                                 cout << ") to SLA " << endl;
    2222 #endif
    2223                                                 //Add fAct to SLA
    2224                                                 facet *marker;
    2225                                                 marker = slEnd;
    2226                                                 facet *f2Act;
    2227                                                 f2Act = fAct->codim2Ptr;
    2228                                                
    2229                                                 slEnd->next = new facet();
    2230                                                 slEnd = slEnd->next;
    2231                                                 facet *slEndCodim2Root;
    2232                                                 facet *slEndCodim2Act;
    2233                                                 slEndCodim2Root = slEnd->codim2Ptr;
     2204                                                slEndCodim2Root = new facet(2);
     2205                                                slEnd->codim2Ptr = slEndCodim2Root;                     
     2206                                                slEndCodim2Root->setFacetNormal(f2Normal);
    22342207                                                slEndCodim2Act = slEndCodim2Root;
    2235                                                                
    2236                                                 slEnd->setUCN(this->getUCN());
    2237                                                 slEnd->isFlippable = TRUE;
    2238                                                 slEnd->setFacetNormal(fNormal);
    2239                                                 slEnd->prev = marker;
    2240                                                 //Copy codim2-facets
    2241                                                 intvec *f2Normal;// = new intvec(this->numVars);
    2242                                                 while(f2Act!=NULL)
    2243                                                 {
    2244                                                         f2Normal=f2Act->getFacetNormal();
    2245                                                         if(slEndCodim2Root==NULL)
    2246                                                         {
    2247                                                                 slEndCodim2Root = new facet(2);
    2248                                                                 slEnd->codim2Ptr = slEndCodim2Root;                     
    2249                                                                 slEndCodim2Root->setFacetNormal(f2Normal);
    2250                                                                 slEndCodim2Act = slEndCodim2Root;
    2251                                                         }
    2252                                                         else                                   
    2253                                                         {
    2254                                                                 slEndCodim2Act->next = new facet(2);
    2255                                                                 slEndCodim2Act = slEndCodim2Act->next;
    2256                                                                 slEndCodim2Act->setFacetNormal(f2Normal);
    2257                                                         }
    2258                                                         f2Act = f2Act->next;
    2259                                                 }
    2260                                                 lengthOfSearchList++;
     2208                                        }
     2209                                        else                                   
     2210                                        {
     2211                                                slEndCodim2Act->next = new facet(2);
     2212                                                slEndCodim2Act = slEndCodim2Act->next;
     2213                                                slEndCodim2Act->setFacetNormal(f2Normal);
     2214                                        }
     2215                                        f2Act = f2Act->next;
     2216                                }
     2217                                lengthOfSearchList++;
    22612218                                                //delete f2Normal;                                             
    2262                                         }//if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE) ||
    2263                                         fAct = fAct->next;
    2264                                 }//if(fAct->isFlippable==TRUE)
    2265                                 else
    2266                                 {
    2267                                         fAct = fAct->next;
    2268                                 }
    2269                         }//while(fAct!=NULL)                                           
    2270                         return slHead;
     2219                        }//if( (notParallelCtr==lengthOfSearchList && removalOccured==FALSE) ||
     2220                        fAct = fAct->next;
     2221                }//if(fAct->isFlippable==TRUE)
     2222                else
     2223                {
     2224                        fAct = fAct->next;
     2225                }
     2226        }//while(fAct!=NULL)                                           
     2227        return slHead;
    22712228//                      delete sl2Normal;
    22722229//                      delete slNormal;
    22732230//                      delete f2Normal;
    22742231//                      delete fNormal;
    2275                 }//addC2N
    2276                
    2277                 /** \brief Compute the gcd of two ints
    2278                 */
    2279                 int intgcd(int a, int b)
    2280                 {
    2281                         int r, p=a, q=b;
    2282                         if(p < 0)
    2283                                 p = -p;
    2284                         if(q < 0)
    2285                                 q = -q;
    2286                         while(q != 0)
    2287                         {
    2288                                 r = p % q;
    2289                                 p = q;
    2290                                 q = r;
    2291                         }
    2292                         return p;
    2293                 }               
    2294                
    2295                 /** \brief Construct a dd_MatrixPtr from a cone's list of facets
    2296                 *
    2297                 */
    2298                 dd_MatrixPtr facets2Matrix(gcone const &gc)
    2299                 {
    2300                         facet *fAct;
    2301                         fAct = gc.facetPtr;
     2232}//addC2N
     2233               
     2234/** \brief Compute the gcd of two ints
     2235 */
     2236int gcone::intgcd(int a, int b)
     2237{
     2238        int r, p=a, q=b;
     2239        if(p < 0)
     2240                p = -p;
     2241        if(q < 0)
     2242                q = -q;
     2243        while(q != 0)
     2244        {
     2245                r = p % q;
     2246                p = q;
     2247                q = r;
     2248        }
     2249        return p;
     2250}               
     2251               
     2252/** \brief Construct a dd_MatrixPtr from a cone's list of facets
     2253 *
     2254 */
     2255dd_MatrixPtr gcone::facets2Matrix(gcone const &gc)
     2256{
     2257        facet *fAct;
     2258        fAct = gc.facetPtr;
    23022259       
    2303                         dd_MatrixPtr M;
    2304                         dd_rowrange ddrows;
    2305                         dd_colrange ddcols;
    2306                         ddcols=(this->numVars)+1;
    2307                         ddrows=this->numFacets;
    2308                         dd_NumberType numb = dd_Integer;
    2309                         M=dd_CreateMatrix(ddrows,ddcols);                       
    2310                        
    2311                         int jj=0;
     2260        dd_MatrixPtr M;
     2261        dd_rowrange ddrows;
     2262        dd_colrange ddcols;
     2263        ddcols=(this->numVars)+1;
     2264        ddrows=this->numFacets;
     2265        dd_NumberType numb = dd_Integer;
     2266        M=dd_CreateMatrix(ddrows,ddcols);                       
     2267                       
     2268        int jj=0;
    23122269                        //while(fAct->next!=NULL)
    2313                         while(fAct!=NULL)
    2314                         {
    2315                                 intvec *comp;
    2316                                 comp = fAct->getFacetNormal();
    2317                                 for(int ii=0;ii<this->numVars;ii++)
    2318                                 {
    2319                                         dd_set_si(M->matrix[jj][ii+1],(*comp)[ii]);
    2320                                 }
    2321                                 jj++;
    2322                                 fAct=fAct->next;                               
    2323                         }                       
    2324                        
    2325                         return M;
     2270        while(fAct!=NULL)
     2271        {
     2272                intvec *comp;
     2273                comp = fAct->getFacetNormal();
     2274                for(int ii=0;ii<this->numVars;ii++)
     2275                {
     2276                        dd_set_si(M->matrix[jj][ii+1],(*comp)[ii]);
    23262277                }
    2327                
    2328                 /** \brief Write information about a cone into a file on disk
    2329                 *
    2330                 * This methods writes the information needed for the "second" method into a file.
    2331                 * The file's is divided in sections containing information on
    2332                 * 1) the ring
    2333                 * 2) the cone's Groebner Basis
    2334                 * 3) the cone's facets
    2335                 * Each line contains exactly one date
    2336                 * Each section starts with its name in CAPITALS
    2337                 */
    2338                 void writeConeToFile(gcone const &gc, bool usingIntPoints=FALSE)
    2339                 {
    2340                         int UCN=gc.UCN;
    2341                         stringstream ss;
    2342                         ss << UCN;
    2343                         string UCNstr = ss.str();               
    2344                        
    2345                         char prefix[]="/tmp/cone";
    2346                         char *UCNstring;
    2347                         strcpy(UCNstring,UCNstr.c_str());
    2348                         char suffix[]=".sg";
    2349                         char *filename=strcat(prefix,UCNstring);
    2350                         strcat(filename,suffix);
     2278                jj++;
     2279                fAct=fAct->next;                               
     2280        }                       
     2281                       
     2282        return M;
     2283}
     2284               
     2285/** \brief Write information about a cone into a file on disk
     2286 *
     2287 * This methods writes the information needed for the "second" method into a file.
     2288 * The file's is divided in sections containing information on
     2289 * 1) the ring
     2290 * 2) the cone's Groebner Basis
     2291 * 3) the cone's facets
     2292 * Each line contains exactly one date
     2293 * Each section starts with its name in CAPITALS
     2294 */
     2295void gcone::writeConeToFile(gcone const &gc, bool usingIntPoints)
     2296{
     2297        int UCN=gc.UCN;
     2298        stringstream ss;
     2299        ss << UCN;
     2300        string UCNstr = ss.str();               
     2301                       
     2302        char prefix[]="/tmp/cone";
     2303        char *UCNstring;
     2304        strcpy(UCNstring,UCNstr.c_str());
     2305        char suffix[]=".sg";
     2306        char *filename=strcat(prefix,UCNstring);
     2307        strcat(filename,suffix);
    23512308                                       
    2352                         ofstream gcOutputFile(filename);
    2353                         facet *fAct = new facet(); //NOTE Why new?
    2354                         fAct = gc.facetPtr;                     
    2355                        
    2356                         char *ringString = rString(currRing);
    2357                        
    2358                         if (!gcOutputFile)
    2359                         {
    2360                                 cout << "Error opening file for writing in writeConeToFile" << endl;
     2309        ofstream gcOutputFile(filename);
     2310        facet *fAct = new facet(); //NOTE Why new?
     2311        fAct = gc.facetPtr;                     
     2312                       
     2313        char *ringString = rString(currRing);
     2314                       
     2315        if (!gcOutputFile)
     2316        {
     2317                cout << "Error opening file for writing in writeConeToFile" << endl;
     2318        }
     2319        else
     2320        {       gcOutputFile << "UCN" << endl;
     2321        gcOutputFile << this->UCN << endl;
     2322        gcOutputFile << "RING" << endl;
     2323        gcOutputFile << ringString << endl;                     
     2324                                //Write this->gcBasis into file
     2325        gcOutputFile << "GCBASIS" << endl;                             
     2326        for (int ii=0;ii<IDELEMS(gc.gcBasis);ii++)
     2327        {                                       
     2328                gcOutputFile << p_String((poly)gc.gcBasis->m[ii],gc.baseRing) << endl;
     2329        }                               
     2330                               
     2331        gcOutputFile << "FACETS" << endl;                                                               
     2332                                //while(fAct->next!=NULL)
     2333        while(fAct!=NULL)
     2334        {       
     2335                intvec *iv = new intvec(gc.numVars);
     2336                iv=fAct->getFacetNormal();
     2337                for (int ii=0;ii<iv->length();ii++)
     2338                {
     2339                        if (ii<iv->length()-1)
     2340                        {
     2341                                gcOutputFile << (*iv)[ii] << ",";
    23612342                        }
    23622343                        else
    2363                         {       gcOutputFile << "UCN" << endl;
    2364                                 gcOutputFile << this->UCN << endl;
    2365                                 gcOutputFile << "RING" << endl;
    2366                                 gcOutputFile << ringString << endl;                     
    2367                                 //Write this->gcBasis into file
    2368                                 gcOutputFile << "GCBASIS" << endl;                             
    2369                                 for (int ii=0;ii<IDELEMS(gc.gcBasis);ii++)
    2370                                 {                                       
    2371                                         gcOutputFile << p_String((poly)gc.gcBasis->m[ii],gc.baseRing) << endl;
    2372                                 }                               
     2344                        {
     2345                                gcOutputFile << (*iv)[ii] << endl;
     2346                        }
     2347                }
     2348                fAct=fAct->next;
     2349                                        //delete iv; iv=NULL;
     2350        }                               
    23732351                               
    2374                                 gcOutputFile << "FACETS" << endl;                                                               
    2375                                 //while(fAct->next!=NULL)
    2376                                 while(fAct!=NULL)
    2377                                 {       
    2378                                         intvec *iv = new intvec(gc.numVars);
    2379                                         iv=fAct->getFacetNormal();
    2380                                         for (int ii=0;ii<iv->length();ii++)
    2381                                         {
    2382                                                 if (ii<iv->length()-1)
    2383                                                 {
    2384                                                         gcOutputFile << (*iv)[ii] << ",";
    2385                                                 }
    2386                                                 else
    2387                                                 {
    2388                                                         gcOutputFile << (*iv)[ii] << endl;
    2389                                                 }
    2390                                         }
    2391                                         fAct=fAct->next;
    2392                                         //delete iv; iv=NULL;
    2393                                 }                               
    2394                                
    2395                                 gcOutputFile.close();
     2352        gcOutputFile.close();
    23962353                                //delete fAct; fAct=NULL;
    2397                         }
    2398                        
    2399                 }//writeConeToFile(gcone const &gc)
    2400                
    2401                 /** \brief Reads a cone from a file identified by its number
    2402                 */
    2403                 void readConeFromFile(int gcNum)
    2404                 {
    2405                 }
    2406                
    2407         friend class facet;
    2408 };//class gcone
     2354        }
     2355                       
     2356}//writeConeToFile(gcone const &gc)
     2357               
     2358/** \brief Reads a cone from a file identified by its number
     2359 */
     2360void gcone::readConeFromFile(int gcNum)
     2361{
     2362}       
     2363
    24092364
    24102365int gcone::counter=0;
Note: See TracChangeset for help on using the changeset viewer.