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