1 /**CFile***********************************************************************
2
3 FileName [cuddHarwell.c]
4
5 PackageName [cudd]
6
7 Synopsis [Function to read a matrix in Harwell format.]
8
9 Description [External procedures included in this module:
10 <ul>
11 <li> Cudd_addHarwell()
12 </ul>
13 ]
14
15 Author [Fabio Somenzi]
16
17 Copyright [Copyright (c) 1995-2004, Regents of the University of Colorado
18
19 All rights reserved.
20
21 Redistribution and use in source and binary forms, with or without
22 modification, are permitted provided that the following conditions
23 are met:
24
25 Redistributions of source code must retain the above copyright
26 notice, this list of conditions and the following disclaimer.
27
28 Redistributions in binary form must reproduce the above copyright
29 notice, this list of conditions and the following disclaimer in the
30 documentation and/or other materials provided with the distribution.
31
32 Neither the name of the University of Colorado nor the names of its
33 contributors may be used to endorse or promote products derived from
34 this software without specific prior written permission.
35
36 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
37 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
38 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
39 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
40 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
41 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
42 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
44 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
45 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
46 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
47 POSSIBILITY OF SUCH DAMAGE.]
48
49 ******************************************************************************/
50
51 #include "misc/util/util_hack.h"
52 #include "cuddInt.h"
53
54 ABC_NAMESPACE_IMPL_START
55
56
57
58 /*---------------------------------------------------------------------------*/
59 /* Constant declarations */
60 /*---------------------------------------------------------------------------*/
61
62
63 /*---------------------------------------------------------------------------*/
64 /* Stucture declarations */
65 /*---------------------------------------------------------------------------*/
66
67
68 /*---------------------------------------------------------------------------*/
69 /* Type declarations */
70 /*---------------------------------------------------------------------------*/
71
72
73 /*---------------------------------------------------------------------------*/
74 /* Variable declarations */
75 /*---------------------------------------------------------------------------*/
76
77 #ifndef lint
78 static char rcsid[] DD_UNUSED = "$Id: cuddHarwell.c,v 1.9 2004/08/13 18:04:49 fabio Exp $";
79 #endif
80
81 /*---------------------------------------------------------------------------*/
82 /* Macro declarations */
83 /*---------------------------------------------------------------------------*/
84
85
86 /**AutomaticStart*************************************************************/
87
88 /*---------------------------------------------------------------------------*/
89 /* Static function prototypes */
90 /*---------------------------------------------------------------------------*/
91
92
93 /**AutomaticEnd***************************************************************/
94
95
96 /*---------------------------------------------------------------------------*/
97 /* Definition of exported functions */
98 /*---------------------------------------------------------------------------*/
99
100 /**Function********************************************************************
101
102 Synopsis [Reads in a matrix in the format of the Harwell-Boeing
103 benchmark suite.]
104
105 Description [Reads in a matrix in the format of the Harwell-Boeing
106 benchmark suite. The variables are ordered as follows:
107 <blockquote>
108 x\[0\] y\[0\] x\[1\] y\[1\] ...
109 </blockquote>
110 0 is the most significant bit. On input, nx and ny hold the numbers
111 of row and column variables already in existence. On output, they
112 hold the numbers of row and column variables actually used by the
113 matrix. m and n are set to the numbers of rows and columns of the
114 matrix. Their values on input are immaterial. Returns 1 on
115 success; 0 otherwise. The ADD for the sparse matrix is returned in
116 E, and its reference count is > 0.]
117
118 SideEffects [None]
119
120 SeeAlso [Cudd_addRead Cudd_bddRead]
121
122 ******************************************************************************/
123 int
Cudd_addHarwell(FILE * fp,DdManager * dd,DdNode ** E,DdNode *** x,DdNode *** y,DdNode *** xn,DdNode *** yn_,int * nx,int * ny,int * m,int * n,int bx,int sx,int by,int sy,int pr)124 Cudd_addHarwell(
125 FILE * fp /* pointer to the input file */,
126 DdManager * dd /* DD manager */,
127 DdNode ** E /* characteristic function of the graph */,
128 DdNode *** x /* array of row variables */,
129 DdNode *** y /* array of column variables */,
130 DdNode *** xn /* array of complemented row variables */,
131 DdNode *** yn_ /* array of complemented column variables */,
132 int * nx /* number or row variables */,
133 int * ny /* number or column variables */,
134 int * m /* number of rows */,
135 int * n /* number of columns */,
136 int bx /* first index of row variables */,
137 int sx /* step of row variables */,
138 int by /* first index of column variables */,
139 int sy /* step of column variables */,
140 int pr /* verbosity level */)
141 {
142 DdNode *one, *zero;
143 DdNode *w;
144 DdNode *cubex, *cubey, *minterm1;
145 int u, v, err, i, j, nv;
146 double val;
147 DdNode **lx = NULL, **ly = NULL, **lxn = NULL, **lyn = NULL; /* local copies of x, y, xn, yn_ */
148 int lnx, lny; /* local copies of nx and ny */
149 char title[73], key[9], mxtype[4], rhstyp[4];
150 int totcrd, ptrcrd, indcrd, valcrd, rhscrd,
151 nrow, ncol, nnzero, neltvl,
152 nrhs, nrhsix;
153 int *colptr, *rowind;
154 #if 0
155 int nguess, nexact;
156 int *rhsptr, *rhsind;
157 #endif
158
159 if (*nx < 0 || *ny < 0) return(0);
160
161 one = DD_ONE(dd);
162 zero = DD_ZERO(dd);
163
164 /* Read the header */
165 err = fscanf(fp, "%72c %8c", title, key);
166 if (err == EOF) {
167 return(0);
168 } else if (err != 2) {
169 return(0);
170 }
171 title[72] = (char) 0;
172 key[8] = (char) 0;
173
174 err = fscanf(fp, "%d %d %d %d %d", &totcrd, &ptrcrd, &indcrd,
175 &valcrd, &rhscrd);
176 if (err == EOF) {
177 return(0);
178 } else if (err != 5) {
179 return(0);
180 }
181
182 err = fscanf(fp, "%3s %d %d %d %d", mxtype, &nrow, &ncol,
183 &nnzero, &neltvl);
184 if (err == EOF) {
185 return(0);
186 } else if (err != 5) {
187 return(0);
188 }
189
190 /* Skip FORTRAN formats */
191 if (rhscrd == 0) {
192 err = fscanf(fp, "%*s %*s %*s \n");
193 } else {
194 err = fscanf(fp, "%*s %*s %*s %*s \n");
195 }
196 if (err == EOF) {
197 return(0);
198 } else if (err != 0) {
199 return(0);
200 }
201
202 /* Print out some stuff if requested to be verbose */
203 if (pr>0) {
204 (void) fprintf(dd->out,"%s: type %s, %d rows, %d columns, %d entries\n", key,
205 mxtype, nrow, ncol, nnzero);
206 if (pr>1) (void) fprintf(dd->out,"%s\n", title);
207 }
208
209 /* Check matrix type */
210 if (mxtype[0] != 'R' || mxtype[1] != 'U' || mxtype[2] != 'A') {
211 (void) fprintf(dd->err,"%s: Illegal matrix type: %s\n",
212 key, mxtype);
213 return(0);
214 }
215 if (neltvl != 0) return(0);
216
217 /* Read optional 5-th line */
218 if (rhscrd != 0) {
219 err = fscanf(fp, "%3c %d %d", rhstyp, &nrhs, &nrhsix);
220 if (err == EOF) {
221 return(0);
222 } else if (err != 3) {
223 return(0);
224 }
225 rhstyp[3] = (char) 0;
226 if (rhstyp[0] != 'F') {
227 (void) fprintf(dd->err,
228 "%s: Sparse right-hand side not yet supported\n", key);
229 return(0);
230 }
231 if (pr>0) (void) fprintf(dd->out,"%d right-hand side(s)\n", nrhs);
232 } else {
233 nrhs = 0;
234 }
235
236 /* Compute the number of variables */
237
238 /* row and column numbers start from 0 */
239 u = nrow - 1;
240 for (i=0; u > 0; i++) {
241 u >>= 1;
242 }
243 lnx = i;
244 if (nrhs == 0) {
245 v = ncol - 1;
246 } else {
247 v = 2* (ddMax(ncol, nrhs) - 1);
248 }
249 for (i=0; v > 0; i++) {
250 v >>= 1;
251 }
252 lny = i;
253
254 /* Allocate or reallocate arrays for variables as needed */
255 if (*nx == 0) {
256 if (lnx > 0) {
257 *x = lx = ABC_ALLOC(DdNode *,lnx);
258 if (lx == NULL) {
259 dd->errorCode = CUDD_MEMORY_OUT;
260 return(0);
261 }
262 *xn = lxn = ABC_ALLOC(DdNode *,lnx);
263 if (lxn == NULL) {
264 dd->errorCode = CUDD_MEMORY_OUT;
265 return(0);
266 }
267 } else {
268 *x = *xn = NULL;
269 }
270 } else if (lnx > *nx) {
271 *x = lx = ABC_REALLOC(DdNode *, *x, lnx);
272 if (lx == NULL) {
273 dd->errorCode = CUDD_MEMORY_OUT;
274 return(0);
275 }
276 *xn = lxn = ABC_REALLOC(DdNode *, *xn, lnx);
277 if (lxn == NULL) {
278 dd->errorCode = CUDD_MEMORY_OUT;
279 return(0);
280 }
281 } else {
282 lx = *x;
283 lxn = *xn;
284 }
285 if (*ny == 0) {
286 if (lny >0) {
287 *y = ly = ABC_ALLOC(DdNode *,lny);
288 if (ly == NULL) {
289 dd->errorCode = CUDD_MEMORY_OUT;
290 return(0);
291 }
292 *yn_ = lyn = ABC_ALLOC(DdNode *,lny);
293 if (lyn == NULL) {
294 dd->errorCode = CUDD_MEMORY_OUT;
295 return(0);
296 }
297 } else {
298 *y = *yn_ = NULL;
299 }
300 } else if (lny > *ny) {
301 *y = ly = ABC_REALLOC(DdNode *, *y, lny);
302 if (ly == NULL) {
303 dd->errorCode = CUDD_MEMORY_OUT;
304 return(0);
305 }
306 *yn_ = lyn = ABC_REALLOC(DdNode *, *yn_, lny);
307 if (lyn == NULL) {
308 dd->errorCode = CUDD_MEMORY_OUT;
309 return(0);
310 }
311 } else {
312 ly = *y;
313 lyn = *yn_;
314 }
315
316 /* Create new variables as needed */
317 for (i= *nx,nv=bx+(*nx)*sx; i < lnx; i++,nv+=sx) {
318 do {
319 dd->reordered = 0;
320 lx[i] = cuddUniqueInter(dd, nv, one, zero);
321 } while (dd->reordered == 1);
322 if (lx[i] == NULL) return(0);
323 cuddRef(lx[i]);
324 do {
325 dd->reordered = 0;
326 lxn[i] = cuddUniqueInter(dd, nv, zero, one);
327 } while (dd->reordered == 1);
328 if (lxn[i] == NULL) return(0);
329 cuddRef(lxn[i]);
330 }
331 for (i= *ny,nv=by+(*ny)*sy; i < lny; i++,nv+=sy) {
332 do {
333 dd->reordered = 0;
334 ly[i] = cuddUniqueInter(dd, nv, one, zero);
335 } while (dd->reordered == 1);
336 if (ly[i] == NULL) return(0);
337 cuddRef(ly[i]);
338 do {
339 dd->reordered = 0;
340 lyn[i] = cuddUniqueInter(dd, nv, zero, one);
341 } while (dd->reordered == 1);
342 if (lyn[i] == NULL) return(0);
343 cuddRef(lyn[i]);
344 }
345
346 /* Update matrix parameters */
347 *nx = lnx;
348 *ny = lny;
349 *m = nrow;
350 if (nrhs == 0) {
351 *n = ncol;
352 } else {
353 *n = (1 << (lny - 1)) + nrhs;
354 }
355
356 /* Read structure data */
357 colptr = ABC_ALLOC(int, ncol+1);
358 if (colptr == NULL) {
359 dd->errorCode = CUDD_MEMORY_OUT;
360 return(0);
361 }
362 rowind = ABC_ALLOC(int, nnzero);
363 if (rowind == NULL) {
364 dd->errorCode = CUDD_MEMORY_OUT;
365 return(0);
366 }
367
368 for (i=0; i<ncol+1; i++) {
369 err = fscanf(fp, " %d ", &u);
370 if (err == EOF){
371 ABC_FREE(colptr);
372 ABC_FREE(rowind);
373 return(0);
374 } else if (err != 1) {
375 ABC_FREE(colptr);
376 ABC_FREE(rowind);
377 return(0);
378 }
379 colptr[i] = u - 1;
380 }
381 if (colptr[0] != 0) {
382 (void) fprintf(dd->err,"%s: Unexpected colptr[0] (%d)\n",
383 key,colptr[0]);
384 ABC_FREE(colptr);
385 ABC_FREE(rowind);
386 return(0);
387 }
388 for (i=0; i<nnzero; i++) {
389 err = fscanf(fp, " %d ", &u);
390 if (err == EOF){
391 ABC_FREE(colptr);
392 ABC_FREE(rowind);
393 return(0);
394 } else if (err != 1) {
395 ABC_FREE(colptr);
396 ABC_FREE(rowind);
397 return(0);
398 }
399 rowind[i] = u - 1;
400 }
401
402 *E = zero; cuddRef(*E);
403
404 for (j=0; j<ncol; j++) {
405 v = j;
406 cubey = one; cuddRef(cubey);
407 for (nv = lny - 1; nv>=0; nv--) {
408 if (v & 1) {
409 w = Cudd_addApply(dd, Cudd_addTimes, cubey, ly[nv]);
410 } else {
411 w = Cudd_addApply(dd, Cudd_addTimes, cubey, lyn[nv]);
412 }
413 if (w == NULL) {
414 Cudd_RecursiveDeref(dd, cubey);
415 ABC_FREE(colptr);
416 ABC_FREE(rowind);
417 return(0);
418 }
419 cuddRef(w);
420 Cudd_RecursiveDeref(dd, cubey);
421 cubey = w;
422 v >>= 1;
423 }
424 for (i=colptr[j]; i<colptr[j+1]; i++) {
425 u = rowind[i];
426 err = fscanf(fp, " %lf ", &val);
427 if (err == EOF || err != 1){
428 Cudd_RecursiveDeref(dd, cubey);
429 ABC_FREE(colptr);
430 ABC_FREE(rowind);
431 return(0);
432 }
433 /* Create new Constant node if necessary */
434 cubex = cuddUniqueConst(dd, (CUDD_VALUE_TYPE) val);
435 if (cubex == NULL) {
436 Cudd_RecursiveDeref(dd, cubey);
437 ABC_FREE(colptr);
438 ABC_FREE(rowind);
439 return(0);
440 }
441 cuddRef(cubex);
442
443 for (nv = lnx - 1; nv>=0; nv--) {
444 if (u & 1) {
445 w = Cudd_addApply(dd, Cudd_addTimes, cubex, lx[nv]);
446 } else {
447 w = Cudd_addApply(dd, Cudd_addTimes, cubex, lxn[nv]);
448 }
449 if (w == NULL) {
450 Cudd_RecursiveDeref(dd, cubey);
451 Cudd_RecursiveDeref(dd, cubex);
452 ABC_FREE(colptr);
453 ABC_FREE(rowind);
454 return(0);
455 }
456 cuddRef(w);
457 Cudd_RecursiveDeref(dd, cubex);
458 cubex = w;
459 u >>= 1;
460 }
461 minterm1 = Cudd_addApply(dd, Cudd_addTimes, cubey, cubex);
462 if (minterm1 == NULL) {
463 Cudd_RecursiveDeref(dd, cubey);
464 Cudd_RecursiveDeref(dd, cubex);
465 ABC_FREE(colptr);
466 ABC_FREE(rowind);
467 return(0);
468 }
469 cuddRef(minterm1);
470 Cudd_RecursiveDeref(dd, cubex);
471 w = Cudd_addApply(dd, Cudd_addPlus, *E, minterm1);
472 if (w == NULL) {
473 Cudd_RecursiveDeref(dd, cubey);
474 ABC_FREE(colptr);
475 ABC_FREE(rowind);
476 return(0);
477 }
478 cuddRef(w);
479 Cudd_RecursiveDeref(dd, minterm1);
480 Cudd_RecursiveDeref(dd, *E);
481 *E = w;
482 }
483 Cudd_RecursiveDeref(dd, cubey);
484 }
485 ABC_FREE(colptr);
486 ABC_FREE(rowind);
487
488 /* Read right-hand sides */
489 for (j=0; j<nrhs; j++) {
490 v = j + (1<< (lny-1));
491 cubey = one; cuddRef(cubey);
492 for (nv = lny - 1; nv>=0; nv--) {
493 if (v & 1) {
494 w = Cudd_addApply(dd, Cudd_addTimes, cubey, ly[nv]);
495 } else {
496 w = Cudd_addApply(dd, Cudd_addTimes, cubey, lyn[nv]);
497 }
498 if (w == NULL) {
499 Cudd_RecursiveDeref(dd, cubey);
500 return(0);
501 }
502 cuddRef(w);
503 Cudd_RecursiveDeref(dd, cubey);
504 cubey = w;
505 v >>= 1;
506 }
507 for (i=0; i<nrow; i++) {
508 u = i;
509 err = fscanf(fp, " %lf ", &val);
510 if (err == EOF || err != 1){
511 Cudd_RecursiveDeref(dd, cubey);
512 return(0);
513 }
514 /* Create new Constant node if necessary */
515 if (val == (double) 0.0) continue;
516 cubex = cuddUniqueConst(dd, (CUDD_VALUE_TYPE) val);
517 if (cubex == NULL) {
518 Cudd_RecursiveDeref(dd, cubey);
519 return(0);
520 }
521 cuddRef(cubex);
522
523 for (nv = lnx - 1; nv>=0; nv--) {
524 if (u & 1) {
525 w = Cudd_addApply(dd, Cudd_addTimes, cubex, lx[nv]);
526 } else {
527 w = Cudd_addApply(dd, Cudd_addTimes, cubex, lxn[nv]);
528 }
529 if (w == NULL) {
530 Cudd_RecursiveDeref(dd, cubey);
531 Cudd_RecursiveDeref(dd, cubex);
532 return(0);
533 }
534 cuddRef(w);
535 Cudd_RecursiveDeref(dd, cubex);
536 cubex = w;
537 u >>= 1;
538 }
539 minterm1 = Cudd_addApply(dd, Cudd_addTimes, cubey, cubex);
540 if (minterm1 == NULL) {
541 Cudd_RecursiveDeref(dd, cubey);
542 Cudd_RecursiveDeref(dd, cubex);
543 return(0);
544 }
545 cuddRef(minterm1);
546 Cudd_RecursiveDeref(dd, cubex);
547 w = Cudd_addApply(dd, Cudd_addPlus, *E, minterm1);
548 if (w == NULL) {
549 Cudd_RecursiveDeref(dd, cubey);
550 return(0);
551 }
552 cuddRef(w);
553 Cudd_RecursiveDeref(dd, minterm1);
554 Cudd_RecursiveDeref(dd, *E);
555 *E = w;
556 }
557 Cudd_RecursiveDeref(dd, cubey);
558 }
559
560 return(1);
561
562 } /* end of Cudd_addHarwell */
563
564
565 /*---------------------------------------------------------------------------*/
566 /* Definition of internal functions */
567 /*---------------------------------------------------------------------------*/
568
569 /*---------------------------------------------------------------------------*/
570 /* Definition of static functions */
571 /*---------------------------------------------------------------------------*/
572
573
574 ABC_NAMESPACE_IMPL_END
575
576
577