Annotation of OpenXM/src/Ti/call.c, Revision 1.1.1.1
1.1 maekawa 1: /*
2: ** call.c Birk Huber, 2/99
3: ** -- main calling file for tigers code
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<string.h>
13: #include<time.h>
14: #include "utils.h"
15: #include "gset.h"
16: #include "matrices.h"
17:
18: int NT = 1;
19:
20: /*
21: ** write a description of program usage to stderr
22: */
23: usage(prog)
24: char *prog;
25: {
26: static char *helpmsg[] = {
27: "Function: Enumerate all Groebner bases of a toric ideal I_A.",
28: " \n",
29: "Input: \n ",
30: " A) A ring description (for now just a number of variables)\n",
31: " followed by a reduced Groebner basis for I_A.\n",
32: " example:\n",
33: " R: 5\n",
34: " G: {a^2*c-b^2*e, a^2*d-b*e^2, b*d-c*e}\n",
35: " or \n",
36: " B) An integer matrix A (defining I_A).\n",
37: " example:\n",
38: " M: { 3 5 : 2 1 1 1 1 1 \n",
39: " 3 0 1 2 1 0 \n",
40: " 4 0 0 1 2 1}\n",
41: " Note: Lines beginning with a % are comments and are ignored.\n",
42: " Comment lines should only occur at the beginning of the file.\n",
43: " : When binomials are printed out (and read in) they can be \n",
44: " preceeded by the characters !, or # \n",
45: " ! means the binomial is known not to be a facet.\n",
46: " # means the binomial is known to be a facet.\n",
47: " \n",
48: "Options:\n",
49: " -h print this message\n"
50: " -i (filename) set file name for input [default: stdin]\n",
51: " -o (filename) set file name for output [default: stdout]\n",
52: " -R only compute root of tree \n",
53: " -r compute all grobner bases [done by default]\n",
54: " -C turn partial caching on [done by default]\n",
55: " -c turn partial caching off \n",
56: " -T print edges of search tree \n",
57: " -t do not print edges of search tree [assumed by default]\n", " -L print vertices by giving initial ideals\n",
58: " and printing facet biomials.\n",
59: " -l print vertices as grobner bases [done by default]\n",
60: " -F Use only linear algebra when testing facets [default]\n",
61: " -f use FLIPPABILITY test first when determining facets\n",
62: " -e use exhaustive search instead of reverse search\n",
63: " -E use reverse search [default]\n",
64: NULL
65: };
66: char **p=helpmsg;
67:
68: fprintf(stderr,"Usage: %s {Options} \n",prog);
69: while(*p)(void) fputs(*p++,stderr);
70: exit(-1);
71: }
72:
73: FILE *infile=stdin, *outfile=stdout;
74: extern int rsearch_cache;
75: extern int print_tree;
76: extern int print_init;
77: extern int stats_minfacets;
78: extern int stats_minelts;
79: extern int stats_mindeg;
80: extern int stats_maxfacets;
81: extern int stats_maxelts;
82: extern int stats_maxdeg;
83: extern int stats_ecounter;
84: extern int stats_tdepth;
85: extern int lptest;
86: int root_only=FALSE;
87: int compGB=FALSE;
88: int use_exsearch=FALSE;
89:
90: #define MATFOUND 1
91: #define GSETFOUND 2
92: main2(int argc, char **argv ){
93: char *c,cc, *prog=argv[0], *ifname=0, *ofname=0;
94: int tmp,acnt,stat=0,counter;
95: gset G1=0,gset_toric_ideal();
96: int **M=0,Mn,Mm;
97: double tt;
98:
99: /* initialize parameters */
100: root_only=FALSE;
101: rsearch_cache=TRUE;
102: print_tree=FALSE;
103: print_init=FALSE;
104:
105: /* parse command line */
106: while (--argc > 0 && (*++argv)[0] == '-'){
107: acnt=0;
108: for (c = argv[0]+1; *c != '\0'; c++){
109: switch (*c) {
110: case 'h': usage(prog); break;
111: case 'R': root_only=TRUE; break; /* Root Flag On */
112: case 'r': root_only=FALSE; break; /* Root Flag Off */
113: case 'C': rsearch_cache=TRUE; break;/* Turn partial caching on*/
114: case 'c': rsearch_cache=FALSE;break;/* Turn partical caching off*/
115: case 'T': print_tree=TRUE; break; /* Turn tree printing on */
116: case 't': print_tree=FALSE; break; /* Turn tree printing off*/
117: case 'L': print_init=TRUE; break; /* Turn initial ideal printing on */
118: case 'l': print_init=FALSE; break; /* Turn initial ideal printing off */
119: case 'f': lptest=3; break; /*check facets with linalg and */
120: /*flipability tests */
121: case 'F': lptest=1; break; /*check facets only with linalg */
122: case 'A': lptest=2; use_exsearch=TRUE;break; /*check facets only for flipability*/
123: case 'E': use_exsearch=FALSE;break; /*use reverse search to enumerate */
124: case 'e': use_exsearch=TRUE; break; /*use exhaustive search */
125: case 'i': case 'I':
126: argc--;
127: ifname=strdup(argv[++acnt]); /* scan infile name */
128: fprintf(stderr,"using filename %s for input\n",ifname);
129: break;
130: case 'o': case 'O':argc--;
131: ofname=strdup(argv[++acnt]); /* scan infile name */
132: fprintf(stderr,"using filename %s for output\n",ofname);
133: break; /* scan outfile name */
134: break;
135: default:
136: fprintf(stderr,"%s: illegal option %c\n",prog,*c);
137: }
138: }
139: argv+=acnt;
140: }
141: if (argc != 0) usage(prog);
142:
143: /* open infile and outfile (if nesc) */
144: if (ifname!=0 && (infile=fopen(ifname,"r"))==0){
145: fprintf(stderr," %s: couldn't open %s for input\n",prog,ifname);
146: exit(1);
147: }
148: if (ofname!=0 && (outfile=fopen(ofname,"w"))==0){
149: fprintf(stderr," %s: couldn't open %s for output\n",prog,ofname);
150: exit(1);
151: }
152:
153: /* scan input from infile and outfile */
154:
155: eatwhite(infile);
156: cc=getc(infile);
157: if (cc=='R'){
158: while((cc=getc(infile))!=':');
159: if (ring_read(infile)==FALSE){
160: fprintf(stderr,"%s: ring_read() failed\n",prog);
161: exit(1);
162: }
163: eatwhite(infile);
164: cc=getc(infile);
165: }
166: if (cc=='G'){
167: while((cc=getc(infile))!=':');
168: if (ring_N<0) {
169: fprintf(stderr,"%s: ring not set\n",prog);
170: exit(1);
171: }
172: G1=gset_new();
173: if (gset_read(infile,G1)==FALSE){
174: fprintf(stderr,"%s: gset_read() failed\n",prog);
175: exit(1);
176: }
177: stat=GSETFOUND;
178: }
179: else if (cc=='M'){
180: while((cc=getc(infile))!=':');
181: if ((M=imatrix_read(infile,&Mm,&Mn))==0){
182: fprintf(stderr,"%s: imatrix_read() failed\n",prog);
183: exit(1);
184: }
185: if (ring_N==0) ring_set(Mn);
186: else if (ring_N!=Mn) {
187: fprintf(stderr,"%s: Matrix collum and ring dimensions must agree\n",prog);
188: exit(1);
189: }
190: stat=MATFOUND;
191: }
192: else {
193: fprintf(stderr,"%s,: Input files contains neither a generating set\n",prog);
194: fprintf(stderr," nor a matrix description of a toric ideal\n");
195: exit(1);
196: }
197:
198: /* ensure we have root */
199: if (stat==MATFOUND){
200: G1=gset_toric_ideal(M,Mm,Mn);
201: }
202: else {
203: if (compGB==TRUE){gset_rgb(G1,monomial_lexcomp);}
204: else {
205: /* could put checks to make sure input is toric rgb */
206: /* then use grobner walk to get to first rgb */
207: }
208: }
209:
210: if (NT == 1) {
211:
212: fprintf(outfile,"[\n");
213: /* perform reverse search if desired*/
214: if (root_only==FALSE){
215: if (use_exsearch==FALSE){
216: /* should double check we are at root */
217: tt=clock();
218: counter=rsearch(G1);
219: tt=(clock()-tt)/CLOCKS_PER_SEC;
220: fprintf(outfile,"\n");
221: } else {
222: tt=clock();
223: counter=exsearch(G1);
224: tt=(clock()-tt)/CLOCKS_PER_SEC;
225: fprintf(outfile,"\n");
226: }
227: }
228:
229: fprintf(outfile,"]\n");
230: goto epilogue ;
231: }
232: /* if NT != 1, then start the followings. */
233: /* output first GB if desired */
234: fprintf(outfile,"%% starting GB:\n");
235: fprintf(outfile,"R: %d\n",ring_N);
236: fprintf(outfile,"G: ");
237: gset_print(outfile,G1);
238: fprintf(outfile,"\n");
239:
240: /* perform reverse search if desired*/
241: if (root_only==FALSE){
242: if (use_exsearch==FALSE){
243: /* should double check we are at root */
244: fprintf(outfile,"\n Enumerating Groebner bases\n");
245: fprintf(outfile," using reverse search\n");
246: if (ifname!=0) fprintf(outfile," taking input from %s\n",ifname);
247: if (rsearch_cache==FALSE) fprintf(outfile," without partial caching\n");
248: else fprintf(outfile," with partial caching\n");
249: switch(lptest){
250: case 1:
251: fprintf(outfile," using only linear programing to test facets\n");
252: break;
253: case 3:
254: fprintf(outfile," using wall ideal pretest for facet checking\n");
255: break;
256: case 2:
257: fprintf(stderr,"Error: can not use -A option with reverse search\n");
258: break;
259: }
260: tt=clock();
261: counter=rsearch(G1);
262: tt=(clock()-tt)/CLOCKS_PER_SEC;
263: fprintf(outfile,"\n");
264: fprintf(outfile,"Number of Groebner bases found %d\n",counter);
265: fprintf(outfile,"Number of edges of state polytope %d\n",stats_ecounter);
266: fprintf(outfile,"max caching depth %d\n",stats_tdepth);
267: fprintf(outfile,"max facet binomials %d\n",stats_maxfacets);
268: fprintf(outfile,"min facet binomials %d\n",stats_minfacets);
269: fprintf(outfile,"max elts %d\n",stats_maxelts);
270: fprintf(outfile,"min elts %d\n",stats_minelts);
271: fprintf(outfile,"max degree %d\n",stats_maxdeg);
272: fprintf(outfile,"min degree %d\n",stats_mindeg);
273: if (ifname!=0) fprintf(outfile,"%s: ",ifname);
274: fprintf(outfile,"Reverse Search, ");
275: switch(rsearch_cache){
276: case TRUE:
277: fprintf(outfile," Caching,");
278: break;
279: case FALSE:
280: fprintf(outfile," NO Caching,");
281: break;
282: }
283: switch(lptest){
284: case 1:
285: fprintf(outfile," LP only.\n");
286: break;
287: case 3:
288: fprintf(outfile," A-pretest,\n");
289: break;
290: }
291: fprintf(outfile,"time used (in seconds) %4.2lf\n",tt);
292: return 0;
293: }
294: else {
295: fprintf(outfile,"\nEnumerating Groebner bases\n");
296: fprintf(outfile,"using exhaustive searching");
297: if (ifname!=0) fprintf(outfile,"taking input from %s\n",ifname);
298: else fprintf(outfile,"\n");
299: switch(lptest){
300: case 1:
301: fprintf(outfile," using only linear programing to test facets\n");
302: break;
303: case 3:
304: fprintf(outfile," using wall ideal pretest for facet checking\n");
305: break;
306: case 2:
307: fprintf(outfile,"Using wall ideal pretest instead of facet checking\n");
308: fprintf(outfile," FINDING ALL A-GRADED INITIALS CONNECTED TO ROOT\n");
309: break;
310: }
311: tt=clock();
312: counter=exsearch(G1);
313: tt=(clock()-tt)/CLOCKS_PER_SEC;
314: fprintf(outfile,"\n");
315: fprintf(outfile,"Number of Groebner bases found %d\n",counter);
316: fprintf(outfile,"Number of edges of state polytope %d\n",stats_ecounter);
317: fprintf(outfile,"max facet binomials %d\n",stats_maxfacets);
318: fprintf(outfile,"min facet binomials %d\n",stats_minfacets);
319: fprintf(outfile,"max elts %d\n",stats_maxelts);
320: fprintf(outfile,"min elts %d\n",stats_minelts);
321: fprintf(outfile,"max degree %d\n",stats_maxdeg);
322: fprintf(outfile,"min degree %d\n",stats_mindeg);
323: if (ifname!=0) fprintf(outfile,"%s: ",ifname);
324: fprintf(outfile,"Exhaustive search, ");
325: switch(lptest){
326: case 1:
327: fprintf(outfile," LP only\n");
328: break;
329: case 3:
330: fprintf(outfile," A-pretest\n");
331: break;
332: case 2:
333: fprintf(outfile," A-only\n");
334: break;
335: default:
336: fprintf(outfile,"\n");
337: }
338: fprintf(outfile,"time used (in seconds) %4.2lf\n",tt);
339: return 0;
340: }
341: }
342:
343: epilogue: ;
344: /* clean up */
345: LP_free_space();
346: if (G1!=0) gset_free(G1);
347: }
348:
349:
350: /************************ NT ***************************/
351: static int findNextToken(char *is, int start)
352: {
353: if (start == -1) goto endtext ;
354: while ( is[start] <= ' ') {
355: if (is[start] == '\0' ) goto endtext ;
356: start++;
357: }
358: while ( is[start] > ' ') {
359: if (is[start] == '\0') goto endtext ;
360: start++;
361: }
362: while ( is[start] <= ' ') {
363: if (is[start] == '\0' ) goto endtext ;
364: start++;
365: }
366: return(start);
367: endtext: ;
368: fprintf(stderr,"findNextToken: end of the text.\n");
369: return(-1);
370: }
371: int **imatrix_read_from_string(char *is,int *m, int *n) {
372: char c;
373: int i,j;
374: int **M;
375: int pt = 0;
376:
377: /* 2 3 :
378: 1 1 1
379: 0 1 2
380: */
381: /* read in matrix dimensions and initialize matrix */
382: sscanf(is,"%d %d :",m,n);
383: M=new_imatrix(*m,*n);
384: pt = findNextToken(is,pt); /* n */
385: pt = findNextToken(is,pt); /* : */
386:
387: /* read in matrix entrees */
388: for(i=0;i<*m;i++){
389: for(j=0;j<*n;j++){
390: pt = findNextToken(is,pt);
391: sscanf(&(is[pt]),"%d",&(IMref(M,i,j)));
392: }
393: }
394:
395: return M;
396: }
397:
398: tiger_executeString_M(char *is) {
399: char *c,cc, *prog="tigers", *ifname=0, *ofname=0;
400: int tmp,acnt,stat=0,counter;
401: gset G1=0,gset_toric_ideal();
402: int **M=0,Mn,Mm;
403: double tt;
404:
405: /* initialize parameters */
406: root_only=FALSE;
407: rsearch_cache=TRUE;
408: print_tree=FALSE;
409: print_init=FALSE;
410:
411: if ((M=imatrix_read_from_string(is,&Mm,&Mn))==0){
412: fprintf(stderr,"%s: imatrix_read() failed\n",prog);
413: exit(1);
414: }
415: if (ring_N==0) ring_set(Mn);
416: else if (ring_N!=Mn) {
417: fprintf(stderr,"%s: Matrix collum and ring dimensions must agree\n",prog);
418: exit(1);
419: }
420: stat=MATFOUND;
421:
422:
423: /* ensure we have root */
424: if (stat==MATFOUND){
425: G1=gset_toric_ideal(M,Mm,Mn);
426: }
427:
428: fprintf(outfile,"[\n");
429: /* perform reverse search if desired*/
430: if (root_only==FALSE){
431: if (use_exsearch==FALSE){
432: /* should double check we are at root */
433: tt=clock();
434: counter=rsearch(G1);
435: tt=(clock()-tt)/CLOCKS_PER_SEC;
436: fprintf(outfile,"\n");
437: } else {
438: tt=clock();
439: counter=exsearch(G1);
440: tt=(clock()-tt)/CLOCKS_PER_SEC;
441: fprintf(outfile,"\n");
442: }
443: }
444:
445: fprintf(outfile,"]\n");
446: LP_free_space();
447: if (G1!=0) gset_free(G1);
448: }
449:
450:
451: main(int argc, char *argv[]) {
452: if (argc > 1) {
453: tiger_executeString_M(argv[1]);
454: }else{
455: tiger_executeString_M("2 4 : 1 1 1 1 0 1 2 3");
456: }
457: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to call.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / src / Ti