sci-libs/cddlib/files/cdd_both_reps.c

   1 /* cdd_both_reps.c: compute reduced H and V representation of polytope
   2    by Volker Braun <vbraun@stp.dias.ie>
   3
   4    The input is taken from stdin and can be either a
   5    H or V representation, not necessarily reduced.
   6
   7    based on testcdd1.c, redcheck.c, and of course the cdd library
   8    written by Komei Fukuda, fukuda@ifor.math.ethz.ch
   9    Standard ftp site: ftp.ifor.math.ethz.ch, Directory: pub/fukuda/cdd
  10 */
  11
  12 /*  This program is free software; you can redistribute it and/or modify
  13     it under the terms of the GNU General Public License as published by
  14     the Free Software Foundation; either version 2 of the License, or
  15     (at your option) any later version.
  16
  17     This program is distributed in the hope that it will be useful,
  18     but WITHOUT ANY WARRANTY; without even the implied warranty of
  19     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20     GNU General Public License for more details.
  21
  22     You should have received a copy of the GNU General Public License
  23     along with this program; if not, write to the Free Software
  24     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  25 */
  26
  27 #include "setoper.h"
  28 #include "cdd.h"
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <time.h>
  32 #include <math.h>
  33 #include <string.h>
  34
  35
  36
  37
  38
  39 void compute_adjacency(dd_MatrixPtr Rep, dd_ErrorType* err_ptr)
  40 {
  41   dd_SetFamilyPtr AdjacencyGraph;
  42   if (*err_ptr != dd_NoError) return;
  43
  44   switch (Rep->representation) {
  45   case dd_Inequality:
  46     printf("Facet graph\n");
  47     break;
  48   case dd_Generator:
  49     printf("Vertex graph\n");
  50     break;
  51   case dd_Unspecified:
  52     printf("unknown representation type!\n");
  53   default:
  54     printf("This should be unreachable!\n");
  55     exit(2);
  56   }
  57
  58   /* Output adjacency of vertices/rays/lines */
  59   if (Rep->rowsize > 0) {  /* workaround for bug with empty polyhedron */
  60     /* compute adjacent vertices/rays/lines */
  61     AdjacencyGraph = dd_Matrix2Adjacency(Rep, err_ptr);
  62     if (*err_ptr == dd_NoError) {
  63       dd_WriteSetFamily(stdout,AdjacencyGraph);
  64       dd_FreeSetFamily(AdjacencyGraph);
  65     }
  66   } else {
  67     printf("begin\n");
  68     printf("  0    0\n");
  69     printf("end\n");
  70   }
  71
  72   printf("\n");
  73 }
  74
  75
  76 void minimal_Vrep_Hrep(dd_MatrixPtr M,
  77                        dd_MatrixPtr* Vrep_ptr, dd_MatrixPtr* Hrep_ptr,
  78                        dd_ErrorType* err_ptr)
  79 {
  80   dd_PolyhedraPtr poly;
  81   dd_rowindex newpos;
  82   dd_rowset impl_linset,redset;
  83   dd_MatrixPtr Vrep, Hrep;
  84
  85   if (*err_ptr != dd_NoError) return;
  86
  87    /* compute the second representation */
  88   poly = dd_DDMatrix2Poly(M, err_ptr);
  89   if (*err_ptr != dd_NoError) return;
  90
  91   if (*err_ptr == dd_NoError) {
  92     /* compute canonical H-representation */
  93     Hrep = dd_CopyInequalities(poly);
  94     if (Hrep->rowsize > 0) {  /* workaround for bug with empty matrix */
  95       dd_MatrixCanonicalize(&Hrep, &impl_linset, &redset, &newpos, err_ptr);
  96       if (*err_ptr == dd_NoError) {
  97         set_free(redset);
  98         set_free(impl_linset);
  99         free(newpos);
 100       }
 101     }
 102     if (*err_ptr == dd_NoError) (*Hrep_ptr) = Hrep;
 103   }
 104
 105   if (*err_ptr == dd_NoError) {
 106     /* compute canonical V-representation */
 107     Vrep = dd_CopyGenerators(poly);
 108     if (Vrep->rowsize > 0) {  /* workaround for bug with empty matrix */
 109       dd_MatrixCanonicalize(&Vrep, &impl_linset, &redset, &newpos, err_ptr);
 110       if (*err_ptr == dd_NoError) {
 111         set_free(redset);
 112         set_free(impl_linset);
 113         free(newpos);
 114       }
 115     }
 116     if (*err_ptr == dd_NoError) (*Vrep_ptr) = Vrep;
 117   }
 118
 119   dd_FreePolyhedra(poly);
 120 }
 121
 122
 123 void print_both_reps(dd_MatrixPtr Vrep, dd_MatrixPtr Hrep)
 124 {
 125   /* Output V-representation */
 126   dd_WriteMatrix(stdout,Vrep);
 127   printf("\n");
 128
 129   /* Output H-representation */
 130   dd_WriteMatrix(stdout,Hrep);
 131   printf("\n");
 132 }
 133
 134
 135 void compute_both_reps(dd_MatrixPtr M, dd_ErrorType* err_ptr)
 136 {
 137   dd_MatrixPtr Vrep, Hrep;
 138   minimal_Vrep_Hrep(M, &Vrep, &Hrep, err_ptr);
 139   if (*err_ptr != dd_NoError) return;
 140
 141   print_both_reps(Vrep, Hrep);
 142   dd_FreeMatrix(Hrep);
 143   dd_FreeMatrix(Vrep);
 144 }
 145
 146
 147 void compute_all(dd_MatrixPtr M, dd_ErrorType* err_ptr)
 148 {
 149   dd_MatrixPtr Vrep, Hrep;
 150   minimal_Vrep_Hrep(M, &Vrep, &Hrep, err_ptr);
 151   if (*err_ptr != dd_NoError) return;
 152
 153   print_both_reps(Vrep, Hrep);
 154   compute_adjacency(Vrep, err_ptr);
 155   compute_adjacency(Hrep, err_ptr);
 156   dd_FreeMatrix(Hrep);
 157   dd_FreeMatrix(Vrep);
 158 }
 159
 160
 161
 162 void usage(char *name)
 163 {
 164   printf("No known option specified, I don't know what to do!\n"
 165          "Usage:\n"
 166          "%s --option\n"
 167          "where --option is precisely one of the following:\n\n"
 168          "  --all: Compute everything.\n"
 169          "    This will compute minimal H-,V-representation and vertex and facet graph.\n"
 170          "\n"
 171          "  --reps: Compute both a minimal H- and minimal V-representation.\n"
 172          "\n"
 173          "  --adjacency: Compute adjacency information only.\n"
 174          "    The input is assumed to be a minimal representation, as, for example, computed\n"
 175          "    by --reps. Warning, you will not get the correct answer if the input\n"
 176          "    representation is not minimal! The output is the vertex or facet graph,\n"
 177          "    depending on the input.\n"
 178          "\n"
 179          "The input data is a H- or V-representation in cdd's ine/ext format and\n"
 180          "is in each case read from stdin.\n",
 181          name);
 182 }
 183
 184
 185 enum command_line_arguments { ALL, REPS, ADJACENCY };
 186
 187
 188 int parse_arguments(char* arg, enum command_line_arguments* option)
 189 {
 190   if (strcmp(arg,"--all")==0) {
 191     *option = ALL;
 192     return 0;
 193   }
 194   if (strcmp(arg,"--reps")==0) {
 195     *option = REPS;
 196     return 0;
 197   }
 198   if (strcmp(arg,"--adjacency")==0) {
 199     *option = ADJACENCY;
 200     return 0;
 201   }
 202   printf("Unknown option: %s\n", arg);
 203   return 1;
 204 }
 205
 206
 207 int main(int argc, char *argv[])
 208 {
 209   dd_ErrorType err=dd_NoError;
 210   dd_MatrixPtr M;
 211   enum command_line_arguments option;
 212
 213   if (argc!=2 || parse_arguments(argv[1],&option)) {
 214     usage(argv[0]);
 215     return 0;
 216   }
 217
 218   dd_set_global_constants();
 219
 220   /* Read data from stdin */
 221   M = dd_PolyFile2Matrix(stdin, &err);
 222   if (err != dd_NoError) {
 223     printf("I was unable to parse the input data!\n");
 224     dd_WriteErrorMessages(stdout,err);
 225     dd_free_global_constants();
 226     return 1;
 227   }
 228
 229   switch (option) {
 230   case ALL:
 231     compute_all(M,&err);
 232     break;
 233   case REPS:
 234     compute_both_reps(M,&err);
 235     break;
 236   case ADJACENCY:
 237     compute_adjacency(M,&err);
 238     break;
 239   default:
 240     printf("unreachable option %d\n", option);
 241     exit(3); /* unreachable */
 242   }
 243
 244   /* cleanup */
 245   dd_FreeMatrix(M);
 246   if (err != dd_NoError) {
 247     dd_WriteErrorMessages(stdout,err);
 248   }
 249
 250   dd_free_global_constants();
 251   return 0;
 252 }
 253
 254
 255