00001 /* 00002 This file is part of PolyLib. 00003 00004 PolyLib is free software: you can redistribute it and/or modify 00005 it under the terms of the GNU General Public License as published by 00006 the Free Software Foundation, either version 3 of the License, or 00007 (at your option) any later version. 00008 00009 PolyLib is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 GNU General Public License for more details. 00013 00014 You should have received a copy of the GNU General Public License 00015 along with PolyLib. If not, see <http://www.gnu.org/licenses/>. 00016 */ 00017 00018 /** 00019 * Tools to compute the ranking function of an iteration J: the number of 00020 * integer points in P that are lexicographically inferior to J 00021 * @author B. Meister <meister@icps.u-strasbg.fr> 00022 * 6/2005 00023 * LSIIT-ICPS, UMR 7005 CNRS Universit� Louis Pasteur 00024 * HiPEAC Network 00025 */ 00026 00027 #ifndef __BM_POLYLIB_RANKING_H__ 00028 #define __BM_POLYLIB_RANKING_H__ 00029 #include <polylib/polylib.h> 00030 00031 /* 00032 * Returns a list of polytopes needed to compute 00033 * the number of points in P that are lexicographically 00034 * smaller than a given point in D. 00035 * Only the first dim dimensions are taken into account 00036 * for computing the lexsmaller relation. 00037 * The remaining variables are assumed to be extra 00038 * existential/control variables. 00039 * When P == D, this is the conventional ranking function. 00040 * P and D are assumed to have the same parameter domain C. 00041 * 00042 * The first polyhedron in the list returned is the 00043 * updated context: a combination of D and C or an extended C. 00044 * 00045 * The order of the variables in the remaining polyhedra is 00046 * - first dim variables of P 00047 * - existential variables of P 00048 * - existential variables of D 00049 * - first dim variables of D 00050 * - the parameters 00051 */ 00052 Polyhedron *LexSmaller(Polyhedron *P, Polyhedron *D, unsigned dim, 00053 Polyhedron *C, unsigned MAXRAYS); 00054 00055 /* 00056 * Returns the number of points in P that are lexicographically 00057 * smaller than a given point in D. 00058 * Only the first dim dimensions are taken into account 00059 * for computing the lexsmaller relation. 00060 * The remaining variables are assumed to be extra 00061 * existential/control variables. 00062 * When P == D, this is the conventional ranking function. 00063 * P and D are assumed to have the same parameter domain C. 00064 * The variables in the Enumeration correspond to the first dim variables 00065 * in D followed by the parameters of D (the variables of C). 00066 */ 00067 Enumeration *Polyhedron_LexSmallerEnumerate(Polyhedron *P, Polyhedron *D, 00068 unsigned dim, 00069 Polyhedron *C, unsigned MAXRAYS); 00070 00071 /* 00072 * Returns a function that assigns a unique number to each point in the 00073 * polytope P ranging from zero to (number of points in P)-1. 00074 * The order of the numbers corresponds to the lexicographical order. 00075 * 00076 * C is the parameter context of the polytope 00077 */ 00078 Enumeration *Polyhedron_Ranking(Polyhedron *P, Polyhedron *C, unsigned MAXRAYS); 00079 00080 #endif /* __BM_POLYLIB_RANKING_H__ */
1.6.1