Annotation of OpenXM/src/Ti/exsearch.c, Revision 1.1
1.1 ! maekawa 1: /*
! 2: ** exsearch.c Birk Huber, 4/99
! 3: ** -- exhaustive search main loop.
! 4: */
! 5: #include<stdio.h>
! 6: #include<stdlib.h>
! 7: #include "utils.h"
! 8: #include "gset.h"
! 9:
! 10:
! 11: /*
! 12: ** use next pointer in Gsets to implement a simple linked list.
! 13: ** for now stored in no particular order.
! 14: */
! 15: void insert(gset g1, gset *L){
! 16: g1->next=*L;
! 17: *L=g1;
! 18: }
! 19:
! 20: /*
! 21: ** determine if two gsets contain equivalent marked binomials
! 22: */
! 23: int gset_equiv(gset g1, gset g2){
! 24: binomial p1,p2;
! 25:
! 26: p1=gset_first(g1);
! 27: p2=gset_first(g2);
! 28:
! 29: while(p1!=0 && p2!=0){
! 30: if(monomial_equal(binomial_lead(p1),binomial_lead(p2))!=TRUE) return FALSE;
! 31: if(monomial_equal(binomial_trail(p1),binomial_trail(p2))!=TRUE) return FALSE;
! 32: p1=binomial_next(p1);
! 33: p2=binomial_next(p2);
! 34: }
! 35: if (p1!=p2) return FALSE;
! 36: return TRUE;
! 37: }
! 38:
! 39: /*
! 40: ** check a gset against those on list untill an equivalent one is found.
! 41: ** (eventually must fix this to use ordered lists or some other more efficient
! 42: ** structure)
! 43: */
! 44: gset find(gset g1, gset L){
! 45: gset g2=0;
! 46: for(g2=L;g2!=0;g2=g2->next)if (gset_equiv(g1,g2)==TRUE) break;
! 47: return g2;
! 48: }
! 49:
! 50:
! 51: /*
! 52: ** use breadth-first search of edge graph of state polytope to find all
! 53: ** grobner bases of a toric ideal.
! 54: */
! 55: extern int stats_ecounter;
! 56: int exsearch(gset g1){
! 57: gset G1,G2,todo=0,seen=0,tmp;
! 58: binomial b=0,btmp;
! 59: int counter=0;
! 60: stats_ecounter=0;
! 61:
! 62: /* make copy of first grobner basis */
! 63: G1=gset_new();
! 64: for(b=gset_first(g1);b!=0;b=binomial_next(b)){
! 65: btmp=binomial_new();
! 66: binomial_copy(b,btmp);
! 67: gset_insert(G1,btmp);
! 68: }
! 69:
! 70: insert(G1,&todo);
! 71: gset_setfacets(G1);
! 72: gset_id(G1)=++counter;
! 73: vertex_print(G1);
! 74:
! 75: while(todo!=0){
! 76: G1=todo; todo=todo->next;
! 77: insert(G1,&seen);
! 78: for(b=gset_first(G1);b!=0;b=binomial_next(b)){
! 79: if (gset_isfacet(G1,b)==TRUE && binomial_ordered(b)==TRUE){
! 80: G2=gset_flip(G1,b);
! 81: stats_ecounter++;
! 82: if (find(G2,todo)==0 && find(G2,seen)==0){
! 83: insert(G2,&todo);
! 84: gset_setfacets(G2);
! 85: gset_id(G2)=++counter;
! 86: vertex_print(G2);
! 87: }
! 88: else gset_free(G2);
! 89: }
! 90: }
! 91: }
! 92:
! 93: while(seen!=0){
! 94: G2=seen;
! 95: seen=G2->next;
! 96: gset_free(G2);
! 97: }
! 98:
! 99: return counter;
! 100: }
! 101:
! 102:
! 103:
! 104:
! 105:
! 106:
! 107:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>