function [ ccsA , ccsN ] = splitintocc( A , D )
%SPLITINTOCC  returns the adj. matrices of the connected components
%
%   CCSA = SPLITINTOCC(A) returns a cell array of adjacency matrices
%       with the same dimension of A, but nodes (and edges) not being
%       part of a component are set to zero.
%
%   [ CCSA , CCSN ] = SPLITINTOCC(A) additionally returns a cell 
%       array of vectors containing the names of the nodes in each
%       connected component.
%
%       Obiviously, length(CCSA) = length(CCSN) = ncc
%
%       If you have the distance matrix of the graph (calculated
%       via adj2dist), you can spare most of the work. Just pass
%       it on as second argument:  SPLITINTOCC( A , D )
%
%  Last change:  10/2/2005 - Florian Knorn

if nargin < 1
	error('Please input adjacency matrix !');
else
	n = size(A,1);
	if n ~= size(A,2)
		error('Please input SQUARE matrix !');
	end
	if nargin < 2
		D = [];
	end
end

if ~isempty(D) % we've got the distance matrix
	
	% check if there are any penalty entries (=> graph disconn.)
	penalties = find(D==length(D));
	if any(penalties)
		notconn = true;
	else
		% set maindiag to something, as any node is reachable from itself
		D = D + 42*eye(n);

		% if no penalities where found, check if there are any zero-entries
		if any(find(D==0))
			notconn = true;

			% now convert D to logical sparse
			warning('off','MATLAB:conversionToLogical');
			D = logical(D);
			warning('on','MATLAB:conversionToLogical');
			D(penalties) = false; Asum2 = sparse(D); clear D;
		else
			notconn = false;
		end
	end

else % no D given, so we must calc Asum2 (has same nnz's as D+eye)

	% some initialisation
	nn = n^2; m = 0; count = []; deltannz = 42; warning off;
	
	A = logical(A); Asum2 = logical(speye(n)); Am = Asum2;
	while (nnz(Asum2) ~= nn) && (deltannz ~= 0) && (m <= n)
		m = m + 1; Am = logical(double(Am)*A);
		Asum1 = Asum2; Asum2 = Asum1 | Am;
		deltannz = nnz(Asum2)-nnz(Asum1); % increase of new shortest paths
	end
	
	if (deltannz == 0) || (m == n)
		notconn = true;
	else
		notconn = false;
	end
	
end
	
% if graph is not connected, count ncc, find nlcc and output warning
if notconn
	ncc = 0; ccsA = {}; ccsN = {}; oneton = 1:n; rmved = [];
	while ~isempty(Asum2)

		ncc = ncc + 1;

		% grab all the nodes that are reachable from first node ...
		thiscc = find(Asum2(1,:)); 

		% note that the indices in "thiscc" are the node names in the 
		% reduced graph! so we need to know what their original names are:
		origind = oneton; origind(rmved) = []; % "simluate" removal
		thiscc_origind = origind(thiscc);

		% now, let's take care of the newly found cc (i.e. store it).
		% "removeme" are the nodes to be "removed" from the original
		% adjacency matrix (that is its rows & cols are to be set 0)
		% For that, again, transformation new->orig. indices needed.
		removeme_origind = oneton; removeme_origind(thiscc_origind) = [];
		
		ccsA{ncc} = A; % asign A and set non-cc-members to 0
		ccsA{ncc}(removeme_origind,:) = false;
		ccsA{ncc}(:,removeme_origind) = false;
		ccsN{ncc} = thiscc_origind; % store their names
		
		% finally get them out of the way (safes work in next step)
		Asum2(thiscc,:) = []; Asum2(:,thiscc) = [];
		rmved = [rmved,thiscc_origind];
	end
	
else % graph connected - piece of cake ;-)

	ccsA = {A};
	ccsN = {1:n};

end