Annotation of OpenXM_contrib/TiGERS_0.9/tigers.c, Revision 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:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>