Added cddlib-094h from http://www.inf.ethz.ch/personal/fukudak/cdd_home/
Change-Id: I64519509269e434b1b9ea87c3fe0805e711c0ac9
diff --git a/third_party/cddlib/src/adjacency.c b/third_party/cddlib/src/adjacency.c
new file mode 100644
index 0000000..de287b4
--- /dev/null
+++ b/third_party/cddlib/src/adjacency.c
@@ -0,0 +1,161 @@
+/* adjacency.c: Test program to call the cdd library cddlib
+ written by Komei Fukuda, fukuda@ifor.math.ethz.ch
+ Version 0.93, July 18, 2003
+ 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;
+}
+
+
+int main(int argc, char *argv[])
+{
+ dd_MatrixPtr M=NULL,M2=NULL,M3=NULL;
+ dd_SetFamilyPtr A=NULL;
+ dd_colrange d;
+ dd_ErrorType err=dd_NoError;
+ dd_rowset redrows,linrows,ignoredrows, basisrows;
+ dd_colset ignoredcols, basiscols;
+ long rank;
+ mytype val;
+ time_t starttime, endtime;
+ dd_DataFileType inputfile;
+ FILE *reading=NULL;
+
+ dd_set_global_constants(); /* First, this must be called. */
+
+ dd_init(val);
+ if (argc>1) strcpy(inputfile,argv[1]);
+ if (argc<=1 || !SetInputFile(&reading,argv[1])){
+ dd_WriteProgramDescription(stdout);
+ fprintf(stdout,"\ncddlib test program to remove redundancy and compute adjacency of the resulting representation.\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) d=M->colsize+1; else d=M->colsize;
+
+ fprintf(stdout, "redundant rows:\n");
+ time(&starttime);
+ redrows=dd_RedundantRows(M, &err);
+ time(&endtime);
+ set_fwrite(stdout, redrows);
+ dd_WriteTimes(stdout,starttime,endtime);
+
+ M2=dd_MatrixSubmatrix(M, redrows);
+
+ fprintf(stdout, "Implicit linearity (after removal of redundant rows): ");
+ linrows=dd_ImplicitLinearityRows(M2, &err);
+
+ if (M->representation==dd_Generator)
+ fprintf(stdout," %ld ", set_card(linrows));
+ else
+ fprintf(stdout," %ld ", set_card(linrows));
+ set_fwrite(stdout,linrows);
+ set_uni(M2->linset, M2->linset, linrows);
+ /* add the implicit linrows to the explicit linearity rows */
+
+ printf("\nNonredundant representation (except possibly for the linearity part):\n");
+ dd_WriteMatrix(stdout, M2);
+
+ /* To remove redundancy of the linearity part,
+ we need to compute the rank and a basis of the linearity part. */
+ set_initialize(&ignoredrows, M2->rowsize);
+ set_initialize(&ignoredcols, M2->colsize);
+ set_compl(ignoredrows, M2->linset);
+ rank=dd_MatrixRank(M2,ignoredrows,ignoredcols, &basisrows, &basiscols);
+ set_diff(ignoredrows, M2->linset, basisrows);
+ M3=dd_MatrixSubmatrix(M2, ignoredrows);
+ if (rank>0){
+ if (set_card(ignoredrows)) {
+ fprintf(stdout,"\nThe following %ld linearity rows are dependent and unnecessary:", set_card(ignoredrows));
+ set_fwrite(stdout,ignoredrows);
+ }
+ } else
+ fprintf(stdout,"\nThe linearity rows are independent and thus minimal\n");
+
+ printf("Nonredundant representation (= minimal representation):\n");
+ dd_WriteMatrix(stdout, M3);
+
+ printf("\nAdjacency of the minimal representation:\n");
+ A=dd_Matrix2Adjacency(M3, &err);
+ dd_WriteSetFamily(stdout, A);
+
+ dd_clear(val);
+ set_free(linrows);
+ set_free(basisrows);
+ set_free(basiscols);
+ set_free(ignoredrows);
+ set_free(ignoredcols);
+ set_free(redrows);
+
+ if (A!=NULL) dd_FreeSetFamily(A);
+ dd_FreeMatrix(M);
+ dd_FreeMatrix(M2);
+ dd_FreeMatrix(M3);
+
+_L99:;
+ if (err!=dd_NoError) dd_WriteErrorMessages(stderr,err);
+ dd_free_global_constants(); /* At the end, this should be called. */
+ return 0;
+}
+
+
+/* end of adjacency.c */