read.c

利用c语言编写

/*
   ============================================================================
   NAME : read.c

   PURPOSE : translation of lp-problem and storage in sparse matrix

   SHORT : Subroutines for yacc program to store the input in an intermediate
   data-structure. The yacc and lex programs translate the input.  First the
   problemsize is determined and the date is read into an intermediate
   structure, then readinput fills the sparse matrix.

   USAGE : call yyparse(); to start reading the input.  call readinput(); to
   fill the sparse matrix.
   ============================================================================
   Rows : contains the amount of rows + 1. Rows-1 is the amount of constraints
   (no bounds) Rows also contains the rownr 0 which is the objective function

   Columns : contains the amount of columns (different variable names found in
   the constraints)

   Nonnuls : contains the amount of nonnuls = sum of different entries of all
   columns in the constraints and in the objectfunction

   Hash_tab : contains all columnnames on the first level of the structure the
   row information is kept under each column structure in a linked list (also
   the objective funtion is in this structure) Bound information is also
   stored under under the column name

   First_rside : points to a linked list containing all relational operators
   and the righthandside values of the constraints the linked list is in
   reversed order with respect to the rownumbers
   ============================================================================ */
#include <string.h>
#include <limits.h>
#include "lpkit.h"
#include "lpglob.h"

short            *relat;
int              Verbose;
constraint_name  *First_constraint_name;
rside            *First_rside, *rs;
tmp_store_struct tmp_store;
short            Ignore_decl;
hashstruct       *Hash_tab;

/*
 * error handling routine for yyparse()
 */
void yyerror(char *string)
{
  report(NULL, CRITICALSTOP, string);
}

int yywrap() /* supply a default yywrap() function */
{
  return(1);
}

void check_decl(int within_int_decl)
{
  if(within_int_decl) {
    Ignore_decl = FALSE;
  }
  else {
    if (Verbose >= NORMAL)
      report(NULL, NORMAL, "Unknown declaration specifier on line %d, ignored",
	      yylineno);
    Ignore_decl = TRUE;
  }
}

void add_int_var(char *name)
{
  hashelem *hp;

  if((hp = findhash(name, Hash_tab)) == NULL) {
    if (Verbose >= NORMAL)
      report(NULL, NORMAL,
 	      "Unknown variable %s declared integer on line %d, ignored",
	      name, yylineno);
  }
  else if(hp->must_be_int) {
    if (Verbose >= NORMAL)
      report(NULL, NORMAL, "Variable %s declared integer more than once on line %d",
	      name, yylineno);
  }
  else
    hp->must_be_int = TRUE;
}

/*
 * initialisation of hashstruct and globals.
 */
int init_read(void)
{
  int ok = FALSE;

  Rows = 0;
  Non_zeros = 0;
  Columns = 0;
  if (CALLOC(First_rside, 1) != NULL) {
    rs = First_rside;
    rs->value = rs->range_value = 0;
    /* first row (nr 0) is always the objective function */
    rs->relat = OF;
    rs->range_relat = -1;
    if ((Hash_tab = create_hash_table(HASHSIZE)) == NULL) {
      FREE(First_rside);
    }
    else
      ok = TRUE;
  }
  return(ok);
} /* init */


/*
 * searchs in column-list (p is pointer to first element of column-list)
 * for column->row = row.
 * getrow() returns a pointer to this column structure.
 * If not found a NULL-pointer is returned
 */
static column *getrow(column *p,
		      int row)
{
  for(; p != NULL; p = p->next)
    if(p->row == row)
      return(p);
  return(p) ;
} /* getrow */

/*
 * Creates a bound record.
 * Set lowbo = 0 and upbo = Infinite
 *
 */
static bound *create_bound_rec(void)
{
  bound *bp;

  if (CALLOC(bp, 1) != NULL) {
    bp->upbo = DEF_INFINITE;
    bp->lowbo = 0;
  }
  return(bp);
} /* create_bound_rec */

/*
 * clears the tmp_store variable after all information has been copied
 */
void null_tmp_store(void)
{
  tmp_store.value = 0;
  tmp_store.rhs_value = 0;
}

/*
 * variable : pointer to text array with name of variable
 * row      : the rownumber of the constraint
 * value    : value of matrixelement
 *            A(row, variable).
 * Sign     : (global)  determines the sign of value.
 * store()  : stores value in matrix
 *	      A(row, variable). If A(row, variable) already contains data,
 *	      value is added to the existing value.
 */
static int store(char *variable,
		  int row,
		  REAL value)
{
  hashelem *h_tab_p;
  column *col_p;

  if(value == 0) {
    if (Verbose >= NORMAL)
      report(NULL, NORMAL,
	      "(store) Warning, variable %s has an effective coefficient of 0 on line %d. Ignored.",
	      variable, yylineno);
    return(TRUE);
  }

  if((h_tab_p = findhash(variable, Hash_tab)) == NULL) {
    if (((h_tab_p = puthash(variable, Hash_tab)) == NULL) ||
        (CALLOC(h_tab_p->col, 1) == NULL)
       ) return(FALSE);
    Columns++; /* counter for calloc of final array */

    Non_zeros++; /* for calloc of final arrays */
    h_tab_p->col->row = row;
    h_tab_p->col->value = value;
  }
  else if((col_p = getrow(h_tab_p->col, row)) == NULL) {
    if (CALLOC(col_p, 1) == NULL)
      return(FALSE);
    Non_zeros++; /* for calloc of final arrays */
    col_p->value = value;
    col_p->row = row;
    col_p->next = h_tab_p->col;
    h_tab_p->col = col_p;
  }
  else
    col_p->value += value;
  return(TRUE);
} /* store */

/*
 * store relational operator given in yylex[0] in the rightside list.
 * Also checks if it constaint was a bound and if so stores it in the
 * boundslist
 */
void store_re_op(void)
{
  short tmp_relat;

  switch(yytext[0]) {

  case '=':
    tmp_relat = EQ;
    break;

  case '>':
    tmp_relat=GE;
    break;

  case '<':
    tmp_relat=LE;
    break;

  default:
    report(NULL, CRITICALSTOP, "Error: unknown relational operator %s on line %d",
	   yytext, yylineno);
    return;
    break;
  }

  if(Lin_term_count > 1) /* it is not a bound */
    rs->relat = tmp_relat;
  else if(Lin_term_count == 0) { /* it is a range */
    if(rs == NULL) { /* range before row, already reported */
      if(Verbose >= CRITICAL)
        report(NULL, CRITICAL, "Error on line %d: range for undefined row.",
  	        yylineno);
    }
    else if(rs->range_relat != -1) {
      if(Verbose >= CRITICAL)
        report(NULL, CRITICAL, "Error on line %d: There was already a range for this row.",
  	        yylineno);
    }
    else if(tmp_relat == rs->relat) {
      if(Verbose >= CRITICAL)
        report(NULL, CRITICAL, "Error on line %d: relational operator for range is the same as relation operator for equation.",
  	        yylineno);
      rs->range_relat = -2;
    }
    else
      rs->range_relat = tmp_relat;
  }
  else /* could be a bound */
    tmp_store.relat = tmp_relat;
} /* save_re_op */

/*
 * store RHS value in the rightside structure
 * if type = true then
 */
void rhs_store(REAL value)
{
  if(Lin_term_count > 1) /* not a bound */
    rs->value += value;
  else if(Lin_term_count == 0) { /* a range */
    if(rs == NULL); /* range before row, already reported */
    else if(rs->range_relat < 0) /* was a bad range; ignore */;
    else if(((rs->relat == LE) && (rs->range_relat == GE) &&
         (rs->value < value)) ||
        ((rs->relat == GE) && (rs->range_relat == LE) &&
         (rs->value > value)) ||
	((rs->relat == EQ) || (rs->range_relat == EQ))) {
      if(Verbose >= CRITICAL)
        report(NULL, CRITICAL, "Error on line %d: range restriction is conflicting with equation on previous line",
  	        yylineno);
      rs->range_relat = -2;
    }
    else
      rs->range_value += value;
  }
  else /* a bound */
    tmp_store.rhs_value += value;
} /* RHS_store */

/*
 * store all data in the right place
 * count the amount of lineair terms in a constraint
 * only store in data-structure if the constraint is not a bound
 */
int var_store(char *var, int row, REAL value)
{
  if(strlen(var) > MAXSTRL) {
    if (Verbose >= CRITICAL)
      report(NULL, CRITICAL, "Variable name '%s' too long, at most %d characters allowed",
	      var, MAXSTRL);
    return(FALSE);
  }
  /* also in a bound the same var name can occur more than once. Check for
     this. Don't increment Lin_term_count */

  if(Lin_term_count != 1 || strcmp(tmp_store.name, var) != 0)
    Lin_term_count++;

  /* always store objective function with rownr == 0. */
  if(row == 0)
    return(store(var,  row,  value));

  if(Lin_term_count == 1) { /* don't store yet. could be a bound */
    strcpy(tmp_store.name, var);
    tmp_store.row = row;
    tmp_store.value += value;
    return(TRUE);
  }

  if(Lin_term_count == 2) { /* now you can also store the first variable */
    rside *rp;

    /* make space for the rhs information */
    if (CALLOC(rp, 1) == NULL)
      return(FALSE);
    rp->next = First_rside;
    First_rside = rs = rp;
    rs->row = row;
    rs->value = tmp_store.rhs_value;
    rs->relat = tmp_store.relat;
    rs->range_relat = -1;

    if(tmp_store.value != 0) {
      if (!store(tmp_store.name, tmp_store.row, tmp_store.value))
        return(FALSE);
    }
    else {
      if (Verbose >= NORMAL)
        report(NULL, NORMAL,
	        "Warning, variable %s has an effective coefficient of 0 on line %d. Ignored.",
	        tmp_store.name, yylineno);
    }

    null_tmp_store();
  }

  return(store(var, row, value));
} /* var_store */



/*
 * store the information in tmp_store because it is a bound
 */
int store_bounds(void)
{
  if(tmp_store.value != 0) {
    hashelem *h_tab_p;
    REAL boundvalue;

    if((h_tab_p = findhash(tmp_store.name, Hash_tab)) == NULL) {
      /* a new columnname is found, create an entry in the hashlist */
      if ((h_tab_p = puthash(tmp_store.name, Hash_tab)) == NULL)