home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / math / lpsolves / read.c < prev    next >
C/C++ Source or Header  |  1993-07-28  |  14KB  |  534 lines
  1. /*
  2. ============================================================================
  3. NAME    : read.c
  4. PURPOSE : translation of lp-problem and storage in sparse matrix
  5. SHORT   : Subroutines for yacc program to store the input in an intermediate
  6.           data-structure. The yacc and lex programs translate the input.
  7.           First the problemsize is determined and the date is read into
  8.           an intermediate structure, then readinput fills the sparse matrix.
  9. USAGE   : call yyparse(); to start reading the input.
  10.           call readinput(); to fill the sparse matrix.
  11. ============================================================================
  12. Rows : contains the amount of rows + 1
  13.        Rows-1 is the amount of constraints (no bounds)
  14.        Rows   also contains the rownr 0 which is the objectfunction
  15. Columns : contains the amount of columns (different variable names
  16.           found in the constraints)
  17. Nonnuls : contains the amount of nonnuls = sum of different entries
  18.           of all columns in the constraints and in the objectfunction
  19. Hash_tab : contains all columnnames on the first level of the structure
  20.            the row information is kept under each column structure
  21.            in a linked list (also the objext funtion is in this structure)
  22.            Bound information is also stored under under the column name
  23. First_rside : points to a linked list containing all relational operators
  24.               and the righthandside values of the constraints
  25.               the linked list is in reversed order with respect to the
  26.               rownumbers
  27. ============================================================================
  28. */
  29. #include "defines.h"
  30. #include "globals.h"
  31.  
  32. /*---------------------------------------------------------------------------*/
  33.  
  34. /*
  35.  * errorhandeling routine for yyparse()
  36.  */
  37. void yyerror(char *string)
  38. {
  39.   fprintf(stderr, "PARSING ERROR: %s on line %d, quiting\n", string, yylineno);
  40.   exit(1);
  41. }
  42.  
  43. void check_decl(char *str)
  44. {
  45.   if(strcmp(str, "int"))
  46.     {
  47.       fprintf(stderr, "Unknown declaration specifier %s on line %d, ignored\n",
  48.           str, yylineno);
  49.       Ignore_decl = TRUE;
  50.     }
  51. }
  52.  
  53. void add_int_var(char *name)
  54. {
  55.   hashelem *hp;
  56.  
  57.   if(Verbose)
  58.     fprintf(stderr, "int: %s\n", name);
  59.   if(!(hp = gethash(name)))
  60.     fprintf(stderr,
  61.         "Unknown variable %s declared integer on line %d, ignored\n",
  62.         name, yylineno);
  63.   else
  64.     hp->must_be_int = 1;
  65. }
  66.  
  67.  
  68. /*
  69.  * initialisation of hashtable and globals.
  70.  */
  71. void init_read(void)
  72. {
  73.   int i;
  74.   Rows = 0;
  75.   Nonnuls = 0;
  76.   Columns = 0;
  77.   for(i = 0; i<HASH_SIZE; Hash_tab[i++] = NULL);
  78.   CALLOC(First_rside, 1, rside);
  79.   First_rside->value = 0;
  80.   First_rside->relat = OF; /* first row (nr 0) is always the objective function */
  81. } /* init */
  82.  
  83. /*---------------------------------------------------------------------------*/
  84.  
  85. /*
  86.  * Returns hashvalue of string
  87.  * hashvalue = sum ( asciivalue of character * indexnumber) mod HASHSIZE
  88.  */
  89. int hashvalue(char *string)
  90. {
  91.   int i, j;
  92.   i = j = 0;
  93.   while((int)string[j]&&j<MAXSTRL)
  94.     i += (NAMELEN-j)*(int)string[j++];
  95.   return(i % HASH_SIZE);
  96. } /* hashvalue */
  97.  
  98.  
  99.  
  100. /*
  101.  * Returns a pointer to hashelement with colname = variable
  102.  * If this hashelement does not exists, gethash() returns a NULL pointer
  103.  */
  104. hashelem *gethash(char *variable) 
  105. {
  106.   hashelem *h_tab_p;
  107.   for(h_tab_p = Hash_tab[hashvalue(variable)];
  108.       h_tab_p != NULL;
  109.       h_tab_p = h_tab_p->next)
  110.     if(strcmp(variable, h_tab_p->colname) == 0)
  111.       return(h_tab_p);
  112.   return(h_tab_p);
  113. } /* gethash */
  114.  
  115.  
  116.  
  117. /*
  118.  * searchs in column-list (p is pointer to first element of column-list)
  119.  * for column->row = row.
  120.  * getrow() returns a pointer to this column structure.
  121.  * If not found a NULL-pointer is returned
  122.  */
  123. column *getrow(column *p,
  124.            int row)
  125. {
  126.   for(; p != NULL; p = p->next)
  127.     if(p->row == row)
  128.       return(p);
  129.   return(p) ;
  130. } /* getrow */
  131.  
  132.  
  133.  
  134. /*
  135.  * Creates a bound record.
  136.  * Set lowbo = 0 and upbo = INFINITE
  137.  *
  138.  */
  139. bound *create_bound_rec(void)
  140. {
  141.   bound *bp;
  142.   CALLOC(bp, 1, bound);
  143.   bp->upbo = INFINITE;
  144.   bp->lowbo = 0;
  145.   return(bp);
  146. } /* create_bound_rec */
  147.  
  148.  
  149.  
  150. /*
  151.  * clears the tmp_store variable after all information has been copied
  152.  */
  153. void null_tmp_store(void)
  154. {
  155.   tmp_store.value = 0;
  156.   tmp_store.rhs_value = 0;
  157. }
  158.  
  159. /*---------------------------------------------------------------------------*/
  160.  
  161. /*
  162.  * variable : pointer to text array with name of variable
  163.  * row      : the rownumber of the constraint
  164.  * value    : value of matrixelement
  165.  *            A(row, variable).
  166.  * Sign     : (global)  determines the sign of value.
  167.  * store()  : stores value in matrix
  168.  *          A(row, variable). If A(row, variable) already contains data,
  169.  *          value is added to the existing value.
  170.  */
  171. void store(char *variable,
  172.        int row,
  173.        double value) 
  174. { 
  175.   hashelem *h_tab_p;
  176.   column *col_p;
  177.   int hv;
  178.  
  179.   if(value == (double)0)
  180.     return;
  181.   if((h_tab_p = gethash(variable)) == NULL)
  182.   {
  183.     CALLOC(h_tab_p, 1, hashelem);
  184.     Columns++; /* counter for calloc of final array */
  185.     hv = hashvalue(variable);
  186.     h_tab_p->next = Hash_tab[hv];
  187.     Hash_tab[hv] = h_tab_p;
  188.     strcpy(h_tab_p->colname, variable);
  189.     CALLOC(h_tab_p->col, 1, column);
  190.     Nonnuls++; /* for calloc of final arrays */
  191.     h_tab_p->col->row = row;
  192.     h_tab_p->col->value = value;
  193.   }
  194.   else
  195.     if((col_p = getrow(h_tab_p->col, row)) == NULL)
  196.     {
  197.       CALLOC(col_p, 1, column);
  198.       Nonnuls++; /* for calloc of final arrays */
  199.       col_p->value = value;
  200.       col_p->row = row;
  201.       col_p->next = h_tab_p->col;
  202.       h_tab_p->col = col_p;
  203.     }
  204.     else
  205.       col_p->value += value;
  206. } /* store */
  207.  
  208.  
  209.  
  210. /*---------------------------------------------------------------------------*/
  211.  
  212. /*
  213.  * store relational operator given in yylex[0] in the rightside list.
  214.  * Also checks if it constaint was a bound and if so stores it in the
  215.  * boundslist
  216.  */
  217. void store_re_op(void)
  218. {
  219.   short tmp_relat;
  220.   switch(yytext[0]) {
  221.  
  222.   case '=':
  223.     tmp_relat = EQ;
  224.     break;
  225.  
  226.   case '>':
  227.     tmp_relat=GE;
  228.     break;
  229.     
  230.   case '<':
  231.     tmp_relat=LE;
  232.     break;
  233.     
  234.   default:
  235.     break;
  236.   }
  237.   
  238.   if(Lin_term_count > 1) /* it is not a bound */
  239.     First_rside->relat = tmp_relat;
  240.   else /* could be a bound */
  241.     tmp_store.relat = tmp_relat;
  242. } /* save_re_op */
  243.  
  244.  
  245.  
  246. /*
  247.  * store RHS value in the rightside structure
  248.  * if type = true then
  249.  */
  250. void rhs_store(double value)
  251. {
  252.   if(Lin_term_count <= 1) /* could be a bound */
  253.     tmp_store.rhs_value += value;
  254.   else /* not a bound */
  255.     First_rside->value += value;
  256. } /* RHS_store */
  257.  
  258.  
  259.  
  260. /*
  261.  * store all data in the right place
  262.  * count the amount of lineair terms in a constraint
  263.  * only store in data-structure if the constraint is not a bound
  264.  */
  265. void var_store(char *var,
  266.            int row,
  267.            double value)
  268. {
  269.   if(strlen(var) > MAXSTRL)
  270.     {
  271.       fprintf(stderr, "Variable name too long, at most %d characters allowed",
  272.           MAXSTRL);
  273.       exit(1);
  274.     }
  275.   /* also in a bound the same var name can occur more than once. Check for
  276.      this. Don't increment Lin_term_count */
  277.  
  278.   if(Lin_term_count != 1 || strcmp(tmp_store.name, var) != 0)
  279.     Lin_term_count++;
  280.  
  281.   if(row == 0) /* always store objective function with rownr == 0 */
  282.     {
  283.       store(var,  row,  value);
  284.       return;
  285.     }
  286.   
  287.   if(Lin_term_count == 1) /* don't yet store. could be a bound */
  288.     {
  289.       strcpy(tmp_store.name, var);
  290.       tmp_store.row = row;
  291.       tmp_store.value += value;
  292.       return;
  293.     }
  294.   
  295.   if(Lin_term_count == 2) /* now you can also store the first variable */
  296.     {
  297.       rside *rp;
  298.       /* make space for the rhs information */
  299.       CALLOC(rp, 1, rside);
  300.       rp->next = First_rside;
  301.       First_rside = rp;
  302.       First_rside->value = tmp_store.rhs_value;
  303.       First_rside->relat = tmp_store.relat;
  304.       
  305.       if (tmp_store.value != 0)
  306.         store(tmp_store.name, tmp_store.row, tmp_store.value);
  307.  
  308.       null_tmp_store();
  309.     }
  310.  
  311.   store(var, row, value);
  312. } /* var_store */
  313.  
  314.  
  315.  
  316. /*
  317.  * store the information in tmp_store because it is a bound
  318.  */
  319. store_bounds(void)
  320. {
  321.   if (tmp_store.value != 0)
  322.     {
  323.       hashelem *h_tab_p;
  324.       int hv;
  325.  
  326.       if((h_tab_p = gethash(tmp_store.name)) == NULL)
  327.         {
  328.           /* a new columnname is found, create an entry in the hashlist */
  329.           CALLOC(h_tab_p, 1, hashelem);
  330.           Columns++; /* counter for calloc of final array */
  331.       hv            = hashvalue(tmp_store.name);
  332.       h_tab_p->next = Hash_tab[hv];
  333.           Hash_tab[hv]  = h_tab_p;
  334.           strcpy(h_tab_p->colname, tmp_store.name);
  335.           /* create a place to store bounds information */
  336.           h_tab_p->bnd = create_bound_rec();
  337.         }
  338.       else
  339.         if(h_tab_p->bnd == NULL)
  340.           /* create a place to store bounds information */
  341.           h_tab_p->bnd = create_bound_rec();
  342.       /* else bound_rec already exists */
  343.    
  344.       if(tmp_store.value < 0) /* divide by negative number, */
  345.                             /* relational operator may change */
  346.         {
  347.           if (tmp_store.relat == GE)
  348.             tmp_store.relat = LE;
  349.           else if (tmp_store.relat == LE)
  350.             tmp_store.relat = GE;
  351.         }
  352.  
  353.       if ((tmp_store.relat == GE) || (tmp_store.relat == EQ))
  354.         h_tab_p->bnd->lowbo = tmp_store.rhs_value / tmp_store.value;
  355.       if ((tmp_store.relat == LE) || (tmp_store.relat == EQ))
  356.         h_tab_p->bnd->upbo = tmp_store.rhs_value / tmp_store.value;
  357.     }
  358.   
  359.   null_tmp_store();
  360. } /* store_bounds */
  361.  
  362. /* ========================================================================= */
  363.  
  364.  
  365. /*
  366.  * reallocates eta
  367.  */
  368. void resize_eta(void)
  369. {
  370.   Cur_eta_size *= 2;
  371.   if (Verbose)
  372.     printf("Resizing Eta_value and Eta_rownr, new size is %d\n", Cur_eta_size);
  373.   if(!(Eta_value = realloc(Eta_value, Cur_eta_size * sizeof(double))))
  374.     {
  375.       fprintf(stderr, "Error: cannot realloc Eta_value to size %d (entries)\n",
  376.           Cur_eta_size);
  377.       exit(1);
  378.     }
  379.   if(!(Eta_rownr = realloc(Eta_rownr, Cur_eta_size * sizeof(int))))
  380.     {
  381.       fprintf(stderr, "Error: cannot realloc Eta_rownr to size %d (entries)\n",
  382.           Cur_eta_size);
  383.       exit(1);
  384.     }
  385. } /* resize_eta */
  386.  
  387.  
  388.  
  389.  
  390. /*
  391.  * transport the data from the intermediate structure to the sparse matrix
  392.  * and free the intermediate structure
  393.  */
  394. void readinput(int *cend,
  395.            double *rh,
  396.            short *relat,
  397.            double *lowbo,
  398.            double *upbo,
  399.            matrec *mat,
  400.            nstring *names)
  401. {
  402.   int    i, j, k, index, nn_ind;
  403.   column *cp,*tcp;    /* tcp (temporary cp) points to memory-space to free */
  404.   hashelem *hp,*thp;
  405.   bound *bp;
  406.   int   x;
  407.   rside *rp;
  408.   intrec *irp;
  409.   
  410.   /* initialize lower and upper bound arrays */
  411.   for (i = 0; i <= Sum; i++)
  412.     {
  413.       lowbo[i] = 0;
  414.       upbo[i] = INFINITE;
  415.     }
  416.   
  417.   /* fill names with the rownames */
  418.   for (i = 0; i <= Rows; i++)
  419.     {
  420.       /* the first row is row zero (the objective function)             */
  421.       sprintf(names[i], "%s%d", STD_ROW_NAME_PREFIX, i);
  422.     }
  423.   
  424.   for (i = Rows;i >= 0;i--)
  425.     {
  426.       rp = First_rside;
  427.       relat[i] = rp->relat;
  428.       rh[i] = rp->value;
  429.       First_rside = rp->next;
  430.       free(rp);  /* free memory when data has been read */
  431.     }
  432.   
  433.   /* change upperbound to zero if the relational operator is the equal sign */
  434.   for (i = 1; i <= Rows; i++)
  435.     if (relat[i] == EQ)
  436.       upbo[i] = 0;
  437.   
  438.   /* start reading the Hash_list structure */
  439.   index = 0;
  440.   nn_ind = 0;
  441.   
  442.   for (i = 0;i < HASH_SIZE;i++)
  443.     {
  444.       hp = Hash_tab[i];
  445.       while (hp != NULL)
  446.         {
  447.       /* put an index in the cend array when a new name is found */
  448.       cend[index++] = nn_ind;
  449.  
  450.       /* check if it must be an integer variable */
  451.       if(hp->must_be_int)
  452.         {
  453.           CALLOC(irp, 1, intrec);
  454.           irp->varnr = Rows + index;
  455.           irp->next  = First_int;
  456.           First_int  = irp;
  457.         }
  458.       /* check for bound */
  459.       if (hp->bnd != NULL)
  460.         {
  461.           bp = hp->bnd;
  462.               lowbo[Rows+index] = bp->lowbo;
  463.               upbo[Rows+index] = bp->upbo;
  464.               free(bp); /* free memory when data has been read*/
  465.         }
  466.       
  467.       /* copy name of column variable */
  468.       strcpy(names[Rows+index], hp->colname);
  469.  
  470.       /* put matrix values in sparse matrix */
  471.           cp = hp->col;
  472.           while (cp!=NULL)
  473.             {
  474.               mat[nn_ind].rownr = cp->row;
  475.           mat[nn_ind].value = cp->value;
  476.           nn_ind++;
  477.           tcp = cp;
  478.           cp = cp->next;
  479.           free(tcp);  /* free memory when data has been read */
  480.         }
  481.       thp = hp;
  482.       hp = hp->next;
  483.           free(thp);    /* free memory when data has been read */
  484.         }
  485.     }
  486.   cend[index] = nn_ind; 
  487.   
  488.   if (Verbose)
  489.     {
  490.       printf("\n");
  491.       printf("**********Data read**********\n");
  492.       printf("Rows    : %d\n", Rows);
  493.       printf("Columns : %d\n", Columns);
  494.       printf("Nonnuls : %d\n", Nonnuls);
  495.       printf("\nSparse Matrix\nRow right hand side\n");
  496.       printf("%4s  %8s %3s %s\n\n", "nr", "row", "rel", "Value");
  497.       for (i = 0; i <= Rows; i++)
  498.     {
  499.       printf("%4d  %8s ", i, names[i]);
  500.       if (relat[i] == LE) printf(" < ");
  501.       if (relat[i] == EQ) printf(" = ");
  502.       if (relat[i] == GE) printf(" > ");
  503.       if (relat[i] == OF) printf("ObF");
  504.       printf(" %f\n", rh[i]);
  505.     }
  506.       
  507.       printf("\nMatrix contents\n%8s  %8s  %s\n\n","colname","row","value");
  508.       j = 0;
  509.       for (i = 0; i < Nonnuls; i++)
  510.     {
  511.       if (i == cend[j])
  512.         printf("%8s  %8s  %f\n", names[Rows+ ++j], names[mat[i].rownr],
  513.            mat[i].value);
  514.       else
  515.         printf("          %8s  %e\n", names[mat[i].rownr], mat[i].value);
  516.     }
  517.       printf("\nBounds\n%8s %3s %s\n\n", "name", "rel", "value");
  518.       for (i = 0; i <= Sum; i++)
  519.     {
  520.       if (upbo[i] < (INFINITE/10000))  /* double is to small to contain
  521.                           INFINITE thus is rounded */
  522.         printf("%8s  <  %f\n", names[i], upbo[i]);
  523.       if (lowbo[i] > 0)
  524.         printf("%8s  >  %f\n", names[i], lowbo[i]);
  525.     }
  526.       
  527.       printf("\n**********End data**********\n\n");
  528.     }
  529. } /* readinput */
  530.  
  531.  
  532. /* ===================== END OF read.c ===================================== */
  533.  
  534.