00001 /** 00002 * Tools to compute the ranking function of an iteration J: the number of 00003 * integer points in P that are lexicographically inferior to J 00004 * @author B. Meister <meister@icps.u-strasbg.fr> 00005 * 6/2005 00006 * LSIIT-ICPS, UMR 7005 CNRS Université Louis Pasteur 00007 * HiPEAC Network 00008 */ 00009 00010 #ifndef __BM_POLYLIB_RANKING_H__ 00011 #define __BM_POLYLIB_RANKING_H__ 00012 #include <polylib/polylib.h> 00013 00014 /* 00015 * Returns a list of polytopes needed to compute 00016 * the number of points in P that are lexicographically 00017 * smaller than a given point in D. 00018 * Only the first dim dimensions are taken into account 00019 * for computing the lexsmaller relation. 00020 * The remaining variables are assumed to be extra 00021 * existential/control variables. 00022 * When P == D, this is the conventional ranking function. 00023 * P and D are assumed to have the same parameter domain C. 00024 * 00025 * The first polyhedron in the list returned is the 00026 * updated context: a combination of D and C or an extended C. 00027 * 00028 * The order of the variables in the remaining polyhedra is 00029 * - first dim variables of P 00030 * - existential variables of P 00031 * - existential variables of D 00032 * - first dim variables of D 00033 * - the parameters 00034 */ 00035 Polyhedron *LexSmaller(Polyhedron *P, Polyhedron *D, unsigned dim, 00036 Polyhedron *C, unsigned MAXRAYS); 00037 00038 /* 00039 * Returns the number of points in P that are lexicographically 00040 * smaller than a given point in D. 00041 * Only the first dim dimensions are taken into account 00042 * for computing the lexsmaller relation. 00043 * The remaining variables are assumed to be extra 00044 * existential/control variables. 00045 * When P == D, this is the conventional ranking function. 00046 * P and D are assumed to have the same parameter domain C. 00047 * The variables in the Enumeration correspond to the first dim variables 00048 * in D followed by the parameters of D (the variables of C). 00049 */ 00050 Enumeration *Polyhedron_LexSmallerEnumerate(Polyhedron *P, Polyhedron *D, 00051 unsigned dim, 00052 Polyhedron *C, unsigned MAXRAYS); 00053 00054 /* 00055 * Returns a function that assigns a unique number to each point in the 00056 * polytope P ranging from zero to (number of points in P)-1. 00057 * The order of the numbers corresponds to the lexicographical order. 00058 * 00059 * C is the parameter context of the polytope 00060 */ 00061 Enumeration *Polyhedron_Ranking(Polyhedron *P, Polyhedron *C, unsigned MAXRAYS); 00062 00063 #endif /* __BM_POLYLIB_RANKING_H__ */
1.5.6