polyparam.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <polylib/polylib.h>

Classes
struct	SatMatrix
Defines
#define	INT_BITS (sizeof(unsigned) * 8)
Functions
static void	traite_m_face (Polyhedron , unsigned int , unsigned int *)
static void	scan_m_face (int, int, Polyhedron , unsigned int )
Polyhedron *	PDomainIntersection (Polyhedron Pol1, Polyhedron Pol2, unsigned NbMaxRays)
Polyhedron *	PDomainDifference (Polyhedron Pol1, Polyhedron Pol2, unsigned NbMaxRays)
static int	TestRank (Matrix *Mat)
static SatMatrix *	SMAlloc (int rows, int cols)
static void	SMPrint (SatMatrix *matrix)
static void	SMFree (SatMatrix *matrix)
static Polyhedron *	Add_CEqualities (Polyhedron *D)
unsigned int *	int_array2bit_vector (unsigned int *array, int n)
static int	count_sat (unsigned int *mf)
static int	bit_vector_includes (unsigned int bv, int len, unsigned int part)
static SatMatrix *	Poly2Sat (Polyhedron Pol, unsigned int *L)
Param_Polyhedron *	GenParamPolyhedron (Polyhedron Pol, Matrix Rays)
Matrix *	PreElim_Columns (Polyhedron E, int p, int *ref, int m)
Polyhedron *	Elim_Columns (Polyhedron A, Polyhedron E, int p, int ref)
static Polyhedron *	Recession_Cone (Polyhedron *P, unsigned nvar, unsigned MaxRays)
static int	ComputeNPLinesRays (int n, Polyhedron D1, Matrix *Rays)
Param_Polyhedron *	Find_m_faces (Polyhedron *Di, Polyhedron C, int keep_dom, int working_space, Polyhedron CEq, Matrix CT)
void	Compute_PDomains (Param_Domain *PD, int nb_domains, int working_space)
Param_Polyhedron *	Polyhedron2Param_Vertices (Polyhedron Din, Polyhedron Cin, int working_space)
void	Param_Vertices_Free (Param_Vertices *PV)
void	Print_Vertex (FILE DST, Matrix V, const char **param_names)
Matrix *	VertexCT (Matrix V, Matrix CT)
void	Print_Domain (FILE DST, Polyhedron D, const char **pname)
void	Param_Vertices_Print (FILE DST, Param_Vertices PV, const char **param_names)
Param_Polyhedron *	Polyhedron2Param_Domain (Polyhedron Din, Polyhedron Cin, int working_space)
Param_Polyhedron *	Polyhedron2Param_SimplifiedDomain (Polyhedron *Din, Polyhedron Cin, int working_space, Polyhedron CEq, Matrix CT)
void	Param_Domain_Free (Param_Domain *PD)
void	Param_Polyhedron_Free (Param_Polyhedron *P)
void	Param_Polyhedron_Scale_Integer (Param_Polyhedron PP, Polyhedron P, Value det, unsigned MaxRays)
Variables
static int	m
static int	m_dim
static int	n
static int	ws
static int	nr
static Polyhedron *	CEqualities
static SatMatrix *	Sat
static unsigned int *	egalite
static Matrix *	Xi
static Matrix *	Pi
static Matrix *	PiTest
static Matrix *	CTest
static Matrix *	PiInv
static Matrix *	RaysDi
static int	KD
static int	nbPV
static Param_Vertices *	PV_Result
static Param_Domain *	PDomains
int	cntbit [256]

Define Documentation

#define INT_BITS (sizeof(unsigned) * 8)

Definition at line 339 of file polyparam.c.

Referenced by int_array2bit_vector().

Function Documentation

static Polyhedron* Add_CEqualities ( Polyhedron * D ) [static]

Definition at line 314 of file polyparam.c.

References AddConstraints(), polyhedron::Constraint, Domain_Free(), emptyQ, polyhedron::NbConstraints, polyhedron::next, Polyhedron_Copy(), and ws.

Referenced by Polyhedron2Param_Domain(), and traite_m_face().

static int bit_vector_includes	(	unsigned int *	bv,
		int	len,
		unsigned int *	part
	)			`[static]`

Definition at line 559 of file polyparam.c.

Referenced by scan_m_face().

void Compute_PDomains	(	Param_Domain *	PD,
		int	nb_domains,
		int	working_space
	)

Definition at line 1366 of file polyparam.c.

References _Param_Domain::Domain, Domain_Free(), DomainConvex(), emptyQ, _Param_Domain::F, MSB, polyhedron::NbEq, polyhedron::next, NEXT, _Param_Domain::next, P_VALUE_FMT, PDomainDifference(), PDomainIntersection(), and Polyhedron_Print().

