diff --git a/cdd_both_reps.c b/cdd_both_reps.c new file mode 100644 index 0000000..3de4247 --- /dev/null +++ b/cdd_both_reps.c @@ -0,0 +1,255 @@ +/* cdd_both_reps.c: compute reduced H and V representation of polytope + by Volker Braun + + The input is taken from stdin and can be either a + H or V representation, not necessarily reduced. + + based on testcdd1.c, redcheck.c, and of course the cdd library + written by Komei Fukuda, fukuda@ifor.math.ethz.ch + 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 +#include +#include +#include +#include + + + + + +void compute_adjacency(dd_MatrixPtr Rep, dd_ErrorType* err_ptr) +{ + dd_SetFamilyPtr AdjacencyGraph; + if (*err_ptr != dd_NoError) return; + + switch (Rep->representation) { + case dd_Inequality: + printf("Facet graph\n"); + break; + case dd_Generator: + printf("Vertex graph\n"); + break; + case dd_Unspecified: + printf("unknown representation type!\n"); + default: + printf("This should be unreachable!\n"); + exit(2); + } + + /* Output adjacency of vertices/rays/lines */ + if (Rep->rowsize > 0) { /* workaround for bug with empty polyhedron */ + /* compute adjacent vertices/rays/lines */ + AdjacencyGraph = dd_Matrix2Adjacency(Rep, err_ptr); + if (*err_ptr == dd_NoError) { + dd_WriteSetFamily(stdout,AdjacencyGraph); + dd_FreeSetFamily(AdjacencyGraph); + } + } else { + printf("begin\n"); + printf(" 0 0\n"); + printf("end\n"); + } + + printf("\n"); +} + + +void minimal_Vrep_Hrep(dd_MatrixPtr M, + dd_MatrixPtr* Vrep_ptr, dd_MatrixPtr* Hrep_ptr, + dd_ErrorType* err_ptr) +{ + dd_PolyhedraPtr poly; + dd_rowindex newpos; + dd_rowset impl_linset,redset; + dd_MatrixPtr Vrep, Hrep; + + if (*err_ptr != dd_NoError) return; + + /* compute the second representation */ + poly = dd_DDMatrix2Poly(M, err_ptr); + if (*err_ptr != dd_NoError) return; + + if (*err_ptr == dd_NoError) { + /* compute canonical H-representation */ + Hrep = dd_CopyInequalities(poly); + if (Hrep->rowsize > 0) { /* workaround for bug with empty matrix */ + dd_MatrixCanonicalize(&Hrep, &impl_linset, &redset, &newpos, err_ptr); + if (*err_ptr == dd_NoError) { + set_free(redset); + set_free(impl_linset); + free(newpos); + } + } + if (*err_ptr == dd_NoError) (*Hrep_ptr) = Hrep; + } + + if (*err_ptr == dd_NoError) { + /* compute canonical V-representation */ + Vrep = dd_CopyGenerators(poly); + if (Vrep->rowsize > 0) { /* workaround for bug with empty matrix */ + dd_MatrixCanonicalize(&Vrep, &impl_linset, &redset, &newpos, err_ptr); + if (*err_ptr == dd_NoError) { + set_free(redset); + set_free(impl_linset); + free(newpos); + } + } + if (*err_ptr == dd_NoError) (*Vrep_ptr) = Vrep; + } + + dd_FreePolyhedra(poly); +} + + +void print_both_reps(dd_MatrixPtr Vrep, dd_MatrixPtr Hrep) +{ + /* Output V-representation */ + dd_WriteMatrix(stdout,Vrep); + printf("\n"); + + /* Output H-representation */ + dd_WriteMatrix(stdout,Hrep); + printf("\n"); +} + + +void compute_both_reps(dd_MatrixPtr M, dd_ErrorType* err_ptr) +{ + dd_MatrixPtr Vrep, Hrep; + minimal_Vrep_Hrep(M, &Vrep, &Hrep, err_ptr); + if (*err_ptr != dd_NoError) return; + + print_both_reps(Vrep, Hrep); + dd_FreeMatrix(Hrep); + dd_FreeMatrix(Vrep); +} + + +void compute_all(dd_MatrixPtr M, dd_ErrorType* err_ptr) +{ + dd_MatrixPtr Vrep, Hrep; + minimal_Vrep_Hrep(M, &Vrep, &Hrep, err_ptr); + if (*err_ptr != dd_NoError) return; + + print_both_reps(Vrep, Hrep); + compute_adjacency(Vrep, err_ptr); + compute_adjacency(Hrep, err_ptr); + dd_FreeMatrix(Hrep); + dd_FreeMatrix(Vrep); +} + + + +void usage(char *name) +{ + printf("No known option specified, I don't know what to do!\n" + "Usage:\n" + "%s --option\n" + "where --option is precisely one of the following:\n\n" + " --all: Compute everything.\n" + " This will compute minimal H-,V-representation and vertex and facet graph.\n" + "\n" + " --reps: Compute both a minimal H- and minimal V-representation.\n" + "\n" + " --adjacency: Compute adjacency information only.\n" + " The input is assumed to be a minimal representation, as, for example, computed\n" + " by --reps. Warning, you will not get the correct answer if the input\n" + " representation is not minimal! The output is the vertex or facet graph,\n" + " depending on the input.\n" + "\n" + "The input data is a H- or V-representation in cdd's ine/ext format and\n" + "is in each case read from stdin.\n", + name); +} + + +enum command_line_arguments { ALL, REPS, ADJACENCY }; + + +int parse_arguments(char* arg, enum command_line_arguments* option) +{ + if (strcmp(arg,"--all")==0) { + *option = ALL; + return 0; + } + if (strcmp(arg,"--reps")==0) { + *option = REPS; + return 0; + } + if (strcmp(arg,"--adjacency")==0) { + *option = ADJACENCY; + return 0; + } + printf("Unknown option: %s\n", arg); + return 1; +} + + +int main(int argc, char *argv[]) +{ + dd_ErrorType err=dd_NoError; + dd_MatrixPtr M; + enum command_line_arguments option; + + if (argc!=2 || parse_arguments(argv[1],&option)) { + usage(argv[0]); + return 0; + } + + dd_set_global_constants(); + + /* Read data from stdin */ + M = dd_PolyFile2Matrix(stdin, &err); + if (err != dd_NoError) { + printf("I was unable to parse the input data!\n"); + dd_WriteErrorMessages(stdout,err); + dd_free_global_constants(); + return 1; + } + + switch (option) { + case ALL: + compute_all(M,&err); + break; + case REPS: + compute_both_reps(M,&err); + break; + case ADJACENCY: + compute_adjacency(M,&err); + break; + default: + printf("unreachable option %d\n", option); + exit(3); /* unreachable */ + } + + /* cleanup */ + dd_FreeMatrix(M); + if (err != dd_NoError) { + dd_WriteErrorMessages(stdout,err); + } + + dd_free_global_constants(); + return 0; +} + + + diff --git a/cddlib-sagemath.patch b/cddlib-sagemath.patch new file mode 100644 index 0000000..ba9a909 --- /dev/null +++ b/cddlib-sagemath.patch @@ -0,0 +1,43 @@ +diff -up cddlib-094g/src-gmp/Makefile.am.orig cddlib-094g/src-gmp/Makefile.am +--- cddlib-094g/src-gmp/Makefile.am.orig 2012-07-05 13:30:30.982562213 -0400 ++++ cddlib-094g/src-gmp/Makefile.am 2012-07-05 13:31:14.576563881 -0400 +@@ -11,7 +11,8 @@ testcdd1_gmp \ + testcdd2_gmp \ + testlp1_gmp \ + testlp2_gmp \ +-testlp3_gmp ++testlp3_gmp \ ++cdd_both_reps_gmp + #cddmathlink + + scdd_gmp_SOURCES = simplecdd.c +@@ -27,6 +28,7 @@ testcdd2_gmp_SOURCES = tes + testlp1_gmp_SOURCES = testlp1.c + testlp2_gmp_SOURCES = testlp2.c + testlp3_gmp_SOURCES = testlp3.c ++cdd_both_reps_gmp_SOURCES = cdd_both_reps.c + # cddmathlink_SOURCES = cddmathlink.c cddmlio.h cddmlio.c + + LDADD = ../lib-src-gmp/libcddgmp.la +diff -up cddlib-094g/src-gmp/Makefile.in.orig cddlib-094g/src-gmp/Makefile.in +diff -up cddlib-094g/src/Makefile.am.orig cddlib-094g/src/Makefile.am +--- cddlib-094g/src/Makefile.am.orig 2012-07-05 13:34:07.449570501 -0400 ++++ cddlib-094g/src/Makefile.am 2012-07-05 13:34:32.128571446 -0400 +@@ -11,7 +11,8 @@ testshoot \ + testcdd2 \ + testlp1 \ + testlp2 \ +-testlp3 ++testlp3 \ ++cdd_both_reps + #cddmathlink + + scdd_SOURCES = simplecdd.c +@@ -27,6 +28,7 @@ testcdd2_SOURCES = testcdd + testlp1_SOURCES = testlp1.c + testlp2_SOURCES = testlp2.c + testlp3_SOURCES = testlp3.c ++cdd_both_reps_SOURCES = cdd_both_reps.c + # cddmathlink_SOURCES = cddmathlink.c cddmlio.h cddmlio.c + + LDADD = ../lib-src/libcdd.la diff --git a/cddlib.spec b/cddlib.spec index a96b845..84e9c46 100644 --- a/cddlib.spec +++ b/cddlib.spec @@ -1,15 +1,18 @@ Name: cddlib Version: 094g -Release: 1%{?dist} +Release: 2%{?dist} Summary: A library for generating all vertices in convex polyhedrons Group: Applications/Engineering License: GPLv2+ URL: http://www.ifor.math.ethz.ch/~fukuda/cdd_home/ Source0: ftp://ftp.ifor.math.ethz.ch/pub/fukuda/cdd/%{name}-%{version}.tar.gz +# Extracted from http://www.sagemath.org/packages/standard/cddlib-094f.p11.spkg +Source1: cdd_both_reps.c BuildRequires: gmp-devel BuildRequires: tex(latex) +Patch0: cddlib-sagemath.patch %description The C-library cddlib is a C implementation of the Double Description @@ -59,6 +62,14 @@ Sample binaries that use cddlib. %prep %setup -q +%patch0 -p1 + +# due to patch0 change to Makefile.am files +autoreconf -ifs + +# install sagemath extra source +cp %{SOURCE1} src +ln -sf ../src/cdd_both_reps.c src-gmp/cdd_both_reps.c # Clean up the examples rm -rf src/~ src-gmp/~ @@ -127,6 +138,9 @@ rm -f $RPM_BUILD_ROOT%{_libdir}/*.la %changelog +* Thu Jul 5 2012 pcpa - 094g-2 +- Add sagemath patches + * Tue Apr 24 2012 Jerry James - 094g-1 - New upstream release - All patches upstreamed