function  clusters=JCSD_coloring_restore(G, Csub, idxV, globalIdx, JCSDAgentMaxID)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General description:
%
% This function restores coloring for original graph from a colored subgraph.
% Those uncolored vertices were removed from the original graph for coloring
% since their degrees are less than the lower bound of chromatic number. 
% Hence, they can be put back after the rest part of the graph is colored.
%
% Note: 
% The uncolored vertices are colored such that the number of vertices in
% each color is as evenly distributed as possible.
%
% input:
%       G(n,n) - The whole graph. If G(i,j)=1, then (i,j) is an edge in G
%       Csub - The colors of the subgraph
%       idxV - The global indices of vertices in the subgraph
%       JCSDAgentMaxID - the largest index of agent in JCSD spectrum library.
%                        Above this number are spectra of surface or
%                        intefernent materials, which should not be
%                        included in clusters.
% output: 
%       C(n,1) - Color array. C(i) is the color of i-th vertex in the whole
%       graph
%
% Written by: Wei Wang
% Machine Learning for Signal Processing Lab
% University of Maryland, Baltimore County
% 8/21/2007
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

n=size(G,1);
C=zeros(1,n);
C(idxV)=Csub; % Mapping the colored subgraph into the whole graph

Vid=[1:n];
Vid(idxV)=[]; % indices of uncolored vertices

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 1. Find feasible colors for uncolored vertices
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 1.1 find colors that have been used by colored neighbours for uncolored
%     vertices
nCol=max(Csub);   % number of colors
m=length(Vid);    % number of uncolored vertices
ColUsed=zeros(m,nCol);  % Colors used by colored neighbours
countUsed=zeros(m,1);   % Number of colors used by colored neighbours
for i=1:m
    v=Vid(i);    
    Nv=find(G(v,:)>0);
    coloredNv=intersect(Nv,idxV);
    
    if numel(coloredNv)==0
        continue;
    end
    
    for j=1:numel(coloredNv)
       if ismember(C(coloredNv(j)),ColUsed(i,:))==0
           countUsed(i)=countUsed(i)+1;
           ColUsed(i,countUsed(i))=C(coloredNv(j));
       end        
    end    
end

% 1.2 find feasible colors for uncolored vertices
ColFeasible=zeros(m,nCol);
for i=1:m
    t=[1:nCol];
    t(ColUsed(i,1:countUsed(i)))=[];
    ColFeasible(i,:)=[t zeros(1,nCol-numel(t))];        
end
countFeasible=nCol-countUsed;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2. Color those uncolored vertices such that the number of vertices in
%    each color is as evenly distributed as possible.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2.1 Put vertices into clusters according to Csub
clusters=zeros(nCol,n);
for i=1:nCol
   lc=find(Csub==i);       
   icount(i)=length(lc);   % number of vertices in each cluster   
   clusters(i,1:icount(i))=idxV(lc);
   iGlobal=globalIdx(clusters(i,1:icount(i)));
   iJCSDcount(i)=length(find(iGlobal<=JCSDAgentMaxID));
end
ll=ceil(n/nCol);
nn=max(ll, max(icount));
clusters=clusters(:,1:nn);

% 2.2 Put uncolored vertice into the cluster with the least number of
% vertices. The uncolored vertices is preordered by the number of its 
% available colors, i.e., add the most free vertices later.
invPosF=zeros(1,n);
invPosF(Vid)=[1:m];
[nF,idF]=sort(countFeasible,'ascend');
for i=1:m
    v=Vid(idF(i));
    
    tcol=ColFeasible(idF(i),1:countFeasible(idF(i)));            
    tlist=iJCSDcount(tcol);
    pos=find(tlist==min(tlist));
    nc=tcol(pos(1)); % the color covering the least vertices
    
    % add 'v' into 'nc'-th cluster, i.e., color vertex 'v' with color 'nc'. 
    icount(nc)=icount(nc)+1;
    clusters(nc, icount(nc))=v;
    if  globalIdx(v) <= JCSDAgentMaxID
        iJCSDcount(nc)=iJCSDcount(nc)+1;
    end
    
    % update ColFeasible for uncolored vertices
    Vuncol=Vid(idF(i+1:end));    
    Nv=find(G(v,:)>0);
    uncolNv=intersect(Nv,Vuncol);
    
    if numel(uncolNv)==0
        continue;
    end
    for j=1:numel(uncolNv)
       vv=uncolNv(j);
       % if nc is a neighbour's feasible color, then remove nc from it
       if ismember(nc, ColFeasible(invPosF(vv),:))
           tdf=setdiff(ColFeasible(invPosF(vv),:),nc);
           tdf=tdf(find(tdf>0)); % remove 0 from tdf since setdiff return 
                                 % array in increasing order
           ColFeasible(invPosF(vv),:)=[tdf zeros(1,nCol-numel(tdf))];    
           countFeasible(invPosF(vv))=countFeasible(invPosF(vv))-1;
       end
    end    
            
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 3. check and output clusters
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% final check if graph G is successfully colored
for i=1:nCol
    for j=1:icount(i)
        C(clusters(i,j))=i;
    end
end
if check_coloring_results(G,C)==0
    error('Coloring failed !!!!!!!!!');
end

% output clusters
clusters2=zeros(nCol,max(iJCSDcount));
for i=1:nCol
    tc=globalIdx(clusters(i,1:icount(i)));    
    clusters2(i,1:iJCSDcount(i))=tc(find(tc<=JCSDAgentMaxID));
end
clusters=clusters2;


