Return to tigers.c CVS log

Up to [local] / OpenXM_contrib / TiGERS_0.9

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