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     ! 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: