Minimun Set Cover

mincover.c

//
//  main.c
//  mincover
//
//  Created by Yiqiu Huang on 4/3/12.
//

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <limits.h>
#include <time.h>

#define UINT_BIT (sizeof(unsigned int) * CHAR_BIT)

typedef struct{
    int id;
    unsigned int* elements;
    size_t size;
} bitset;

int num_elements, num_subsets;
static size_t mem_size;
static size_t block_size;
static int current_best=INT_MAX;
static int* current_best_chosen;
static int overallcalls=0;

static bitset* bitset_create_empty(size_t mem_size);
static bitset* bitset_create_full(size_t mem_size, int num_elements);
static inline void bitset_set_bit(bitset* bitset, size_t idx);
static inline void bitset_unset_bit(bitset* bitset, size_t idx);



static bitset* bitset_create_empty(size_t mem_size){
    bitset* temp_set = (bitset*) malloc(sizeof(bitset));
    temp_set->elements=malloc(mem_size);
    memset(temp_set->elements, 0, mem_size);
    temp_set->size = 0;
    return temp_set;
}

static bitset* bitset_create_full(size_t mem_size, int num_elements){
    bitset* temp_set = (bitset*) malloc(sizeof(bitset));
    temp_set->elements = malloc(mem_size);
    temp_set->size= num_elements;
    memset(temp_set->elements, ~0, mem_size);
    int h;
    for(h = num_elements; h<mem_size*CHAR_BIT; h++){
        bitset_unset_bit(temp_set, h);
    }
    temp_set->size= num_elements;
    return temp_set;
}

static bitset* bitset_clone(bitset* old_bitset){
    bitset* temp_set = (bitset*) malloc(sizeof(bitset));
    temp_set->elements = malloc(mem_size);
    memcpy(temp_set->elements, old_bitset->elements, mem_size);
    temp_set->size = old_bitset->size;
    temp_set->id = old_bitset->id;
    return temp_set;
}

static void bitset_dealloc(bitset* bitset){
    free(bitset->elements);
    free(bitset);
}

static inline bool bitset_is_set(bitset* bitset, size_t idx){
    return (bitset->elements[idx / UINT_BIT] & (0x80000000 >> (idx % UINT_BIT)));
}

static inline void bitset_set_bit(bitset* bitset, size_t idx) {
    if(!bitset_is_set(bitset, idx)){
        bitset->size++;
    }
    bitset->elements[idx / UINT_BIT] |= (0x80000000 >> (idx % UINT_BIT));
}

static inline void bitset_unset_bit(bitset* bitset, size_t idx) {
    if(bitset_is_set(bitset, idx)){
        bitset->size--;
    }
    bitset->elements[idx / UINT_BIT] &= ~(0x80000000 >> (idx % UINT_BIT));
}

static bool bitset_contains(bitset* bitset1, bitset* bitset2) {
    int i;
    for(i=0; i<num_elements;i++){
        if (bitset_is_set(bitset2, i)&&!(bitset_is_set(bitset1, i))){
            return false;
        }
    }
    return true;
}

static inline bool bitset_is_equal(bitset* bitset1, bitset* bitset2) {
    if(bitset1->size!=bitset2->size) return false;
    return memcmp(bitset1->elements, bitset2->elements, mem_size)==0;
}

static void unionTo(char * bitarray1, char * bitarray2){
    int i;
    for (i = 0 ; i<block_size; i++) {
        bitarray1[i] |= bitarray2[i];
    }
}

static bitset* bitset_array_union(bitset** bitset_arr, int num_subsets){
    bitset* temp_bitset = bitset_clone(bitset_arr[0]);
    int i,j;
    for (i = 1 ; i<num_subsets; i++) {
        for (j = 0 ; j<block_size; j++) {
            temp_bitset->elements[j] |= bitset_arr[i]->elements[j];
        }
    }
    return temp_bitset;
}

