// The purpose if this program is to show students how to work with the
// compressed adjacency format for a graph.
// The find_clique and find_dom_set routines are not complete.
#define MAIN 1 
#include "bit.h"
#define DEBUG 1
int find_dom_set(int level, int k, int n, int m, int G[NMAX][MMAX], int dominated[MMAX], int dom_set[MMAX]);
int find_clique(int level, int k, int n, int m, int G[NMAX][MMAX], int candidates[MMAX], int clique[MMAX]);
main(int argc, char *argv[])
{
     int n,m;
     int G[NMAX][MMAX];
     int vertex_set[MMAX];
     int answer[MMAX];

     while (read_graph(&n, &m, G))
     {
         printf("The input graph:\n");
         print_graph(n, G);

         find_clique(0, 5, n, m, G, vertex_set, answer);

         find_dom_set(0, 5, n, m, G, vertex_set, answer);
     }
}
int find_dom_set(int level, int k, int n, int m, int G[NMAX][MMAX], int dominated[MMAX], int dom_set[MMAX])
{
    int new_dominated[MMAX];
    int i, j, u;


    if (level == 0)
    {
        // Set diagonal entries of adjacency matrix to 1 to simplify logic.

        for (i=0; i < n; i++)
            ADD_ELEMENT(G[i], i);

        // Initialize dominated and dom_set to have no vertices.

        for (j=0; j < m; j++)
        {
            dominated[j]=0;
            dom_set[j]=0;
        }
    }
    if (level == k)
    {
        if (set_size(n, dom_set) == n)
        {
            printf("Dominating set: ");
            print_set(n, dom_set);
            return(1);
        }
        else return(0);
    }
#if DEBUG
    printf("Level %3d: The dominated vertices are: ", level);
    print_set(n, dominated);
#endif

    if (level >= 1) return(0); // students should write their own code.

//  This would put vertex 0 into the dominating set:

    u=0;
    ADD_ELEMENT(dom_set, u);
    for (j=0; j < m; j++)
    {
        new_dominated[j]= dominated[j] | G[u][j];
    }
    if (find_dom_set(level+1, k-1, n, m, G, new_dominated, dom_set)) return(1);

//  Take u out again.

    DEL_ELEMENT(dom_set, u);

    return(0);
}
// level is used in all print messages for debugging.
int find_clique(int level, int k, int n, int m, int G[NMAX][MMAX], int candidates[MMAX], int clique[MMAX])
{
    int new_candidates[MMAX];
    int i, j, u;

    if (level == 0)
    {
        // Initialize candidates and clique to have no vertices.

        for (j=0; j < m; j++)
        {
            candidates[j]=0;
            clique[j]=0;
        }

        // Every vertex is a candidate.

        for (i=0; i < n; i++)
            ADD_ELEMENT(candidates, i);
    }
    // When k is 0 we have found a
    // clique of the desired order.
    if (k==0)
    {
        printf("Clique: ");
        print_set(n, clique);
        return(1);
    }

#if DEBUG
    printf("Level %3d: The candidates are: ", level);
    print_set(n, candidates);
#endif

    //  No candidates remaining.

    if (set_size(n, candidates) == 0) return(0);


    if (level >= 1) return(0); // students should write their own code.

//  This would put vertex 0 into the clique:

    u=0;
    ADD_ELEMENT(clique, u);
    for (j=0; j < m; j++)
    {
        new_candidates[j]= candidates[j] & G[u][j];
    }
    if (find_clique(level+1, k-1, n, m, G, new_candidates, clique)) return(1);

//  Take u out again.

    DEL_ELEMENT(clique, u);

    return(0);
}