1 <!DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.0 Transitional//EN">
2 <html><head><meta http-equiv=
"Content-Type" content=
"text/html;charset=iso-8859-1">
3 <title>testlib.c Source File
</title>
4 <link href=
"doxygen.css" rel=
"stylesheet" type=
"text/css">
6 <!-- Generated by Doxygen 1.2.15 -->
8 <a class=
"qindex" href=
"main.html">Main Page
</a> <a class=
"qindex" href=
"annotated.html">Compound List
</a> <a class=
"qindex" href=
"files.html">File List
</a> <a class=
"qindex" href=
"functions.html">Compound Members
</a> <a class=
"qindex" href=
"globals.html">File Members
</a> </center>
9 <hr><h1>testlib.c
</h1><a href=
"testlib_8c.html">Go to the documentation of this file.
</a><div class=
"fragment"><pre>00001 <font class=
"comment">/* main.c
</font>
10 00002 <font class=
"comment"> COPYRIGHT
</font>
11 00003 <font class=
"comment"> Both this software and its documentation are
</font>
12 00004 <font class=
"comment"></font>
13 00005 <font class=
"comment"> Copyright
1993 by IRISA /Universite de Rennes I - France,
</font>
14 00006 <font class=
"comment"> Copyright
1995,
1996 by BYU
</font>
15 00007 <font class=
"comment"> all rights reserved.
</font>
16 00008 <font class=
"comment"></font>
17 00009 <font class=
"comment"> Permission is granted to copy, use, and distribute
</font>
18 00010 <font class=
"comment"> for any commercial or noncommercial purpose under the terms
</font>
19 00011 <font class=
"comment"> of the GNU General Public license, version
2, June
1991</font>
20 00012 <font class=
"comment"> (see file : LICENSING).
</font>
21 00013 <font class=
"comment"></font>
22 00014 <font class=
"comment"> This file along with polyhedron.c and vector.c do the following functions:
</font>
23 00015 <font class=
"comment"> - Extraction of a minimal set of constraints from some set of constraints
</font>
24 00016 <font class=
"comment"> - Intersection of two convexes
</font>
25 00017 <font class=
"comment"> - Application of a linear function to some convex
</font>
26 00018 <font class=
"comment"> - Verification that a convex is included in some other convex
</font>
27 00019 <font class=
"comment"></font>
28 00020 <font class=
"comment"> They are compiled together into an executable file called
"test".
</font>
29 00021 <font class=
"comment"> The file test.in contains sample input data for the program.
</font>
30 00022 <font class=
"comment"> The file test.out contains the output produced by the program.
</font>
31 00023 <font class=
"comment"></font>
32 00024 <font class=
"comment"> This directory also contains a makefile to build and run the test.
</font>
33 00025 <font class=
"comment"></font>
34 00026 <font class=
"comment"> This file is a tutorial on how to use the library. The comments
</font>
35 00027 <font class=
"comment"> explain whats going on. You can use this file as a pattern for your
</font>
36 00028 <font class=
"comment"> own program. Good Luck !
</font>
37 00029 <font class=
"comment"></font>
38 00030 <font class=
"comment"> --Doran
</font>
39 00031 <font class=
"comment">*/
</font>
41 00033 <font class=
"preprocessor">#include
<stdio.h
></font>
43 00035 <font class=
"preprocessor">#include
<polylib/polylib.h
></font>
46 <a name=
"l00038"></a><a class=
"code" href=
"testlib_8c.html#a0">00038</a> <font class=
"keywordtype">int
</font> <a class=
"code" href=
"c2p_8c.html#a1">main
</a>() {
48 00040 Matrix *a, *b, *t;
49 00041 Polyhedron *A, *B, *C, *D;
51 00043 printf(
<font class=
"stringliteral">"Polyhedral Library Test\n\n"</font>);
53 00045 <font class=
"comment">/* read in a matrix containing your equations */
</font>
54 00046 <font class=
"comment">/* for example, run this program and type in these five lines:
</font>
55 00047 <font class=
"comment"> 4 4</font>
56 00048 <font class=
"comment"> 1 0 1 -
1</font>
57 00049 <font class=
"comment"> 1 -
1 0 6</font>
58 00050 <font class=
"comment"> 1 0 -
1 7</font>
59 00051 <font class=
"comment"> 1 1 0 -
2</font>
60 00052 <font class=
"comment"> This is a matrix for the following inequalities
</font>
61 00053 <font class=
"comment"> 1 = inequality,
0x +
1y -
1 >=
0 --
> y
>=
1</font>
62 00054 <font class=
"comment"> 1 = inequality, -
1x +
0y +
6 >=
0 --
> x
<=
6</font>
63 00055 <font class=
"comment"> 1 = inequality,
0x + -
1y +
7 >=
0 --
> y
<=
7</font>
64 00056 <font class=
"comment"> 1 = inequality,
1x +
0y -
2 >=
0 --
> x
>=
2</font>
65 00057 <font class=
"comment"> If the first number is a
0 instead of a
1, then that constraint
</font>
66 00058 <font class=
"comment"> is an 'equality' instead of an 'inequality'.
</font>
67 00059 <font class=
"comment"> */
</font>
68 00060 a =
<a class=
"code" href=
"matrix_8c.html#a4">Matrix_Read
</a>();
70 00062 <font class=
"comment">/* read in a second matrix containing a second set of constraints:
</font>
71 00063 <font class=
"comment"> for example :
</font>
72 00064 <font class=
"comment"> 4 4</font>
73 00065 <font class=
"comment"> 1 1 0 -
1</font>
74 00066 <font class=
"comment"> 1 -
1 0 3</font>
75 00067 <font class=
"comment"> 1 0 -
1 5</font>
76 00068 <font class=
"comment"> 1 0 1 -
2</font>
77 00069 <font class=
"comment"> */
</font>
78 00070 b =
<a class=
"code" href=
"matrix_8c.html#a4">Matrix_Read
</a>();
80 00072 <font class=
"comment">/* Convert the constraints to a Polyhedron.
</font>
81 00073 <font class=
"comment"> This operation
1. Computes the dual ray/vertice form of the
</font>
82 00074 <font class=
"comment"> system, and
2. Eliminates redundant constraints and reduces
</font>
83 00075 <font class=
"comment"> them to a minimal form.
</font>
84 00076 <font class=
"comment"> */
</font>
85 00077 A =
<a class=
"code" href=
"polyhedron_8c.html#a24">Constraints2Polyhedron
</a>(a,
200);
86 00078 B =
<a class=
"code" href=
"polyhedron_8c.html#a24">Constraints2Polyhedron
</a>(b,
200);
88 00080 <font class=
"comment">/* the
200 is the size of the working space (in terms of number
</font>
89 00081 <font class=
"comment"> of rays) that is allocated temporarily
</font>
90 00082 <font class=
"comment"> -- you can enlarge or reduce it as needed */
</font>
92 00084 <font class=
"comment">/* There is likewise a rays to polyhedron procedure */
</font>
94 00086 <font class=
"comment">/* Since you are done with the matrices a and b, be a good citizen
</font>
95 00087 <font class=
"comment"> and clean up your garbage */
</font>
96 00088 <a class=
"code" href=
"matrix_8c.html#a1">Matrix_Free
</a>(a);
97 00089 <a class=
"code" href=
"matrix_8c.html#a1">Matrix_Free
</a>(b);
99 00091 <font class=
"comment">/* If you want the the reduced set of equations back, you can
</font>
100 00092 <font class=
"comment"> either learn to read the polyhedron structure (not hard,
</font>
101 00093 <font class=
"comment"> look in
"types.h"...
</font>
102 00094 <font class=
"comment"> or you can get the matrix back in the same format it started
</font>
103 00095 <font class=
"comment"> in... */
</font>
104 00096 a =
<a class=
"code" href=
"polyhedron_8c.html#a25">Polyhedron2Constraints
</a>(A);
105 00097 b =
<a class=
"code" href=
"polyhedron_8c.html#a25">Polyhedron2Constraints
</a>(B);
107 00099 <font class=
"comment">/* Take a look at them if you want */
</font>
108 00100 printf(
<font class=
"stringliteral">"\na ="</font>);
109 00101 <a class=
"code" href=
"matrix_8c.html#a2">Matrix_Print
</a>(stdout,P_VALUE_FMT,a);
110 00102 printf(
<font class=
"stringliteral">"\nb ="</font>);
111 00103 <a class=
"code" href=
"matrix_8c.html#a2">Matrix_Print
</a>(stdout,P_VALUE_FMT,b);
113 00105 <font class=
"comment">/* To intersect the two systems, use the polyhedron formats... */
</font>
114 00106 C =
<a class=
"code" href=
"polyhedron_8c.html#a32">DomainIntersection
</a>(A, B,
200);
116 00108 <font class=
"comment">/* Again, the
200 is the size of the working space */
</font>
118 00110 <font class=
"comment">/* This time, lets look a the polyhedron itself... */
</font>
119 00111 printf(
<font class=
"stringliteral">"\nC = A and B ="</font>);
120 00112 <a class=
"code" href=
"polyhedron_8c.html#a20">Polyhedron_Print
</a>(stdout,P_VALUE_FMT,C);
122 00114 <font class=
"comment">/*
</font>
123 00115 <font class=
"comment"> * The operations DomainUnion, DomainDifference, and DomainConvex
</font>
124 00116 <font class=
"comment"> * are also available
</font>
125 00117 <font class=
"comment"> */
</font>
127 00119 <font class=
"comment">/*
</font>
128 00120 <font class=
"comment"> * Read in a third matrix containing a transformation matrix,
</font>
129 00121 <font class=
"comment"> * this one swaps the indices (x,y --
> y,x):
</font>
130 00122 <font class=
"comment"> *
3 3</font>
131 00123 <font class=
"comment"> *
0 1 0</font>
132 00124 <font class=
"comment"> *
1 0 0</font>
133 00125 <font class=
"comment"> *
0 0 1</font>
134 00126 <font class=
"comment"> */
</font>
137 00129 t =
<a class=
"code" href=
"matrix_8c.html#a4">Matrix_Read
</a>();
139 00131 <font class=
"comment">/* Take the preimage (transform the equations) of the domain C to
</font>
140 00132 <font class=
"comment"> get D. Are you catching on to this
200 thing yet ??? */
</font>
142 00134 D =
<a class=
"code" href=
"polyhedron_8c.html#a50">Polyhedron_Preimage
</a>(C, t,
200);
144 00136 <font class=
"comment">/* cleanup please */
</font>
145 00137 <a class=
"code" href=
"matrix_8c.html#a1">Matrix_Free
</a>(t);
147 00139 printf(
<font class=
"stringliteral">"\nD = transformed C ="</font>);
148 00140 <a class=
"code" href=
"polyhedron_8c.html#a20">Polyhedron_Print
</a>(stdout,P_VALUE_FMT,D);
149 00141 <a class=
"code" href=
"polyhedron_8c.html#a19">Domain_Free
</a>(D);
151 00143 <font class=
"comment">/* in a similar way, Polyhedron_Image(dom, mat,
200), takes the image
</font>
152 00144 <font class=
"comment"> of dom under matrix mat (transforms the vertices/rays) */
</font>
154 00146 <font class=
"comment">/* The function PolyhedronIncludes(Pol1, Pol2) returns
1 if Pol1
</font>
155 00147 <font class=
"comment"> includes (covers) Pol2, and a
0 otherwise */
</font>
157 00149 <font class=
"keywordflow">if
</font> (
<a class=
"code" href=
"polyhedron_8c.html#a29">PolyhedronIncludes
</a>(A,C))
158 00150 printf(
<font class=
"stringliteral">"\nWe expected A to cover C since C = A intersect B\n"</font>);
159 00151 <font class=
"keywordflow">if
</font> (!
<a class=
"code" href=
"polyhedron_8c.html#a29">PolyhedronIncludes
</a>(C,B))
160 00152 printf(
<font class=
"stringliteral">"and C does not cover B...\n"</font>);
162 00154 <font class=
"comment">/* Final note: some functions are defined for Domains, others
</font>
163 00155 <font class=
"comment"> * for Polyhedrons. A domain is simply a list of polyhedrons.
</font>
164 00156 <font class=
"comment"> * Every polyhedron structure has a
"next" pointer used to
</font>
165 00157 <font class=
"comment"> * make a list of polyhedrons... For instance, the union of
</font>
166 00158 <font class=
"comment"> * two disjoint polyhedra is a domain consisting of two polyhedra.
</font>
167 00159 <font class=
"comment"> * If you want the convex domain... you have to call
</font>
168 00160 <font class=
"comment"> * DomainConvex(Pol1,
200) explicity.
</font>
169 00161 <font class=
"comment"> * Note that includes does not work on domains, only on simple
</font>
170 00162 <font class=
"comment"> * polyhedrons...
</font>
171 00163 <font class=
"comment"> * Thats the end of the demo... write me if you have questions.
</font>
172 00164 <font class=
"comment"> * And remember to clean up...
</font>
173 00165 <font class=
"comment"> */
</font>
175 00167 <a class=
"code" href=
"polyhedron_8c.html#a19">Domain_Free
</a>(A);
176 00168 <a class=
"code" href=
"polyhedron_8c.html#a19">Domain_Free
</a>(B);
177 00169 <a class=
"code" href=
"polyhedron_8c.html#a19">Domain_Free
</a>(C);
179 00171 <font class=
"keywordflow">return
</font> 0;
183 </pre></div><hr><address align=
"right"><small>Generated on Fri Nov
8 12:
10:
07 2002 for Polylib by
184 <a href=
"http://www.doxygen.org/index.html">
185 <img src=
"doxygen.png" alt=
"doxygen" align=
"middle" border=
0
186 width=
110 height=
53></a>1.2.15 </small></address>