Referenced by Polyhedron2Param_Domain(), and Polyhedron2Param_SimplifiedDomain().

static int ComputeNPLinesRays	(	int	n,
		Polyhedron *	D1,
		Matrix **	Rays
	)			`[static]`

Definition at line 1033 of file polyparam.c.

References Matrix_Alloc(), Matrix_Print(), polyhedron::NbBid, polyhedron::NbRays, P_VALUE_FMT, Polyhedron_Free(), polyhedron::Ray, Recession_Cone(), value_zero_p, Vector_Copy(), and ws.

Referenced by Find_m_faces().

static int count_sat ( unsigned int * mf ) [static]

Definition at line 542 of file polyparam.c.

References cntbit, and nr.

Referenced by scan_m_face().

Polyhedron* Elim_Columns	(	Polyhedron *	A,
		Polyhedron *	E,
		int *	p,
		int *	ref
	)

Definition at line 955 of file polyparam.c.

References polyhedron::Constraint, Constraints2Polyhedron(), Matrix_Alloc(), Matrix_Free(), Matrix_Print(), matrix::NbColumns, polyhedron::NbEq, matrix::NbRows, matrix::p, P_VALUE_FMT, Polyhedron2Constraints(), Polyhedron_Print(), value_assign, value_clear, value_init, value_multiply, value_notzero_p, value_subtract, and ws.

Referenced by Find_m_faces().

Param_Polyhedron* Find_m_faces	(	Polyhedron **	Di,
		Polyhedron *	C,
		int	keep_dom,
		int	working_space,
		Polyhedron **	CEq,
		Matrix **	CT
	)

Definition at line 1068 of file polyparam.c.

References align_context(), ComputeNPLinesRays(), _Param_Polyhedron::Constraints, Constraints2Polyhedron(), _Param_Polyhedron::D, polyhedron::Dimension, Domain_Free(), DomainAddRays(), DomainIntersection(), DomainSimplify(), egalite, Elim_Columns(), emptyQ, GenParamPolyhedron(), KD, m, m_dim, Matrix_Alloc(), Matrix_Free(), Matrix_Print(), n, polyhedron::NbBid, polyhedron::NbConstraints, polyhedron::NbEq, nbPV, _Param_Polyhedron::nbV, nr, matrix::p, p, P_VALUE_FMT, Poly2Sat(), Polyhedron2Constraints(), Polyhedron_Free(), Polyhedron_Print(), PreElim_Columns(), _Param_Polyhedron::Rays, scan_m_face(), SMFree(), SMPrint(), Universe_Polyhedron(), _Param_Polyhedron::V, value_assign, value_notzero_p, value_set_si, Vector_Copy(), and ws.

Referenced by Polyhedron2Param_Domain(), Polyhedron2Param_SimplifiedDomain(), and Polyhedron2Param_Vertices().

Param_Polyhedron* GenParamPolyhedron	(	Polyhedron *	Pol,
		Matrix *	Rays
	)

unsigned int* int_array2bit_vector	(	unsigned int *	array,
		int	n
	)

Definition at line 341 of file polyparam.c.

References assert, INT_BITS, MSB, and NEXT.

Referenced by traite_m_face().

void Param_Domain_Free ( Param_Domain * PD )

Definition at line 1863 of file polyparam.c.

References _Param_Domain::Domain, Domain_Free(), _Param_Domain::F, and _Param_Domain::next.

Referenced by Param_Polyhedron_Free().

void Param_Polyhedron_Free ( Param_Polyhedron * P )

Definition at line 1880 of file polyparam.c.

References _Param_Polyhedron::Constraints, _Param_Polyhedron::D, Matrix_Free(), Param_Domain_Free(), Param_Vertices_Free(), _Param_Polyhedron::Rays, and _Param_Polyhedron::V.

Referenced by main(), and Polyhedron_Enumerate().

void Param_Polyhedron_Scale_Integer	(	Param_Polyhedron *	PP,
		Polyhedron **	P,
		Value *	det,
		unsigned	MaxRays
	)

Definition at line 1896 of file polyparam.c.

References _Param_Polyhedron::D, polyhedron::Dimension, _Param_Domain::Domain, Matrix_Alloc(), Matrix_Free(), matrix::NbRows, _Param_Polyhedron::nbV, _Param_Vertex::next, matrix::p, Vector::p, Polyhedron_Preimage(), _Param_Polyhedron::V, value_assign, value_clear, value_division, value_init, value_lcm, value_multiply, value_set_si, Vector_Alloc(), Vector_Free(), Vector_Normalize(), Vector_Scale(), and _Param_Vertex::Vertex.

Referenced by Ehrhart_Quick_Apx_Full_Dim().

void Param_Vertices_Free ( Param_Vertices * PV )

Definition at line 1577 of file polyparam.c.

References _Param_Vertex::Domain, _Param_Vertex::Facets, Matrix_Free(), _Param_Vertex::next, and _Param_Vertex::Vertex.

Referenced by Param_Polyhedron_Free(), and Polyhedron_Enumerate().

void Param_Vertices_Print	(	FILE *	DST,
		Param_Vertices *	PV,
		const char **	param_names
	)

Definition at line 1746 of file polyparam.c.

References Constraints2Polyhedron(), _Param_Vertex::Domain, Domain_Free(), _Param_Vertex::next, Print_Domain(), Print_Vertex(), and _Param_Vertex::Vertex.

Referenced by main().

Polyhedron* PDomainDifference	(	Polyhedron *	Pol1,
		Polyhedron *	Pol2,
		unsigned	NbMaxRays
	)

Definition at line 103 of file polyparam.c.

References AddPolyToDomain(), polyhedron::Constraint, polyhedron::Dimension, Domain_Free(), emptyQ, polyhedron::NbConstraints, polyhedron::NbEq, polyhedron::next, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, Polyhedron_Free(), and SubConstraint().

Referenced by Compute_PDomains().

Polyhedron* PDomainIntersection	(	Polyhedron *	Pol1,
		Polyhedron *	Pol2,
		unsigned	NbMaxRays
	)

Definition at line 62 of file polyparam.c.

References AddConstraints(), AddPolyToDomain(), polyhedron::Constraint, polyhedron::Dimension, polyhedron::NbConstraints, polyhedron::NbEq, polyhedron::next, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, and Polyhedron_Free().

Referenced by Compute_PDomains().

static SatMatrix* Poly2Sat	(	Polyhedron *	Pol,
		unsigned int **	L
	)			`[static]`

Definition at line 756 of file polyparam.c.

References polyhedron::Constraint, polyhedron::Dimension, MSB, polyhedron::NbConstraints, polyhedron::NbRays, NEXT, nr, SatMatrix::p, SatMatrix::p_init, polyhedron::Ray, SMAlloc(), value_addto, value_clear, value_init, value_multiply, value_set_si, and value_zero_p.

Referenced by Find_m_faces().

Param_Polyhedron* Polyhedron2Param_Domain	(	Polyhedron *	Din,
		Polyhedron *	Cin,
		int	working_space
	)

Definition at line 1771 of file polyparam.c.

References Add_CEqualities(), Compute_PDomains(), _Param_Polyhedron::D, polyhedron::Dimension, _Param_Domain::Domain, emptyQ, Find_m_faces(), _Param_Polyhedron::nbV, _Param_Domain::next, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, and Polyhedron_Free().

Referenced by main().

Param_Polyhedron* Polyhedron2Param_SimplifiedDomain	(	Polyhedron **	Din,
		Polyhedron *	Cin,
		int	working_space,
		Polyhedron **	CEq,
		Matrix **	CT
	)

Definition at line 1816 of file polyparam.c.

References assert, Compute_PDomains(), _Param_Polyhedron::D, polyhedron::Dimension, Find_m_faces(), _Param_Polyhedron::nbV, POL_ENSURE_FACETS, and POL_ENSURE_VERTICES.

Referenced by Ehrhart_Quick_Apx_Full_Dim(), and Polyhedron_Enumerate().

Param_Polyhedron* Polyhedron2Param_Vertices	(	Polyhedron *	Din,
		Polyhedron *	Cin,
		int	working_space
	)

Definition at line 1546 of file polyparam.c.

References Find_m_faces(), _Param_Polyhedron::nbV, POL_ENSURE_FACETS, and POL_ENSURE_VERTICES.

Referenced by main().

Matrix* PreElim_Columns	(	Polyhedron *	E,
		int *	p,
		int *	ref,
		int	m
	)

Definition at line 882 of file polyparam.c.

References polyhedron::Constraint, polyhedron::Dimension, Matrix_Alloc(), Matrix_Print(), matrix::NbColumns, polyhedron::NbEq, matrix::NbRows, matrix::p, P_VALUE_FMT, Polyhedron_Print(), value_notzero_p, value_set_si, and value_zero_p.

Referenced by Find_m_faces().

void Print_Domain	(	FILE *	DST,
		Polyhedron *	D,
		const char **	pname
	)

Definition at line 1693 of file polyparam.c.

References polyhedron::Constraint, polyhedron::Dimension, polyhedron::NbConstraints, polyhedron::next, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, Print_Domain(), value_mone_p, value_notzero_p, value_one_p, value_pos_p, and value_print.

Referenced by compute_poly(), Ehrhart_Quick_Apx_Full_Dim(), Enumerate_NoParameters(), main(), Param_Vertices_Print(), Polyhedron_Enumerate(), and Print_Domain().

void Print_Vertex	(	FILE *	DST,
		Matrix *	V,
		const char **	param_names
	)

Definition at line 1594 of file polyparam.c.

References matrix::NbColumns, matrix::NbRows, matrix::p, value_clear, value_divexact, value_gcd, value_init, value_mone_p, value_notone_p, value_notzero_p, value_posz_p, and value_print.

Referenced by main(), Param_Vertices_Print(), and Scan_Vertices().

static Polyhedron* Recession_Cone	(	Polyhedron *	P,
		unsigned	nvar,
		unsigned	MaxRays
	)			`[static]`

Definition at line 1014 of file polyparam.c.

References polyhedron::Constraint, Constraints2Polyhedron(), Matrix_Alloc(), Matrix_Free(), polyhedron::NbConstraints, matrix::p, and Vector_Copy().

Referenced by ComputeNPLinesRays().

static void scan_m_face	(	int	pos,
		int	nb_un,
		Polyhedron *	D,
		unsigned int *	mf
	)			`[static]`

Definition at line 615 of file polyparam.c.

References bit_vector_includes(), polyhedron::Constraint, count_sat(), polyhedron::Dimension, egalite, m, m_dim, Matrix_Print(), n, matrix::NbColumns, polyhedron::NbConstraints, nr, matrix::p, SatMatrix::p, P_VALUE_FMT, TestRank(), traite_m_face(), and value_assign.

Referenced by Find_m_faces().

static SatMatrix* SMAlloc	(	int	rows,
		int	cols
	)			`[static]`

Definition at line 229 of file polyparam.c.

References assert, SatMatrix::NbColumns, SatMatrix::NbRows, SatMatrix::p, p, and SatMatrix::p_init.

Referenced by Poly2Sat().

static void SMFree ( SatMatrix * matrix ) [static]

Definition at line 268 of file polyparam.c.

References SatMatrix::p, and SatMatrix::p_init.

Referenced by Find_m_faces().

static void SMPrint ( SatMatrix * matrix ) [static]

Definition at line 252 of file polyparam.c.

References SatMatrix::NbColumns, SatMatrix::NbRows, SatMatrix::p, and p.

Referenced by Find_m_faces().

static int TestRank ( Matrix * Mat ) [static]

Definition at line 151 of file polyparam.c.

References matrix::NbColumns, matrix::NbRows, matrix::p, value_assign, value_clear, value_division, value_gcd, value_init, value_multiply, value_notzero_p, value_subtract, and value_zero_p.

Referenced by scan_m_face(), and traite_m_face().

static void traite_m_face	(	Polyhedron *	D,
		unsigned int *	mf,
		unsigned int *	egalite
	)			`[static]`

Definition at line 363 of file polyparam.c.

References Add_CEqualities(), _Param_Domain::Domain, _Param_Vertex::Domain, _Param_Domain::F, _Param_Vertex::Facets, int_array2bit_vector(), KD, m, MatInverse(), Matrix_Alloc(), Matrix_Print(), MSB, n, matrix::NbColumns, polyhedron::NbConstraints, nbPV, polyhedron::NbRays, matrix::NbRows, _Param_Domain::next, _Param_Vertex::next, NEXT, matrix::p, P_VALUE_FMT, Polyhedron2Constraints(), Polyhedron_Free(), Polyhedron_Print(), rat_prodmat(), polyhedron::Ray, Rays2Polyhedron(), TestRank(), value_assign, Vector_Copy(), _Param_Vertex::Vertex, and ws.

Referenced by scan_m_face().

Matrix* VertexCT	(	Matrix *	V,
		Matrix *	CT
	)

Definition at line 1663 of file polyparam.c.

References Matrix_Alloc(), matrix::NbColumns, matrix::NbRows, matrix::p, value_assign, value_notzero_p, and value_set_si.

Referenced by Scan_Vertices().

Variable Documentation

Polyhedron* CEqualities [static]

Definition at line 288 of file polyparam.c.

int cntbit[256]

Initial value:

 {                              
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }

Definition at line 521 of file polyparam.c.

Referenced by count_sat().

Matrix* CTest [static]

Definition at line 293 of file polyparam.c.

unsigned int* egalite [static]

Definition at line 290 of file polyparam.c.

Referenced by Find_m_faces(), and scan_m_face().

int KD [static]

Definition at line 298 of file polyparam.c.

Referenced by Find_m_faces(), and traite_m_face().

int m [static]

Definition at line 282 of file polyparam.c.