applications/testlib.c

   1 /*
   2     This file is part of PolyLib.
   3
   4     PolyLib is free software: you can redistribute it and/or modify
   5     it under the terms of the GNU General Public License as published by
   6     the Free Software Foundation, either version 3 of the License, or
   7     (at your option) any later version.
   8
   9     PolyLib is distributed in the hope that it will be useful,
  10     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12     GNU General Public License for more details.
  13
  14     You should have received a copy of the GNU General Public License
  15     along with PolyLib.  If not, see <http://www.gnu.org/licenses/>.
  16 */
  17 /* main.c
  18      COPYRIGHT
  19           Both this software and its documentation are
  20
  21               Copyright 1993 by IRISA /Universite de Rennes I - France,
  22               Copyright 1995,1996 by BYU
  23                          all rights reserved.
  24
  25
  26    This file along with polyhedron.c and vector.c do the following functions:
  27     - Extraction of a minimal set of constraints from some set of constraints
  28     - Intersection of two convexes
  29     - Application of a linear function to some convex
  30     - Verification that a convex is included in some other convex
  31
  32    They are compiled together into an executable file called "test".
  33    The file test.in contains sample input data for the program.
  34    The file test.out contains the output produced by the program.
  35
  36    This directory also contains a makefile to build and run the test.
  37
  38    This file is a tutorial on how to use the library.  The comments
  39    explain whats going on.  You can use this file as a pattern for your
  40    own program.  Good Luck !
  41
  42    --Doran
  43 */
  44
  45 #include <stdio.h>
  46
  47 #include <polylib/polylib.h>
  48
  49
  50 int main() {
  51
  52   Matrix *a, *b, *t;
  53   Polyhedron *A, *B, *C, *D;
  54
  55   printf("Polyhedral Library Test\n\n");
  56
  57   /* read in a matrix containing your equations */
  58   /* for example, run this program and type in these five  lines:
  59      4 4
  60      1 0 1 -1
  61      1 -1 0 6
  62      1 0 -1 7
  63      1 1 0 -2
  64      This is a matrix for the following inequalities
  65      1 = inequality,  0x +  1y -1 >=0  -->      y >= 1
  66      1 = inequality, -1x +  0y +6 >=0  -->      x <= 6
  67      1 = inequality,  0x + -1y +7 >=0  -->      y <= 7
  68      1 = inequality,  1x +  0y -2 >=0  -->      x >= 2
  69      If the first number is a 0 instead of a 1, then that constraint
  70      is an 'equality' instead of an 'inequality'.
  71   */
  72   a = Matrix_Read();
  73
  74   /* read in a second matrix containing a second set of constraints:
  75      for example :
  76      4 4
  77      1 1 0 -1
  78      1 -1 0 3
  79      1 0 -1 5
  80      1 0 1 -2
  81   */
  82   b = Matrix_Read();
  83
  84   /* Convert the constraints to a Polyhedron.
  85      This operation 1. Computes the dual ray/vertice form of the
  86      system, and 2. Eliminates redundant constraints and reduces
  87      them to a minimal form.
  88   */
  89   A = Constraints2Polyhedron(a, 200);
  90   B = Constraints2Polyhedron(b, 200);
  91
  92   /* the 200 is the size of the working space (in terms of number
  93      of rays) that is allocated temporarily
  94      -- you can enlarge or reduce it as needed */
  95
  96   /* There is likewise a rays to polyhedron procedure */
  97
  98   /* Since you are done with the matrices a and b, be a good citizen
  99      and clean up your garbage */
 100   Matrix_Free(a);
 101   Matrix_Free(b);
 102
 103   /* If you want the the reduced set of equations back, you can
 104      either learn to read the polyhedron structure (not hard,
 105      look in "types.h"...
 106      or you can get the matrix back in the same format it started
 107      in... */
 108   a = Polyhedron2Constraints(A);
 109   b = Polyhedron2Constraints(B);
 110
 111   /* Take a look at them if you want */
 112   printf("\na =");
 113   Matrix_Print(stdout,P_VALUE_FMT,a);
 114   printf("\nb =");
 115   Matrix_Print(stdout,P_VALUE_FMT,b);
 116
 117   Matrix_Free(a);
 118   Matrix_Free(b);
 119
 120   /* To intersect the two systems, use the polyhedron formats... */
 121   C = DomainIntersection(A, B, 200);
 122
 123   /* Again, the 200 is the size of the working space */
 124
 125   /* This time, lets look a the polyhedron itself... */
 126   printf("\nC = A and B =");
 127   Polyhedron_Print(stdout,P_VALUE_FMT,C);
 128
 129   /*
 130    * The operations DomainUnion, DomainDifference, and DomainConvex
 131    * are also available
 132    */
 133
 134   /*
 135    * Read in a third matrix containing a transformation matrix,
 136    * this one swaps the indices (x,y --> y,x):
 137    * 3 3
 138    * 0 1 0
 139    * 1 0 0
 140    * 0 0 1
 141    */
 142
 143
 144   t = Matrix_Read();
 145
 146   /* Take the preimage (transform the equations) of the domain C to
 147      get D.  Are you catching on to this 200 thing yet ??? */
 148
 149   D = Polyhedron_Preimage(C, t, 200);
 150
 151   /* cleanup please */
 152   Matrix_Free(t);
 153
 154   printf("\nD = transformed C =");
 155   Polyhedron_Print(stdout,P_VALUE_FMT,D);
 156   Domain_Free(D);
 157
 158   /* in a similar way, Polyhedron_Image(dom, mat, 200), takes the image
 159      of dom under matrix mat  (transforms the vertices/rays) */
 160
 161   /* The function PolyhedronIncludes(Pol1, Pol2) returns 1 if Pol1
 162      includes (covers) Pol2, and a 0 otherwise */
 163
 164   if (PolyhedronIncludes(A,C))
 165     printf("\nWe expected A to cover C since C = A intersect B\n");
 166   if (!PolyhedronIncludes(C,B))
 167     printf("and C does not cover B...\n");
 168
 169   /* Final note:  some functions are defined for Domains, others
 170    * for Polyhedrons.  A domain is simply a list of polyhedrons.
 171    * Every polyhedron structure has a "next" pointer used to
 172    * make a list of polyhedrons...  For instance, the union of
 173    * two disjoint polyhedra is a domain consisting of two polyhedra.
 174    * If you want the convex domain... you have to call
 175    * DomainConvex(Pol1, 200) explicity.
 176    * Note that includes does not work on domains, only on simple
 177    * polyhedrons...
 178    * Thats the end of the demo...  write me if you have questions.
 179    * And remember to clean up...
 180    */
 181
 182   Domain_Free(A);
 183   Domain_Free(B);
 184   Domain_Free(C);
 185
 186   return 0;
 187 }
 188
 189