mincov.c File Reference

#include "mincov_int.h"

Include dependency graph for mincov.c:

Go to the source code of this file.

Macros
#define	USE_GIMPEL
#define	USE_INDEP_SET
#define	fail(why)

Functions
sm_row *	sm_minimum_cover (sm_matrix *A, int *weight, int heuristic, int debug_level)
solution_t *	sm_mincov (sm_matrix *A, solution_t *select, int *weight, int lb, int bound, int depth, stats_t *stats)

Macro Definition Documentation

fail

#define fail

(

why

)

Value:

    {\
    (void) fprintf(stderr, "Fatal error: file %s, line %d\n%s\n",\
    __FILE__, __LINE__, why);\
    (void) fflush(stdout);\
    abort();\
}

Definition at line 26 of file mincov.c.

#define fail(why) {\
    (void) fprintf(stderr, "Fatal error: file %s, line %d\n%s\n",\
    __FILE__, __LINE__, why);\
    (void) fflush(stdout);\
    abort();\
}

USE_GIMPEL

#define USE_GIMPEL

Definition at line 19 of file mincov.c.

USE_INDEP_SET

#define USE_INDEP_SET

Definition at line 20 of file mincov.c.

Function Documentation

sm_mincov()

solution_t * sm_mincov	(	sm_matrix *	A,
		solution_t *	select,
		int *	weight,
		int	lb,
		int	bound,
		int	depth,
		stats_t *	stats )

Definition at line 119 of file mincov.c.

{
    sm_matrix *A1, *A2, *L, *R;
    sm_element *p;
    solution_t *select1, *select2, *best, *best1, *best2, *indep;
    int pick, lb_new, debug;
 
    /* Start out with some debugging information */
    stats->nodes++;
    if (depth > stats->max_depth) stats->max_depth = depth;
    debug = stats->debug && (depth <= stats->max_print_depth);
 
    /* Apply row dominance, column dominance, and select essentials */
    select_essential(A, select, weight, bound);
    if (select->cost >= bound) {
    return NIL(solution_t);
    }
 
    /* See if gimpel's reduction technique applies ... */
#ifdef USE_GIMPEL
    if ( weight == NIL(int)) {    /* hack until we fix it */
    if (gimpel_reduce(A, select, weight, lb, bound, depth, stats, &best)) {
        return best;
    }
    }
#endif
 
#ifdef USE_INDEP_SET
    /* Determine bound from here to final solution using independent-set */
    indep = sm_maximal_independent_set(A, weight);
 
    /* make sure the lower bound is monotonically increasing */
    lb_new = MAX(select->cost + indep->cost, lb);
    pick = select_column(A, weight, indep);
    solution_free(indep);
#else
    lb_new = select->cost + (A->nrows > 0);
    pick = select_column(A, weight, NIL(solution_t));
#endif
 
    if (depth == 0) {
    stats->lower_bound = lb_new + stats->gimpel;
    }
 
    if (debug) {
        (void) printf("ABSMIN[%2d]%s", depth, stats->component ? "*" : " ");
        (void) printf(" %3dx%3d sel=%3d bnd=%3d lb=%3d %12s ",
            A->nrows, A->ncols, select->cost + stats->gimpel, 
        bound + stats->gimpel, lb_new + stats->gimpel, 
        util_print_time(util_cpu_time()-stats->start_time));
    }
 
    /* Check for bounding based on no better solution possible */
    if (lb_new >= bound) {
    if (debug) (void) printf("bounded\n");
    best = NIL(solution_t);
 
 
    /* Check for new best solution */
    } else if (A->nrows == 0) {
    best = solution_dup(select);
    if (debug) (void) printf("BEST\n");
    if (stats->debug && stats->component == 0) {
            (void) printf("new 'best' solution %d at level %d (time is %s)\n", 
        best->cost + stats->gimpel, depth, 
        util_print_time(util_cpu_time() - stats->start_time));
        }
 
 
    /* Check for a partition of the problem */
    } else if (sm_block_partition(A, &L, &R)) {
    /* Make L the smaller problem */
    if (L->ncols > R->ncols) {
        A1 = L;
        L = R;
        R = A1;
    }
    if (debug) (void) printf("comp %d %d\n", L->nrows, R->nrows);
    stats->comp_count++;
 
    /* Solve problem for L */
    select1 = solution_alloc();
    stats->component++;
    best1 = sm_mincov(L, select1, weight, 0, 
                    bound-select->cost, depth+1, stats);
    stats->component--;
    solution_free(select1);
    sm_free(L);
 
    /* Add best solution to the selected set */
    if (best1 == NIL(solution_t)) {
        best = NIL(solution_t);
    } else {
        for(p = best1->row->first_col; p != 0; p = p->next_col) {
        solution_add(select, weight, p->col_num);
        }
        solution_free(best1);
 
        /* recur for the remaining block */
        best = sm_mincov(R, select, weight, lb_new, bound, depth+1, stats);
    }
    sm_free(R);
 
    /* We've tried as hard as possible, but now we must split and recur */
    } else {
    if (debug) (void) printf("pick=%d\n", pick);
 
        /* Assume we choose this column to be in the covering set */
    A1 = sm_dup(A);
    select1 = solution_dup(select);
    solution_accept(select1, A1, weight, pick);
        best1 = sm_mincov(A1, select1, weight, lb_new, bound, depth+1, stats);
    solution_free(select1);
    sm_free(A1);
 
    /* Update the upper bound if we found a better solution */
    if (best1 != NIL(solution_t) && bound > best1->cost) {
        bound = best1->cost;
    }
 
    /* See if this is a heuristic covering (no branching) */
    if (stats->no_branching) {
        return best1;
    }
 
    /* Check for reaching lower bound -- if so, don't actually branch */
    if (best1 != NIL(solution_t) && best1->cost == lb_new) {
        return best1;
    }
 
        /* Now assume we cannot have that column */
    A2 = sm_dup(A);
    select2 = solution_dup(select);
    solution_reject(select2, A2, weight, pick);
        best2 = sm_mincov(A2, select2, weight, lb_new, bound, depth+1, stats);
    solution_free(select2);
    sm_free(A2);
 
    best = solution_choose_best(best1, best2);
    }
 
    return best;
}

