1 | /* |
---|
2 | * lib_cone.h |
---|
3 | * |
---|
4 | * Created on: Sep 28, 2010 |
---|
5 | * Author: anders |
---|
6 | */ |
---|
7 | |
---|
8 | #ifndef LIB_CONE_H_ |
---|
9 | #define LIB_CONE_H_ |
---|
10 | |
---|
11 | #include "../factory/globaldefs.h" |
---|
12 | #include "gfanlib_matrix.h" |
---|
13 | |
---|
14 | namespace gfan{ |
---|
15 | /** |
---|
16 | * Returns true if cddlib is needed for the ZCone implementation. |
---|
17 | */ |
---|
18 | bool isCddlibRequired(); |
---|
19 | /** |
---|
20 | * Only call this function if gfanlib is the only code in your program using cddlib. |
---|
21 | * Should be paired with a deinitializeCddlibIfRequired() call. |
---|
22 | * Calling the function repeatedly may cause memory leaks even if deinitializeCddlibIfRequired() is also called. |
---|
23 | */ |
---|
24 | void initializeCddlibIfRequired(); |
---|
25 | /** |
---|
26 | * This function may do nothing. |
---|
27 | */ |
---|
28 | void deinitializeCddlibIfRequired(); |
---|
29 | |
---|
30 | /** |
---|
31 | A PolyhedralCone is represented by linear inequalities and equations. The inequalities are non-strict |
---|
32 | and stored as the rows of a matrix and the equations are stored as rows of a second matrix. |
---|
33 | |
---|
34 | A cone can be in one of the four states: |
---|
35 | 0) Nothing has been done to remove redundancies. This is the initial state. |
---|
36 | 1) A basis for the true, implied equations space has been computed. This means that |
---|
37 | the implied equations have been computed. In particular the dimension of the cone is known. |
---|
38 | 2) Redundant inequalities have been computed and have been eliminated. |
---|
39 | This means that the true set of facets is known - one for each element in halfSpaces. |
---|
40 | 3) The inequalities and equations from 2) have been transformed into a canonical form. Besides having |
---|
41 | a unique representation for the cone this also allows comparisons between cones with operator<(). |
---|
42 | |
---|
43 | Since moving for one state to the next is expensive, the user of the PolyhedralCone can specify flags |
---|
44 | at the construction of the cone informing about which things are known. |
---|
45 | |
---|
46 | PCP_impliedEquationsKnown means that the given set of equations generate the space of implied equations. |
---|
47 | PCP_facetsKnown means that each inequalities describe define a (different) facet of the cone. |
---|
48 | |
---|
49 | Each cone has the additional information: multiplicity and linear forms. |
---|
50 | The multiplicity is an integer whose default value is one. It can be set by the user. |
---|
51 | When a cone is projected, it can happen that the multiplicity changes according to a lattice index. |
---|
52 | The linear forms are stored in a matrix linearForms, whose width equals the dimension of the ambient space. |
---|
53 | The idea is that a collection of cones in this way can represent a piecewise linear function (a tropical rational function). |
---|
54 | |
---|
55 | Caching: |
---|
56 | When new properties are computed by changing state the information is stored in the object by updating equations and inequalities. |
---|
57 | When some other properties are computed, such as rays the result is cached in the object. Each cached property has a corresponding flag telling if a cached value has been stored. |
---|
58 | These methods |
---|
59 | for these properties are considered const. Caching only works for extreme rays at the moment. |
---|
60 | |
---|
61 | Notice: |
---|
62 | The lineality space of a cone C is C\cap(-C). |
---|
63 | A cone is ray if its dimension is 1+the dimension of the its lineality space. |
---|
64 | |
---|
65 | Should the user of this class know about the states? |
---|
66 | |
---|
67 | need to think about this... |
---|
68 | Always putting the cone in state 1 after something has changed helps a lot. |
---|
69 | Then all operations can be performed except comparing and getting facets with |
---|
70 | out taking the cone to a special state. |
---|
71 | |
---|
72 | |
---|
73 | Things to change: |
---|
74 | - Thomas wants operations where the natural description is the dual to be fast. |
---|
75 | One way to achieve this is as Frank suggests to have a state -1, in which only |
---|
76 | the generator description is known. These should be stored in the cache. If it |
---|
77 | is required to move to state 0, then the inequality description is computed. |
---|
78 | This sounds like a reasonable solution, but of course, what we are really storing is the dual. |
---|
79 | |
---|
80 | - Basically all data in the object should be mutable, while almost every method should be const. |
---|
81 | |
---|
82 | - A method should set the cone in a given state if required. The reason for this is that |
---|
83 | it will be difficult for the user to figure out which state is required and therefore |
---|
84 | will tend to call canonicalize when not needed. |
---|
85 | |
---|
86 | - Cache should be added for more properties. |
---|
87 | |
---|
88 | Optimization: |
---|
89 | - When inequalities can be represented in 32 bit some optimizations can be done. |
---|
90 | |
---|
91 | More things to consider: |
---|
92 | - Does it make sense to do dimension reduction when lineality space / linear span has been |
---|
93 | computed? |
---|
94 | |
---|
95 | |
---|
96 | When calling generated by rays, two flags should be passed. |
---|
97 | |
---|
98 | */ |
---|
99 | |
---|
100 | enum PolyhedralConePreassumptions{ |
---|
101 | PCP_none=0, |
---|
102 | PCP_impliedEquationsKnown=1, |
---|
103 | PCP_facetsKnown=2 |
---|
104 | }; |
---|
105 | |
---|
106 | class ZCone; |
---|
107 | ZCone intersection(const ZCone &a, const ZCone &b); |
---|
108 | class ZCone |
---|
109 | { |
---|
110 | int preassumptions; |
---|
111 | mutable int state; |
---|
112 | int n; |
---|
113 | Integer multiplicity; |
---|
114 | ZMatrix linearForms; |
---|
115 | mutable ZMatrix inequalities; |
---|
116 | mutable ZMatrix equations; |
---|
117 | mutable ZMatrix cachedExtremeRays; |
---|
118 | /** |
---|
119 | * If this bool is true it means that cachedExtremeRays contains the extreme rays as found by extremeRays(). |
---|
120 | */ |
---|
121 | mutable bool haveExtremeRaysBeenCached; |
---|
122 | void ensureStateAsMinimum(int s)const; |
---|
123 | |
---|
124 | bool isInStateMinimum(int s)const; |
---|
125 | int getState()const; |
---|
126 | public: |
---|
127 | /** |
---|
128 | * Constructs a polyhedral cone with specified equations and inequalities. They are read off as rows |
---|
129 | * of the matrices. For efficiency it is possible to specify a PolyhedralConePreassumptions flag |
---|
130 | * which tells what is known about the description already. |
---|
131 | */ |
---|
132 | ZCone(ZMatrix const &inequalities_, ZMatrix const &equations_, int preassumptions_=PCP_none); |
---|
133 | |
---|
134 | /** |
---|
135 | * Get the multiplicity of the cone. |
---|
136 | */ |
---|
137 | Integer getMultiplicity()const; |
---|
138 | /** |
---|
139 | * Set the multiplicity of the cone. |
---|
140 | */ |
---|
141 | void setMultiplicity(Integer const &m); |
---|
142 | /** |
---|
143 | * Returns the matrix of linear forms stored in the cone object. |
---|
144 | */ |
---|
145 | ZMatrix getLinearForms()const; |
---|
146 | /** |
---|
147 | * Store a matrix of linear forms in the cone object. |
---|
148 | */ |
---|
149 | void setLinearForms(ZMatrix const &linearForms_); |
---|
150 | |
---|
151 | /** |
---|
152 | * Get the inequalities in the description of the cone. |
---|
153 | */ |
---|
154 | ZMatrix getInequalities()const; |
---|
155 | /** |
---|
156 | * Get the equations in the description of the cone. |
---|
157 | */ |
---|
158 | ZMatrix getEquations()const; |
---|
159 | /** |
---|
160 | * Compute generators of the span of the cone. They are stored as rows of the returned matrix. |
---|
161 | */ |
---|
162 | ZMatrix generatorsOfSpan()const; |
---|
163 | /** |
---|
164 | * Compute generators of the lineality space of the cone. The returned set of generators is a vector spaces basis. They are stored as rows of the returned matrix. |
---|
165 | */ |
---|
166 | ZMatrix generatorsOfLinealitySpace()const; |
---|
167 | /** |
---|
168 | * Returns true iff it is known that every inequalities in the description defines a different facets of the cone. |
---|
169 | */ |
---|
170 | bool areFacetsKnown()const{return (state>=2)||(preassumptions&PCP_facetsKnown);} |
---|
171 | /** |
---|
172 | * Returns true iff it is known that the set of equations span the space of implied equations of the description. |
---|
173 | */ |
---|
174 | bool areImpliedEquationsKnown()const{return (state>=1)||(preassumptions&PCP_impliedEquationsKnown);} |
---|
175 | /** |
---|
176 | * Returns true iff the extreme rays are known. |
---|
177 | */ |
---|
178 | bool areExtremeRaysKnown()const{return haveExtremeRaysBeenCached;} |
---|
179 | |
---|
180 | /** |
---|
181 | * Takes the cone to a canonical form. After taking cones to canonical form, two cones are the same |
---|
182 | * if and only if their matrices of equations and inequalities are the same. |
---|
183 | */ |
---|
184 | void canonicalize(); |
---|
185 | /** |
---|
186 | * Computes and returns the facet inequalities of the cone. |
---|
187 | */ |
---|
188 | ZMatrix getFacets()const; |
---|
189 | /** |
---|
190 | * After this function has been called all inequalities describe different facets of the cone. |
---|
191 | */ |
---|
192 | void findFacets(); |
---|
193 | /** |
---|
194 | * The set of linear forms vanishing on the cone is a subspace. This routine returns a basis |
---|
195 | * of this subspace as the rows of a matrix. |
---|
196 | */ |
---|
197 | ZMatrix getImpliedEquations()const; |
---|
198 | /** |
---|
199 | * After this function has been called a minimal set of implied equations for the cone is known and is |
---|
200 | * returned when calling getEquations(). The returned equations form a basis of the space of implied |
---|
201 | * equations. |
---|
202 | */ |
---|
203 | void findImpliedEquations(); |
---|
204 | |
---|
205 | /** |
---|
206 | * Constructor for polyhedral cone with no inequalities or equations. Tthat is, the full space of some dimension. |
---|
207 | */ |
---|
208 | ZCone(int ambientDimension=0); |
---|
209 | |
---|
210 | /** |
---|
211 | * Computes are relative interior point of the cone. |
---|
212 | */ |
---|
213 | ZVector getRelativeInteriorPoint()const; |
---|
214 | /** |
---|
215 | Assuming that this cone C is in state at least 3 (why not 2?), this routine returns a relative interior point v(C) of C with the following properties: |
---|
216 | 1) v is a function, that is v(C) is found deterministically |
---|
217 | 2) for any angle preserving, lattice preserving and lineality space preserving transformation T of R^n we have that v(T(C))=T(v(C)). This makes it easy to check if two cones in the same fan are equal up to symmetry. Here preserving the lineality space L just means T(L)=L. |
---|
218 | */ |
---|
219 | ZVector getUniquePoint()const; |
---|
220 | /** |
---|
221 | * Takes a list of possible extreme rays and add up those actually contained in the cone. |
---|
222 | */ |
---|
223 | ZVector getUniquePointFromExtremeRays(ZMatrix const &extremeRays)const; |
---|
224 | /** |
---|
225 | * Returns the dimension of the ambient space. |
---|
226 | */ |
---|
227 | int ambientDimension()const; |
---|
228 | /** |
---|
229 | * Returns the dimension of the cone. |
---|
230 | */ |
---|
231 | int dimension()const; |
---|
232 | /** |
---|
233 | * Returns (ambient dimension)-(dimension). |
---|
234 | */ |
---|
235 | int codimension()const; |
---|
236 | /** |
---|
237 | * Returns the dimension of the lineality space of the cone. |
---|
238 | */ |
---|
239 | int dimensionOfLinealitySpace()const; |
---|
240 | /** |
---|
241 | * Returns true iff the cone is the origin. |
---|
242 | */ |
---|
243 | bool isOrigin()const; |
---|
244 | /** |
---|
245 | * Returns true iff the cone is the full space. |
---|
246 | */ |
---|
247 | bool isFullSpace()const; |
---|
248 | |
---|
249 | /** |
---|
250 | * Returns the intersection of cone a and b as a cone object. |
---|
251 | */ |
---|
252 | friend ZCone intersection(const ZCone &a, const ZCone &b); |
---|
253 | /** |
---|
254 | * Returns the Cartesian product of the two cones a and b. |
---|
255 | */ |
---|
256 | friend ZCone product(const ZCone &a, const ZCone &b); |
---|
257 | /** |
---|
258 | * Returns the positive orthant of some dimension as a polyhedral cone. |
---|
259 | */ |
---|
260 | static ZCone positiveOrthant(int dimension); |
---|
261 | /** |
---|
262 | * Returns the cone which is the sum of row span of linealitySpace and |
---|
263 | * the non-negative span of the rows of generators. |
---|
264 | */ |
---|
265 | static ZCone givenByRays(ZMatrix const &generators, ZMatrix const &linealitySpace); |
---|
266 | |
---|
267 | /** |
---|
268 | * To use the comparison operator< the cones must have been canonicalized. |
---|
269 | */ |
---|
270 | friend bool operator<(ZCone const &a, ZCone const &b); |
---|
271 | /** |
---|
272 | * To use the comparison operator!= the cones must have been canonicalized. |
---|
273 | */ |
---|
274 | friend bool operator!=(ZCone const &a, ZCone const &b); |
---|
275 | |
---|
276 | /** |
---|
277 | * Returns true iff the cone contains a positive vector. |
---|
278 | */ |
---|
279 | bool containsPositiveVector()const; |
---|
280 | /** |
---|
281 | * Returns true iff the cone contains the specified vector v. |
---|
282 | */ |
---|
283 | bool contains(ZVector const &v)const; |
---|
284 | /** |
---|
285 | * Returns true iff the cone contains all rows of the matrix l. |
---|
286 | */ |
---|
287 | bool containsRowsOf(ZMatrix const &l)const; |
---|
288 | /** |
---|
289 | * Returns true iff c is contained in the cone. |
---|
290 | */ |
---|
291 | bool contains(ZCone const &c)const; |
---|
292 | /** |
---|
293 | * Returns true iff the PolyhedralCone contains v in its relative interior. False otherwise. The cone must be in state at least 1. |
---|
294 | */ |
---|
295 | bool containsRelatively(ZVector const &v)const; |
---|
296 | /* |
---|
297 | * Returns true iff the cone is simplicial. That is, iff the dimension of the cone equals the number of facets. |
---|
298 | */ |
---|
299 | bool isSimplicial()const; |
---|
300 | |
---|
301 | //PolyhedralCone permuted(IntegerVector const &v)const; |
---|
302 | |
---|
303 | /** |
---|
304 | * Returns the lineality space of the cone as a polyhedral cone. |
---|
305 | */ |
---|
306 | ZCone linealitySpace()const; |
---|
307 | |
---|
308 | /** |
---|
309 | * Returns the dual cone of the cone. |
---|
310 | */ |
---|
311 | ZCone dualCone()const; |
---|
312 | /** |
---|
313 | * Return -C, where C is the cone. |
---|
314 | */ |
---|
315 | ZCone negated()const; |
---|
316 | /** |
---|
317 | * Compute the extreme rays of the cone, and return generators of these as the rows of a matrix. |
---|
318 | * The returned extreme rays are represented by vectors which are orthogonal to the lineality |
---|
319 | * space and which are primitive primitive. |
---|
320 | * This makes them unique and invariant under lattice and angle preserving linear transformations |
---|
321 | * in the sense that a transformed cone would give the same set of extreme rays except the |
---|
322 | * extreme rays have been transformed. |
---|
323 | * If generators for the lineality space are known, they can be supplied. This can |
---|
324 | * speed up computations a lot. |
---|
325 | */ |
---|
326 | ZMatrix extremeRays(ZMatrix const *generatorsOfLinealitySpace=0)const; |
---|
327 | /** |
---|
328 | The cone defines two lattices, namely Z^n intersected with the |
---|
329 | span of the cone and Z^n intersected with the lineality space of |
---|
330 | the cone. Clearly the second is contained in the |
---|
331 | first. Furthermore, the second is a saturated lattice of the |
---|
332 | first. The quotient is torsion-free - hence a lattice. Generators |
---|
333 | of this lattice as vectors in the span of the cone are computed |
---|
334 | by this routine. The implied equations must be known when this |
---|
335 | function is called - if not the routine asserts. |
---|
336 | */ |
---|
337 | ZMatrix quotientLatticeBasis()const; |
---|
338 | /** |
---|
339 | For a ray (dim=linealitydim +1) |
---|
340 | the quotent lattice described in quotientLatticeBasis() is |
---|
341 | isomorphic to Z. In fact the ray intersected with Z^n modulo the |
---|
342 | lineality space intersected with Z^n is a semigroup generated by |
---|
343 | just one element. This routine computes that element as an |
---|
344 | integer vector in the cone. Asserts if the cone is not a ray. |
---|
345 | Asserts if the implied equations have not been computed. |
---|
346 | */ |
---|
347 | ZVector semiGroupGeneratorOfRay()const; |
---|
348 | |
---|
349 | /** |
---|
350 | Computes the link of the face containing v in its relative |
---|
351 | interior. |
---|
352 | */ |
---|
353 | ZCone link(ZVector const &w)const; |
---|
354 | |
---|
355 | /** |
---|
356 | Tests if f is a face of the cone. |
---|
357 | */ |
---|
358 | bool hasFace(ZCone const &f)const; |
---|
359 | /** |
---|
360 | Computes the face of the cone containing v in its relative interior. |
---|
361 | The vector MUST be contained in the cone. |
---|
362 | */ |
---|
363 | ZCone faceContaining(ZVector const &v)const; |
---|
364 | /** |
---|
365 | * Computes the projection of the cone to the first newn coordinates. |
---|
366 | * The ambient space of the returned cone has dimension newn. |
---|
367 | */ |
---|
368 | // PolyhedralCone projection(int newn)const; |
---|
369 | friend std::ostream &operator<<(std::ostream &f, ZCone const &c); |
---|
370 | std::string toString()const; |
---|
371 | }; |
---|
372 | |
---|
373 | } |
---|
374 | |
---|
375 | |
---|
376 | |
---|
377 | |
---|
378 | #endif /* LIB_CONE_H_ */ |
---|