
%FindCG(neighbor,cgI,p)
function cgNew = FindCG(neighbor, cgI)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%% FindCG finds the connected subgraphs of certain length(kk+1). 
%%%
%%% INPUT:
%%% neighbor: a graph with p nodes, in a form of p by p contingency matrix 
%%% cgI: a matrix with kk columns, each row is the indeces of the nodes in
%%%      a connected subgraph.
%%%
%%% OUTPUT:
%%% The output is a matrix with kk+1 columns, each row is the indeces of 
%%% the nodes in a connected subgraph.
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

cgNew = [];
%Given cgI, a list of CG with k-1 nodes
[p, pp] = size(neighbor);
[nCG, kk] = size(cgI);
nk = kk + 1;

%% find all the connected subgraphs with kk+1 nodes by adding one neighbor on all the connected subgraphs with kk nodes
for j = 1:nCG
    %want to construct CGs with k nodes by add one node to the CG with k-1 nodes 
    iCG = cgI(j, :);
    % list the neighbors of the connected subgraph iCG
    [cgg, iNeighbor] = find(neighbor(iCG, :));
    iNeighbor = unique(setdiff(iNeighbor, iCG));
    lengthNeighbor = length(iNeighbor);
    if lengthNeighbor > 0
        %%create a matrix, each row is a CG with k nodes
        %%created by adding one node to CG cgg
    iCgNew = [iCG'*ones(1, lengthNeighbor); iNeighbor]';
    %sorted the indices in each CG in ascending order
    iCgNew = sort(iCgNew, 2);
    cgNew = [cgNew; iCgNew];
    end
end

%% if no connected subgraphs found in the last step, return an empty set and a warning. If some were found, delete the repetitions.
if length(cgNew) == 0
    warningMessage = char(strcat('No CG with', {' '}, num2str(nk), ' nodes detected.'));
    warning(warningMessage)
else 
    %%delete the repetitions in the list
    cgNew = sort(cgNew, 1);
    diffCgM = diff(cgNew, 1, 1);
    diffCg = sum(diffCgM, 2);
    idUnique = find(diffCg)+1;
    idUnique = [1, idUnique'];
    cgNew = cgNew(idUnique, :);
%     i = 1;
%     [nCgNew, lCgNew] = size(cgNew);
%     while i < nCgNew
%     %for each current CG, delete the later CGs that are the same. 
%     iCG = cgNew(i, :);
%     lSame = sum((cgNew((i+1):nCgNew, :) == ones(nCgNew-i, 1)*iCG), 2);
%     iSame = find(lSame == lCgNew) + i;
%     iDiff = setdiff(1:nCgNew, iSame);
%     cgNew = cgNew(iDiff, :);
%     [nCgNew, lCgNew] = size(cgNew);
%     i = i+1;
%     end
end    
    
end
    
    
    
    