Here is the call graph for this function:

sm_minimum_cover()

sm_row * sm_minimum_cover	(	sm_matrix *	A,
		int *	weight,
		int	heuristic,
		int	debug_level )

Definition at line 34 of file mincov.c.

{
    stats_t stats;
    solution_t *best, *select;
    sm_row *prow, *sol;
    sm_col *pcol;
    sm_matrix *dup_A;
    int nelem, bound;
    double sparsity;
 
    /* Avoid sillyness */
    if (A->nrows <= 0) {
    return sm_row_alloc();        /* easy to cover */
    }
 
    /* Initialize debugging structure */
    stats.start_time = util_cpu_time();
    stats.debug = debug_level > 0;
    stats.max_print_depth = debug_level;
    stats.max_depth = -1;
    stats.nodes = 0;
    stats.component = stats.comp_count = 0;
    stats.gimpel = stats.gimpel_count = 0;
    stats.no_branching = heuristic != 0;
    stats.lower_bound = -1;
 
    /* Check the matrix sparsity */
    nelem = 0;
    sm_foreach_row(A, prow) {
    nelem += prow->length;
    }
    sparsity = (double) nelem / (double) (A->nrows * A->ncols);
 
    /* Determine an upper bound on the solution */
    bound = 1;
    sm_foreach_col(A, pcol) {
    bound += WEIGHT(weight, pcol->col_num);
    }
 
    /* Perform the covering */
    select = solution_alloc();
    dup_A = sm_dup(A);
    best = sm_mincov(dup_A, select, weight, 0, bound, 0, &stats);
    sm_free(dup_A);
    solution_free(select);
 
    if (stats.debug) {
    if (stats.no_branching) {
        (void) printf("**** heuristic covering ...\n");
        (void) printf("lower bound = %d\n", stats.lower_bound);
    }
    (void) printf("matrix     = %d by %d with %d elements (%4.3f%%)\n",
        A->nrows, A->ncols, nelem, sparsity * 100.0);
    (void) printf("cover size = %d elements\n", best->row->length);
    (void) printf("cover cost = %d\n", best->cost);
    (void) printf("time       = %s\n", 
            util_print_time(util_cpu_time() - stats.start_time));
    (void) printf("components = %d\n", stats.comp_count);
    (void) printf("gimpel     = %d\n", stats.gimpel_count);
    (void) printf("nodes      = %d\n", stats.nodes);
    (void) printf("max_depth  = %d\n", stats.max_depth);
    }
 
    sol = sm_row_dup(best->row);
    if (! verify_cover(A, sol)) {
    fail("mincov: internal error -- cover verification failed\n");
    }
    solution_free(best);
    return sol;
}

Here is the call graph for this function: