Annotation of OpenXM/src/Ti/call.c, Revision 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