third_party/cddlib/src/allfaces.c

/* allfaces.c: Test program to call the cdd library cddlib
   written by Komei Fukuda, fukuda@ifor.math.ethz.ch
   Version 0.94, August 4, 2005
   Standard ftp site: ftp.ifor.math.ethz.ch, Directory: pub/fukuda/cdd
*/

/*  This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#include "setoper.h"
#include "cdd.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>

dd_boolean SetInputFile(FILE **f, dd_DataFileType fname)
{
  dd_boolean success=dd_FALSE;
  success=dd_FALSE;

  if ( ( *f = fopen(fname, "r") )!= NULL) {
    printf("input file %s is open\n", fname);
    success=dd_TRUE;
  }
  else{
    printf("The input file %s not found\n",fname);
  }
  return success;
}

dd_boolean SetWriteFile(FILE **f, dd_DataFileType fname)
{
  dd_boolean success=dd_FALSE;

  if ( (*f = fopen(fname, "w")) != NULL){
    printf("output file %s is open\n",fname);
    success=dd_TRUE;
  }
  else{
    printf("The output file %s cannot be opened\n",fname);
  }
  return success;
}

dd_boolean FaceEnum(dd_MatrixPtr M, dd_rowset R, dd_rowset S, dd_boolean rip, dd_colrange mindim)
{
  dd_ErrorType err;
  dd_rowset LL, ImL, RR, SS, Lbasis;
  dd_rowrange i,iprev=0;
  dd_colrange j,dim;
  dd_LPSolutionPtr lps=NULL;
  dd_boolean success=dd_FALSE;

  set_initialize(&LL, M->rowsize);
  set_initialize(&RR, M->rowsize);
  set_initialize(&SS, M->rowsize);
  set_copy(LL, M->linset); /* rememer the linset. */
  set_copy(RR, R); /* copy of R. */
  set_copy(SS, S); /* copy of S. */
  if (dd_ExistsRestrictedFace(M, R, S, &err)){
    set_uni(M->linset, M->linset, R);
	dd_FindRelativeInterior(M, &ImL, &Lbasis, &lps, &err);
	dim=M->colsize - set_card(Lbasis)-1;
    set_uni(M->linset, M->linset, ImL);
	fprintf(stdout,"%ld: ", dim); set_fwrite(stdout,M->linset);
	if (rip){
    	/* Write an interior point. */
	  printf("RIP: (");
	  for (j=1; j <(lps->d)-1; j++) {
	    dd_WriteNumber(stdout,lps->sol[j]);
	  }
	  printf(")\n");
	}
	dd_FreeLPSolution(lps);
	set_free(ImL);
	set_free(Lbasis);
   
    if (dim>mindim){
	  for (i=1; i<=M->rowsize; i++){
	    if (!set_member(i, M->linset) && !set_member(i, S)){
		  set_addelem(RR, i);
		  if (iprev) {
		    set_delelem(RR,iprev);
		    set_delelem(M->linset,iprev);
		    set_addelem(SS, iprev);
		  }
		  iprev=i;
		  FaceEnum(M, RR, SS, rip, mindim);
		}
	  }
	}
  } else if (err!=dd_NoError) goto _L99;
  success=dd_TRUE;

_L99:
  set_copy(M->linset, LL); /* restore the linset */
  set_free(LL);
  set_free(RR);
  set_free(SS);
  return success;
}



int main(int argc, char *argv[])
{
  dd_MatrixPtr M=NULL;
  dd_rowrange m;
  dd_ErrorType err=dd_NoError;
  dd_rowset R, S;
  dd_DataFileType inputfile;
  FILE *reading=NULL;
  char ch;
  dd_colrange mindim;
  dd_boolean rip=dd_FALSE;
  
  
  dd_set_global_constants();  /* First, this must be called. */

  if (argc>1) strcpy(inputfile,argv[1]);
  if (argc<=1 || !SetInputFile(&reading,argv[1])){
    dd_WriteProgramDescription(stdout);
    fprintf(stdout,"\ncddlib test program to list all faces of an H-polyhedron.\n");
    dd_SetInputFile(&reading,inputfile, &err);
  }
  if (err==dd_NoError) {
    M=dd_PolyFile2Matrix(reading, &err);
  }
  else {
    fprintf(stderr,"Input file not found\n");
    goto _L99;
  }

  if (err!=dd_NoError) goto _L99;
  
  if (M->representation==dd_Generator){
    printf("The input is V-representation.  Consider it as H-representation (N)? ");
    ch=getchar(); getchar();
    if (ch!='y' && ch!='Y') goto _L99;
  }

  m=M->rowsize;
  
  set_initialize(&R, M->rowsize); 
  set_initialize(&S, M->rowsize); 
  
  printf("Output relative interior points (N)? ");
  ch=getchar();
  if (ch=='y' || ch=='Y') rip=dd_TRUE;
  printf("Minimum dimension of faces to list (0..%ld) ? ",M->colsize-1);
  scanf("%ld", &mindim);
  if (mindim>=M->colsize) mindim=M->colsize-1;
  printf("Minimum dimension is set to %ld.", mindim);

  printf("\n--- FaceEnum (dim: active set) ---\nbegin\n");
  FaceEnum(M, R, S, rip, mindim);
  fprintf(stderr,"end\nFaceEnum completed.\n");

  dd_FreeMatrix(M);
  set_free(R);
  set_free(S);
_L99:;
  if (err!=dd_NoError) dd_WriteErrorMessages(stderr,err);
  dd_free_global_constants();  /* At the end, this should be called. */
  return 0;
}


/* end of allfaces.c */