abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions | Variables
cuddHarwell.c File Reference
#include "misc/util/util_hack.h"
#include "cuddInt.h"

Go to the source code of this file.

Functions

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)
 

Variables

static
ABC_NAMESPACE_IMPL_START char
rcsid[] 		DD_UNUSED = "$Id: cuddHarwell.c,v 1.9 2004/08/13 18:04:49 fabio Exp $"
 

Function Documentation

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 
)

AutomaticStart AutomaticEnd Function********************************************************************

Synopsis [Reads in a matrix in the format of the Harwell-Boeing benchmark suite.]

Description [Reads in a matrix in the format of the Harwell-Boeing benchmark suite. The variables are ordered as follows:

x[0] y[0] x[1] y[1] ...

0 is the most significant bit. On input, nx and ny hold the numbers of row and column variables already in existence. On output, they hold the numbers of row and column variables actually used by the matrix. m and n are set to the numbers of rows and columns of the matrix. Their values on input are immaterial. Returns 1 on success; 0 otherwise. The ADD for the sparse matrix is returned in E, and its reference count is > 0.]

SideEffects [None]

SeeAlso [Cudd_addRead Cudd_bddRead]

Definition at line 124 of file cuddHarwell.c.

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 */
cuddRef
#define cuddRef(n)
Definition: cuddInt.h:584
Cudd_RecursiveDeref
void Cudd_RecursiveDeref(DdManager *table, DdNode *n)
Definition: cuddRef.c:154
DdNode
Definition: cudd.h:278
cuddUniqueConst
DdNode * cuddUniqueConst(DdManager *unique, CUDD_VALUE_TYPE value)
Definition: cuddTable.c:1450
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
DdManager::err
FILE * err
Definition: cuddInt.h:442
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Cudd_addApply
DdNode * Cudd_addApply(DdManager *dd, DdNode *(*)(DdManager *, DdNode **, DdNode **), DdNode *f, DdNode *g)
DdManager::reordered
int reordered
Definition: cuddInt.h:409
one
static DdNode * one
Definition: cuddDecomp.c:112
DdManager::out
FILE * out
Definition: cuddInt.h:441
Cudd_addPlus
DdNode * Cudd_addPlus(DdManager *dd, DdNode **f, DdNode **g)
Definition: cuddAddApply.c:168
ddMax
#define ddMax(x, y)
Definition: cuddInt.h:832
CUDD_VALUE_TYPE
#define CUDD_VALUE_TYPE
Definition: cudd.h:94
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
key
enum keys key
Definition: misc/espresso/main.h:25
DD_ONE
#define DD_ONE(dd)
Definition: cuddInt.h:911
Cudd_addTimes
DdNode * Cudd_addTimes(DdManager *dd, DdNode **f, DdNode **g)
Definition: cuddAddApply.c:208
DdManager::errorCode
Cudd_ErrorType errorCode
Definition: cuddInt.h:447
cuddUniqueInter
DdNode * cuddUniqueInter(DdManager *unique, int index, DdNode *T, DdNode *E)
Definition: cuddTable.c:1128
zero
static DdNode * zero
Definition: cuddApa.c:100
DD_ZERO
#define DD_ZERO(dd)
Definition: cuddInt.h:927

Variable Documentation

ABC_NAMESPACE_IMPL_START char rcsid [] DD_UNUSED = "$Id: cuddHarwell.c,v 1.9 2004/08/13 18:04:49 fabio Exp $"
static

CFile***********************************************************************

FileName [cuddHarwell.c]

PackageName [cudd]

Synopsis [Function to read a matrix in Harwell format.]

Description [External procedures included in this module:

]

Author [Fabio Somenzi]

Copyright [Copyright (c) 1995-2004, Regents of the University of Colorado

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.]

Definition at line 78 of file cuddHarwell.c.