/******************************************
 *
 *   Cedric Pradalier   2001
 *   mail : http://cedric.pradalier.free.fr/mail.html  
 *
 *****************************************/
#include "matchGraph.h"
#include <stdlib.h>
#include <stdio.h>
#include <algo.h>
#include <function.h>

// #define DEBUG
//#define TRACE

MatchGraph::MatchGraph(char * filename)
{
    FILE * fid;
    unsigned int nvertices,nadj;
    unsigned int t;
    unsigned int i,j;
    fid = fopen(filename,"r");
    if (fid == NULL) return;

    fscanf(fid," %d ",&nvertices);
    internalG = Graph(nvertices);
    for (i=0;i<nvertices;i++)
    {
        fscanf(fid," %d ",&nadj);
        internalG[i].init();
        internalG[i].id = i;
        for (j=0;j<nadj;j++)
        {
            fscanf(fid," %d ",&t);
            internalG[i].adj.insert(t);
        }
        
    }
    fclose(fid);
    gt = NULL;
}

MatchGraph::MatchGraph(unsigned int nbNodes) :
    internalG(nbNodes)
{
    for (unsigned int i=0;i<nbNodes;i++)
        internalG[i].id = i;
    gt = NULL;
}

MatchGraph::~MatchGraph()
{
    // if gt == NULL, does nothing
    delete gt;
}
    

void MatchGraph::addEdge(unsigned int i,unsigned int j)
{
    delete gt;
    gt = NULL;
    internalG[i].adj.insert(j);
    internalG[j].adj.insert(i);
}
    


void MatchGraph::convert()
{
    unsigned int i;
    // if gt == NULL, does nothing
    delete gt;
    gt = new GraphTable(internalG.size(),vector<bool>(internalG.size(),false));
    for (i=0;i<internalG.size();i++)
        for (CliqueIt j=internalG[i].adj.begin(); 
                j!=internalG[i].adj.end();j++)
            (*gt)[internalG[i].id][*j] = true;
}

void MatchGraph::GtPrint() const
{
    unsigned int i,j;
    if (gt == NULL) return;
    for (i=0;i<gt->size();i++)
    {
        for (j=0;j<(*gt)[i].size();j++)
            if ((*gt)[i][j])
                printf(" X ");
            else
                printf(" . ");
        printf("\n");
    }
}





void MatchGraph::Print(bool pretty) const
{
    unsigned int i;
    if (pretty)
    {
        printf("#Vertices : %d\n",internalG.size());
        for (i=0;i<internalG.size();i++)
        {
            printf("%d : %d connection : ",internalG[i].id,
                    internalG[i].adj.size());
            for (CliqueIt j=internalG[i].adj.begin();
                    j!=internalG[i].adj.end();j++)
                printf(" %d ",*j);
            printf("\n");
        }
    } 
    else
    {
        printf("%d\n",internalG.size());
        for (i=0;i<internalG.size();i++)
        {
            printf("%d",internalG[i].adj.size());
            for (CliqueIt j=internalG[i].adj.begin();
                    j!=internalG[i].adj.end();j++)
                printf("\t%d",*j);
            printf("\n");
        }
    }
}


// precondition : gt != NULL
void MatchGraph::FindMaximalClique(Clique & clique,const vector<bool> & active)
{
    unsigned int i,first;
    bool present;
    CliqueIt it;
    Graph g = internalG;
    //Print(true);
    clique.erase(clique.begin(),clique.end());
    sort<vector<Node>::iterator,ltdeg>(g.begin(),g.end(),ltdeg());
    first = 0;
    //printf("Graph sorted\n");
    while ((first < g.size()) && !active[g[first].id]) first += 1;
    if (first >= g.size())
        return;
    //printf("Inertion\n");
    clique.insert(g[first].id);
    //printf("\tOK\n");
    for (i=first+1;i<g.size();i++)
    {
        if (!active[g[i].id]) continue;
        present = true;
        for (it=clique.begin();it!=clique.end();it++)
            if (!(*gt)[g[i].id][*it])
            {
                present = false;
                break;
            }
        if (present)
            clique.insert(g[i].id);
    }
}


