function [clusters, list_of_high_corr_spectra]=...
    JCSD_LibraryPartitioning(LibSpectra, threshold, JCSDAgentMaxID)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% General description:
%%
%% This function partitions spectrum library such that the canonical
%% correlations among library is less than the given threshold. 
%%
%% The whole library paritioning consists of 3 steps:
%% 1. Call 'LibraryPartitioning_FindForbiddenPairs.m' to find forbidden
%%    pairs for the library. 
%% 2. Use graph coloring algorithm to partition the spectrum library
%% 3. Form spectrum clusters for future detection           
%%
%% Input:
%%    LibSpectra - JCSD spectrum library 
%%    threshold - The threshold for single correlations and canonical 
%                   correlations.
%%    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:
%%    clusters - partitioned library
%%    list_of_high_corr_spectra - list of pairs with correlation 
%%        greater than threshold. The firt column is indices of components 
%%        that have been removed from the library. The second column is the
%%        indices of components that are kept. 
%%        In detection, when a component whose index is in the second column
%%        appears, a second stage classification is performed to identify
%%        the target between this component and its counterpart.
%%
%% Written by: Wei Wang
%% 8/21/2007
%%
%% Copyright(c) 2007 by
%% Machine Learning for Signal Processing Laboratory
%% University of Maryland, Baltimore County
%%
%% Permission to use, copy, modify, and distribute this software for any
%% purpose without fee is hereby granted, provided that this entire notice
%% is included in all copies of any software which is or includes a copy
%% or modification of this software and in all copies of the supporting
%% documentation for such software.
%% THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
%% WARRANTY.  IN PARTICULAR, NEITHER THE AUTHOR DOES NOT MAKE ANY
%% REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
%% OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%   1. Find forbidden pairs in LibSpectra                     %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
disp('Finding forbidden pairs...');

[conn,list_of_high_corr_spectra, idxV] ...
         =LibraryPartitioning_FindForbiddenPairs(LibSpectra, threshold);
     
ss=sprintf('%s %d %s','Finding forbidden pairs finished. Total', ...
    sum(sum(conn))/2, 'forbidden pairs found.');
disp(ss);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%   2. Partition the library using graph coloring algorithm   %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
disp('Partitioning the library ...');
[C,idxVsubG] = JCSD_graph_coloring(conn);

disp('Partitioning the library finished successfully.');

ss=sprintf('%s %d %s','Library is partitioned into', max(C),'clusters.');
disp(ss);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%    3. Restore the original graph                            %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Complete coloring by putting back discarded vertices
clusters=JCSD_coloring_restore(conn, C, idxVsubG, idxV, JCSDAgentMaxID);  
%disp('Partitioning results:');
%disp(C);

disp('Spectrum library partitions:');
disp(clusters);

display_flag=0;
if display_flag==1
    %%% Display CC intra/inter clusters
    numcluster=size(clusters,1);
    for i=1:numcluster
        iclustercount(i)=length(find(clusters(i,:)>0));   
    end
    libsall=LibSpectra;
    figure;
    hold on;
    for i=1:numcluster
       curiid=clusters(i,1:iclustercount(i));   
       for j=1:iclustercount(i)
          ccc=[1:j-1 j+1:iclustercount(i)];
          ccciid=curiid(ccc);
          curlibs=libsall(:,ccciid); 
          [A1,B1,r1] = CCA_nonnegative(libsall(:,clusters(i,j)),curlibs);
          rrs(i,j)=r1(1);            
       end        
       plot(curiid,rrs(i,1:iclustercount(i)),'or','LineWidth',3);

       idothercluster=[1:i-1 i+1:numcluster]; 
       for k=1:numcluster-1
           rrsout=0;
           curclu= idothercluster(k);
           curiid2=clusters(curclu,1:iclustercount(curclu));       
           curlibs=libsall(:,curiid2); 

           for j=1:iclustercount(i)   
               [A1,B1,r1] = CCA_nonnegative(libsall(:,clusters(i,j)),curlibs);              
               rrsout(j)=r1(1); 
           end
           plot(curiid,rrsout(1:iclustercount(i)),'xb','LineWidth',2);
       end
    end
    title('Canonical correlations between each spetrum with the rest of the library',...
        'FontSize',14);
    xlabel('Spectrum index','FontSize',14);
    ylabel('Canonical correlation','FontSize',14);
    grid on;
    legend('Intra-cluster','Inter-cluster');
    ylim([0.3 1]);
end

