next up previous contents
Next: Lattices and -polyhedra Up: Data structures Previous: Data structures   Contents

Matrices and Polyhedra

typedef struct  {
  unsigned Size;
  Value *p;
} Vector;

typedef struct matrix {
  unsigned NbRows, NbColumns;
  Value **p;
  Value *p_Init;
} Matrix;

typedef struct polyhedron { 
  unsigned Dimension, NbConstraints, NbRays, NbEq, NbBid;
  Value **Constraint;
  Value **Ray;
  Value *p_Init;
  struct polyhedron *next;
} Polyhedron;
The Saturation matrix is a boolean matrix which has a row for every constraint and a column for every line or ray. The bits in the binary format of each integer in the stauration matrix stores the information whether the corresponding constraint is saturated by ray(line) or not.
S Lines Rays
=||== Equations 0 0
Inequalities 0 0 or 1
typedef struct {
  unsigned int NbRows;
  unsigned int NbColumns;
  int **p;
  int *p_init;
} SatMatrix;
The scheme of the polyhedron structure can be the following:

Figure: Polyhedron structure.
\begin{figure}
\psfig{figure=poli.eps,width=\textwidth}
\end{figure}



Sorin Olaru 2002-04-24