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