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:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>