From 93eac5f75c5da98ffc861bcad273a2b83f253926 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 5 Jan 2007 15:35:03 +0100 Subject: [PATCH] barvinok_enumerate: integrate barvinok_series --- Makefile.am | 4 +- barvinok_enumerate.c => barvinok_enumerate.cc | 54 +++++++++++---- barvinok_series.cc | 76 --------------------- doc/applications.tex | 95 ++++++++++++--------------- 4 files changed, 86 insertions(+), 143 deletions(-) rename barvinok_enumerate.c => barvinok_enumerate.cc (66%) delete mode 100644 barvinok_series.cc diff --git a/Makefile.am b/Makefile.am index ddc9697..004812b 100644 --- a/Makefile.am +++ b/Makefile.am @@ -10,7 +10,7 @@ lib_LTLIBRARIES = libbarvinok.la noinst_PROGRAMS = test barvinok_count randomtest barvinok_enumerate \ barvinok_ehrhart \ verif_ehrhart barvinok_enumerate_e \ - barvinok_series remove_redundant_equalities \ + remove_redundant_equalities \ barvinok_union \ @bv_extra_programs@ EXTRA_PROGRAMS = piptest verify_lexsmaller polyhedron_sample 4coins lexmin \ @@ -88,13 +88,13 @@ LDADD = libbarvinok.la test_SOURCES = test.c barvinok_count_SOURCES = barvinok_count.c barvinok_ehrhart_SOURCES = barvinok_ehrhart.cc -barvinok_series_SOURCES = barvinok_series.cc barvinok_union_SOURCES = barvinok_union.cc if HAVE_OMEGA BEEO_SOURCES = omega/Exit.cc omega/convert.cc else BEEO_SOURCES = endif +barvinok_enumerate_SOURCES = barvinok_enumerate.cc barvinok_enumerate_e_SOURCES = \ verify.h \ verify.c \ diff --git a/barvinok_enumerate.c b/barvinok_enumerate.cc similarity index 66% rename from barvinok_enumerate.c rename to barvinok_enumerate.cc index 38a1335..d8c8c25 100644 --- a/barvinok_enumerate.c +++ b/barvinok_enumerate.cc @@ -16,6 +16,8 @@ struct argp_option argp_options[] = { { "convert", 'c', 0, 0, "convert fractionals to periodics" }, { "floor", 'f', 0, 0, "convert fractionals to floorings" }, { "size", 'S' }, + { "series", 's', 0, 0, "compute rational generating function" }, + { "explicit", 'e', 0, 0, "convert rgf to psp" }, { 0 } }; @@ -24,11 +26,13 @@ struct arguments { int convert; int floor; int size; + int series; + int function; }; error_t parse_opt(int key, char *arg, struct argp_state *state) { - struct arguments *options = state->input; + struct arguments *options = (struct arguments*) state->input; switch (key) { case ARGP_KEY_INIT: @@ -36,6 +40,8 @@ error_t parse_opt(int key, char *arg, struct argp_state *state) options->convert = 0; options->floor = 0; options->size = 0; + options->series = 0; + options->function = 0; break; case 'c': options->convert = 1; @@ -46,6 +52,12 @@ error_t parse_opt(int key, char *arg, struct argp_state *state) case 'S': options->size = 1; break; + case 'e': + options->function = 1; + /* fall through */ + case 's': + options->series = 1; + break; default: return ARGP_ERR_UNKNOWN; } @@ -78,22 +90,38 @@ int main(int argc, char **argv) Polyhedron_Print(stdout, P_VALUE_FMT, A); Polyhedron_Print(stdout, P_VALUE_FMT, C); param_name = Read_ParamNames(stdin, C->Dimension); - EP = barvinok_enumerate_with_options(A, C, bv_options); - print_evalue(stdout, EP, param_name); - if (options.size) - printf("\nSize: %d\n", evalue_size(EP)); - if (options.floor) { - fprintf(stderr, "WARNING: floor conversion not supported\n"); - evalue_frac2floor2(EP, 0); - print_evalue(stdout, EP, param_name); - } else if (options.convert) { - evalue_mod2table(EP, C->Dimension); + + if (options.series) { + gen_fun *gf; + gf = barvinok_series_with_options(A, C, bv_options); + gf->print(std::cout, C->Dimension, param_name); + puts(""); + if (options.function) { + EP = *gf; + print_evalue(stdout, EP, param_name); + free_evalue_refs(EP); + free(EP); + } + delete gf; + } else { + EP = barvinok_enumerate_with_options(A, C, bv_options); print_evalue(stdout, EP, param_name); if (options.size) printf("\nSize: %d\n", evalue_size(EP)); + if (options.floor) { + fprintf(stderr, "WARNING: floor conversion not supported\n"); + evalue_frac2floor2(EP, 0); + print_evalue(stdout, EP, param_name); + } else if (options.convert) { + evalue_mod2table(EP, C->Dimension); + print_evalue(stdout, EP, param_name); + if (options.size) + printf("\nSize: %d\n", evalue_size(EP)); + } + free_evalue_refs(EP); + free(EP); } - free_evalue_refs(EP); - free(EP); + Free_ParamNames(param_name, C->Dimension); Polyhedron_Free(A); Polyhedron_Free(C); diff --git a/barvinok_series.cc b/barvinok_series.cc deleted file mode 100644 index d9c6c72..0000000 --- a/barvinok_series.cc +++ /dev/null @@ -1,76 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include "config.h" - -/* The input of this example program is the same as that of testehrhart - * in the PolyLib distribution, i.e., a polytope in combined - * data and parameter space, a context polytope in parameter space - * and (optionally) the names of the parameters. - * Both polytopes are in PolyLib notation. - */ - -#ifdef HAVE_GROWING_CHERNIKOVA -#define MAXRAYS 0 -#else -#define MAXRAYS 600 -#endif - -#ifndef HAVE_GETOPT_H -#define getopt_long(a,b,c,d,e) getopt(a,b,c) -#else -#include -struct option options[] = { - { "explicit", no_argument, 0, 'e' }, - { "version", no_argument, 0, 'V' }, - { 0, 0, 0, 0 } -}; -#endif - -int main(int argc, char **argv) -{ - Polyhedron *A, *C; - Matrix *M; - evalue *EP; - char **param_name; - gen_fun *gf; - int c, ind = 0; - int function = 0; - - while ((c = getopt_long(argc, argv, "eV", options, &ind)) != -1) { - switch (c) { - case 'e': - function = 1; - break; - case 'V': - printf(barvinok_version()); - exit(0); - break; - } - } - - M = Matrix_Read(); - A = Constraints2Polyhedron(M, MAXRAYS); - Matrix_Free(M); - M = Matrix_Read(); - C = Constraints2Polyhedron(M, MAXRAYS); - Matrix_Free(M); - Polyhedron_Print(stdout, P_VALUE_FMT, A); - Polyhedron_Print(stdout, P_VALUE_FMT, C); - param_name = Read_ParamNames(stdin, C->Dimension); - gf = barvinok_series(A, C, MAXRAYS); - gf->print(std::cout, C->Dimension, param_name); - puts(""); - if (function) { - EP = *gf; - print_evalue(stdout, EP, param_name); - } - delete gf; - Free_ParamNames(param_name, C->Dimension); - Polyhedron_Free(A); - Polyhedron_Free(C); - return 0; -} diff --git a/doc/applications.tex b/doc/applications.tex index b7f6105..61cd68b 100644 --- a/doc/applications.tex +++ b/doc/applications.tex @@ -93,7 +93,7 @@ vertices {barvinok\_enumerate}} The program \ai[\tt]{barvinok\_enumerate} enumerates a -parametric polytope. It takes two polytopes in \PolyLib/ +parametric polytope as a \psp/ or \rgf/. It takes two polytopes in \PolyLib/ notation as input, optionally followed by a list of parameter names. The two polytopes refer to arguments \verb+P+ and \verb+C+ @@ -184,14 +184,55 @@ $$ . \end{cases} $$ +The following is an example of Petr Lison\u{e}k\index{Lison\u{e}k, P.}. +\begin{verbatim} +> cat petr +4 6 +1 -1 -1 -1 1 0 +1 1 -1 0 0 0 +1 0 1 -1 0 0 +1 0 0 1 0 -1 + +0 3 +n +> ./barvinok_enumerate --series < petr +POLYHEDRON Dimension:4 + Constraints:5 Equations:0 Rays:5 Lines:0 +Constraints 5 6 +Inequality: [ -1 -1 -1 1 0 ] +Inequality: [ 1 -1 0 0 0 ] +Inequality: [ 0 1 -1 0 0 ] +Inequality: [ 0 0 1 0 -1 ] +Inequality: [ 0 0 0 0 1 ] +Rays 5 6 +Ray: [ 1 1 1 3 ] +Ray: [ 1 1 0 2 ] +Ray: [ 1 0 0 1 ] +Ray: [ 0 0 0 1 ] +Vertex: [ 1 1 1 3 ]/1 +POLYHEDRON Dimension:1 + Constraints:1 Equations:0 Rays:2 Lines:1 +Constraints 1 3 +Inequality: [ 0 1 ] +Rays 2 3 +Line: [ 1 ] +Vertex: [ 0 ]/1 +(n^3)/((1-n) * (1-n) * (1-n^2) * (1-n^3)) +\end{verbatim} Options:\\ -\begin{tabular}{lll} +\begin{tabular}{llp{0.7\textwidth}} \ai[\tt]{--floor} & \ai[\tt]{-f} & convert \ai[\tt]{fractional}s to \ai[\tt]{flooring}s \\ \ai[\tt]{--convert} & \ai[\tt]{-c} & convert \ai[\tt]{fractional}s to \ai[\tt]{periodic}s +\\ +\ai[\tt]{--series} & \ai[\tt]{-s} & +compute \rgf/ instead of \psp/ +\\ +\ai[\tt]{--explicit} & \ai[\tt]{-e} & +convert computed \rgf/ to a \psp/ \end{tabular} \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_enumerate\_e}} @@ -260,56 +301,6 @@ use \Omegalib/ as a preprocessor call \ai[\tt]{barvinok\_enumerate\_pip} instead of \ai[\tt]{barvinok\_enumerate\_e} \end{tabular} -\subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_series}} -{barvinok\_series}} - -The program \ai[\tt]{barvinok\_series} enumerates a -parametric polytope in the form of a \rgf/. -The input of this program is the same as that of -\ai[\tt]{barvinok\_enumerate}, except that the input polyhedron -is assumed to be full-dimensional. -The following is an example of Petr Lison\u{e}k\index{Lison\u{e}k, P.}. -\begin{verbatim} -> cat petr -4 6 -1 -1 -1 -1 1 0 -1 1 -1 0 0 0 -1 0 1 -1 0 0 -1 0 0 1 0 -1 - -0 3 -n -> ./barvinok_series < petr -POLYHEDRON Dimension:4 - Constraints:5 Equations:0 Rays:5 Lines:0 -Constraints 5 6 -Inequality: [ -1 -1 -1 1 0 ] -Inequality: [ 1 -1 0 0 0 ] -Inequality: [ 0 1 -1 0 0 ] -Inequality: [ 0 0 1 0 -1 ] -Inequality: [ 0 0 0 0 1 ] -Rays 5 6 -Ray: [ 1 1 1 3 ] -Ray: [ 1 1 0 2 ] -Ray: [ 1 0 0 1 ] -Ray: [ 0 0 0 1 ] -Vertex: [ 1 1 1 3 ]/1 -POLYHEDRON Dimension:1 - Constraints:1 Equations:0 Rays:2 Lines:1 -Constraints 1 3 -Inequality: [ 0 1 ] -Rays 2 3 -Line: [ 1 ] -Vertex: [ 0 ]/1 -(n^3)/((1-n) * (1-n) * (1-n^2) * (1-n^3)) -\end{verbatim} - -Options:\\ -\begin{tabular}{llp{0.7\textwidth}} -\ai[\tt]{--explicit} & \ai[\tt]{-e} & -convert computed \rgf/ to a \psp/ -\end{tabular} - \subsection{\texorpdfstring{\protect\ai[\tt]{barvinok\_union}} {barvinok\_union}} -- 2.11.4.GIT