| #include "espresso.h" | |
| static void dump_irredundant(); | |
| static pcover do_minimize(); | |
| /* | |
| * minimize_exact -- main entry point for exact minimization | |
| * | |
| * Global flags which affect this routine are: | |
| * | |
| * debug | |
| * skip_make_sparse | |
| */ | |
| pcover | |
| minimize_exact(F, D, R, exact_cover) | |
| pcover F, D, R; | |
| int exact_cover; | |
| { | |
| return do_minimize(F, D, R, exact_cover, /*weighted*/ 0); | |
| } | |
| pcover | |
| minimize_exact_literals(F, D, R, exact_cover) | |
| pcover F, D, R; | |
| int exact_cover; | |
| { | |
| return do_minimize(F, D, R, exact_cover, /*weighted*/ 1); | |
| } | |
| static pcover | |
| do_minimize(F, D, R, exact_cover, weighted) | |
| pcover F, D, R; | |
| int exact_cover; | |
| int weighted; | |
| { | |
| pcover newF, E, Rt, Rp; | |
| pset p, last; | |
| int heur, level, *weights; | |
| sm_matrix *table; | |
| sm_row *cover; | |
| sm_element *pe; | |
| int debug_save = debug; | |
| if (debug & EXACT) { | |
| debug |= (IRRED | MINCOV); | |
| } | |
| #if defined(sun) || defined(bsd4_2) /* hack ... */ | |
| if (debug & MINCOV) { | |
| setlinebuf(stdout); | |
| } | |
| #endif | |
| level = (debug & MINCOV) ? 4 : 0; | |
| heur = ! exact_cover; | |
| /* Generate all prime implicants */ | |
| EXEC(F = primes_consensus(cube2list(F, D)), "PRIMES ", F); | |
| /* Setup the prime implicant table */ | |
| EXEC(irred_split_cover(F, D, &E, &Rt, &Rp), "ESSENTIALS ", E); | |
| EXEC(table = irred_derive_table(D, E, Rp), "PI-TABLE ", Rp); | |
| /* Solve either a weighted or nonweighted covering problem */ | |
| if (weighted) { | |
| /* correct only for all 2-valued variables */ | |
| weights = ALLOC(int, F->count); | |
| foreach_set(Rp, last, p) { | |
| weights[SIZE(p)] = cube.size - set_ord(p); | |
| } | |
| } else { | |
| weights = NIL(int); | |
| } | |
| EXEC(cover=sm_minimum_cover(table,weights,heur,level), "MINCOV ", F); | |
| if (weights != 0) { | |
| FREE(weights); | |
| } | |
| if (debug & EXACT) { | |
| dump_irredundant(E, Rt, Rp, table); | |
| } | |
| /* Form the result cover */ | |
| newF = new_cover(100); | |
| foreach_set(E, last, p) { | |
| newF = sf_addset(newF, p); | |
| } | |
| sm_foreach_row_element(cover, pe) { | |
| newF = sf_addset(newF, GETSET(F, pe->col_num)); | |
| } | |
| free_cover(E); | |
| free_cover(Rt); | |
| free_cover(Rp); | |
| sm_free(table); | |
| sm_row_free(cover); | |
| free_cover(F); | |
| /* Attempt to make the results more sparse */ | |
| debug &= ~ (IRRED | SHARP | MINCOV); | |
| if (! skip_make_sparse && R != 0) { | |
| newF = make_sparse(newF, D, R); | |
| } | |
| debug = debug_save; | |
| return newF; | |
| } | |
| static void | |
| dump_irredundant(E, Rt, Rp, table) | |
| pcover E, Rt, Rp; | |
| sm_matrix *table; | |
| { | |
| FILE *fp_pi_table, *fp_primes; | |
| pPLA PLA; | |
| pset last, p; | |
| char *file; | |
| if (filename == 0 || strcmp(filename, "(stdin)") == 0) { | |
| fp_pi_table = fp_primes = stdout; | |
| } else { | |
| file = ALLOC(char, strlen(filename)+20); | |
| (void) sprintf(file, "%s.primes", filename); | |
| if ((fp_primes = fopen(file, "w")) == NULL) { | |
| fprintf(stderr, "espresso: Unable to open %s\n", file); | |
| fp_primes = stdout; | |
| } | |
| (void) sprintf(file, "%s.pi", filename); | |
| if ((fp_pi_table = fopen(file, "w")) == NULL) { | |
| fprintf(stderr, "espresso: Unable to open %s\n", file); | |
| fp_pi_table = stdout; | |
| } | |
| FREE(file); | |
| } | |
| PLA = new_PLA(); | |
| PLA_labels(PLA); | |
| fpr_header(fp_primes, PLA, F_type); | |
| free_PLA(PLA); | |
| (void) fprintf(fp_primes, "# Essential primes are\n"); | |
| foreach_set(E, last, p) { | |
| (void) fprintf(fp_primes, "%s\n", pc1(p)); | |
| } | |
| fprintf(fp_primes, "# Totally redundant primes are\n"); | |
| foreach_set(Rt, last, p) { | |
| (void) fprintf(fp_primes, "%s\n", pc1(p)); | |
| } | |
| fprintf(fp_primes, "# Partially redundant primes are\n"); | |
| foreach_set(Rp, last, p) { | |
| (void) fprintf(fp_primes, "%s\n", pc1(p)); | |
| } | |
| if (fp_primes != stdout) { | |
| (void) fclose(fp_primes); | |
| } | |
| sm_write(fp_pi_table, table); | |
| if (fp_pi_table != stdout) { | |
| (void) fclose(fp_pi_table); | |
| } | |
| } |