File: [local] / OpenXM_contrib / TiGERS_0.9 / Attic / tigers.c (download)
Revision 1.1.1.1 (vendor branch), Sat Nov 27 10:58:42 1999 UTC (24 years, 10 months ago) by maekawa
Branch: TIGERS
CVS Tags: maekawa-ipv6, VERSION_0_9, RELEASE_20000124, RELEASE_1_2_3, RELEASE_1_2_2_KNOPPIX_b, RELEASE_1_2_2_KNOPPIX, RELEASE_1_2_2, RELEASE_1_2_1, RELEASE_1_1_3, RELEASE_1_1_2 Changes since 1.1: +0 -0
lines
Import TiGERS 0.9
|
/*
** tigers.c Birk Huber, 2/99
** -- reverse search loop and main calling program for tigers.
**
**
** TiGERS, Toric Groebner Basis Enumeration by Reverse Search
** copyright (c) 1999 Birk Huber
**
*/
#include<stdio.h>
#include<stdlib.h>
#include "utils.h"
#include "gset.h"
int rsearch_cache=TRUE;
/*
** Output initial ideals and numbers of facets at each stage.
*/
FILE *outfile;
int print_init=TRUE;
int print_tree=TRUE;
int stats_minfacets=-1;
int stats_minelts=-1;
int stats_mindeg=-1;
int stats_maxfacets=0;
int stats_maxelts=0;
int stats_maxdeg=0;
int stats_tdepth=0;
int stats_ecounter=0;
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
void vertex_print(gset g1){
stats_maxfacets=max(gset_nfacets(g1),stats_maxfacets);
stats_maxelts=max(gset_nelts(g1),stats_maxelts);
stats_maxdeg=max(gset_deg(g1),stats_maxdeg);
if (stats_minfacets<0) stats_minfacets=gset_nfacets(g1);
else stats_minfacets=min(stats_minfacets,gset_nfacets(g1));
if (stats_minelts<0) stats_minelts=gset_nelts(g1);
else stats_minelts=min(stats_minelts,gset_nelts(g1));
if (stats_mindeg<0) stats_mindeg=gset_deg(g1);
else stats_mindeg=min(stats_mindeg,gset_deg(g1));
fprintf(outfile,"Vtx: %d (%d facets/%d binomials/degree %d)\n",
gset_id(g1),gset_nfacets(g1),gset_nelts(g1),gset_deg(g1));
if (print_init==TRUE){
fprintf(outfile," Initial ideal:");gset_init_print(outfile,g1);
fprintf(outfile,"\n Facet Binomials:");gset_facet_print(outfile,g1);
}
else gset_print(outfile,g1);
if (print_tree==TRUE && rsearch_cache==TRUE && gset_cache_vtx(g1)!=0){
fprintf(outfile,"\n Reducing Edge: [%d,%d]",
gset_id(g1),gset_id(gset_cache_vtx(g1)));
}
fprintf(outfile,"\n");
}
int rsearch(gset g1){
gset G1,G2=0;
binomial b=0,btmp;
int counter=0,done=FALSE, depth=0;
stats_tdepth=0;
stats_ecounter=0;
/* make copy of first grobner basis */
G1=gset_new();
for(b=gset_first(g1);b!=0;b=binomial_next(b)){
btmp=binomial_new();
binomial_copy(b,btmp);
gset_insert(G1,btmp);
}
/* Do groebner walk to grobner basis wrt default term order*/
while((b=gset_downedge(G1))!=0){
fprintf(stderr,"Warning: rsearch doing walk to get to root\n");
G2=gset_flip(G1,b);
gset_free(G1);
G1=G2;
}
btmp=(b=gset_first(G1));
/* output first groebner basis*/
gset_setfacets(G1);
gset_id(G1)=++counter;
vertex_print(G1);
while(done==FALSE){
while(b!=0){
if (gset_isfacet(G1,b)==TRUE && binomial_ordered(b)==TRUE){
stats_ecounter++;
G2=gset_flip(G1,b);
btmp=gset_downedge(G2);
if (monomial_equal(binomial_lead(b),binomial_trail(btmp))==TRUE &&
monomial_equal(binomial_trail(b),binomial_lead(btmp))==TRUE ){
if (rsearch_cache==TRUE){
gset_cache_vtx(G2)=G1;
gset_cache_edge(G2)=b->next;
}
else{
gset_free(G1);
}
G1=G2;
depth++;
if (stats_tdepth<depth) stats_tdepth=depth;
b=gset_first(G1);
gset_setfacets(G1);
gset_id(G1)=++counter;
vertex_print(G1);
}
else {
gset_free(G2);
b=binomial_next(b);
}
}
else b=binomial_next(b);
}
depth--;
if (rsearch_cache==TRUE){
b=gset_cache_edge(G1);
if ((G2=gset_cache_vtx(G1))==0) done=TRUE;
else{
gset_free(G1);
G1=G2;
}
}
else{
if ((btmp=gset_downedge(G1))==0) done=TRUE;
else{
G2=gset_flip(G1,btmp);
b=gset_first(G2);
while(monomial_equal(binomial_lead(b),binomial_trail(btmp))==FALSE){
b=binomial_next(b);
}
b=binomial_next(b);
gset_free(G1);
G1=G2;
}
}
}
gset_free(G1);
return counter;
}