sc_enumerate.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <limits.h>
#include <unistd.h>
#include "linear.h"
#include "polylib/polylib.h"

Include dependency graph for sc_enumerate.c:

Go to the source code of this file.

Macros
#define	MAX_NB_RAYS   (20000)
	IRISA/POLYLIB data structures. More...
#define	VALUE_TO_IRINT(val)   (val)
	Irisa is based on int. More...
#define	IRINT_TO_VALUE(i)   (i)

Functions
static void	my_Matrix_Free (Matrix *volatile *m)
static void	my_Polyhedron_Free (Polyhedron *volatile *p)
static void	contrainte_to_matrix_ligne (Pcontrainte pc, Matrix *mat, int i, Pbase base)
	Fonctions de conversion traduisant une Pcontrainte en une ligne de la structure matrix de l'IRISA. More...
static void	sc_to_matrix (Psysteme sc, Matrix *mat)
	Passage du systeme lineaire sc a une matrice matrix (structure Irisa) Cette fonction de conversion est utilisee par la fonction sc_to_sg_chernikova. More...
static Variable	base_nth (Pbase b, size_t i)
static Ppolynome	evalue_to_polynome (evalue *, Pbase)
static Ppolynome	enode_to_polynome (enode *e, Pbase ordered_base)
Ppolynome	sc_enumerate (Psysteme ordered_sc, Pbase ordered_base, const char *variable_names[])
	enumerate the systeme sc using base pb pb contains the unknow variables and sc all the constraints ordered_sc must be order as follows: elements from ordered_base appear last variable_names can be provided for debugging purpose (name of bases) or set to NULL More...

Macro Definition Documentation

IRINT_TO_VALUE

#define IRINT_TO_VALUE

(

i

)

(i)

Definition at line 60 of file sc_enumerate.c.

MAX_NB_RAYS

#define MAX_NB_RAYS   (20000)

IRISA/POLYLIB data structures.

maximum number of rays allowed in chernikova... (was 20000) it does not look a good idea to move the limit up, as it makes both time and memory consumption to grow a lot.

Definition at line 47 of file sc_enumerate.c.

VALUE_TO_IRINT

#define VALUE_TO_IRINT

(

val

)

(val)

Irisa is based on int.

We would like to change this to some other type, say "long long" if desired, as VALUE may also be changed. It is currently an int. Let us assume that the future type will be be called "IRINT" (Irisa Int)

Definition at line 59 of file sc_enumerate.c.

Function Documentation

base_nth()

static Variable base_nth ( Pbase  b, size_t  i  )

static

Definition at line 254 of file sc_enumerate.c.

{
  while(i--) {
    b=vecteur_succ(b);
  }
  return vecteur_var(b);
}

References vecteur_succ, and vecteur_var.

Referenced by enode_to_polynome().

Here is the caller graph for this function:

contrainte_to_matrix_ligne()

static void contrainte_to_matrix_ligne ( Pcontrainte  pc, Matrix *  mat, int  i, Pbase  base  )

static

Fonctions de conversion traduisant une Pcontrainte en une ligne de la structure matrix de l'IRISA.

Definition at line 91 of file sc_enumerate.c.

{
  Pvecteur pv;
  int j;
  Value v;
 
  for (pv=base,j=1; !VECTEUR_NUL_P(pv); pv=pv->succ,j++)
  {
    v = value_uminus(vect_coeff(vecteur_var(pv),pc->vecteur));
    mat->p[i][j] = VALUE_TO_IRINT(v);
  }
 
  v = value_uminus(vect_coeff(TCST,pc->vecteur));
  mat->p[i][j]= VALUE_TO_IRINT(v);
}

