Return to tigers.c CVS log

Up to [local] / OpenXM / src / Ti

Annotation of OpenXM/src/Ti/tigers.c, Revision 1.1.1.1

1.1       maekawa     1: /*
                      2: ** tigers.c                                 Birk Huber, 2/99
                      3: ** -- reverse search loop and main calling program for tigers.
                      4: **
                      5: **
                      6: ** TiGERS,  Toric Groebner Basis Enumeration by Reverse Search
                      7: ** copyright (c) 1999  Birk Huber
                      8: **
                      9: */
                     10: #include<stdio.h>
                     11: #include<stdlib.h>
                     12: #include "utils.h"
                     13: #include "gset.h"
                     14: int rsearch_cache=TRUE;
                     15: extern int NT;
                     16:
                     17: /*
                     18: ** Output initial ideals and numbers of facets at each stage.
                     19: */
                     20: FILE *outfile;
                     21: int print_init=TRUE;
                     22: int print_tree=TRUE;
                     23:
                     24: int stats_minfacets=-1;
                     25: int stats_minelts=-1;
                     26: int stats_mindeg=-1;
                     27: int stats_maxfacets=0;
                     28: int stats_maxelts=0;
                     29: int stats_maxdeg=0;
                     30: int stats_tdepth=0;
                     31: int stats_ecounter=0;
                     32:
                     33: #define max(a,b) (((a)>(b))?(a):(b))
                     34: #define min(a,b) (((a)<(b))?(a):(b))
                     35: void vertex_print(gset g1){
                     36:   if (NT == 1) {
                     37:     gset_print(outfile,g1); fprintf(outfile," ,\n");
                     38:   }else{
                     39:     stats_maxfacets=max(gset_nfacets(g1),stats_maxfacets);
                     40:     stats_maxelts=max(gset_nelts(g1),stats_maxelts);
                     41:     stats_maxdeg=max(gset_deg(g1),stats_maxdeg);
                     42:     if (stats_minfacets<0) stats_minfacets=gset_nfacets(g1);
                     43:     else stats_minfacets=min(stats_minfacets,gset_nfacets(g1));
                     44:     if (stats_minelts<0) stats_minelts=gset_nelts(g1);
                     45:     else stats_minelts=min(stats_minelts,gset_nelts(g1));
                     46:     if (stats_mindeg<0) stats_mindeg=gset_deg(g1);
                     47:     else stats_mindeg=min(stats_mindeg,gset_deg(g1));
                     48:     fprintf(outfile,"Vtx: %d (%d facets/%d binomials/degree %d)\n",
                     49:            gset_id(g1),gset_nfacets(g1),gset_nelts(g1),gset_deg(g1));
                     50:     if (print_init==TRUE){
                     51:       fprintf(outfile,"    Initial ideal:");gset_init_print(outfile,g1);
                     52:       fprintf(outfile,"\n  Facet Binomials:");gset_facet_print(outfile,g1);
                     53:     }
                     54:     else  gset_print(outfile,g1);
                     55:     if (print_tree==TRUE && rsearch_cache==TRUE && gset_cache_vtx(g1)!=0){
                     56:       fprintf(outfile,"\n  Reducing Edge: [%d,%d]",
                     57:               gset_id(g1),gset_id(gset_cache_vtx(g1)));
                     58:     }
                     59:     fprintf(outfile,"\n");
                     60:   }
                     61: }
                     62:
                     63:
                     64: int rsearch(gset g1){
                     65:   gset G1,G2=0;
                     66:   binomial b=0,btmp;
                     67:   int counter=0,done=FALSE, depth=0;
                     68:
                     69:   stats_tdepth=0;
                     70:   stats_ecounter=0;
                     71:
                     72:   /* make copy of first grobner basis */
                     73:   G1=gset_new();
                     74:   for(b=gset_first(g1);b!=0;b=binomial_next(b)){
                     75:      btmp=binomial_new();
                     76:      binomial_copy(b,btmp);
                     77:      gset_insert(G1,btmp);
                     78:   }
                     79:
                     80:
                     81:   /* Do groebner walk to grobner basis wrt default term order*/
                     82:    while((b=gset_downedge(G1))!=0){
                     83:       fprintf(stderr,"Warning: rsearch doing walk to get to root\n");
                     84:       G2=gset_flip(G1,b);
                     85:       gset_free(G1);
                     86:       G1=G2;
                     87:     }
                     88:     btmp=(b=gset_first(G1));
                     89:
                     90:   /* output first groebner basis*/
                     91:     gset_setfacets(G1);
                     92:     gset_id(G1)=++counter;
                     93:     vertex_print(G1);
                     94:
                     95:   while(done==FALSE){
                     96:     while(b!=0){
                     97:       if (gset_isfacet(G1,b)==TRUE && binomial_ordered(b)==TRUE){
                     98:         stats_ecounter++;
                     99:         G2=gset_flip(G1,b);
                    100:         btmp=gset_downedge(G2);
                    101:         if (monomial_equal(binomial_lead(b),binomial_trail(btmp))==TRUE &&
                    102:             monomial_equal(binomial_trail(b),binomial_lead(btmp))==TRUE ){
                    103:           if (rsearch_cache==TRUE){
                    104:             gset_cache_vtx(G2)=G1;
                    105:             gset_cache_edge(G2)=b->next;
                    106:           }
                    107:           else{
                    108:            gset_free(G1);
                    109:           }
                    110:           G1=G2;
                    111:           depth++;
                    112:           if (stats_tdepth<depth) stats_tdepth=depth;
                    113:           b=gset_first(G1);
                    114:           gset_setfacets(G1);
                    115:           gset_id(G1)=++counter;
                    116:           vertex_print(G1);
                    117:         }
                    118:         else {
                    119:           gset_free(G2);
                    120:           b=binomial_next(b);
                    121:        }
                    122:       }
                    123:       else b=binomial_next(b);
                    124:     }
                    125:     depth--;
                    126:     if (rsearch_cache==TRUE){
                    127:       b=gset_cache_edge(G1);
                    128:       if ((G2=gset_cache_vtx(G1))==0) done=TRUE;
                    129:       else{
                    130:         gset_free(G1);
                    131:         G1=G2;
                    132:       }
                    133:     }
                    134:     else{
                    135:       if ((btmp=gset_downedge(G1))==0) done=TRUE;
                    136:       else{
                    137:         G2=gset_flip(G1,btmp);
                    138:         b=gset_first(G2);
                    139:         while(monomial_equal(binomial_lead(b),binomial_trail(btmp))==FALSE){
                    140:           b=binomial_next(b);
                    141:         }
                    142:         b=binomial_next(b);
                    143:         gset_free(G1);
                    144:         G1=G2;
                    145:       }
                    146:     }
                    147:   }
                    148:   gset_free(G1);
                    149:   return counter;
                    150:  }
                    151:
                    152:
                    153:
                    154:
                    155:
                    156:
                    157:
                    158:
                    159:
                    160:
                    161:
                    162: