--- /srv/reproducible-results/rbuild-debian/r-b-build.LIlW3P51/b1/cddlib_094m-1.1_arm64.changes +++ /srv/reproducible-results/rbuild-debian/r-b-build.LIlW3P51/b2/cddlib_094m-1.1_arm64.changes ├── Files │ @@ -1,7 +1,7 @@ │ │ d9f4b886079d3d22fd430bb214ce32cc 18516 libdevel optional libcdd-dev_094m-1.1_arm64.deb │ - 887ee058b9961fd0189839cf1aa4f813 254988 doc optional libcdd-doc_094m-1.1_all.deb │ + 7dabbec9effa7ad2f45bfc9b326869f6 255576 doc optional libcdd-doc_094m-1.1_all.deb │ 14f1b7a8befd2982d80797754db15b0d 120072 debug optional libcdd-tools-dbgsym_094m-1.1_arm64.deb │ 5d6abbcd0b3364133bd34cdfff66759f 30596 math optional libcdd-tools_094m-1.1_arm64.deb │ 28a42948591ff975461384b15101c491 383488 debug optional libcdd0t64-dbgsym_094m-1.1_arm64.deb │ b0712db721d737b32c8ffeaaa277c165 96264 libs optional libcdd0t64_094m-1.1_arm64.deb ├── libcdd-doc_094m-1.1_all.deb │ ├── file list │ │ @@ -1,3 +1,3 @@ │ │ -rw-r--r-- 0 0 0 4 2024-02-28 05:59:09.000000 debian-binary │ │ --rw-r--r-- 0 0 0 840 2024-02-28 05:59:09.000000 control.tar.xz │ │ --rw-r--r-- 0 0 0 253956 2024-02-28 05:59:09.000000 data.tar.xz │ │ +-rw-r--r-- 0 0 0 836 2024-02-28 05:59:09.000000 control.tar.xz │ │ +-rw-r--r-- 0 0 0 254548 2024-02-28 05:59:09.000000 data.tar.xz │ ├── control.tar.xz │ │ ├── control.tar │ │ │ ├── ./control │ │ │ │ @@ -1,13 +1,13 @@ │ │ │ │ Package: libcdd-doc │ │ │ │ Source: cddlib │ │ │ │ Version: 094m-1.1 │ │ │ │ Architecture: all │ │ │ │ Maintainer: Debian Math Team │ │ │ │ -Installed-Size: 258 │ │ │ │ +Installed-Size: 259 │ │ │ │ Breaks: libcdd-dev (<< 094g-3) │ │ │ │ Replaces: libcdd-dev (<< 094g-3) │ │ │ │ Section: doc │ │ │ │ Priority: optional │ │ │ │ Multi-Arch: foreign │ │ │ │ Homepage: https://github.com/cddlib/cddlib │ │ │ │ Description: documentation for libcdd │ │ │ ├── ./md5sums │ │ │ │ ├── ./md5sums │ │ │ │ │┄ Files differ │ ├── data.tar.xz │ │ ├── data.tar │ │ │ ├── file list │ │ │ │ @@ -1,12 +1,12 @@ │ │ │ │ drwxr-xr-x 0 root (0) root (0) 0 2024-02-28 05:59:09.000000 ./ │ │ │ │ drwxr-xr-x 0 root (0) root (0) 0 2024-02-28 05:59:09.000000 ./usr/ │ │ │ │ drwxr-xr-x 0 root (0) root (0) 0 2024-02-28 05:59:09.000000 ./usr/share/ │ │ │ │ drwxr-xr-x 0 root (0) root (0) 0 2024-02-28 05:59:09.000000 ./usr/share/doc/ │ │ │ │ drwxr-xr-x 0 root (0) root (0) 0 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-dev/ │ │ │ │ --rw-r--r-- 0 root (0) root (0) 245728 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-dev/cddlibman.pdf.gz │ │ │ │ +-rw-r--r-- 0 root (0) root (0) 246304 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-dev/cddlibman.pdf.gz │ │ │ │ drwxr-xr-x 0 root (0) root (0) 0 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-doc/ │ │ │ │ -rw-r--r-- 0 root (0) root (0) 572 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-doc/changelog.Debian.gz │ │ │ │ -rw-r--r-- 0 root (0) root (0) 5059 2020-12-08 14:43:12.000000 ./usr/share/doc/libcdd-doc/changelog.gz │ │ │ │ -rw-r--r-- 0 root (0) root (0) 1209 2018-09-29 19:12:01.000000 ./usr/share/doc/libcdd-doc/copyright │ │ │ │ drwxr-xr-x 0 root (0) root (0) 0 2024-02-28 05:59:09.000000 ./usr/share/doc-base/ │ │ │ │ -rw-r--r-- 0 root (0) root (0) 1173 2018-09-29 19:40:06.000000 ./usr/share/doc-base/libcdd-doc.cddlibman │ │ │ ├── ./usr/share/doc/libcdd-dev/cddlibman.pdf.gz │ │ │ │ ├── cddlibman.pdf │ │ │ │ │ ├── pdftotext {} - │ │ │ │ │ │ @@ -4,19 +4,19 @@ │ │ │ │ │ │ and Institute of Theoretical Computer Science │ │ │ │ │ │ ETH Zentrum, CH-8092 Zurich, Switzerland │ │ │ │ │ │ (cddlib ver. 0.94, manual ver. February 7, 2008) │ │ │ │ │ │ │ │ │ │ │ │ Contents │ │ │ │ │ │ 1 Introduction │ │ │ │ │ │ │ │ │ │ │ │ -1 │ │ │ │ │ │ +2 │ │ │ │ │ │ │ │ │ │ │ │ 2 Polyhedra H- and V-Formats (Version 1999) │ │ │ │ │ │ │ │ │ │ │ │ -2 │ │ │ │ │ │ +3 │ │ │ │ │ │ │ │ │ │ │ │ 3 Basic Object Types (Structures) in cddlib │ │ │ │ │ │ │ │ │ │ │ │ 4 │ │ │ │ │ │ │ │ │ │ │ │ 4 Library Functions │ │ │ │ │ │ 4.1 Library Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . │ │ │ │ │ │ @@ -29,36 +29,36 @@ │ │ │ │ │ │ 4.3.5 Polyhedra Data Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . │ │ │ │ │ │ 4.3.6 LP Data Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . │ │ │ │ │ │ 4.3.7 Matrix Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . │ │ │ │ │ │ 4.4 Input/Output Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . │ │ │ │ │ │ 4.5 Obsolete Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . │ │ │ │ │ │ 4.6 Set Functions in setoper library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . │ │ │ │ │ │ │ │ │ │ │ │ -6 │ │ │ │ │ │ 7 │ │ │ │ │ │ 7 │ │ │ │ │ │ -10 │ │ │ │ │ │ -10 │ │ │ │ │ │ +7 │ │ │ │ │ │ 11 │ │ │ │ │ │ 11 │ │ │ │ │ │ +11 │ │ │ │ │ │ +12 │ │ │ │ │ │ 12 │ │ │ │ │ │ 12 │ │ │ │ │ │ 13 │ │ │ │ │ │ 13 │ │ │ │ │ │ 14 │ │ │ │ │ │ -14 │ │ │ │ │ │ +15 │ │ │ │ │ │ 15 │ │ │ │ │ │ │ │ │ │ │ │ 5 An Extension of the CDD Library in GMP mode │ │ │ │ │ │ │ │ │ │ │ │ -15 │ │ │ │ │ │ +16 │ │ │ │ │ │ │ │ │ │ │ │ 6 Examples │ │ │ │ │ │ │ │ │ │ │ │ -15 │ │ │ │ │ │ +16 │ │ │ │ │ │ │ │ │ │ │ │ 7 Numerical Accuracy │ │ │ │ │ │ │ │ │ │ │ │ 16 │ │ │ │ │ │ │ │ │ │ │ │ 8 Other Useful Codes │ │ │ │ │ │ │ │ │ │ │ │ @@ -83,15 +83,15 @@ │ │ │ │ │ │ possibly including multiple strict inequalities. │ │ │ │ │ │ The new functions are particularly important for the development of related software packages MinkSum (by Ch. Weibel) and Gfan (by Anders Jensen), │ │ │ │ │ │ │ │ │ │ │ │ 1 │ │ │ │ │ │ │ │ │ │ │ │ Introduction │ │ │ │ │ │ │ │ │ │ │ │ -The program cddlib is an efficient implementation [16] of the double description Method [19] for │ │ │ │ │ │ +The program cddlib is an efficient implementation [?] of the double description Method [?] for │ │ │ │ │ │ generating all vertices (i.e. extreme points) and extreme rays of a general convex polyhedron given │ │ │ │ │ │ by a system of linear inequalities: │ │ │ │ │ │ P = {x = (x1 , x2 , . . . , xd )T ∈ Rd : b − Ax ≥ 0} │ │ │ │ │ │ where A is a given m × d real matrix and b is a given real m-vector. In the mathematical language, the computation is the transformation of an H-representation of a convex polytope to an │ │ │ │ │ │ V-representation. │ │ │ │ │ │ cddlib is a C-library version of the previously released C-code cdd/cdd+. In order to make │ │ │ │ │ │ this library version, a large part of the cdd source (Version 0.61) has been rewritten. This library │ │ │ │ │ │ @@ -115,25 +115,25 @@ │ │ │ │ │ │ cddlib comes with an LP code to solve the general linear programming (LP) problem to maximize (or minimize) a linear function over polyhedron P . It is useful mainly for solving dense LP’s │ │ │ │ │ │ with large m (say, up to few hundred thousands) and small d (say, up to 100). It implements a │ │ │ │ │ │ revised dual simplex method that updates (d + 1) × (d + 1) matrix for a pivot operation. │ │ │ │ │ │ The program cddlib has an I/O routines that read and write files in Polyhedra format which │ │ │ │ │ │ was defined by David Avis and the author in 1993, and has been updated in 1997 and 1999. The │ │ │ │ │ │ 2 │ │ │ │ │ │ │ │ │ │ │ │ - program called lrs and lrslib [2] developed by David Avis is a C-implementation of the reverse │ │ │ │ │ │ -search algorithm [4] for the same enumeration purpose, and it conforms to Polyhedra format as │ │ │ │ │ │ + program called lrs and lrslib [?] developed by David Avis is a C-implementation of the reverse │ │ │ │ │ │ +search algorithm [?] for the same enumeration purpose, and it conforms to Polyhedra format as │ │ │ │ │ │ well. Hopefully, this compatibility of the two programs enables users to use both programs for the │ │ │ │ │ │ same input files and to choose whichever is useful for their purposes. From our experiences with │ │ │ │ │ │ relatively large problems, the two methods are both useful and perhaps complementary to each │ │ │ │ │ │ other. In general, the program cddlib tends to be efficient for highly degenerate inputs and the │ │ │ │ │ │ program rs tends to be efficient for nondegenerate or slightly degenerate problems. │ │ │ │ │ │ Although the program can be used for nondegenerate inputs, it might not be very efficient. │ │ │ │ │ │ For nondegenerate inputs, other available programs, such as the reverse search code lrs or qhull │ │ │ │ │ │ -(developed by the Geometry Center), might be more efficient. See Section 8 for pointers to these │ │ │ │ │ │ -codes. The paper [3] contains many interesting results on polyhedral computation and experimental │ │ │ │ │ │ +(developed by the Geometry Center), might be more efficient. See Section ?? for pointers to these │ │ │ │ │ │ +codes. The paper [?] contains many interesting results on polyhedral computation and experimental │ │ │ │ │ │ results on cdd+, lrs, qhull and porta. │ │ │ │ │ │ This program can be distributed freely under the GNU GENERAL PUBLIC LICENSE. Please │ │ │ │ │ │ read the file COPYING carefully before using. │ │ │ │ │ │ I will not take any responsibility of any problems you might have with this program. But I will │ │ │ │ │ │ be glad to receive bug reports or suggestions at the e-mail addresses above. If cddlib turns out │ │ │ │ │ │ to be useful, please kindly inform me of what purposes cdd has been used for. I will be happy to │ │ │ │ │ │ include a list of applications in future distribution if I receive enough replies. The most powerful │ │ │ │ │ │ @@ -232,15 +232,15 @@ │ │ │ │ │ │ GNU MP Library or the C double array of size 1. This abstract type allows us to write a single │ │ │ │ │ │ program that can be compiled with the two or more different arithmetics, see example programs │ │ │ │ │ │ such as simplecdd.c, testlp*.c and testcdd*.c in the src and src-gmp subdirectories of the source │ │ │ │ │ │ distribution. │ │ │ │ │ │ There is another data type that is used very often, dd SetFamilyType. This is to store a │ │ │ │ │ │ family of subsets of a finite set. Such a family can represent the incidence relations between the │ │ │ │ │ │ set of extreme points and the set of facets of a polyhedron. Also, it can represent a graph structure by listing the set of vertices adjacent to each vertex (i.e. the adjacency list). To implement │ │ │ │ │ │ -dd SetFamilyType, we use a separate set library called setoper, that handles the basic set operations, This library is briefly introduced in Section 4.6. │ │ │ │ │ │ +dd SetFamilyType, we use a separate set library called setoper, that handles the basic set operations, This library is briefly introduced in Section ??. │ │ │ │ │ │ │ │ │ │ │ │ #define dd_FALSE 0 │ │ │ │ │ │ #define dd_TRUE 1 │ │ │ │ │ │ typedef long dd_rowrange; │ │ │ │ │ │ typedef long dd_colrange; │ │ │ │ │ │ typedef long dd_bigrange; │ │ │ │ │ │ typedef set_type dd_rowset; │ │ │ │ │ │ @@ -340,15 +340,15 @@ │ │ │ │ │ │ │ │ │ │ │ │ 4.1 │ │ │ │ │ │ │ │ │ │ │ │ Library Initialization │ │ │ │ │ │ │ │ │ │ │ │ void dd set global constants(void) : │ │ │ │ │ │ This is to set the global constants such as dd zero, dd purezero and dd one for sign recognition and basic arithmetic operations. Every program to use cddlib must call this function │ │ │ │ │ │ -before doing any computation. Just call this once. See Section 4.3.3 for the definitions of │ │ │ │ │ │ +before doing any computation. Just call this once. See Section ?? for the definitions of │ │ │ │ │ │ constants. │ │ │ │ │ │ void dd free global constants(void) : │ │ │ │ │ │ This is to free the global constants. This should be called when one does not use cddlib │ │ │ │ │ │ functions anymore. │ │ │ │ │ │ │ │ │ │ │ │ 4.2 │ │ │ │ │ │ │ │ │ │ │ │ @@ -370,15 +370,15 @@ │ │ │ │ │ │ computation terminates normally. Otherwise, it returns a value according to the error occurred. │ │ │ │ │ │ dd PolyhedraPtr dd DDMatrix2Poly2(matrix, roworder, err) : │ │ │ │ │ │ This is the same function as dd DDMatrix2Poly except that the insertion order is specified by the user. The argument roworder is of dd RowOrderType and takes one of the values: dd MaxIndex, dd MinIndex, dd MinCutoff, dd MaxCutoff, dd MixCutoff, dd LexMin, │ │ │ │ │ │ dd LexMax, dd RandomRow. In general, dd LexMin is the best choice which is in fact chosen │ │ │ │ │ │ in dd DDMatrix2Poly. If you know that the input is already sorted in the order you like, use │ │ │ │ │ │ dd MinIndex or dd MaxIndex. If the input contains many redundant rows (say more than │ │ │ │ │ │ 80% redundant), you might want to try dd MaxCutoff which might result in much faster │ │ │ │ │ │ -termination, see [3, 16] │ │ │ │ │ │ +termination, see [?, ?] │ │ │ │ │ │ boolean dd DDInputAppend(poly, matrix, err) : │ │ │ │ │ │ Modify the input representation in *poly by appending the matrix of *matrix, and compute │ │ │ │ │ │ the second representation. The number of columns in *matrix must be equal to the input │ │ │ │ │ │ representation. │ │ │ │ │ │ boolean dd LPSolve(lp, solver, err) : │ │ │ │ │ │ Solve lp by the algorithm solver and save the solututions in *lp. Unlike the earlier versions │ │ │ │ │ │ (dplex, cdd+), it can deal with equations and totally zero right hand sides. It is recommended │ │ │ │ │ │ @@ -704,15 +704,15 @@ │ │ │ │ │ │ Write the representation conversion time information on poly to stream f. │ │ │ │ │ │ │ │ │ │ │ │ 4.5 │ │ │ │ │ │ │ │ │ │ │ │ Obsolete Functions │ │ │ │ │ │ │ │ │ │ │ │ boolean dd DoubleDescription(poly, err) : (removed in Version 0.90c) │ │ │ │ │ │ -The new function dd DDMatrix2Poly(matrix, err) (see Section 4.2) replaces (and actually │ │ │ │ │ │ +The new function dd DDMatrix2Poly(matrix, err) (see Section ??) replaces (and actually │ │ │ │ │ │ combines) both this and dd Matrix2Poly(matrix, err). │ │ │ │ │ │ dd PolyhedraPtr dd Matrix2Poly(matrix, err) : (removed in Version 0.90c) │ │ │ │ │ │ See above for the reason for removal. │ │ │ │ │ │ dd LPSolutionPtr dd LPSolutionLoad(lp) : (renamed in Version 0.90c) │ │ │ │ │ │ This function is now called dd CopyLPSolution(lp). │ │ │ │ │ │ │ │ │ │ │ │ 4.6 │ │ │ │ │ │ @@ -792,47 +792,46 @@ │ │ │ │ │ │ magnitude than those in another column, scale one so that they become comparable. │ │ │ │ │ │ │ │ │ │ │ │ 8 │ │ │ │ │ │ │ │ │ │ │ │ Other Useful Codes │ │ │ │ │ │ │ │ │ │ │ │ There are several other useful codes available for vertex enumeration and/or convex hull computation such as lrs, qhull, porta and irisa-polylib. The pointers to these codes are available at │ │ │ │ │ │ -1. lrs by D. Avis [2] (C implementation of the reverse search algorithm [4]). │ │ │ │ │ │ +1. lrs by D. Avis [?] (C implementation of the reverse search algorithm [?]). │ │ │ │ │ │ 16 │ │ │ │ │ │ │ │ │ │ │ │ - 2. qhull by C.B. Barber [6] (C implementation of the beneath-beyond method, see [10, 20], which │ │ │ │ │ │ + 2. qhull by C.B. Barber [?] (C implementation of the beneath-beyond method, see [?, ?], which │ │ │ │ │ │ is the dual of the dd method). │ │ │ │ │ │ -3. porta by T. Christof and A. Löbel [8] (C implementation of the Fourier-Motzkin elimination). │ │ │ │ │ │ -4. IRISA polyhedral library by D.K. Wilde [23] (C implementation of a variation of the dd │ │ │ │ │ │ +3. porta by T. Christof and A. Löbel [?] (C implementation of the Fourier-Motzkin elimination). │ │ │ │ │ │ +4. IRISA polyhedral library by D.K. Wilde [?] (C implementation of a variation of the dd │ │ │ │ │ │ algorithm). │ │ │ │ │ │ -5. PPL: the Parma Polyhedra Library [5] by R. Bagnara (C++ implementation of a variation │ │ │ │ │ │ +5. PPL: the Parma Polyhedra Library [?] by R. Bagnara (C++ implementation of a variation │ │ │ │ │ │ of the dd algorithm). │ │ │ │ │ │ -6. pd by A. Marzetta [18] (C implementation of the primal-dual algorithm [7]). │ │ │ │ │ │ -7. Geometry Center Software List by N. Amenta [1]. │ │ │ │ │ │ -8. Computational Geometry Pages by J. Erickson [11]. │ │ │ │ │ │ -9. Linear Programming FAQ by R. Fourer and J. Gregory [12]. │ │ │ │ │ │ +6. pd by A. Marzetta [?] (C implementation of the primal-dual algorithm [?]). │ │ │ │ │ │ +7. Geometry Center Software List by N. Amenta [?]. │ │ │ │ │ │ +8. Computational Geometry Pages by J. Erickson [?]. │ │ │ │ │ │ +9. Linear Programming FAQ by R. Fourer and J. Gregory [?]. │ │ │ │ │ │ 10. ZIB Berlin polyhedral software list: │ │ │ │ │ │ ftp://elib.zib-berlin.de/pub/mathprog/polyth/index.html. │ │ │ │ │ │ -11. Polyhedral Computation FAQ [13]. │ │ │ │ │ │ +11. Polyhedral Computation FAQ [?]. │ │ │ │ │ │ │ │ │ │ │ │ 9 │ │ │ │ │ │ │ │ │ │ │ │ Codes Using Cddlib │ │ │ │ │ │ │ │ │ │ │ │ There are quite a few nice programs using some functions of cddlib. Here are some of them. │ │ │ │ │ │ -1. LattE [9] computes the number of lattice points in a convex polytope. │ │ │ │ │ │ -2. Minksum [22] is a program to compute the V-representation (i.e. the set of vertices) of the │ │ │ │ │ │ +1. LattE [?] computes the number of lattice points in a convex polytope. │ │ │ │ │ │ +2. Minksum [?] is a program to compute the V-representation (i.e. the set of vertices) of the │ │ │ │ │ │ Minkowski addition of several convex polytopes given by their V-representation in Rd . It is an │ │ │ │ │ │ -implementation in C++ language of the reverse search algorithm [14] whose time complexity │ │ │ │ │ │ +implementation in C++ language of the reverse search algorithm [?] whose time complexity │ │ │ │ │ │ is polynomially bounded by the sizes of input and output. │ │ │ │ │ │ -3. Gfan [17] is a program to list all reduced Gröbner bases of a general polynomial ideal given │ │ │ │ │ │ -by a set of generating polynomials in n-variables. It is an implementation in C++ language │ │ │ │ │ │ -of the reverse search algorithm [15]. │ │ │ │ │ │ -4. TOPCOM [21] computes the combinatorial structure (the oriented matroid) of a point configuration and enumerates all triangulations of a point set. It detects the regularity of a │ │ │ │ │ │ -triangulation using cddlib. │ │ │ │ │ │ +3. Gfan [?] is a program to list all reduced Gröbner bases of a general polynomial ideal given by │ │ │ │ │ │ +a set of generating polynomials in n-variables. It is an implementation in C++ language of │ │ │ │ │ │ +the reverse search algorithm [?]. │ │ │ │ │ │ +4. TOPCOM [?] computes the combinatorial structure (the oriented matroid) of a point configuration and enumerates all triangulations of a point set. It detects the regularity of a triangulation using cddlib. │ │ │ │ │ │ │ │ │ │ │ │ Acknowledgements. │ │ │ │ │ │ I am grateful to Tom Liebling who provided me with an ideal opportunity to visit EPFL for │ │ │ │ │ │ the academic year 1993-1994. Later, Hans-Jakob Lüthi (ETHZ) and Emo Welzl (ETHZ) joined │ │ │ │ │ │ to support the the development of cdd codes (cdd, cdd+, cddlib). Without their generous and │ │ │ │ │ │ continuing support, the present form of this program would not have existed. │ │ │ │ │ │ There are many other people who helped me to improve cdd, in particular, I am indebted to