Biddy  1.7.1
An academic Binary Decision Diagrams package
biddy-example-independence-usa.c
1 /* $Revision: 148 $ */
2 /* $Date: 2016-03-08 22:03:25 +0100 (tor, 08 mar 2016) $ */
3 /* This file (biddy-example-independence-usa.c) is a C file */
4 /* Author: Robert Meolic (robert.meolic@um.si) */
5 /* This file has been released into the public domain by the author. */
6 
7 /* data are obtained from Donald E. Knuth, http://www-cs-faculty.stanford.edu/~uno/sgb.html */
8 /* direct link: http://www-cs-faculty.stanford.edu/~uno/contiguous-*usa.dat */
9 
10 /* CODES IN ALPHABETICAL ORDER */
11 #define CODES "AL,AR,AZ,CA,CO,CT,DC,DE,FL,GA,IA,ID,IL,IN,KS,KY,LA,MA,MD,ME,MI,MN,MO,MS,MT,NC,ND,NE,NH,NJ,NM,NV,NY,OH,OK,OR,PA,RI,SC,SD,TN,TX,UT,VA,VT,WA,WI,WV,WY"
12 
13 /* THIS LIST MUST BE IN THE SAME (ALPHABETICAL) ORDER */
14 #define AL 0
15 #define AR 1
16 #define AZ 2
17 #define CA 3
18 #define CO 4
19 #define CT 5
20 #define DC 6
21 #define DE 7
22 #define FL 8
23 #define GA 9
24 #define IA 10
25 #define ID 11
26 #define IL 12
27 #define IN 13
28 #define KS 14
29 #define KY 15
30 #define LA 16
31 #define MA 17
32 #define MD 18
33 #define ME 19
34 #define MI 20
35 #define MN 21
36 #define MO 22
37 #define MS 23
38 #define MT 24
39 #define NC 25
40 #define ND 26
41 #define NE 27
42 #define NH 28
43 #define NJ 29
44 #define NM 30
45 #define NV 31
46 #define NY 32
47 #define OH 33
48 #define OK 34
49 #define OR 35
50 #define PA 36
51 #define RI 37
52 #define SC 38
53 #define SD 39
54 #define TN 40
55 #define TX 41
56 #define UT 42
57 #define VA 43
58 #define VT 44
59 #define WA 45
60 #define WI 46
61 #define WV 47
62 #define WY 48
63 
64 # include <stdio.h>
65 # include <stdlib.h>
66 # include <stdint.h>
67 # include <string.h>
68 # include <ctype.h>
69 # include <stdarg.h>
70 
71 void setDataUSA(unsigned int *size, unsigned int ***usa, unsigned int **order, char **codes) {
72 
73  unsigned int i,j;
74 
75  /* initialorder1: ALPHABETICAL ORDER - THERE ARE 306214 NODES (306213 IF USING COMPLEMENT EDGES) IN BDD FOR INDEPENDENCE SETS */
76  /* initialorder2: FROM D.E.KNUTH - THERE ARE 339 NODES (338 IF USING COMPLEMENT EDGES) IN BDD FOR INDEPENDENCE SETS */
77  /* initialorder3: THE BEST OBTAINED FROM initialorder1 BY BIDDY USING REPEATED SIFTING ON SYSTEM - THERE ARE 860 NODES (859 IF USING COMPLEMENT EDGES) IN BDD FOR INDEPENDENCE SETS */
78  /* initialorder4: THE BEST OBTAINED FROM initialorder1 BY BIDDY USING REPEATED SIFTING ON FUNCTION - THERE ARE 859 NODES (858 IF USING COMPLEMENT EDGES) IN BDD FOR INDEPENDENCE SETS */
79  /* initialorder5: THE BEST OBTAINED FROM initialorder1 BY CUDD USING REPEATED SIFTING ON SYSTEM - THERE ARE 521 NODES (USING COMPLEMENT EDGES) IN BDD FOR INDEPENDENCE SETS */
80 
81  unsigned int initialorder1[] = {AL,AR,AZ,CA,CO,CT,DC,DE,FL,GA,IA,ID,IL,IN,KS,KY,LA,MA,MD,ME,MI,MN,MO,MS,MT,NC,ND,NE,NH,NJ,NM,NV,NY,OH,OK,OR,PA,RI,SC,SD,TN,TX,UT,VA,VT,WA,WI,WV,WY};
82  unsigned int initialorder2[] = {OR,ID,NV,WA,AZ,CA,UT,NM,WY,CO,MT,SD,MN,ND,IA,NE,OK,KS,TX,MO,LA,AR,MS,WI,KY,MI,IN,IL,AL,TN,FL,NC,SC,GA,WV,OH,MD,DC,VA,PA,NJ,DE,NY,CT,RI,NH,ME,VT,MA};
83  unsigned int initialorder3[] = {AL,GA,FL,TN,NC,SC,VA,MS,AR,TX,LA,OK,KY,NM,MO,NE,KS,CO,IA,IL,WI,MI,IN,SD,MN,MT,ND,UT,WY,OH,PA,WV,DC,NJ,MD,DE,NY,VT,NH,ME,RI,CT,MA,NV,ID,WA,CA,AZ,OR};
84  unsigned int initialorder4[] = {AL,GA,FL,TN,NC,SC,VA,MS,AR,TX,LA,OK,KY,NM,MO,NE,KS,CO,IA,IL,WI,MI,IN,SD,MN,MT,ND,UT,WY,OH,PA,WV,DC,NJ,MD,DE,NY,VT,NH,ME,RI,CT,MA,ID,CA,AZ,OR,WA,NV};
85  unsigned int initialorder5[] = {GA,AL,FL,TN,NC,SC,MS,VA,AR,TX,LA,OK,NM,NE,KS,CO,AZ,UT,ID,CA,OR,WA,NV,WY,SD,IA,ND,MT,MN,IL,MO,KY,MI,WI,IN,WV,DC,PA,OH,MD,NJ,DE,NY,RI,CT,NH,ME,VT,MA};
86 
87  *size = 49;
88 
89  /* THIS LIST MUST BE IN ALPHABETICAL ORDER */
90  *codes = strdup(CODES);
91 
92  *order = (unsigned int *) malloc((*size)*sizeof(unsigned int));
93  for (i=0; i<(*size); i++) {
94  (*order)[i] = initialorder1[i];
95  }
96 
97  *usa = (unsigned int **) malloc((*size)*sizeof(unsigned int *));
98  for (i=0; i<(*size); i++) {
99  (*usa)[i] = (unsigned int *) malloc((*size)*sizeof(unsigned int));
100  }
101 
102  for (i=0; i<(*size); i++) {
103  for (j=0; j<(*size); j++) {
104  (*usa)[i][j] = 0;
105  }
106  }
107 
108  (*usa)[AL][FL]=1;
109  (*usa)[AL][GA]=1;
110  (*usa)[AL][MS]=1;
111  (*usa)[AL][TN]=1;
112  (*usa)[AR][LA]=1;
113  (*usa)[AR][MO]=1;
114  (*usa)[AR][MS]=1;
115  (*usa)[AR][OK]=1;
116  (*usa)[AR][TN]=1;
117  (*usa)[AR][TX]=1;
118  (*usa)[AZ][CA]=1;
119  (*usa)[AZ][NM]=1;
120  (*usa)[AZ][NV]=1;
121  (*usa)[AZ][UT]=1;
122  (*usa)[CA][NV]=1;
123  (*usa)[CA][OR]=1;
124  (*usa)[CO][KS]=1;
125  (*usa)[CO][NE]=1;
126  (*usa)[CO][NM]=1;
127  (*usa)[CO][OK]=1;
128  (*usa)[CO][UT]=1;
129  (*usa)[CO][WY]=1;
130  (*usa)[CT][MA]=1;
131  (*usa)[CT][NY]=1;
132  (*usa)[CT][RI]=1;
133  (*usa)[DC][MD]=1;
134  (*usa)[DC][VA]=1;
135  (*usa)[DE][MD]=1;
136  (*usa)[DE][NJ]=1;
137  (*usa)[DE][PA]=1;
138  (*usa)[FL][GA]=1;
139  (*usa)[GA][NC]=1;
140  (*usa)[GA][SC]=1;
141  (*usa)[GA][TN]=1;
142  (*usa)[IA][IL]=1;
143  (*usa)[IA][MN]=1;
144  (*usa)[IA][MO]=1;
145  (*usa)[IA][NE]=1;
146  (*usa)[IA][SD]=1;
147  (*usa)[IA][WI]=1;
148  (*usa)[ID][MT]=1;
149  (*usa)[ID][NV]=1;
150  (*usa)[ID][OR]=1;
151  (*usa)[ID][UT]=1;
152  (*usa)[ID][WA]=1;
153  (*usa)[ID][WY]=1;
154  (*usa)[IL][IN]=1;
155  (*usa)[IL][KY]=1;
156  (*usa)[IL][MO]=1;
157  (*usa)[IL][WI]=1;
158  (*usa)[IN][KY]=1;
159  (*usa)[IN][MI]=1;
160  (*usa)[IN][OH]=1;
161  (*usa)[KS][MO]=1;
162  (*usa)[KS][NE]=1;
163  (*usa)[KS][OK]=1;
164  (*usa)[KY][MO]=1;
165  (*usa)[KY][OH]=1;
166  (*usa)[KY][TN]=1;
167  (*usa)[KY][VA]=1;
168  (*usa)[KY][WV]=1;
169  (*usa)[LA][MS]=1;
170  (*usa)[LA][TX]=1;
171  (*usa)[MA][NH]=1;
172  (*usa)[MA][NY]=1;
173  (*usa)[MA][RI]=1;
174  (*usa)[MA][VT]=1;
175  (*usa)[MD][PA]=1;
176  (*usa)[MD][VA]=1;
177  (*usa)[MD][WV]=1;
178  (*usa)[ME][NH]=1;
179  (*usa)[MI][OH]=1;
180  (*usa)[MI][WI]=1;
181  (*usa)[MN][ND]=1;
182  (*usa)[MN][SD]=1;
183  (*usa)[MN][WI]=1;
184  (*usa)[MO][NE]=1;
185  (*usa)[MO][OK]=1;
186  (*usa)[MO][TN]=1;
187  (*usa)[MS][TN]=1;
188  (*usa)[MT][ND]=1;
189  (*usa)[MT][SD]=1;
190  (*usa)[MT][WY]=1;
191  (*usa)[NC][SC]=1;
192  (*usa)[NC][TN]=1;
193  (*usa)[NC][VA]=1;
194  (*usa)[ND][SD]=1;
195  (*usa)[NE][SD]=1;
196  (*usa)[NE][WY]=1;
197  (*usa)[NH][VT]=1;
198  (*usa)[NJ][NY]=1;
199  (*usa)[NJ][PA]=1;
200  (*usa)[NM][OK]=1;
201  (*usa)[NM][TX]=1;
202  (*usa)[NV][OR]=1;
203  (*usa)[NV][UT]=1;
204  (*usa)[NY][PA]=1;
205  (*usa)[NY][VT]=1;
206  (*usa)[OH][PA]=1;
207  (*usa)[OH][WV]=1;
208  (*usa)[OK][TX]=1;
209  (*usa)[OR][WA]=1;
210  (*usa)[PA][WV]=1;
211  (*usa)[SD][WY]=1;
212  (*usa)[TN][VA]=1;
213  (*usa)[UT][WY]=1;
214  (*usa)[VA][WV]=1;
215 
216  for (i=0; i<(*size); i++) {
217  for (j=0; j<(*size); j++) {
218  if ((*usa)[j][i]) (*usa)[i][j]=1;
219  }
220  }
221 
222 }