vertex_cover_bruteforce.c

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#include <math.h>

bool checkVertexCover(int ** G, int *S, int n){
    int i, j;
    int **Gdash = (int**)malloc(sizeof(int*)*n);
    for(i = 0; i < n; i++){
        Gdash[i] = (int*)malloc(sizeof(int)*n);

        for(j = 0; j < n; j++){
            Gdash[i][j] = G[i][j];
        }
    }

    for(i = 0; i < n; i++){
        if (S[i] == 1){
            for (j = 0; j < n; j++){
                Gdash[i][j] = 0;
                Gdash[j][i] = 0;
            }
        }
    }

    bool cover = true;

    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if (Gdash[i][j] == 1){
                cover = false;
                break;
            }
        }
        if (cover == false){
            break;
        }
    }

    return cover;
}


void vertexCoverBruteforce(int **G, int set_size)
{
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;
    /*
    int* set = (int*)malloc(sizeof(int)*set_size);

    for(j = 0; j < set_size; j++){
        set[j] = j;
    }
    */
    int curr_min = INT_MAX;
    //int* curr_best = (int*)malloc(sizeof(int)*set_size);
    int curr_best;
    int* check = (int*)malloc(sizeof(int)*set_size);
    int temp;

    bool isVertex;

    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
        temp = 0;
        for(j = 0; j < set_size; j++){
            /* Check if jth bit in the counter is set
            If set then print jth element from set */

            if(counter & (1<<j)){
                check[j] = 1;
                temp += 1;
            }
            else{
                check[j] = 0;
            }
        }

        if (temp < curr_min){
            isVertex = checkVertexCover(G, check, set_size);
            if (isVertex){
                curr_best = counter;
                curr_min = temp;
            }
        }
    }

    for(j = 0; j < set_size; j++){
        /* Check if jth bit in the counter is set
        If set then print jth element from set */

        if(curr_best & (1<<j)){
            printf("1 ");
        }
        else{
            printf("0 ");
        }
    }

}

void solve(){
    int n; // number of vertex
    scanf("%d", &n);

    int **G = (int**)malloc(sizeof(int*)*n);
    int i, j;
    for(i = 0; i < n; i++){
        G[i] = (int*)malloc(sizeof(int)*n);
    }

    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            scanf("%d", &G[i][j]);
        }
    }

    vertexCoverBruteforce(G, n);

}
int main(){
    solve();
    return 0;
}