// precondition : gt != NULL
void MatchGraph::FindMaximalClique(Clique & clique)
{
    unsigned int i;
    bool present;
    CliqueIt it;
    Graph g = internalG;
    clique.erase(clique.begin(),clique.end());
    sort<vector<Node>::iterator,ltdeg>(g.begin(),g.end(),ltdeg());
    clique.insert(g[0].id);
    for (i=1;i<g.size();i++)
    {
        present = true;
        for (it=clique.begin();it!=clique.end();it++)
            if (!(*gt)[g[i].id][*it])
            {
                present = false;
                break;
            }
        if (present)
            clique.insert(g[i].id);
    }
}

MatchGraph::Clique MatchGraph::maximalClique()
{
    Clique klik;
    if (gt == NULL) convert();
    FindMaximalClique(klik);
    return klik;
}

unsigned int MatchGraph::highestDegree() const
{
    unsigned int i,max;
    max = 0;
    for (i=0;i<internalG.size();i++)
        if (internalG[i].adj.size()>max) max = internalG[i].adj.size();
    return max;
}

// precondition, active a ete initialise a la taille de g
void MatchGraph::RemoveLowerDegree(Graph & g,unsigned int maxRemoved,
        vector<bool> & active)
{
    unsigned int i;
    for (i=0;i<g.size();i++)
        active[i] = g[i].adj.size() > maxRemoved;
}



// Precondition : gt != NULL
bool MatchGraph::isAClique(const vui & vertices,const vui & selected) const
{
    unsigned int i,j;
    for (i=0;i<selected.size();i++)
        for (j=0;j<i;j++)
            if (!(*gt)[vertices[selected[i]]][vertices[selected[j]]])
                return false;
    return true;
        
}



void MatchGraph::initActiveSet(const vector<bool> & active,vui & v)
{
    unsigned int i;
    for (i=0;i<active.size();i++)
        if (active[i])
            v.push_back(i);
}
        


// precondition : klik has been initialized to the right size
void MatchGraph::initKlik(vui & klik,unsigned int nbElem)
{
    unsigned int k;
    for (k=0;k<klik.size();k++)
        klik[k] = nbElem - klik.size() + k;
}
    
bool MatchGraph::decrement(vui & klik)
{
    unsigned int i,max;
    int j;
    i = 0;
    
    while ((i<klik.size()) && (klik[i] == i)) i+= 1;
    if (i == klik.size()) return false;
    klik[i] -= 1;
    max = klik[i];
    for (j=i-1;j>=0;j--)
        klik[j] = --max;
    return true;
}


MatchGraph::Clique MatchGraph::maximumClique()
{
    unsigned int i,k;
    bool theEnd,klikFound;
    Clique clique;
    Graph g = internalG;
    vector<bool> active(g.size(),true);
    vui activeNodes;
    vui klik;
    vui maxClique;
    if (gt == NULL) convert();

    // RemoveLowerDegree(g,1,active);
    FindMaximalClique(clique,active);
    RemoveLowerDegree(g,clique.size()-1,active);
    for (k=clique.size()+1;k<=highestDegree()+1;k++)
    {
        
        initActiveSet(active,activeNodes);
        theEnd = false;
        klikFound = false;
        // not enough remaining nodes
        if (activeNodes.size()<k) break; 
        klik = vui(k,0);
        initKlik(klik,activeNodes.size());
        while (!theEnd)
        {
            klikFound = isAClique(activeNodes,klik);
            if (klikFound) break;
            theEnd = !decrement(klik);
        }
        if (klikFound)
        {
            clique.erase(clique.begin(),clique.end());
            for (i=0;i<klik.size();i++)
                clique.insert(activeNodes[klik[i]]);
            // next search will be for a k+1 clique
            RemoveLowerDegree(g,k,active);
        }
        else break;
    }
    return clique;
}



void MatchGraph::test_function(char * filename)
{
    MatchGraph g(filename);
    MatchGraph::Clique clique;

    printf("Printing\n");
    g.Print(true);
    printf("Converting\n");
    g.convert();
    g.GtPrint();
    printf("Highest degree : %d\n",g.highestDegree());
    printf("Maximal clique\n");
    clique = g.maximalClique();
    MatchGraph::Print(clique);
    printf("\nMaximum clique\n");
    clique = g.maximumClique();
    MatchGraph::Print(clique);
    printf("\n");
}


void MatchGraph::Print(Clique & klik)
{
    printf("{");
    for (CliqueIt it=klik.begin();it!=klik.end();it++)
        printf(" %d ",*it);
    printf("}");
}