[TECH] A note on enumerating subsets using BFS.

I have several things which I want to make a note on my blog, but unfortunately I'm not getting enough time to write the blog posts. Any way.

Recently I came across several Dynamic Programming formulations which involve subsets in the Subproblem for example take the TSP problem, the Subproblem T(S-{j},j) is often used in the D.P formulation which indicates the optimal path starting from node '1' and covering all the nodes in the subset 'S' and ending in node 'j'. Here 'S' is a subset of V (set of all the nodes/vertices's of the given graph.). The final answer for the TSP problem is found by finding a 'k' such that T(V-{k},k) + d(k,1) is minimum.

If we observe we need a small algorithm framework which moves the solution from all the subsets of size '1' to '|V|'. In simple terms we need to enumerate the subsets in the order of their sizes. I found that a BFS can really help in enumerating the Subsets. The following code should be very handy in providing an enumeration framework and will be greatly useful to solve optimization problems which involve subsets in their D.P formulation.

---

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<math.h>
#include "List.h"
#define VERBOSE_MODE 1

/*Returns the new tail of the list*/
inline List* ListAppend(List **tail,void *_data){
    List *new_node = (List *)malloc(sizeof(new_node)*1);
    assert(new_node);
    if(!(*tail)){
        (*tail) = new_node;
        (*tail)->_data = _data;
        (*tail)->next = NULL;
        return *tail;
    }
    new_node->_data = _data;
    new_node->next = NULL;
    (*tail)->next = new_node;
    return new_node;
}
typedef struct _subset_{
    /*if i^th bit is set then subset has i^th
     *element*/
    unsigned int ebits;
    unsigned int max; /*Maximum element in the subset*/
    unsigned int size; /*Size of subset*/
}SubSet;
/*Enumerate the Subset using BFS, n is 
 *the set size [1,2...n] */
void EnumSubSetsBFS(unsigned int n){
    unsigned int i;
    List *bfs_list = NULL;
    List *tail = NULL; List *free_node;
    SubSet *sub_set,*new_sub_set;
    SubSet *one_sets = (SubSet *)malloc(sizeof(SubSet)*n);
    unsigned int current_level = 0;
    /*Add the 1-subsets*/
    for(i=0;i<n;i++){
        one_sets[i].ebits = 0; one_sets[i].ebits |= (1<<i);
        one_sets[i].max = i; one_sets[i].size = 1;
        if(!tail){
            ListAppend(&bfs_list,(void *)&(one_sets[i]));
            tail = bfs_list;
            continue;
        }
        tail = ListAppend(&tail,(void *)&(one_sets[i]));
    }
    /*Now do the BFS*/
    while(bfs_list){
        sub_set = (SubSet *)bfs_list->_data; 
        free_node = bfs_list;
        bfs_list=bfs_list->next;

#ifdef VERBOSE_MODE 
        if(sub_set->size != current_level){
            current_level = sub_set->size;
            printf("Printing SubSets of Size [%u] \n",current_level);
            printf("===============================\n");
        }
        /*print this set*/
        printf("[ ");
        for(i=0;i<n;i++){
            if(sub_set->ebits & (1<<i)){
                printf("%u ",i);
            }
        }
        printf("]\n");
#endif

        assert(sub_set->max < n);
        for(i=((sub_set->max)+1);i<n;i++){
            new_sub_set = (SubSet *) malloc(sizeof(SubSet)*1);
            new_sub_set->size = (sub_set->size)+1;
            new_sub_set->max = i;
            new_sub_set->ebits = (sub_set->ebits | (1<<i));
            tail = ListAppend(&tail,(void *)new_sub_set);
        }
        if(!(sub_set >= one_sets && sub_set <= &(one_sets[n-1]))){
            free(sub_set); 
        }
        free(free_node);
    }
    free(one_sets);
}
int main(int argc,char **argv){
    EnumSubSetsBFS(5);
    return 0;
}

Thanks to this http://puzzleware.net/codehtmler/default.aspx for converting my code.

Cheers! Vamsi.