= cddlib =
== Description ==
The C-library cddlib is a C implementation of the Double Description
Method of Motzkin et al. for generating all vertices (i.e. extreme points)
and extreme rays of a general convex polyhedron in R^d given by a system
of linear inequalities:
P = { x=(x1, ..., xd)^T : b - A x >= 0 }
where A is a given m x d real matrix, b is a given m-vector
and 0 is the m-vector of all zeros.
The program can be used for the reverse operation (i.e. convex hull
computation). This means that one can move back and forth between
an inequality representation and a generator (i.e. vertex and ray)
representation of a polyhedron with cdd. Also, cdd can solve a linear
programming problem, i.e. a problem of maximizing and minimizing
a linear function over P.
== License ==
GPL v2
== SPKG Maintainers ==
* Marshall Hampton
* Volker Braun
== Upstream Contact ==
Komei Fukuda <[email protected]>
Institute for Operations Research
and Institute of Theoretical Computer Science
ETH Zentrum, CH-8092 Zurich, Switzerland
Tel +41-1-632-4023, Fax +41-1-632-1025
http://www.ifor.math.ethz.ch/staff/fukuda/
== Dependencies ==
* gmp (or its fork mpir)
== Special Update/Build Instructions ==
From clean upstream sources:
* remove directories doc, examples/*, src-mathlink/*, autom4te.cache
* Important - when recreating spkg, must make sure to first use hard links
See Trac 11245, where this caused it to fail on Cygwin:
Instructions from Dima Pasechnik, where of course foo = cddlib-vers
/* on a Unix, with good tar: */
$ tar xjf foo.spkg
$ tar chjf foo.spkg foo/
$ tar xjf foo.spkg
$ sage -spkg foo
== Changelog ==
=== cddlib-094f.p11 (Jeroen Demeyer, 13 February 2012) ===
* Trac #12501: refresh autogenerated files using the
patches/refresh_autogenerated.sh script.
=== cddlib-094f.p10 (Karl-Dieter Crisman, 1st July 2011) ===
* Changed to hard links so that the package would build on Cygwin
See Trac 11245
=== cddlib-094f.p9 (Simon King, 10th Dec 2011) ===
* #12131: Use --libdir, to make the package work on openSUSE.
=== cddlib-094f.p8 (Volker Braun, 21th Sept 2010) ===
* Add command line option to cdd_both_reps to optionally skip
adjacency computations.
* Include a simple random number generator (taken from the GNU C
library) to ensure the same output ordering on different platforms,
see http://trac.sagemath.org/sage_trac/ticket/9926
=== cddlib-094f.p7 (Volker Braun, 7th June 2010) ===
* Rewrite of configure.ac and Makefile.am's
Now ./configure --with-gmp=<path> works.
* I added a script patches/refresh_autogenerated.sh that explains how
to update the autotools output.
* allfaces.c now gone for good, nobody used it.
=== cddlib-094f.p6 (Volker Braun, 20th April 2010) ===
* use Sage's gmp/mpir libraries, not /usr/local in Automake.am
=== cddlib-094f.p5 (David Kirkby, 25th February 2010) ===
* #8363 Remove pointless check for mpir, which is breaking on Solaris.
mpir is built long before cddlib (50 packages earlier), so its
hard to see why it should be checked. In any case, the dependancy
is already in spkg/standard/deps.
* Allow a 64-bit build on any platform, not just OS X by resolving the
usual use of SAGE64 which currently only works on OS X.
=== cddlib-094f.p4 (Volker Braun, Minh Van Nguyen, January 29th, 2010) ===
* renamed patches/cdd_both_reps-makefiles.patch -> patches/automake.patch
* added check for required mpir (aka GMP) to spkg-install
* added spkg-check
* corrected src/patching, see
http://trac.sagemath.org/sage_trac/ticket/8115 and
http://groups.google.com/group/sage-devel/browse_thread/thread/e599fd37de909264
* removed CFLAGS settings in spkg-install, not required.
=== cddlib-094f.p3 (Volker Braun, January 26th, 2010) ===
* libtool-ized
After implementing the changes, I found that tabbott proposed a
similar patch to the automake files earlier:
http://sagetrac.org/sage_trac/ticket/3304
* renamed configure.in -> configure.ac (preferred usage)
=== cddlib-094f.p2 (Volker Braun, Marshall Hampton, Alex Ghitza, January 25th, 2010) ===
* patch cdd_both_reps.c
* remove dist/
* clean up SPKG.txt
* updated makefiles and regenerated configure scripts
Note: For future reference, patches/cdd_both_reps-makefiles.patch
shows the changed automake-sources. This is already applied to src/
=== cddlib-094f (Sebastien Barthelemy, January 26th, 2009) ===
* using upstream version 094f
=== cddlib-094b.p3 (Michael Abshoff, September 22nd, 2008) ===
* add Solaris x86[-64] build support
=== cddlib-094b.p2 (Michael Abshoff, May 18th, 2008) ===
* add 64 bit support on OSX
=== ??? (Michael Abshoff, November 11th, 2007) ===
* add -L$SAGE_LOCAL/lib to CFLAGS to force linking against Sage's gmp
(issue reported by Justin Walker)
