
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General description:
%
% This function find a maximum clique using the maximum degree algorithm
% with one step look-ahead.
%
% input:
%       Gall(n,n) - The global graph. If G(i,j)=1, then (i,j) is an edge.
%                   Keeping unchanged in all recursive calls.
%       V - The vertices of the subgraph being processed in the current call
%       C - The clique under construction
%       best - The largest clique found so far
%       ub - The upper bound of size of maximum clique (Obtained from
%            Dsatur coloring algorithm)
% output: 
%       output - vertices of a maximm clique
%
% Written by: Wei Wang
% Machine Learning for Signal Processing Lab
% University of Maryland, Baltimore County
% 8/21/2007
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [Clique] = MaxClique_maxDegree(G)
n=size(G,1);
Gall=G;
V=[1:n];
len=max(sum(G));

Clique=[];

while 1
    if length(V)==0
        break;
    end
    
    degG=sum(G);
    vlist=find(degG==max(degG));
    
    nn=length(vlist);
    if nn==1
        Clique=[Clique V(vlist)];
        Nbs=find(G(vlist,:)==1);
        if length(Nbs)==0
            break;
        end
        V=V(Nbs);
        G=Gall(V,V);
        %V(vlist)=[];
        continue;
    end
    
    maxdeg=0;
    vmaxdeg=vlist(1);
    for i=1:nn
        nNbs=length(find(G(i,:)==1));
        if nNbs>maxdeg
            maxdeg=nNbs;
            vmaxdeg=vlist(i);
        end
    end
       
    Clique=[Clique V(vmaxdeg)];
    Nbs=find(G(vmaxdeg,:)==1);
    if length(Nbs)==0
        break;
    end
    
    V=V(Nbs);
    G=Gall(V,V);
end