static inline int bit_count(unsigned int i){
    int v = i;
    v =  v - ((v >> 1) & 0x55555555);                    
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

static void bitset_resize(bitset* bitset){
    int size = 0;
    int i;
    for (i = 0 ; i<block_size; i++) {
        size += bit_count(bitset->elements[i]);
    }
    bitset->size = size;
}

static void bitset_subtract_from(bitset* bitset1, bitset* bitset2){
    int i;
    int bitset_size = 0;
    for (i = 0 ; i<block_size; i++) {
        bitset1->elements[i] &= ~(bitset2->elements[i]);
        bitset_size+=bit_count(bitset1->elements[i]);
    }
    bitset1->size=bitset_size;
}

static bitset* bitset_subtract(bitset* bitset1, bitset* bitset2){
    bitset* temp_bitset = bitset_clone(bitset1);
    bitset_subtract_from(temp_bitset, bitset2);
    return temp_bitset;
}

static bitset** bitset_array_deep_copy(bitset* old_subsets[], int size){
    bitset** subsets = (bitset**) malloc(sizeof(bitset *)*size);
    int k;
    for (k=0; k<size; k++) {
        subsets[k] = bitset_clone(old_subsets[k]);
    }
    return subsets;
}

static void bitset_array_deep_dealloc(bitset* subsets[], int size){
    int k;
    for (k=0; k<size; k++) {
        bitset_dealloc(subsets[k]);
    }
    free(subsets);
}


static void print_set(bitset* bitset, int num_elements){
    int i, j=0;
    printf("%d(%zu): ", bitset->id,bitset->size);
    for (i = 0 ; i<num_elements; i++) {
        if(bitset->elements[i / UINT_BIT] & (0x80000000 >> (i % UINT_BIT))){
            printf("%d ", i+1);
            j++;
        }
    }
    printf("\n");
}

static void print_sets(bitset** subsets, int num_subsets){
    int i;
    for (i = 0;i<num_subsets; i++) {
        print_set(subsets[i], num_elements);
    }
}

static void print_result(int* chosen, int num_chosen){
    printf("Number of subsets:%d>\n", num_chosen);
    int i;
    for(i=0; i<num_chosen; i++){
        printf("%d ", chosen[i]+1);
    }
    printf("\n");
}

static void process_result(int* chosen, int num_chosen){
    memcpy(current_best_chosen, chosen, num_chosen*sizeof(int));
    current_best =  num_chosen;
}

static int bitset_compare(const void *pStr1, const void *pStr2) {
    int d = (*(bitset **)pStr2)->size - (*(bitset **)pStr1)->size;
    return d;
}



void backtrack(bitset* uniset, bitset* subsets[], int num_subsets, int* chosen, int num_chosen){
    overallcalls++;
    
    qsort(subsets, num_subsets, sizeof(bitset *), bitset_compare);
    
    int k;
    for (k=0; k<num_subsets; k++) {
        if(subsets[k]->size==0){
            num_subsets = k;
            break;
        }
    }
    if (num_subsets<=0) {
        return;
    }
    
    int t,sum=0;
    for(t=0; t<current_best-num_chosen-1&&t<num_subsets; t++){
        sum+=subsets[t]->size;
    }
    if(sum<uniset->size){
        return;
    }
    
    if (num_subsets<=0) {
        return;
    }
    
    bitset* subset_union = bitset_array_union(subsets, num_subsets);
    if(!bitset_is_equal(subset_union, uniset)){
        bitset_dealloc(subset_union);
        return;
    }
    bitset_dealloc(subset_union);
    
    if(num_chosen+1<current_best){
        int new_num_subsets=num_subsets-1;
        bitset* new_uniset = bitset_subtract(uniset, subsets[0]);
        if(new_uniset->size<=0){
            chosen[num_chosen] = subsets[0]->id;
            process_result(chosen, num_chosen+1);
        }else{
            bitset** new_subsets = bitset_array_deep_copy(subsets+1, new_num_subsets);
            int h;
            for(h=0; h<new_num_subsets; h++){
                bitset_subtract_from(new_subsets[h], subsets[0]);
            }
            chosen[num_chosen] = subsets[0]->id;
            backtrack(new_uniset, new_subsets, new_num_subsets, chosen, num_chosen+1);
            bitset_dealloc(new_uniset);
            bitset_array_deep_dealloc(new_subsets, num_subsets-1);
        }
    }
    backtrack(uniset, subsets+1, num_subsets-1, chosen, num_chosen);
}

int main(int argc, const char * argv[]){
    FILE *fp ;
    fp = fopen (argv[1], "r");
    fscanf(fp, "%d",&num_elements);
    fscanf(fp, "%d\n",&num_subsets);
    //    scanf("%d",&num_elements);
    //    scanf("%d\n",&num_subsets);
    block_size = (num_elements / UINT_BIT + 1);
    mem_size = block_size * sizeof(unsigned int);
    bitset* uniset = bitset_create_full(mem_size, num_elements);
    uniset->id=-1;
    bitset* subsets[num_subsets];
    int chosen[num_subsets];
    current_best_chosen = malloc(num_subsets* sizeof(int));
    
    int* essential=calloc(num_elements, sizeof(int));
    int* essential_list=malloc(num_elements*sizeof(int));    
    int j;
    int largest = 0;
    for (j=0; j<num_subsets; j++){
        char line[2048], *p, *e;
        int v;
        fgets(line, 2048, fp);
        //        fgets(line, 2048, stdin);
        bitset* tempset = bitset_create_empty(mem_size);
        for (p = line; ; p = e) {
            v = strtol(p, &e, 10);
            if (p == e)
                break;
            bitset_set_bit(tempset, v-1);
            essential[v-1]++;
            essential_list[v-1]=j;
        }
        tempset->id=j;
        subsets[j]=tempset;
        if (largest<tempset->size) {
            largest=tempset->size;
        }
    }
    
    int l;
    int num_chosen=0;
    for (l=0; l<num_elements; l++) {
        if(essential[l]==1){
            int index = essential_list[l];
            if(subsets[index]->size!=0){
                chosen[num_chosen]=subsets[index]->id;
                num_chosen++;
                bitset_subtract_from(uniset, subsets[index]);
                int h;
                for(h=0; h<num_subsets; h++){
                    if(h!=index){
                        bitset_subtract_from(subsets[h], subsets[essential_list[l]]);
                    }
                }
                subsets[index]->size=0;
            }
            break;
        }
    }
    free(essential);
    free(essential_list);
    time_t start, stop;
    time(&start);
    backtrack(uniset, subsets, num_subsets, chosen, num_chosen);
    time(&stop);
    print_result(current_best_chosen, current_best);
    printf("\nCalls:%d, time:%f\n", overallcalls, difftime(stop, start));
    free(current_best_chosen);
    return 0;
}