ex4_enum.c File Reference

Appfs Exercise 4: BIP Enumerator. More...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
#include "mshell.h"
#include "sid.h"
#include "allocate.h"

Go to the source code of this file.

Data Structures
struct	binary_program

Macros
#define	BIP_SID   0x42495078
#define	BIP_COLS   32
#define	BIP_ROWS   32
#define	MAX_LINE_LEN   512
	Maximum input line length. More...
#define	MAX_COEF_VAL   1e20
	Maximum absolute value of a coefficient. More...
#define	GET_SEC(a, b)   ((b - a) / (double)CLOCKS_PER_SEC)

Typedefs
typedef struct binary_program	BIP

Enumerations
enum	LINE_MODE { READ_COLS, READ_ROWS, READ_COEF }

Functions
bool	bip_is_valid (const BIP *bip)
	Check whether BIP data structure is consistent. More...
void	bip_free (BIP *bip)
	Deallocate BIP data structure. More...
BIP *	bip_read (const char *filename)
	Read a bip file. More...
void	bip_print (FILE *fp, const BIP *bip)
	Print Binary Program from BIP. More...
void	print_solu (FILE *fp, int vars, const double *x)
	Print solution vector. More...
bool	bip_is_feasible (const BIP *bip, const double *x)
	Check whether a particular vector is a feasible solution to a BIP. More...
int	bip_enumerate (const BIP *bip, bool with_output)
	Enumerate all possible solution of a BIP. More...
int	main (int argc, const char **argv)
	Usage: ex4_enum bip_file. More...

Detailed Description

Author

Thorsten Koch

Date

13Nov2014

gcc -O3 -Wall -std=c99 -o ex4_enum ex4_enum.c

Options: -DUSE_SCANF use sscanf() for input -DUSE_STRTOK use strtok() for input otherwise strtol() is used. -DNO_MSHELL don't compile with mshell

Definition in file ex4_enum.c.

Macro Definition Documentation

#define BIP_COLS   32

Definition at line 28 of file ex4_enum.c.

#define BIP_ROWS   32

Definition at line 29 of file ex4_enum.c.

#define BIP_SID   0x42495078

Definition at line 27 of file ex4_enum.c.

#define GET_SEC	(		a,
			b
	)		((b - a) / (double)CLOCKS_PER_SEC)

Definition at line 46 of file ex4_enum.c.

#define MAX_COEF_VAL   1e20

Definition at line 44 of file ex4_enum.c.

#define MAX_LINE_LEN   512

Definition at line 42 of file ex4_enum.c.

Typedef Documentation

typedef struct binary_program BIP

Definition at line 40 of file ex4_enum.c.

Enumeration Type Documentation

enum LINE_MODE

Enumerator
READ_COLS
READ_ROWS
READ_COEF

Definition at line 48 of file ex4_enum.c.

{ READ_COLS, READ_ROWS, READ_COEF } LINE_MODE;

Function Documentation

int bip_enumerate	(	const BIP *	bip,
		bool	with_output
	)

Prints all solutions.

Returns

number of feasible solutions found.

Definition at line 382 of file ex4_enum.c.

{
   assert(bip_is_valid(bip));
   
   clock_t start = clock();
   int     solus = 0;
   int     count = 0;
   
   /* generate all permutation
    */
   for(unsigned long long bitvec = 0; bitvec < (1uL << bip->cols); bitvec++)
   {      
      unsigned long long mask = 1;  // long long because long is 32 bit on 32 bit computers
      double             x[BIP_COLS];

      assert(sizeof(bitvec) * 8 > BIP_COLS); //lint !e506
      
      /* construct solution vector
       */
      for(int j = 0; j < bip->cols; j++, mask <<= 1)
         x[j] = (bitvec & mask) ? 1.0 : 0.0; 

      if (bip_is_feasible(bip, &x[0])) //lint !e772 
      {
         if (with_output)
            print_solu(stdout, bip->rows, &x[0]);
         
         solus++;
      }
      count++;
   }
   assert((unsigned)count == (1u << bip->cols));
   
   double elapsed = GET_SEC(start, clock());
   
   printf("Checked %d vectors in %.3f s = %.3f kvecs/s\n",
      count, elapsed, count / elapsed / 1000.0);

   return solus;
}

void bip_free

(

BIP *

bip

)

Definition at line 77 of file ex4_enum.c.

{
   assert(bip_is_valid(bip));

   SID_del(bip);

   mem_check(bip);
   
   deallocate(bip);
}

bool bip_is_feasible	(	const BIP *	bip,
		const double *	x
	)

Returns

true if feasible, false otherwise.

Definition at line 356 of file ex4_enum.c.

{
   assert(bip_is_valid(bip));
   
   int r;
   
   for(r = 0; r < bip->rows; r++)
   {
      double lhs = 0.0;
      
      for(int c = 0; c < bip->cols; c++)
      {
         assert(x[c] == 0.0 || x[c] == 1.0);
         
         lhs += bip->a[r][c] * x[c];
      }
      if (lhs > bip->b[r])
         break;
   }
   return r == bip->rows;
}

bool bip_is_valid

(

const BIP *

bip

)

Returns

true if ok, false otherwise.

Definition at line 53 of file ex4_enum.c.

{
   if (NULL == bip || !SID_ok(bip, BIP_SID))
      return false;
   
   if (bip->rows < 1 || bip->rows > BIP_ROWS)
      return false;
   if (bip->cols < 1 || bip->cols > BIP_COLS)
      return false;

   for(int r = 0; r < bip->rows; r++)
   {
      for(int c = 0; c < bip->cols; c++)
         if (bip->a[r][c] < -MAX_COEF_VAL || bip->a[r][c] > MAX_COEF_VAL)
            return false;

      if (bip->b[r] < -MAX_COEF_VAL || bip->b[r] > MAX_COEF_VAL)
         return false;
   }
   return true;
}

void bip_print	(	FILE *	fp,
		const BIP *	bip
	)

Definition at line 323 of file ex4_enum.c.

{
   assert(NULL != fp);
   assert(bip_is_valid(bip));

   for(int r = 0; r < bip->rows; r++)
   {
      for(int c = 0; c < bip->cols; c++)
         fprintf(fp, "%5g ", bip->a[r][c]);
      fprintf(fp, "<= %5g\n", bip->b[r]);
   }
}

BIP* bip_read

(

const char *

filename

)

Format example:

4 # cols (variables) 3 # rows (constraints) 2 3 5 4 <= 8 3 6 0 8 <= 10 0 0 1 1 <= 1

comments (#) and empty lines are ignored.

Parameters

filename

name of file to read

Returns

ptr to BIP data structure

Definition at line 102 of file ex4_enum.c.

{
   assert(NULL != filename);
   assert(0    <  strlen(filename));

#ifdef USE_SCANF
   char input[] = "%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf";
#endif
   
   char      buf[MAX_LINE_LEN];
   char*     s;
   FILE*     fp;
   BIP*      bip   = allocate(1, sizeof(*bip));
   int       lines = 0;
   int       rows  = 0;
   int       cols;
   LINE_MODE mode  = READ_COLS;
   
   if (NULL == (fp = fopen(filename, "r")))
   {
      fprintf(stderr, "Can't open file %s\n", filename);
      goto read_error;
   }
   printf("Reading %s\n", filename);

   while(NULL != (s = fgets(buf, sizeof(buf), fp)))
   {
      char* t = strpbrk(s, "#\n\r"); 

      lines++;
      
      if (NULL != t) /* else line is not terminated or too long */
         *t = '\0';  /* clip comment or newline */
      
/* Skip over leading space
       */
      while(isspace(*s))
         s++;

      /* Skip over empty lines
       */
      if (!*s)  /* <=> (*s == '\0') */
         continue;

#ifdef USE_SCANF
      double v[33];
      int    nums;      
      
      nums = sscanf(s, input,
         &v[ 0], &v[ 1], &v[ 2], &v[ 3], &v[ 4], &v[ 5], &v[ 6], &v[ 7], 
         &v[ 8], &v[ 9], &v[10], &v[11], &v[12], &v[13], &v[14], &v[15],
         &v[16], &v[17], &v[18], &v[19], &v[20], &v[21], &v[22], &v[23],
         &v[24], &v[25], &v[26], &v[27], &v[28], &v[29], &v[30], &v[31]);

      if (nums < 1)
      {
         fprintf(stderr, "Error line %d: Expected number, got \"%s\"\n", lines, s);
         goto read_error;
      }

      /* do processing here:
       * mode tells which kind of line is next.
       */
      switch(mode)
      {
      case READ_COLS :
         bip->cols = (int)v[0];
         
         if (bip->cols < 1 || bip->cols > BIP_COLS)
         {
fprintf(stderr, "Error line %d: 1 <= cols=%d <= %d\n", lines, bip->cols, BIP_COLS);
goto read_error;
         }
         /* Insert <= into the input string
          */
         strncpy(input + bip->cols * 4, "<= ", 3);
         
         mode = READ_ROWS;
         break;
      case READ_ROWS :
         bip->rows = (int)v[0];

         if (bip->rows < 1 || bip->rows > BIP_ROWS)
         {
fprintf(stderr, "Error line %d: 1 <= rows <= %d\n", lines, BIP_ROWS);
            goto read_error;
         }
         mode = READ_COEF;
         break;
      case READ_COEF :
         if (rows >= bip->rows)
         {
            fprintf(stderr, "Error line=%d too many rows (expetced %d)\n",
               lines, bip->rows);
            goto read_error;
         }
         if (nums != bip->cols + 1)
         {
            fprintf(stderr, "Error line=%d Expected %d cols, got %d\n",
               lines, bip->cols, nums);
            goto read_error;
         }
         for(cols = 0; cols < bip->cols; cols++)
            bip->a[rows][cols] = v[cols];

         bip->b[rows] = v[cols];
         
         rows++;
         break;
      default :
         abort();
      }
#else         
      /* do processing here:
       * mode tells which kind of line is next.
       */
      switch(mode)
      {
      case READ_COLS :
         bip->cols = atoi(s);
         
         if (bip->cols < 1 || bip->cols > BIP_COLS)
         {
            fprintf(stderr, "Error line %d: 1 <= cols=%d <= %d\n", lines, bip->cols, BIP_COLS);
            goto read_error;
         }
         mode = READ_ROWS;
         break;
      case READ_ROWS :
         bip->rows = atoi(s);

         if (bip->rows < 1 || bip->rows > BIP_ROWS)
         {
            fprintf(stderr, "Error line %d: 1 <= rows <= %d\n", lines, BIP_ROWS);
            goto read_error;
         }
         mode = READ_COEF;
         break;
      case READ_COEF :
         if (rows >= bip->rows)
         {
            fprintf(stderr, "Error line=%d too many rows (expetced %d)\n",
               lines, bip->rows);
            goto read_error;
         }
#ifdef USE_STRTOK  // not  thread safe, rarely a problem in reading
         const char* delim = " \t";
         cols = 0;
         
         for(s = strtok(s, delim); s != NULL; s = strtok(NULL, delim)) /* not thread safe */
         {
            if (cols == bip->cols && strcmp(s, "<="))
               bip->b[rows] = atof(s);
            else if (cols < bip->cols)
            {
               bip->a[rows][cols] = atof(s);
               cols++;
            }
         }
#else
         for(cols = 0; cols < bip->cols; cols++)
         {
            bip->a[rows][cols] = (double)strtol(s, &t, 10);

            if (s == t)
            {
               fprintf(stderr, "Error line=%d Expected %d cols, got %d\n",
                  lines, bip->cols, cols);
               goto read_error;
            }
            s = t;
         }
         while(isspace(*s))
            s++;

         if (strncmp(s, "<=", 2))
         {
            fprintf(stderr, "Error line=%d Expected <= , got \"%s\"\n",
               lines, s);
            goto read_error;
         }
         s += 2;
         bip->b[rows] = (double)strtol(s, &t, 10);

         if (s == t)
         {
            fprintf(stderr, "Error line=%d Expected rhs\n", lines);
            goto read_error;
         }
#endif // !USE_STRTOK
         rows++;
         break;
      default :
         abort();
      }
#endif // !USE_SCANF
   }
   fclose(fp);

   if (rows != bip->rows)
   {
      fprintf(stderr, "Error line=%d Expetced %d rows, got %d\n",
         lines, bip->rows, rows);
      goto read_error;
   }

   SID_set(bip, BIP_SID);

   assert(bip_is_valid(bip));

   printf("Read %d rows, %d cols\n", bip->rows, bip->cols);
   
   return bip;

 read_error:
      deallocate(bip);
      return NULL;   
}

int main	(	int	argc,
		const char **	argv
	)

Definition at line 425 of file ex4_enum.c.

{
   if (argc < 2)
   {
      fprintf(stderr, "usage: %s filename", argv[0]);
      return EXIT_FAILURE;
   }
   BIP* bip = bip_read(argv[1]);

   if (NULL == bip)
      return EXIT_FAILURE;

   bip_print(stdout, bip);
   
   printf("%d solutions\n", bip_enumerate(bip, true));

   bip_free(bip);

   mem_maximum(stdout);
   
   return EXIT_SUCCESS;
}

void print_solu	(	FILE *	fp,
		int	vars,
		const double *	x
	)

Parameters

fp	file pointer to output to
vars	number of variables
x	ptr to solution vector

Definition at line 338 of file ex4_enum.c.

{
   assert(NULL != fp);
   assert(vars >= 0);
   assert(vars <  BIP_COLS);
   assert(NULL != x);

   for(int r = 0; r < vars; r++)
      fprintf(fp, "%2g ", x[r]);
   fputc('\n', fp);
}