Return to exsearch.c CVS log

Up to [local] / OpenXM_contrib / TiGERS_0.9

Annotation of OpenXM_contrib/TiGERS_0.9/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: