1 | // term_ordering.h |
---|
2 | |
---|
3 | |
---|
4 | // Our IP-algorithms need two kinds of term orderings: a weighted term ordering |
---|
5 | // and a block ordering that eliminates some auxiliary variables. Both |
---|
6 | // are constructed from the input or for the specific requirements of the |
---|
7 | // algorithms. To allow an easy and flexible handling, the term ordering is |
---|
8 | // realized as a class. |
---|
9 | |
---|
10 | // Weight vectors for term orderings have to be nonnegative in most contexts. |
---|
11 | // But input vectors with negative components are not refused by the |
---|
12 | // constructors. This has the following two reasons: |
---|
13 | // - There is a more general notion of term ordering who does not claim |
---|
14 | // the monomial 1 to be a (unique) minimal monomial. This allows negative |
---|
15 | // weights. |
---|
16 | // - This class is written for the final purpose of integer programming. |
---|
17 | // The linear objective function induces the term ordering and might also |
---|
18 | // have negative components. Although the program actually cannot treat |
---|
19 | // this case, there are ways to tackle it. In view of a possible later |
---|
20 | // expansion of the program, the nonnegativity check is delegated to a |
---|
21 | // separate function instead of doing it in the constructors. |
---|
22 | |
---|
23 | // For the same reasons as mentionned in the binomial class, frequently |
---|
24 | // used operations on Integer vectors do not perform range checks. Nor do |
---|
25 | // they check if an error has occurred (i.e. control the "error flag", see |
---|
26 | // below). |
---|
27 | // These are concretely the functions weight(...), compare_to_zero(...) and |
---|
28 | // compare(...). |
---|
29 | // All other routines perform argument checks (range, file format...). |
---|
30 | // This is only really important when reading from a file (as most other range |
---|
31 | // checks are already made by the routines calling these functions). But as |
---|
32 | // all these operations are executed only a few times in the course of our |
---|
33 | // algorithms, the checks do not slow down computation. |
---|
34 | |
---|
35 | #ifndef TERM_ORDERING_H |
---|
36 | #define TERM_ORDERING_H |
---|
37 | |
---|
38 | #include "globals.h" |
---|
39 | |
---|
40 | class binomial; |
---|
41 | |
---|
42 | class term_ordering |
---|
43 | { |
---|
44 | protected: |
---|
45 | |
---|
46 | float *weight_vector; |
---|
47 | |
---|
48 | short weighted_block_size; |
---|
49 | // the number of weighted variables |
---|
50 | // Also the "error flag", i.e. values <0 indicate an error: |
---|
51 | // -1 indicates a "semantic" error (arguments out of range, for example a |
---|
52 | // negative number of variables); |
---|
53 | // -2 indicates an error occured when reading from a file. |
---|
54 | |
---|
55 | short weighted_ordering; |
---|
56 | // the term ordering refining the weight on the weighted variables |
---|
57 | // possibilities: see in globals.h |
---|
58 | |
---|
59 | short elimination_block_size; |
---|
60 | // the number of elimination variables |
---|
61 | |
---|
62 | short elimination_ordering; |
---|
63 | // the term ordering on the elimination variables |
---|
64 | |
---|
65 | BOOLEAN homogeneous; |
---|
66 | // This flag is set to TRUE if the term ordering is thought of as a |
---|
67 | // homogeneous one (i.e. the weighted part), else to FALSE. The standard |
---|
68 | // setting is FALSE. |
---|
69 | // The routine compare_to_zero is faster if the term ordering is homogenous. |
---|
70 | // It would be safer and more natural to take this flag as a member of |
---|
71 | // the ideal class; this would, however, require many supplementary |
---|
72 | // functions (homogeneous versions of existing functions) in the ideal and |
---|
73 | // even in the binomial class. |
---|
74 | |
---|
75 | public: |
---|
76 | // constructors and destructor |
---|
77 | |
---|
78 | term_ordering(const BOOLEAN& homogeneous=FALSE); |
---|
79 | // Sets weighted_block_size and elimination_block_size to zero. |
---|
80 | // With this default contructor, the term ordering can be taken as a member |
---|
81 | // of another class (the ideal class in our case). |
---|
82 | |
---|
83 | term_ordering(const short& number_of_weighted_variables, |
---|
84 | const float* weights, |
---|
85 | const short& _weighted_ordering, |
---|
86 | const BOOLEAN& _homogeneous=FALSE); |
---|
87 | // Initializes weight vector with weights, |
---|
88 | // weighted_block_size with number_of_weighted_variables, |
---|
89 | // the refining ordering as given in the argument |
---|
90 | // and elimination_block_size with 0. |
---|
91 | |
---|
92 | term_ordering(const short& number_of_weighted_variables, |
---|
93 | const float* weights, |
---|
94 | const short& _weighted_ordering, |
---|
95 | const short& number_of_elimination_variables, |
---|
96 | const short& _elimination_ordering, |
---|
97 | const BOOLEAN& _homogeneous=FALSE); |
---|
98 | // Initializes weight vector with weights, |
---|
99 | // weighted_block_size with number_of_weighted_variables, |
---|
100 | // the orderings as given in the arguments |
---|
101 | // and elimination_block_size with _number_of_elimination_variables. |
---|
102 | |
---|
103 | term_ordering(ifstream& input, const short& _weighted_ordering, |
---|
104 | const BOOLEAN& _homogeneous=FALSE); |
---|
105 | // Reads a weight vector from the input stream and converts it into a |
---|
106 | // weighted term ordering (with the refining ordering given by the second |
---|
107 | // argument). |
---|
108 | // The input stream must have the following format: |
---|
109 | // |
---|
110 | // size n of the weight vector (=weighted_block_size) |
---|
111 | // components 0..n-1 of the weight vector |
---|
112 | // |
---|
113 | |
---|
114 | term_ordering(const short& n, ifstream& input, |
---|
115 | const short& _weighted_ordering, |
---|
116 | const BOOLEAN& _homogeneous=FALSE); |
---|
117 | // Reads a weight vector of size n from the input stream and converts it |
---|
118 | // into a weighted term ordering (with the refining ordering given by the |
---|
119 | // second argument). |
---|
120 | // The input stream has the following format: |
---|
121 | // |
---|
122 | // components 0..n-1 of the weight vector |
---|
123 | // |
---|
124 | |
---|
125 | term_ordering(const term_ordering&); |
---|
126 | // copy-constructor |
---|
127 | |
---|
128 | |
---|
129 | ~term_ordering(); |
---|
130 | // destructor |
---|
131 | |
---|
132 | // object properties |
---|
133 | |
---|
134 | short number_of_weighted_variables() const; |
---|
135 | // Returns weighted_block_size. |
---|
136 | |
---|
137 | short weight_refinement() const; |
---|
138 | // Returns weighted_ordering. |
---|
139 | |
---|
140 | short number_of_elimination_variables() const; |
---|
141 | // Returns elimination_block_size. |
---|
142 | |
---|
143 | short elimination_refinement() const; |
---|
144 | // Returns elimination_ordering. |
---|
145 | |
---|
146 | BOOLEAN is_homogeneous() const; |
---|
147 | // Returns homogeneous. |
---|
148 | |
---|
149 | short error_status() const; |
---|
150 | // Returns weighted_block_size if weighted_block_size<0, else 0 |
---|
151 | // (this is the "error flag"). |
---|
152 | |
---|
153 | BOOLEAN is_nonnegative() const; |
---|
154 | // Returns TRUE iff all components of the weight vector are >=0. |
---|
155 | // If this is not the case, Buchberger's algorithm will perhaps not |
---|
156 | // terminate using the actual ordering, i.e. the ordering is no |
---|
157 | // well ordering. |
---|
158 | |
---|
159 | BOOLEAN is_positive() const; |
---|
160 | // Returns TRUE ifs all components of the weight vector are >0. |
---|
161 | // If this is not the case, this may lead to problems even if all weights |
---|
162 | // are nonnegative: Zero weights do not give a well ordering in combination |
---|
163 | // with a reverse lexicographical refinement. |
---|
164 | |
---|
165 | // frequently used comparison functions |
---|
166 | |
---|
167 | double weight(const Integer* v) const; |
---|
168 | // Returns the weight of an Integer vector v with respect to weight_vector, |
---|
169 | // i.e. the scalar product of the two vectors. |
---|
170 | // UNCHECKED PRECONDITION: v has weighted_block_size components. |
---|
171 | // The return type is double to avoid overflows. |
---|
172 | |
---|
173 | short compare_to_zero(const Integer* v) const; |
---|
174 | // This function is used to determine a binomials's head with respect to the |
---|
175 | // actual term ordering. The comparison of its two monomials is done |
---|
176 | // according to the binomial data structure: |
---|
177 | // Instead of comparing explicitely two monomials, the Integer vector |
---|
178 | // corresponding to their difference is compared to the zero vector. |
---|
179 | // The function returns |
---|
180 | // 1, if v>0, |
---|
181 | // -1, if v<0, |
---|
182 | // 0, if v=0 |
---|
183 | // UNCHECKED PRECONDITION: |
---|
184 | // v has weighted_block_size + elimination_block_size components |
---|
185 | |
---|
186 | short compare(const binomial& bin1, const binomial& bin2) const; |
---|
187 | // Compares the given binomials by first comparing the heads, then in the |
---|
188 | // case of equality the tails. |
---|
189 | // UNCHECKED PRECONDITION: The exponent vectors of the binomials have |
---|
190 | // already the correct sign, i.e. the positive part of a vector is really |
---|
191 | // its head and not its tail. |
---|
192 | // The function returns |
---|
193 | // -1 if bin1<bin2 |
---|
194 | // 0 if bin1=bin2 |
---|
195 | // 1 if bin1>bin2 |
---|
196 | |
---|
197 | // operators and routines needed by the algorithms to manipulate the term |
---|
198 | // ordering |
---|
199 | |
---|
200 | term_ordering& operator=(const term_ordering&); |
---|
201 | // assignment operator with memory control |
---|
202 | |
---|
203 | float operator[](const short& i) const; |
---|
204 | // Returns weight_vector[i] (FLT_MAX if i is out of range). |
---|
205 | |
---|
206 | term_ordering& convert_to_weighted_ordering(); |
---|
207 | // Sets elimination_block_size to 0. |
---|
208 | |
---|
209 | term_ordering& convert_to_elimination_ordering |
---|
210 | (const short& number_of_elimination_variables, |
---|
211 | const short& _elimination_ordering); |
---|
212 | // Sets elimination_block_size to number_of_elimination_variables |
---|
213 | // and the ordering on the elimination variables as given in the argument. |
---|
214 | |
---|
215 | term_ordering& append_weighted_variable(const float& weight); |
---|
216 | // Appends the given weight to the weight vector (with memory control). |
---|
217 | |
---|
218 | term_ordering& delete_last_weighted_variable(); |
---|
219 | // Deletes the last weighted variable (with memory control). |
---|
220 | |
---|
221 | term_ordering& swap_weights(const short& i, const short& j); |
---|
222 | // This function is used if two weighted variables must change their |
---|
223 | // position (order) with respect to the refining ordering. |
---|
224 | |
---|
225 | // output |
---|
226 | |
---|
227 | void print_weight_vector() const; |
---|
228 | void print() const; |
---|
229 | // Writes the term ordering to the standard output medium |
---|
230 | // (only the weight vector or with supplementary information). |
---|
231 | |
---|
232 | void print_weight_vector(FILE*) const; |
---|
233 | void print(FILE*) const; |
---|
234 | // Writes the term ordering to the referenced file |
---|
235 | // which has to be opened for writing before. |
---|
236 | |
---|
237 | void print_weight_vector(ofstream&) const; |
---|
238 | void print(ofstream&) const; |
---|
239 | // Writes the term ordering to the given ofstream. |
---|
240 | |
---|
241 | void format_print_weight_vector(ofstream&) const; |
---|
242 | // Writes the term ordering to the given ofstream in the format required |
---|
243 | // by the IP-algorithms. |
---|
244 | |
---|
245 | }; |
---|
246 | #endif // TERM_ORDERING_H |
---|