vedemo.c

/* 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);
     }

}