/******************************************
 *
 *   Cedric Pradalier   2001
 *   mail : http://cedric.pradalier.free.fr/mail.html  
 *
 *****************************************/
#ifndef MATCH_GRAPH_H
#define MATCH_GRAPH_H

#include <vector.h>
#include <set.h>


class MatchGraph
{
    public :
        typedef set<unsigned int,less<unsigned int> > Clique;
        typedef Clique::iterator CliqueIt;


    private :
    
        typedef set<unsigned int,less<unsigned int> > Adjacence;
        class Node {
            public :
                unsigned int id;
                Adjacence adj;
                Node() {id=0;}
                Node(unsigned int Id) {id = Id;}
                Node(const Node & n){id = n.id;adj = n.adj;}
                void init() {id=0;adj.erase(adj.begin(),adj.end());}
        };
        struct ltdeg {
            bool operator() (const Node & n1,const Node & n2)
            {
                return n1.adj.size() > n2.adj.size();
            }
        };

        typedef vector<Node> Graph;
        typedef vector< vector<bool> > GraphTable;
        typedef vector<unsigned int> vui;

        Graph internalG;
        GraphTable * gt;

        void convert();
        void GtPrint() const;

        void FindMaximalClique(Clique & clique,const vector<bool> & active);
        void FindMaximalClique(Clique & clique);

        bool isAClique(const vui & vertices,const vui & selected) const;

        
        static void RemoveLowerDegree(Graph & g,unsigned int maxRemoved,
                vector<bool> & active);
        static void initActiveSet(const vector<bool> & active,vui & v);
        static void initKlik(vui & klik,unsigned int nbElem);
        static bool decrement(vui & klik);


    public :
        MatchGraph(unsigned int nbNodes);
        MatchGraph(char * filename);

        ~MatchGraph();

        // non oriented graph. edge (j,i) is implicit
        void addEdge(unsigned int i,unsigned int j);

        Clique maximalClique();
        Clique maximumClique();
        
        void Print(bool pretty) const;
        
        unsigned int highestDegree() const;

        static void test_function(char * filename);
        static void Print(Clique & klik);
};

#endif // MATCH_GRAPH_H