1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
/* vedemo.c lrslib vertex enumeration demo */
/* last modified: May 29, 2001 */
/* Copyright: David Avis 2001, avis@cs.mcgill.ca */
/* Demo driver for ve code using lrs */
/* This program computes vertices of generated cubes */
/* given by H-representation */
#include <stdio.h>
#include <string.h>
#include "lrslib.h"
#define MAXCOL 1000 /* maximum number of colums */
void makecube (lrs_dic *P, lrs_dat *Q);
int
main (int argc, char *argv[])
{
lrs_dic *P; /* structure for holding current dictionary and indices */
lrs_dat *Q; /* structure for holding static problem data */
lrs_mp_vector output; /* one line of output:ray,vertex,facet,linearity */
lrs_mp_matrix Lin; /* holds input linearities if any are found */
long i;
long col; /* output column index for dictionary */
/* Global initialization - done once */
if ( !lrs_init ("\n*vedemo:"))
return 1;
/* compute the vertices of a set of hypercubes given by */
/* their H-representations. */
for(i=1;i<=3;i++)
{
/* allocate and init structure for static problem data */
Q = lrs_alloc_dat ("LRS globals");
if (Q == NULL)
return 1;
/* now flags in lrs_dat can be set */
Q->n=i+2; /* number of input columns (dimension + 1 ) */
Q->m=2*i+2; /* number of input rows = number of inequalities */
output = lrs_alloc_mp_vector (Q->n);
P = lrs_alloc_dic (Q); /* allocate and initialize lrs_dic */
if (P == NULL)
return 1;
/* Build polyhedron: constraints and objective */
makecube(P,Q);
/* code from here is borrowed from lrs_main */
/* Pivot to a starting dictionary */
if (!lrs_getfirstbasis (&P, Q, &Lin, FALSE))
return 1;
/* There may have been column redundancy */
/* (although not for this example of hypercubes) */
/* If so the linearity space is obtained and redundant */
/* columns are removed. User can access linearity space */
/* from lrs_mp_matrix Lin dimensions nredundcol x d+1 */
for (col = 0L; col < Q->nredundcol; col++) /* print linearity space */
lrs_printoutput (Q, Lin[col]); /* Array Lin[][] holds the coeffs. */
/* We initiate reverse search from this dictionary */
/* getting new dictionaries until the search is complete */
/* User can access each output line from output which is */
/* a vertex/ray/facet from the lrs_mp_vector output */
do
{
for (col = 0; col <= P->d; col++)
if (lrs_getsolution (P, Q, output, col))
lrs_printoutput (Q, output);
}
while (lrs_getnextbasis (&P, Q, FALSE));
lrs_printtotals (P, Q); /* print final totals */
/* free space : do not change order of next 3 lines! */
lrs_clear_mp_vector (output, Q->n);
lrs_free_dic (P,Q); /* deallocate lrs_dic */
lrs_free_dat (Q); /* deallocate lrs_dat */
} /* end of loop for i= ... */
lrs_close ("vedemo:");
printf("\n");
return 0;
} /* end of main */
void
makecube (lrs_dic *P, lrs_dat *Q)
/* generate H-representation of a unit hypercube */
{
long num[MAXCOL];
long den[MAXCOL];
long row, j;
long m=Q->m; /* number of inequalities */
long n=Q->n; /* hypercube has dimension n-1 */
for (row=1;row<=m;row++)
{
for(j=0;j<n;j++)
{ num [j] = 0;
den [j] = 1;
}
if (row < n)
{ num[0] = 1;
num[row] = -1;
}
else
{ num[0] = 0;
num[row+1-n] = 1;
}
lrs_set_row(P,Q,row,num,den,GE);
}
}
|