References base, Svecteur::succ, TCST, VALUE_TO_IRINT, value_uminus, vect_coeff(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_var.

Referenced by sc_to_matrix().

Here is the call graph for this function:

Here is the caller graph for this function:

enode_to_polynome()

static Ppolynome enode_to_polynome ( enode *  e, Pbase  ordered_base  )

static

Definition at line 264 of file sc_enumerate.c.

{
  int i;
  if (!e)
    return POLYNOME_UNDEFINED;
  Ppolynome p = POLYNOME_NUL;
  switch(e->type) {
  case evector:
    for (i=0; i<e->size; i++) {
      Ppolynome pp = evalue_to_polynome(&e->arr[i],ordered_base);
      polynome_add(&p,pp);
    }
    return p;
  case polynomial:
    for (i=e->size-1; i>=0; i--) {
      Ppolynome pp = evalue_to_polynome(&e->arr[i],ordered_base);
      pp=polynome_mult(pp,make_polynome(1,base_nth(ordered_base,e->pos-1),i));
      polynome_add(&p,pp);
    }
    return p;
  default:
    fprintf(stderr,"cannot represent periodic polynomials in linear\n");
    return POLYNOME_UNDEFINED;
  }
}

References base_nth(), evalue_to_polynome(), fprintf(), make_polynome(), polynome_add(), polynome_mult(), POLYNOME_NUL, and POLYNOME_UNDEFINED.

Referenced by evalue_to_polynome().

Here is the call graph for this function:

Here is the caller graph for this function:

evalue_to_polynome()

static Ppolynome evalue_to_polynome ( evalue *  e, Pbase  ordered_base  )

static

Definition at line 290 of file sc_enumerate.c.

{
  Ppolynome p = NULL;
  if(value_notzero_p(e->d))
    p=make_polynome((float)e->x.n/(float)e->d,TCST,0);
  else
    p = enode_to_polynome(e->x.p,ordered_base);
  return p;
}

References enode_to_polynome(), make_polynome(), TCST, and value_notzero_p.

Referenced by enode_to_polynome(), and sc_enumerate().

Here is the call graph for this function:

Here is the caller graph for this function:

my_Matrix_Free()

static void my_Matrix_Free ( Matrix *volatile *  m )

static

Definition at line 63 of file sc_enumerate.c.

{
  ifscdebug(9)
    fprintf(stderr, "[my_Matrix_Free] in %p\n", *m);
 
  Matrix_Free(*m);
  *m = NULL;
 
  ifscdebug(9)
    fprintf(stderr, "[my_Matrix_Free] out %p\n", *m);
}

References fprintf().

Referenced by sc_enumerate().

Here is the call graph for this function:

Here is the caller graph for this function:

my_Polyhedron_Free()

static void my_Polyhedron_Free ( Polyhedron *volatile *  p )

static

Definition at line 75 of file sc_enumerate.c.

{
  ifscdebug(9)
    fprintf(stderr, "[my_Polyhedron_Free] in %p\n", *p);
 
  Polyhedron_Free(*p);
  *p = NULL;
 
  ifscdebug(9)
    fprintf(stderr, "[my_Polyhedron_Free] out %p\n", *p);
}

References fprintf().

Referenced by sc_enumerate().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_enumerate()

Ppolynome sc_enumerate	(	Psysteme	ordered_sc,
		Pbase	ordered_base,
		const char *	variable_names[]
	)

enumerate the systeme sc using base pb pb contains the unknow variables and sc all the constraints ordered_sc must be order as follows: elements from ordered_base appear last variable_names can be provided for debugging purpose (name of bases) or set to NULL

sc_enumerate.c

Parameters

ordered_sc	rdered_sc
ordered_base	rdered_base
variable_names	ariable_names

Definition at line 307 of file sc_enumerate.c.

{
  // Automatic variables read in a CATCH block need to be declared volatile as
  // specified by the documentation
  Polyhedron * volatile A = NULL;
  Matrix * volatile a = NULL;
  Polyhedron * volatile C = NULL;
  Enumeration * volatile ehrhart = NULL;
 
  int nbrows = 0;
  int nbcolumns = 0;
  if( sc_dimension(ordered_sc) == 0 )
    return make_polynome(1,TCST,1);
  else
  {
    CATCH(any_exception_error)
    {
      if (A) my_Polyhedron_Free(&A);
      if (a) my_Matrix_Free(&a);
      if (C) my_Polyhedron_Free(&C);
      RETHROW();
    }
    TRY
    {
      assert(!SC_UNDEFINED_P(ordered_sc) && (sc_dimension(ordered_sc) != 0));
      nbrows = ordered_sc->nb_eq + ordered_sc->nb_ineq+1;
      nbcolumns = ordered_sc->dimension +2;
      a = Matrix_Alloc(nbrows, nbcolumns);
      sc_to_matrix(ordered_sc,a);
 
      A = Constraints2Polyhedron(a, MAX_NB_RAYS);
      my_Matrix_Free(&a);
 
      C = Universe_Polyhedron(base_dimension(ordered_base));
 
      ehrhart = Polyhedron_Enumerate(A, C, MAX_NB_RAYS, variable_names);
      // Value vals[2]= {0,0};
      // Value *val = compute_poly(ehrhart,&vals[0]);
      // printf("%lld\n",*val);
      my_Polyhedron_Free(&A);
      my_Polyhedron_Free(&C);
    } // end TRY
 
    UNCATCH(any_exception_error);
    return evalue_to_polynome(&ehrhart->EP,ordered_base);
  }
}

References any_exception_error, assert, base_dimension, CATCH, Ssysteme::dimension, evalue_to_polynome(), make_polynome(), MAX_NB_RAYS, my_Matrix_Free(), my_Polyhedron_Free(), Ssysteme::nb_eq, Ssysteme::nb_ineq, RETHROW, sc_to_matrix(), TCST, TRY, and UNCATCH.

Here is the call graph for this function:

sc_to_matrix()

static void sc_to_matrix ( Psysteme  sc, Matrix *  mat  )

static

Passage du systeme lineaire sc a une matrice matrix (structure Irisa) Cette fonction de conversion est utilisee par la fonction sc_to_sg_chernikova.

Definition at line 115 of file sc_enumerate.c.

{
  int nbrows, i, j;
  Pcontrainte peq;
  Pvecteur pv;
 
  nbrows = mat->NbRows;
 
  // Differentiation equations and inequations
  for (i=0; i<=sc->nb_eq-1;i++)
    mat->p[i][0] =0;
  for (; i<=nbrows-1;i++)
    mat->p[i][0] =1;
 
  // Matrix initialisation
  for (peq = sc->egalites,i=0;
       !CONTRAINTE_UNDEFINED_P(peq);
       peq=peq->succ, i++)
    contrainte_to_matrix_ligne(peq,mat,i,sc->base);
 
  for (peq =sc->inegalites;
       !CONTRAINTE_UNDEFINED_P(peq);
       peq=peq->succ, i++)
    contrainte_to_matrix_ligne(peq,mat,i,sc->base);
 
  for (pv=sc->base,j=1; !VECTEUR_NUL_P(pv); pv=pv->succ, j++)
    mat->p[i][j] = 0;
  mat->p[i][j]=1;
}

References Ssysteme::base, contrainte_to_matrix_ligne(), CONTRAINTE_UNDEFINED_P, Ssysteme::egalites, Ssysteme::inegalites, Ssysteme::nb_eq, Scontrainte::succ, Svecteur::succ, and VECTEUR_NUL_P.

Referenced by sc_enumerate().

Here is the call graph for this function:

Here is the caller graph for this function: