#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

Include dependency graph for MP/Source/vinci.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	T_Vertex

struct	T_VertexSet

struct	T_VertexSuperset

union	T_Key

struct	T_Tree

Macros
#define	COPYRIGHT1 "(C) Benno Bueeler and Andreas Enge, {bueeler,enge}@ifor.math.ethz.ch"

#define	COPYRIGHT2 " Developed in the ETHZ-EPFL project on Optimisation and Computational"

#define	COPYRIGHT3 " Geometry with Komei Fukuda"

#define	VERSION "1"

#define	VERSION_DATE "March 1998"

#define	T01 "The package computes the volume of a polytope whose vertices, defining"

#define	T02 "hyperplanes and/or incidences of vertices and facettes are stored in files"

#define	T03 "following Avis' and Fukuda's polytope format. The vertices are supposed to"

#define	T04 "be in a file with extension '.ine', the hyperplanes in '.ext' and the"

#define	T05 "incidences in '.icd' (see the sample files 'square.ext', 'square.icd' and"

#define	T06 "'square.ine').\n"

#define	T07 "Its basic call is 'vinci file' where 'file' stands for the polyhedron file"

#define	T08 "name without extension, e. g. 'vinci square'. In this case the existing files"

#define	T09 "and installed additional packages are analysed and according to the problem"

#define	T10 "type an appropriate volume computation method is chosen automatically."

#define	T11 ""

#define	T12 "The following additional parameters are possible:"

#define	T13 "-m followed by the label of a specific volume computation method; to see a"

#define	T14 " list of the implemented methods, use 'vinci -m' without any label."

#define	T15 "-p1, -p2 or -p3 which are valid for some methods. They determine the space"

#define	T16 " and time complexity. Higher values lead to more space consume and a fast-"

#define	T17 " er execution. If none of the parameters is specified the value"

#define	T18 " DEFAULT_PRECOMP defined in 'vinci.h' is chosen."

#define	T19 "-s directly followed by a natural integer. The value determines for how many"

#define	T20 " recursion levels intermediate results are stored. A higher value speeds"

#define	T21 " up certain methods considerably while needing more storage space."

#define	T22 "-r directly followed by an integer. The value sets the random seed used for"

#define	T23 " determining the objective function for Lawrence's formula."

#define	T24 "\nFor more information please consult the manual."

#define	LRS_EXEC "lrs"

#define	CDD_EXEC "cddf+"

#define	QHULL_EXEC "qhull"

#define	QHULL_OPTIONS "d i Q0 Qz"

#define	PIVOTING 1

#define	MIN_PIVOT 0.5

#define	PIVOTING_LASS 0

#define	MIN_PIVOT_LASS 0.1

#define	MAX_PRECOMP 3

#define	DEFAULT_PRECOMP 1

#define	DEFAULT_STORAGE 20

#define	STATISTICS

#define	NO_RATIONAL

#define	NO_COG

#define	EPSILON 1e-10

#define	ARRAYSIZESTEP 5

#define	FALSE 0

#define	TRUE 1

#define	EOLN 10 /* end of line character */

#define	NONE 0 /* constants for data types in files */

#define	INTEGER_T 1

#define	REAL_T 2

#define	RATIONAL_T 3

#define	RCH 1 /* constants for the volume computation methods */

#define	GS 2

#define	GSH 3

#define	HOT 4

#define	HOTH 5

#define	CDDP 6

#define	CDDM 7

#define	QHULL 8

#define	LAWD 9

#define	LAWND 10

#define	RLASS 11

#define	LRS 12

#define	PREPARE 1 /* constants for precomputation of hyperplane intersections */

#define	RETRIEVE 2

#define	FREE 3

#define	KEY_PLANES 1 /* constants for the key type actually used in the balanced */

#define	KEY_VERTICES 2 /* tree routines */

#define	KEY_PLANES_VAR 3

#define	SCHMIDT 1 /* constants for the orthonormalisation technique used */

#define	HOUSEHOLDER 2

#define	STAT_SMALLEST_EXP -200

#define	STAT_BIGGEST_EXP 200

Typedefs
typedef double	real

typedef int	boolean

typedef unsigned char	T_LassInt

typedef real	rational

typedef struct T_Vertex	T_Vertex

typedef struct T_VertexSet	T_VertexSet

typedef struct T_VertexSuperset	T_VertexSuperset

typedef union T_Key	T_Key

typedef struct T_Tree	T_Tree

Functions
void *	my_malloc (long int size)

void *	my_realloc (void *pointer, long int new_size, long int size_diff)

void	my_free (void *pointer, long int size)

T_Vertex *	create_vertex ()

void	free_vertex (T_Vertex *v)

void	create_hyperplanes ()

void	free_hyperplanes ()

void	create_incidence ()

void	free_incidence ()

T_VertexSet *	create_faces ()

void	free_faces (T_VertexSet *face)

rational ***	create_basis ()

void	free_basis (rational ***basis)

rational *	create_fact ()

void	free_fact (rational *fact)

rational *	create_vector ()

void	free_vector (rational *v)

int *	create_int_vector (int n)

void	free_int_vector (int *v, int n)

rational **	create_matrix (int m, int n)

void	redim_matrix (rational ***A, int m_alt, int m_neu, int n)

void	free_matrix (rational **A, int m, int n)

void	create_key (T_Key *key, int key_choice)

void	free_key (T_Key key, int key_choice)

void	tree_out (T_Tree *ppr, int pi_balance, T_Key key, rational volume, T_Key keyfound, int key_choice)

void	add_hypervar (T_LassInt hyperplane, T_LassInt variable, T_Key *key)

void	delete_hypervar (T_LassInt hyperplane, T_LassInt variable, T_Key *key)

T_VertexSet	create_empty_set (void)

T_VertexSet	duplicate_set (T_VertexSet s)

rational	normalise_vertices ()

void	print_set (FILE *f, T_VertexSet s)

boolean	empty (T_VertexSet s)

boolean	is_in_set (T_Vertex *e, T_VertexSet s)

boolean	is_contained (T_VertexSet s1, T_VertexSet s2)

boolean	are_equal_sets (T_VertexSet s1, T_VertexSet s2)

void	add_element (T_VertexSet s, T_Vertex e)

boolean	delete_element (T_VertexSet s, T_Vertex e)

void	intersect (T_VertexSet s1, T_VertexSet s2, T_VertexSet *inter)

T_VertexSuperset *	create_empty_superset (void)

void	free_superset (T_VertexSuperset **S)

void	print_superset (FILE f, T_VertexSuperset S)

boolean	is_in_superset (T_VertexSet s, T_VertexSuperset *S)

void	add_superelement (T_VertexSuperset **S, T_VertexSet s)

rational	factorial (int n)

rational	det_and_invert (rational **A, int rows, int columns, boolean verbose)

void	simplex_volume (T_VertexSet S, rational *volume, boolean verbose)

T_VertexSet *	do_intersections (int precomp, int i1, int i2, int i3, int action)

rational	add_orthonormal_schmidt (int d, T_VertexSet face, rational *B, T_Vertex vertex)

rational	orthonormal_schmidt (int d, T_VertexSet face, rational **B)

rational	add_orthonormal_householder (int d, T_VertexSet face, rational *H, T_Vertex vertex)

rational	orthonormal_householder (int d, T_VertexSet face, rational **H)

void	volume_ch_file (rational *volume, char vertexfile[255], char incidencefile[255])

void	volume_ortho_file (rational *volume, char vertexfile[255], char incidencefile[255], int key_choice, int ortho_choice)

void	volume_cdd_file (rational *volume, int direction, char vertexfile[255])

void	volume_qhull_file (rational *volume, char vertexfile[255])

void	volume_lawrence_file (rational *volume, char vertexfile[255], char planesfile[255], char incidencefile[255])

void	volume_lawrence_lrs_file (rational *volume, char planesfile[255])

void	volume_lrs_file (rational volume, char rational_volume, char vertexfile[255])

void	volume_lasserre_file (double planes2[7][4], rational *volume)

Variables
int	G_d

int	G_m

real **	G_Hyperplanes

T_VertexSet *	G_Incidence

T_VertexSet	G_Vertices

int	G_Precomp

int	G_Storage

int	G_RandomSeed

boolean	G_OutOfMem

void *	G_MemRes

rational	G_Minus1

unsigned int	Stat_Count

real	Stat_Smallest

real	Stat_Biggest

unsigned int	Stat_CountPos [STAT_BIGGEST_EXP-STAT_SMALLEST_EXP+3]

unsigned int	Stat_CountNeg [STAT_BIGGEST_EXP-STAT_SMALLEST_EXP+3]

unsigned int *	Stat_CountStored

unsigned int *	Stat_CountRetrieved

unsigned int	Stat_CountShifts

long int	Stat_ActualMem

long int	Stat_MaxMem

Macro Definition Documentation

#define ARRAYSIZESTEP 5

Definition at line 130 of file MP/Source/vinci.h.

#define CDD_EXEC "cddf+"

Definition at line 65 of file MP/Source/vinci.h.

#define CDDM 7

Definition at line 148 of file MP/Source/vinci.h.

#define CDDP 6

Definition at line 147 of file MP/Source/vinci.h.

#define COPYRIGHT1 "(C) Benno Bueeler and Andreas Enge, {bueeler,enge}@ifor.math.ethz.ch"

Definition at line 22 of file MP/Source/vinci.h.

#define COPYRIGHT2 " Developed in the ETHZ-EPFL project on Optimisation and Computational"

Definition at line 23 of file MP/Source/vinci.h.

#define COPYRIGHT3 " Geometry with Komei Fukuda"

Definition at line 24 of file MP/Source/vinci.h.

#define DEFAULT_PRECOMP 1

Definition at line 88 of file MP/Source/vinci.h.

#define DEFAULT_STORAGE 20

Definition at line 101 of file MP/Source/vinci.h.

#define EOLN 10 /* end of line character */

Definition at line 135 of file MP/Source/vinci.h.

#define EPSILON 1e-10

Definition at line 129 of file MP/Source/vinci.h.

#define FALSE 0

Definition at line 133 of file MP/Source/vinci.h.

#define FREE 3

Definition at line 157 of file MP/Source/vinci.h.

#define GS 2

Definition at line 143 of file MP/Source/vinci.h.

#define GSH 3

Definition at line 144 of file MP/Source/vinci.h.

#define HOT 4

Definition at line 145 of file MP/Source/vinci.h.

#define HOTH 5

Definition at line 146 of file MP/Source/vinci.h.

#define HOUSEHOLDER 2

Definition at line 164 of file MP/Source/vinci.h.

#define INTEGER_T 1

Definition at line 138 of file MP/Source/vinci.h.

#define KEY_PLANES 1 /* constants for the key type actually used in the balanced */

Definition at line 159 of file MP/Source/vinci.h.

#define KEY_PLANES_VAR 3

Definition at line 161 of file MP/Source/vinci.h.

#define KEY_VERTICES 2 /* tree routines */

Definition at line 160 of file MP/Source/vinci.h.

#define LAWD 9

Definition at line 150 of file MP/Source/vinci.h.

#define LAWND 10

Definition at line 151 of file MP/Source/vinci.h.

#define LRS 12

Definition at line 153 of file MP/Source/vinci.h.

#define LRS_EXEC "lrs"

Definition at line 64 of file MP/Source/vinci.h.

#define MAX_PRECOMP 3

Definition at line 87 of file MP/Source/vinci.h.

#define MIN_PIVOT 0.5

Definition at line 71 of file MP/Source/vinci.h.

#define MIN_PIVOT_LASS 0.1

Definition at line 73 of file MP/Source/vinci.h.

#define NO_COG

Definition at line 115 of file MP/Source/vinci.h.

#define NO_RATIONAL

Definition at line 110 of file MP/Source/vinci.h.

#define NONE 0 /* constants for data types in files */

Definition at line 137 of file MP/Source/vinci.h.

#define PIVOTING 1

Definition at line 70 of file MP/Source/vinci.h.

#define PIVOTING_LASS 0

Definition at line 72 of file MP/Source/vinci.h.

#define PREPARE 1 /* constants for precomputation of hyperplane intersections */

Definition at line 155 of file MP/Source/vinci.h.

#define QHULL 8

Definition at line 149 of file MP/Source/vinci.h.

#define QHULL_EXEC "qhull"

Definition at line 66 of file MP/Source/vinci.h.

#define QHULL_OPTIONS "d i Q0 Qz"

Definition at line 67 of file MP/Source/vinci.h.

#define RATIONAL_T 3

Definition at line 140 of file MP/Source/vinci.h.

#define RCH 1 /* constants for the volume computation methods */

Definition at line 142 of file MP/Source/vinci.h.

#define REAL_T 2

Definition at line 139 of file MP/Source/vinci.h.

#define RETRIEVE 2

Definition at line 156 of file MP/Source/vinci.h.

#define RLASS 11

Definition at line 152 of file MP/Source/vinci.h.

#define SCHMIDT 1 /* constants for the orthonormalisation technique used */

Definition at line 163 of file MP/Source/vinci.h.

#define STAT_BIGGEST_EXP 200

Definition at line 168 of file MP/Source/vinci.h.

#define STAT_SMALLEST_EXP -200

Definition at line 167 of file MP/Source/vinci.h.

#define STATISTICS

Definition at line 106 of file MP/Source/vinci.h.

#define T01 "The package computes the volume of a polytope whose vertices, defining"

Definition at line 28 of file MP/Source/vinci.h.

#define T02 "hyperplanes and/or incidences of vertices and facettes are stored in files"

Definition at line 29 of file MP/Source/vinci.h.

#define T03 "following Avis' and Fukuda's polytope format. The vertices are supposed to"

Definition at line 30 of file MP/Source/vinci.h.

#define T04 "be in a file with extension '.ine', the hyperplanes in '.ext' and the"

Definition at line 31 of file MP/Source/vinci.h.

#define T05 "incidences in '.icd' (see the sample files 'square.ext', 'square.icd' and"

Definition at line 32 of file MP/Source/vinci.h.

#define T06 "'square.ine').\n"

Definition at line 33 of file MP/Source/vinci.h.

#define T07 "Its basic call is 'vinci file' where 'file' stands for the polyhedron file"

Definition at line 34 of file MP/Source/vinci.h.

#define T08 "name without extension, e. g. 'vinci square'. In this case the existing files"

Definition at line 35 of file MP/Source/vinci.h.

#define T09 "and installed additional packages are analysed and according to the problem"

Definition at line 36 of file MP/Source/vinci.h.

#define T10 "type an appropriate volume computation method is chosen automatically."

Definition at line 37 of file MP/Source/vinci.h.

#define T11 ""

Definition at line 38 of file MP/Source/vinci.h.

#define T12 "The following additional parameters are possible:"

Definition at line 39 of file MP/Source/vinci.h.

#define T13 "-m followed by the label of a specific volume computation method; to see a"

Definition at line 40 of file MP/Source/vinci.h.

#define T14 " list of the implemented methods, use 'vinci -m' without any label."

Definition at line 41 of file MP/Source/vinci.h.

#define T15 "-p1, -p2 or -p3 which are valid for some methods. They determine the space"

Definition at line 42 of file MP/Source/vinci.h.

#define T16 " and time complexity. Higher values lead to more space consume and a fast-"

Definition at line 43 of file MP/Source/vinci.h.

#define T17 " er execution. If none of the parameters is specified the value"

Definition at line 44 of file MP/Source/vinci.h.

#define T18 " DEFAULT_PRECOMP defined in 'vinci.h' is chosen."

Definition at line 45 of file MP/Source/vinci.h.

#define T19 "-s directly followed by a natural integer. The value determines for how many"

Definition at line 46 of file MP/Source/vinci.h.

#define T20 " recursion levels intermediate results are stored. A higher value speeds"

Definition at line 47 of file MP/Source/vinci.h.

#define T21 " up certain methods considerably while needing more storage space."

Definition at line 48 of file MP/Source/vinci.h.

#define T22 "-r directly followed by an integer. The value sets the random seed used for"

Definition at line 49 of file MP/Source/vinci.h.

#define T23 " determining the objective function for Lawrence's formula."

Definition at line 50 of file MP/Source/vinci.h.

#define T24 "\nFor more information please consult the manual."

Definition at line 51 of file MP/Source/vinci.h.

#define TRUE 1

Definition at line 134 of file MP/Source/vinci.h.

#define VERSION "1"

Definition at line 25 of file MP/Source/vinci.h.

#define VERSION_DATE "March 1998"

Definition at line 26 of file MP/Source/vinci.h.

Typedef Documentation

typedef int boolean

Definition at line 183 of file MP/Source/vinci.h.

typedef real rational

Definition at line 189 of file MP/Source/vinci.h.

typedef double real

Definition at line 182 of file MP/Source/vinci.h.

typedef union T_Key T_Key

Definition at line 236 of file MP/Source/vinci.h.

typedef unsigned char T_LassInt

Definition at line 184 of file MP/Source/vinci.h.

typedef struct T_Tree T_Tree

Definition at line 244 of file MP/Source/vinci.h.

typedef struct T_Vertex T_Vertex

Definition at line 197 of file MP/Source/vinci.h.

typedef struct T_VertexSet T_VertexSet

Definition at line 208 of file MP/Source/vinci.h.

typedef struct T_VertexSuperset T_VertexSuperset

Definition at line 217 of file MP/Source/vinci.h.

Function Documentation

void add_element	(	T_VertexSet *	s,
		T_Vertex *	e
	)

void add_hypervar	(	T_LassInt	hyperplane,
		T_LassInt	variable,
		T_Key *	key
	)

Definition at line 168 of file vinci_lass.c.

References G_d, G_m, i, and j.

 {  int i, j;
 
    if (hyperplane != G_m+1)
    {  
       for (i = 0; (*key).hypervar.hyperplanes [i] < hyperplane; i++);
       if ((*key).hypervar.hyperplanes [i] != hyperplane)
       {  /* insert index */
          for (j = G_d; j > i; j--)
             (*key).hypervar.hyperplanes [j] = (*key).hypervar.hyperplanes [j-1];
          (*key).hypervar.hyperplanes [i] = hyperplane;
       }
    }
 
    if (variable != G_d+1)
    {  
       for (i = 0; (*key).hypervar.variables [i] < variable; i++);
       if ((*key).hypervar.variables [i] != variable)
       {  /* insert index */
          for (j = G_d; j > i; j--)
             (*key).hypervar.variables [j] = (*key).hypervar.variables [j-1];
          (*key).hypervar.variables [i] = variable;
       }
    }
 }

rational add_orthonormal_householder	(	int	d,
		T_VertexSet	face,
		rational **	H,
		T_Vertex *	vertex
	)

rational add_orthonormal_schmidt	(	int	d,
		T_VertexSet	face,
		rational **	B,
		T_Vertex *	vertex
	)

void add_superelement	(	T_VertexSuperset **	S,
		T_VertexSet	s
	)

boolean are_equal_sets	(	T_VertexSet	s1,
		T_VertexSet	s2
	)

rational*** create_basis ( )

T_VertexSet create_empty_set ( void )

T_VertexSuperset* create_empty_superset ( void )

T_VertexSet* create_faces ( )

rational* create_fact ( )

void create_hyperplanes ( )

void create_incidence ( )

int* create_int_vector ( int n )

void create_key	(	T_Key *	key,
		int	key_choice
	)

Definition at line 131 of file vinci_lass.c.

References create_int_vector(), G_d, G_Storage, T_Key::hyperplanes, KEY_PLANES, KEY_PLANES_VAR, my_malloc(), and T_Key::variables.

 {
    switch (key_choice)
    {
    case KEY_PLANES:
       key -> hyperplanes = create_int_vector (G_d + 1);
       break;
    case KEY_PLANES_VAR:
       key -> hypervar.hyperplanes =
                                  (T_LassInt *) my_malloc ((G_Storage + 2) * sizeof (T_LassInt));
       key -> hypervar.variables =
                                  (T_LassInt *) my_malloc ((G_Storage + 2) * sizeof (T_LassInt));
       break;
    }
 }

Here is the call graph for this function:

rational** create_matrix	(	int	m,
		int	n
	)

rational* create_vector ( )

T_Vertex* create_vertex ( )

boolean delete_element	(	T_VertexSet *	s,
		T_Vertex *	e
	)

void delete_hypervar	(	T_LassInt	hyperplane,
		T_LassInt	variable,
		T_Key *	key
	)

Definition at line 204 of file vinci_lass.c.

References G_d, G_m, i, and j.

 {  int i, j;
 
    if (hyperplane != G_m+1)
    {  
       for (i = 0; i <= G_d && (*key).hypervar.hyperplanes [i] != hyperplane; i++);
       if (i != G_d + 1)
       {  /* index found, delete it */
          for (j = i; (*key).hypervar.hyperplanes [j] != G_m + 1; j++)
             (*key).hypervar.hyperplanes [j] = (*key).hypervar.hyperplanes [j+1];
       }
    }
 
    if (variable != G_d+1)
    {  
       for (i = 0; i <= G_d && (*key).hypervar.variables [i] != variable; i++);
       if (i != G_d + 1)
       {  /* index found, delete it */
          for (j = i; (*key).hypervar.variables [j] != G_d + 1; j++)
             (*key).hypervar.variables [j] = (*key).hypervar.variables [j+1];
       }
    }
 }

rational det_and_invert	(	rational **	A,
		int	rows,
		int	columns,
		boolean	verbose
	)

T_VertexSet* do_intersections	(	int	precomp,
		int	i1,
		int	i2,
		int	i3,
		int	action
	)

T_VertexSet duplicate_set ( T_VertexSet s )

Definition at line 1028 of file vinci_lass.c.

References T_VertexSet::lastel, T_VertexSet::loe, T_VertexSet::maxel, and my_malloc().

 {  T_VertexSet newset;
 
    newset.maxel = s.lastel;
    newset.lastel = s.lastel;
    newset.loe = (T_Vertex **) my_malloc ((s.lastel + 1) * sizeof (T_Vertex *));
    memcpy (newset.loe, s.loe, (s.lastel + 1) * sizeof (T_Vertex *));
    return newset;
 }

Here is the call graph for this function:

boolean empty ( T_VertexSet s )

rational factorial ( int n )

void free_basis ( rational *** basis )

void free_faces ( T_VertexSet * face )

void free_fact ( rational * fact )

void free_hyperplanes ( )

void free_incidence ( )

void free_int_vector	(	int *	v,
		int	n
	)

Definition at line 248 of file vinci_lass.c.

References my_free().

 {  
    my_free (v, n * sizeof (int));
 }

Here is the call graph for this function:

void free_key	(	T_Key	key,
		int	key_choice
	)

Definition at line 151 of file vinci_lass.c.

References free_int_vector(), G_d, G_Storage, T_Key::hyperplanes, T_Key::hypervar, KEY_PLANES, KEY_PLANES_VAR, my_free(), and T_Key::variables.

 {
    switch (key_choice)
    {
    case KEY_PLANES:
       free_int_vector (key.hyperplanes, G_d + 1);
       break;
    case KEY_PLANES_VAR:
       my_free (key.hypervar.hyperplanes, (G_Storage + 2) * sizeof (T_LassInt));
       my_free (key.hypervar.variables, (G_Storage + 2) * sizeof (T_LassInt));
       break;
    }
 }

Here is the call graph for this function:

void free_matrix	(	rational **	A,
		int	m,
		int	n
	)

void free_superset ( T_VertexSuperset ** S )

void free_vector ( rational * v )

void free_vertex ( T_Vertex * v )

void intersect	(	T_VertexSet	s1,
		T_VertexSet	s2,
		T_VertexSet *	inter
	)

boolean is_contained	(	T_VertexSet	s1,
		T_VertexSet	s2
	)

boolean is_in_set	(	T_Vertex *	e,
		T_VertexSet	s
	)

boolean is_in_superset	(	T_VertexSet	s,
		T_VertexSuperset *	S
	)

void my_free	(	void *	pointer,
		long int	size
	)

Definition at line 121 of file vinci_lass.c.

 {
    free (pointer);
 }

void* my_malloc ( long int size )

Definition at line 90 of file vinci_lass.c.

References G_MemRes, G_OutOfMem, my_malloc(), and TRUE.

 {  void *pointer;
 
    pointer = malloc (size);
 
    if (pointer == NULL)
       if (!G_OutOfMem)
       {
          fprintf (stderr, "\n***** WARNING: Out of memory; freeing memory reserve\n");
          free (G_MemRes);
          G_OutOfMem = TRUE;
          pointer = my_malloc (size);
       }
       else
       {
          fprintf (stderr, "\n***** ERROR: Out of memory\n");
          exit (0);
       }
    else
    {
 
    }
 
    return pointer;
 }

Here is the call graph for this function:

void* my_realloc	(	void *	pointer,
		long int	new_size,
		long int	size_diff
	)

rational normalise_vertices ( )

rational orthonormal_householder	(	int	d,
		T_VertexSet	face,
		rational **	H
	)

rational orthonormal_schmidt	(	int	d,
		T_VertexSet	face,
		rational **	B
	)

void print_set	(	FILE *	f,
		T_VertexSet	s
	)

void print_superset	(	FILE *	f,
		T_VertexSuperset *	S
	)

void redim_matrix	(	rational ***	A,
		int	m_alt,
		int	m_neu,
		int	n
	)

void simplex_volume	(	T_VertexSet	S,
		rational *	volume,
		boolean	verbose
	)

void tree_out	(	T_Tree **	ppr,
		int *	pi_balance,
		T_Key	key,
		rational **	volume,
		T_Key **	keyfound,
		int	key_choice
	)

Definition at line 870 of file vinci_lass.c.

References compare_key(), create_key(), T_Key::d, duplicate_set(), FALSE, G_d, G_Minus1, G_OutOfMem, G_Storage, T_Key::hyperplanes, T_Key::hypervar, if(), key, KEY_PLANES, KEY_PLANES_VAR, KEY_VERTICES, my_malloc(), p1, T_Key::set, T_Tree::tree_b, T_Tree::tree_l, tree_out(), T_Tree::tree_r, TRUE, T_Key::variables, T_Key::vertices, and T_Tree::vol.

 {  T_Tree *p1, *p2;
    int    cmp;
 
    /* Are we grounded? If so, add the node here and set the rebalance flag, then exit.  */
    if (!*ppr)
    {
       if (G_OutOfMem)
       {  /* don't allocate if out of memory */
          *volume = &G_Minus1;
       }
       else
       {  (*ppr) = (T_Tree *) my_malloc (sizeof (T_Tree));
          (*ppr) -> tree_l = NULL;
          (*ppr) -> tree_r = NULL;
          (*ppr) -> tree_b = 0;
          /* copy the key into the new node */
          create_key (&((*ppr) -> key), key_choice);
          switch (key_choice)
          {
          case KEY_PLANES:
             memcpy ((*ppr) -> key.hyperplanes, key.hyperplanes,
                     (G_d + 1) * sizeof (int));
             break;
          case KEY_VERTICES:
             (*ppr) -> key.vertices.set = duplicate_set (key.vertices.set);
             (*ppr) -> key.vertices.d = key.vertices.d;
             break;
          case KEY_PLANES_VAR:
             memcpy ((*ppr) -> key.hypervar.hyperplanes, key.hypervar.hyperplanes,
                     (G_Storage + 2) * sizeof (T_LassInt));
             memcpy ((*ppr) -> key.hypervar.variables, key.hypervar.variables,
                     (G_Storage + 2) * sizeof (T_LassInt));
             break;
          }
          (*ppr) -> vol = -1;       /* to recognise that element is newly created */
          *volume = &((*ppr) -> vol);
          *pi_balance = TRUE;
       }
       return;
    }
 
    cmp = compare_key ((*ppr) -> key, key, key_choice);
 
    /* if LESS, prepare to move to the left. */
    if (cmp < 0)
    {
       tree_out (&((*ppr) -> tree_l), pi_balance, key, volume, keyfound, key_choice);
       if (*pi_balance)
       {  /* left branch has grown longer */
          switch ((*ppr) -> tree_b)
          {
          case 1:  /* right branch WAS longer; balance is ok now */
                   /* LESS: case 1.. balance restored implicitly */
             (*ppr) -> tree_b = 0;
             *pi_balance = FALSE;
             break;
          case 0:  /* balance WAS okay; now left branch longer */
                   /* LESS: case 0.. balance bad but still ok */
             (*ppr) -> tree_b = -1;
             break;
          case -1: /* left branch was already too long. rebalance */
             p1 = (*ppr) -> tree_l;
             if (p1 -> tree_b == -1)
             {  /* LESS: single LL */
                (*ppr) -> tree_l = p1->tree_r;
                p1 -> tree_r = (*ppr);
                (*ppr) -> tree_b = 0;
                (*ppr) = p1;
             }
             else
             {  /* LESS: real LR */
                p2 = p1 -> tree_r;
                p1 -> tree_r = p2 -> tree_l;
                p2 -> tree_l = p1;
                (*ppr) -> tree_l = p2 -> tree_r;
                p2 -> tree_r = (*ppr);
                if (p2 -> tree_b == -1)
                   (*ppr) -> tree_b = 1;
                else (*ppr) -> tree_b = 0;
                if (p2->tree_b == 1)
                   p1 -> tree_b = -1;
                else p1 -> tree_b = 0;
                (*ppr) = p2;
             }
             (*ppr) -> tree_b = 0;
             *pi_balance = FALSE;
          } /* switch */
       } /* if */
    } /* cmp < 0 */
 
    /* if MORE, prepare to move to the right. */
    else if (cmp > 0)
    {
       tree_out (&((*ppr) -> tree_r), pi_balance, key, volume, keyfound, key_choice);
       if (*pi_balance)
       {  /* right branch has grown longer */
          switch ((*ppr) -> tree_b)
          {
          case -1: /* MORE: balance was off, fixed implicitly */
             (*ppr) -> tree_b = 0;
             *pi_balance = FALSE;
             break;
          case 0:  /* MORE: balance was okay, now off but ok */
             (*ppr)->tree_b = 1;
             break;
          case 1:  /* MORE: balance was off, need to rebalance */
             p1 = (*ppr) -> tree_r;
             if (p1 -> tree_b == 1)
             {  /* MORE: single RR */
                (*ppr) -> tree_r = p1 -> tree_l;
                p1 -> tree_l = (*ppr);
                (*ppr) -> tree_b = 0;
                (*ppr) = p1;
             }
             else
             {  /* MORE: real RL */
                p2 = p1 -> tree_l;
                p1 -> tree_l = p2 -> tree_r;
                p2 -> tree_r = p1;
                (*ppr) -> tree_r = p2 -> tree_l;
                p2 -> tree_l = (*ppr);
                if (p2 -> tree_b == 1)
                   (*ppr) -> tree_b = -1;
                else (*ppr) -> tree_b = 0;
                if (p2 -> tree_b == -1)
                   p1 -> tree_b = 1;
                else p1 -> tree_b = 0;
                (*ppr) = p2;
             }
             (*ppr) -> tree_b = 0;
             *pi_balance = FALSE;
          } /* switch */
       } /* if */
    } /* cmp > 0 */
 
    /* not less, not more: this is the same key! give volume back! */
    else
    {
       *pi_balance = FALSE;
       *volume = &((*ppr) -> vol);
       *keyfound = &((*ppr) -> key);
    }
 }

Here is the call graph for this function:

void volume_cdd_file	(	rational *	volume,
		int	direction,
		char	vertexfile[255]
	)

void volume_ch_file	(	rational *	volume,
		char	vertexfile[255],
		char	incidencefile[255]
	)

void volume_lasserre_file	(	double	planes2[7][4],
		rational *	volume
	)

Definition at line 800 of file vinci_lass.c.

References VOLUME_LASSERRE_FILE().

                                                                      {
   VOLUME_LASSERRE_FILE( planes2, volume);
 }

Here is the call graph for this function:

void volume_lawrence_file	(	rational *	volume,
		char	vertexfile[255],
		char	planesfile[255],
		char	incidencefile[255]
	)

void volume_lawrence_lrs_file	(	rational *	volume,
		char	planesfile[255]
	)

void volume_lrs_file	(	rational *	volume,
		char *	rational_volume,
		char	vertexfile[255]
	)

void volume_ortho_file	(	rational *	volume,
		char	vertexfile[255],
		char	incidencefile[255],
		int	key_choice,
		int	ortho_choice
	)

void volume_qhull_file	(	rational *	volume,
		char	vertexfile[255]
	)

Variable Documentation

int G_d

Definition at line 50 of file vinci_lass.c.

real** G_Hyperplanes

Definition at line 53 of file vinci_lass.c.

T_VertexSet* G_Incidence

Definition at line 54 of file vinci_lass.c.

int G_m

Definition at line 51 of file vinci_lass.c.

void* G_MemRes

Definition at line 62 of file vinci_lass.c.

rational G_Minus1

Definition at line 63 of file vinci_lass.c.

boolean G_OutOfMem

Definition at line 61 of file vinci_lass.c.

int G_Precomp

Definition at line 57 of file vinci_lass.c.

int G_RandomSeed

Definition at line 59 of file vinci_lass.c.

int G_Storage

Definition at line 58 of file vinci_lass.c.

T_VertexSet G_Vertices

Definition at line 55 of file vinci_lass.c.

long int Stat_ActualMem

real Stat_Biggest

unsigned int Stat_Count

unsigned int Stat_CountNeg[STAT_BIGGEST_EXP-STAT_SMALLEST_EXP+3]

unsigned int Stat_CountPos[STAT_BIGGEST_EXP-STAT_SMALLEST_EXP+3]

unsigned int * Stat_CountRetrieved

unsigned int Stat_CountShifts

unsigned int* Stat_CountStored

long int Stat_MaxMem

real Stat_Smallest

Classes

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

Typedef Documentation

Function Documentation

Variable Documentation